libs/utils/VectorImpl.cpp

   1 /*
   2  * Copyright (C) 2005 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #define LOG_TAG "Vector"
  18
  19 #include <string.h>
  20 #include <stdlib.h>
  21 #include <stdio.h>
  22
  23 #include <utils/Log.h>
  24 #include <utils/Errors.h>
  25 #include <utils/SharedBuffer.h>
  26 #include <utils/VectorImpl.h>
  27
  28 /*****************************************************************************/
  29
  30
  31 namespace android {
  32
  33 // ----------------------------------------------------------------------------
  34
  35 const size_t kMinVectorCapacity = 4;
  36
  37 static inline size_t max(size_t a, size_t b) {
  38     return a>b ? a : b;
  39 }
  40
  41 // ----------------------------------------------------------------------------
  42
  43 VectorImpl::VectorImpl(size_t itemSize, uint32_t flags)
  44     : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize)
  45 {
  46 }
  47
  48 VectorImpl::VectorImpl(const VectorImpl& rhs)
  49     :   mStorage(rhs.mStorage), mCount(rhs.mCount),
  50         mFlags(rhs.mFlags), mItemSize(rhs.mItemSize)
  51 {
  52     if (mStorage) {
  53         SharedBuffer::sharedBuffer(mStorage)->acquire();
  54     }
  55 }
  56
  57 VectorImpl::~VectorImpl()
  58 {
  59     LOG_ASSERT(!mCount,
  60         "[%p] "
  61         "subclasses of VectorImpl must call finish_vector()"
  62         " in their destructor. Leaking %d bytes.",
  63         this, (int)(mCount*mItemSize));
  64     // We can't call _do_destroy() here because the vtable is already gone.
  65 }
  66
  67 VectorImpl& VectorImpl::operator = (const VectorImpl& rhs)
  68 {
  69     LOG_ASSERT(mItemSize == rhs.mItemSize,
  70         "Vector<> have different types (this=%p, rhs=%p)", this, &rhs);
  71     if (this != &rhs) {
  72         release_storage();
  73         if (rhs.mCount) {
  74             mStorage = rhs.mStorage;
  75             mCount = rhs.mCount;
  76             SharedBuffer::sharedBuffer(mStorage)->acquire();
  77         } else {
  78             mStorage = 0;
  79             mCount = 0;
  80         }
  81     }
  82     return *this;
  83 }
  84
  85 void* VectorImpl::editArrayImpl()
  86 {
  87     if (mStorage) {
  88         SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage)->attemptEdit();
  89         if (sb == 0) {
  90             sb = SharedBuffer::alloc(capacity() * mItemSize);
  91             if (sb) {
  92                 _do_copy(sb->data(), mStorage, mCount);
  93                 release_storage();
  94                 mStorage = sb->data();
  95             }
  96         }
  97     }
  98     return mStorage;
  99 }
 100
 101 size_t VectorImpl::capacity() const
 102 {
 103     if (mStorage) {
 104         return SharedBuffer::sharedBuffer(mStorage)->size() / mItemSize;
 105     }
 106     return 0;
 107 }
 108
 109 ssize_t VectorImpl::insertVectorAt(const VectorImpl& vector, size_t index)
 110 {
 111     if (index > size())
 112         return BAD_INDEX;
 113     void* where = _grow(index, vector.size());
 114     if (where) {
 115         _do_copy(where, vector.arrayImpl(), vector.size());
 116     }
 117     return where ? index : (ssize_t)NO_MEMORY;
 118 }
 119
 120 ssize_t VectorImpl::appendVector(const VectorImpl& vector)
 121 {
 122     return insertVectorAt(vector, size());
 123 }
 124
 125 ssize_t VectorImpl::insertAt(size_t index, size_t numItems)
 126 {
 127     return insertAt(0, index, numItems);
 128 }
 129
 130 ssize_t VectorImpl::insertAt(const void* item, size_t index, size_t numItems)
 131 {
 132     if (index > size())
 133         return BAD_INDEX;
 134     void* where = _grow(index, numItems);
 135     if (where) {
 136         if (item) {
 137             _do_splat(where, item, numItems);
 138         } else {
 139             _do_construct(where, numItems);
 140         }
 141     }
 142     return where ? index : (ssize_t)NO_MEMORY;
 143 }
 144
 145 static int sortProxy(const void* lhs, const void* rhs, void* func)
 146 {
 147     return (*(VectorImpl::compar_t)func)(lhs, rhs);
 148 }
 149
 150 status_t VectorImpl::sort(VectorImpl::compar_t cmp)
 151 {
 152     return sort(sortProxy, (void*)cmp);
 153 }
 154
 155 status_t VectorImpl::sort(VectorImpl::compar_r_t cmp, void* state)
 156 {
 157     // the sort must be stable. we're using insertion sort which
 158     // is well suited for small and already sorted arrays
 159     // for big arrays, it could be better to use mergesort
 160     const ssize_t count = size();
 161     if (count > 1) {
 162         void* array = const_cast<void*>(arrayImpl());
 163         void* temp = 0;
 164         ssize_t i = 1;
 165         while (i < count) {
 166             void* item = reinterpret_cast<char*>(array) + mItemSize*(i);
 167             void* curr = reinterpret_cast<char*>(array) + mItemSize*(i-1);
 168             if (cmp(curr, item, state) > 0) {
 169
 170                 if (!temp) {
 171                     // we're going to have to modify the array...
 172                     array = editArrayImpl();
 173                     if (!array) return NO_MEMORY;
 174                     temp = malloc(mItemSize);
 175                     if (!temp) return NO_MEMORY;
 176                     _do_construct(temp, 1);
 177                     item = reinterpret_cast<char*>(array) + mItemSize*(i);
 178                     curr = reinterpret_cast<char*>(array) + mItemSize*(i-1);
 179                 }
 180
 181                 _do_copy(temp, item, 1);
 182
 183                 ssize_t j = i-1;
 184                 void* next = reinterpret_cast<char*>(array) + mItemSize*(i);
 185                 do {
 186                     _do_copy(next, curr, 1);
 187                     next = curr;
 188                     --j;
 189                     curr = reinterpret_cast<char*>(array) + mItemSize*(j);
 190                 } while (j>=0 && (cmp(curr, temp, state) > 0));
 191
 192                 _do_copy(next, temp, 1);
 193             }
 194             i++;
 195         }
 196
 197         if (temp) {
 198             _do_destroy(temp, 1);
 199             free(temp);
 200         }
 201     }
 202     return NO_ERROR;
 203 }
 204
 205 void VectorImpl::pop()
 206 {
 207     if (size())
 208         removeItemsAt(size()-1, 1);
 209 }
 210
 211 void VectorImpl::push()
 212 {
 213     push(0);
 214 }
 215
 216 void VectorImpl::push(const void* item)
 217 {
 218     insertAt(item, size());
 219 }
 220
 221 ssize_t VectorImpl::add()
 222 {
 223     return add(0);
 224 }
 225
 226 ssize_t VectorImpl::add(const void* item)
 227 {
 228     return insertAt(item, size());
 229 }
 230
 231 ssize_t VectorImpl::replaceAt(size_t index)
 232 {
 233     return replaceAt(0, index);
 234 }
 235
 236 ssize_t VectorImpl::replaceAt(const void* prototype, size_t index)
 237 {
 238     LOG_ASSERT(index<size(),
 239         "[%p] replace: index=%d, size=%d", this, (int)index, (int)size());
 240
 241     void* item = editItemLocation(index);
 242     if (item == 0)
 243         return NO_MEMORY;
 244     _do_destroy(item, 1);
 245     if (prototype == 0) {
 246         _do_construct(item, 1);
 247     } else {
 248         _do_copy(item, prototype, 1);
 249     }
 250     return ssize_t(index);
 251 }
 252
 253 ssize_t VectorImpl::removeItemsAt(size_t index, size_t count)
 254 {
 255     LOG_ASSERT((index+count)<=size(),
 256         "[%p] remove: index=%d, count=%d, size=%d",
 257                this, (int)index, (int)count, (int)size());
 258
 259     if ((index+count) > size())
 260         return BAD_VALUE;
 261    _shrink(index, count);
 262    return index;
 263 }
 264
 265 void VectorImpl::finish_vector()
 266 {
 267     release_storage();
 268     mStorage = 0;
 269     mCount = 0;
 270 }
 271
 272 void VectorImpl::clear()
 273 {
 274     _shrink(0, mCount);
 275 }
 276
 277 void* VectorImpl::editItemLocation(size_t index)
 278 {
 279     LOG_ASSERT(index<capacity(),
 280         "[%p] itemLocation: index=%d, capacity=%d, count=%d",
 281         this, (int)index, (int)capacity(), (int)mCount);
 282
 283     void* buffer = editArrayImpl();
 284     if (buffer)
 285         return reinterpret_cast<char*>(buffer) + index*mItemSize;
 286     return 0;
 287 }
 288
 289 const void* VectorImpl::itemLocation(size_t index) const
 290 {
 291     LOG_ASSERT(index<capacity(),
 292         "[%p] editItemLocation: index=%d, capacity=%d, count=%d",
 293         this, (int)index, (int)capacity(), (int)mCount);
 294
 295     const  void* buffer = arrayImpl();
 296     if (buffer)
 297         return reinterpret_cast<const char*>(buffer) + index*mItemSize;
 298     return 0;
 299 }
 300
 301 ssize_t VectorImpl::setCapacity(size_t new_capacity)
 302 {
 303     size_t current_capacity = capacity();
 304     ssize_t amount = new_capacity - size();
 305     if (amount <= 0) {
 306         // we can't reduce the capacity
 307         return current_capacity;
 308     }
 309     SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
 310     if (sb) {
 311         void* array = sb->data();
 312         _do_copy(array, mStorage, size());
 313         release_storage();
 314         mStorage = const_cast<void*>(array);
 315     } else {
 316         return NO_MEMORY;
 317     }
 318     return new_capacity;
 319 }
 320
 321 void VectorImpl::release_storage()
 322 {
 323     if (mStorage) {
 324         const SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage);
 325         if (sb->release(SharedBuffer::eKeepStorage) == 1) {
 326             _do_destroy(mStorage, mCount);
 327             SharedBuffer::dealloc(sb);
 328         }
 329     }
 330 }
 331
 332 void* VectorImpl::_grow(size_t where, size_t amount)
 333 {
 334 //    LOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
 335 //        this, (int)where, (int)amount, (int)mCount, (int)capacity());
 336
 337     if (where > mCount)
 338         where = mCount;
 339
 340     const size_t new_size = mCount + amount;
 341     if (capacity() < new_size) {
 342         const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2);
 343 //        LOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity);
 344         if ((mStorage) &&
 345             (mCount==where) &&
 346             (mFlags & HAS_TRIVIAL_COPY) &&
 347             (mFlags & HAS_TRIVIAL_DTOR))
 348         {
 349             const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
 350             SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
 351             mStorage = sb->data();
 352         } else {
 353             SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
 354             if (sb) {
 355                 void* array = sb->data();
 356                 if (where>0) {
 357                     _do_copy(array, mStorage, where);
 358                 }
 359                 if (mCount>where) {
 360                     const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize;
 361                     void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
 362                     _do_copy(dest, from, mCount-where);
 363                 }
 364                 release_storage();
 365                 mStorage = const_cast<void*>(array);
 366             }
 367         }
 368     } else {
 369         ssize_t s = mCount-where;
 370         if (s>0) {
 371             void* array = editArrayImpl();
 372             void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
 373             const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize;
 374             _do_move_forward(to, from, s);
 375         }
 376     }
 377     mCount += amount;
 378     void* free_space = const_cast<void*>(itemLocation(where));
 379     return free_space;
 380 }
 381
 382 void VectorImpl::_shrink(size_t where, size_t amount)
 383 {
 384     if (!mStorage)
 385         return;
 386
 387 //    LOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
 388 //        this, (int)where, (int)amount, (int)mCount, (int)capacity());
 389
 390     if (where >= mCount)
 391         where = mCount - amount;
 392
 393     const size_t new_size = mCount - amount;
 394     if (new_size*3 < capacity()) {
 395         const size_t new_capacity = max(kMinVectorCapacity, new_size*2);
 396 //        LOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity);
 397         if ((where == mCount-amount) &&
 398             (mFlags & HAS_TRIVIAL_COPY) &&
 399             (mFlags & HAS_TRIVIAL_DTOR))
 400         {
 401             const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
 402             SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
 403             mStorage = sb->data();
 404         } else {
 405             SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
 406             if (sb) {
 407                 void* array = sb->data();
 408                 if (where>0) {
 409                     _do_copy(array, mStorage, where);
 410                 }
 411                 if (mCount > where+amount) {
 412                     const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize;
 413                     void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
 414                     _do_copy(dest, from, mCount-(where+amount));
 415                 }
 416                 release_storage();
 417                 mStorage = const_cast<void*>(array);
 418             }
 419         }
 420     } else {
 421         void* array = editArrayImpl();
 422         void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
 423         _do_destroy(to, amount);
 424         ssize_t s = mCount-(where+amount);
 425         if (s>0) {
 426             const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
 427             _do_move_backward(to, from, s);
 428         }
 429     }
 430
 431     // adjust the number of items...
 432     mCount -= amount;
 433 }
 434
 435 size_t VectorImpl::itemSize() const {
 436     return mItemSize;
 437 }
 438
 439 void VectorImpl::_do_construct(void* storage, size_t num) const
 440 {
 441     if (!(mFlags & HAS_TRIVIAL_CTOR)) {
 442         do_construct(storage, num);
 443     }
 444 }
 445
 446 void VectorImpl::_do_destroy(void* storage, size_t num) const
 447 {
 448     if (!(mFlags & HAS_TRIVIAL_DTOR)) {
 449         do_destroy(storage, num);
 450     }
 451 }
 452
 453 void VectorImpl::_do_copy(void* dest, const void* from, size_t num) const
 454 {
 455     if (!(mFlags & HAS_TRIVIAL_COPY)) {
 456         do_copy(dest, from, num);
 457     } else {
 458         memcpy(dest, from, num*itemSize());
 459     }
 460 }
 461
 462 void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
 463     do_splat(dest, item, num);
 464 }
 465
 466 void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
 467     do_move_forward(dest, from, num);
 468 }
 469
 470 void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
 471     do_move_backward(dest, from, num);
 472 }
 473
 474 void VectorImpl::reservedVectorImpl1() { }
 475 void VectorImpl::reservedVectorImpl2() { }
 476 void VectorImpl::reservedVectorImpl3() { }
 477 void VectorImpl::reservedVectorImpl4() { }
 478 void VectorImpl::reservedVectorImpl5() { }
 479 void VectorImpl::reservedVectorImpl6() { }
 480 void VectorImpl::reservedVectorImpl7() { }
 481 void VectorImpl::reservedVectorImpl8() { }
 482
 483 /*****************************************************************************/
 484
 485 SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
 486     : VectorImpl(itemSize, flags)
 487 {
 488 }
 489
 490 SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
 491 : VectorImpl(rhs)
 492 {
 493 }
 494
 495 SortedVectorImpl::~SortedVectorImpl()
 496 {
 497 }
 498
 499 SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
 500 {
 501     return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
 502 }
 503
 504 ssize_t SortedVectorImpl::indexOf(const void* item) const
 505 {
 506     return _indexOrderOf(item);
 507 }
 508
 509 size_t SortedVectorImpl::orderOf(const void* item) const
 510 {
 511     size_t o;
 512     _indexOrderOf(item, &o);
 513     return o;
 514 }
 515
 516 ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
 517 {
 518     // binary search
 519     ssize_t err = NAME_NOT_FOUND;
 520     ssize_t l = 0;
 521     ssize_t h = size()-1;
 522     ssize_t mid;
 523     const void* a = arrayImpl();
 524     const size_t s = itemSize();
 525     while (l <= h) {
 526         mid = l + (h - l)/2;
 527         const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
 528         const int c = do_compare(curr, item);
 529         if (c == 0) {
 530             err = l = mid;
 531             break;
 532         } else if (c < 0) {
 533             l = mid + 1;
 534         } else {
 535             h = mid - 1;
 536         }
 537     }
 538     if (order) *order = l;
 539     return err;
 540 }
 541
 542 ssize_t SortedVectorImpl::add(const void* item)
 543 {
 544     size_t order;
 545     ssize_t index = _indexOrderOf(item, &order);
 546     if (index < 0) {
 547         index = VectorImpl::insertAt(item, order, 1);
 548     } else {
 549         index = VectorImpl::replaceAt(item, index);
 550     }
 551     return index;
 552 }
 553
 554 ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
 555 {
 556     // naive merge...
 557     if (!vector.isEmpty()) {
 558         const void* buffer = vector.arrayImpl();
 559         const size_t is = itemSize();
 560         size_t s = vector.size();
 561         for (size_t i=0 ; i<s ; i++) {
 562             ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is );
 563             if (err<0) {
 564                 return err;
 565             }
 566         }
 567     }
 568     return NO_ERROR;
 569 }
 570
 571 ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
 572 {
 573     // we've merging a sorted vector... nice!
 574     ssize_t err = NO_ERROR;
 575     if (!vector.isEmpty()) {
 576         // first take care of the case where the vectors are sorted together
 577         if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) {
 578             err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0);
 579         } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) {
 580             err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector));
 581         } else {
 582             // this could be made a little better
 583             err = merge(static_cast<const VectorImpl&>(vector));
 584         }
 585     }
 586     return err;
 587 }
 588
 589 ssize_t SortedVectorImpl::remove(const void* item)
 590 {
 591     ssize_t i = indexOf(item);
 592     if (i>=0) {
 593         VectorImpl::removeItemsAt(i, 1);
 594     }
 595     return i;
 596 }
 597
 598 void SortedVectorImpl::reservedSortedVectorImpl1() { };
 599 void SortedVectorImpl::reservedSortedVectorImpl2() { };
 600 void SortedVectorImpl::reservedSortedVectorImpl3() { };
 601 void SortedVectorImpl::reservedSortedVectorImpl4() { };
 602 void SortedVectorImpl::reservedSortedVectorImpl5() { };
 603 void SortedVectorImpl::reservedSortedVectorImpl6() { };
 604 void SortedVectorImpl::reservedSortedVectorImpl7() { };
 605 void SortedVectorImpl::reservedSortedVectorImpl8() { };
 606
 607
 608 /*****************************************************************************/
 609
 610 }; // namespace android
 611