frameworks/base/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     return insertArrayAt(vector.arrayImpl(), index, vector.size());
 112 }
 113
 114 ssize_t VectorImpl::appendVector(const VectorImpl& vector)
 115 {
 116     return insertVectorAt(vector, size());
 117 }
 118
 119 ssize_t VectorImpl::insertArrayAt(const void* array, size_t index, size_t length)
 120 {
 121     if (index > size())
 122         return BAD_INDEX;
 123     void* where = _grow(index, length);
 124     if (where) {
 125         _do_copy(where, array, length);
 126     }
 127     return where ? index : (ssize_t)NO_MEMORY;
 128 }
 129
 130 ssize_t VectorImpl::appendArray(const void* array, size_t length)
 131 {
 132     return insertArrayAt(array, size(), length);
 133 }
 134
 135 ssize_t VectorImpl::insertAt(size_t index, size_t numItems)
 136 {
 137     return insertAt(0, index, numItems);
 138 }
 139
 140 ssize_t VectorImpl::insertAt(const void* item, size_t index, size_t numItems)
 141 {
 142     if (index > size())
 143         return BAD_INDEX;
 144     void* where = _grow(index, numItems);
 145     if (where) {
 146         if (item) {
 147             _do_splat(where, item, numItems);
 148         } else {
 149             _do_construct(where, numItems);
 150         }
 151     }
 152     return where ? index : (ssize_t)NO_MEMORY;
 153 }
 154
 155 static int sortProxy(const void* lhs, const void* rhs, void* func)
 156 {
 157     return (*(VectorImpl::compar_t)func)(lhs, rhs);
 158 }
 159
 160 status_t VectorImpl::sort(VectorImpl::compar_t cmp)
 161 {
 162     return sort(sortProxy, (void*)cmp);
 163 }
 164
 165 status_t VectorImpl::sort(VectorImpl::compar_r_t cmp, void* state)
 166 {
 167     // the sort must be stable. we're using insertion sort which
 168     // is well suited for small and already sorted arrays
 169     // for big arrays, it could be better to use mergesort
 170     const ssize_t count = size();
 171     if (count > 1) {
 172         void* array = const_cast<void*>(arrayImpl());
 173         void* temp = 0;
 174         ssize_t i = 1;
 175         while (i < count) {
 176             void* item = reinterpret_cast<char*>(array) + mItemSize*(i);
 177             void* curr = reinterpret_cast<char*>(array) + mItemSize*(i-1);
 178             if (cmp(curr, item, state) > 0) {
 179
 180                 if (!temp) {
 181                     // we're going to have to modify the array...
 182                     array = editArrayImpl();
 183                     if (!array) return NO_MEMORY;
 184                     temp = malloc(mItemSize);
 185                     if (!temp) return NO_MEMORY;
 186                     item = reinterpret_cast<char*>(array) + mItemSize*(i);
 187                     curr = reinterpret_cast<char*>(array) + mItemSize*(i-1);
 188                 } else {
 189                     _do_destroy(temp, 1);
 190                 }
 191
 192                 _do_copy(temp, item, 1);
 193
 194                 ssize_t j = i-1;
 195                 void* next = reinterpret_cast<char*>(array) + mItemSize*(i);
 196                 do {
 197                     _do_destroy(next, 1);
 198                     _do_copy(next, curr, 1);
 199                     next = curr;
 200                     --j;
 201                     curr = reinterpret_cast<char*>(array) + mItemSize*(j);
 202                 } while (j>=0 && (cmp(curr, temp, state) > 0));
 203
 204                 _do_destroy(next, 1);
 205                 _do_copy(next, temp, 1);
 206             }
 207             i++;
 208         }
 209
 210         if (temp) {
 211             _do_destroy(temp, 1);
 212             free(temp);
 213         }
 214     }
 215     return NO_ERROR;
 216 }
 217
 218 void VectorImpl::pop()
 219 {
 220     if (size())
 221         removeItemsAt(size()-1, 1);
 222 }
 223
 224 void VectorImpl::push()
 225 {
 226     push(0);
 227 }
 228
 229 void VectorImpl::push(const void* item)
 230 {
 231     insertAt(item, size());
 232 }
 233
 234 ssize_t VectorImpl::add()
 235 {
 236     return add(0);
 237 }
 238
 239 ssize_t VectorImpl::add(const void* item)
 240 {
 241     return insertAt(item, size());
 242 }
 243
 244 ssize_t VectorImpl::replaceAt(size_t index)
 245 {
 246     return replaceAt(0, index);
 247 }
 248
 249 ssize_t VectorImpl::replaceAt(const void* prototype, size_t index)
 250 {
 251     LOG_ASSERT(index<size(),
 252         "[%p] replace: index=%d, size=%d", this, (int)index, (int)size());
 253
 254     void* item = editItemLocation(index);
 255     if (item == 0)
 256         return NO_MEMORY;
 257     _do_destroy(item, 1);
 258     if (prototype == 0) {
 259         _do_construct(item, 1);
 260     } else {
 261         _do_copy(item, prototype, 1);
 262     }
 263     return ssize_t(index);
 264 }
 265
 266 ssize_t VectorImpl::removeItemsAt(size_t index, size_t count)
 267 {
 268     LOG_ASSERT((index+count)<=size(),
 269         "[%p] remove: index=%d, count=%d, size=%d",
 270                this, (int)index, (int)count, (int)size());
 271
 272     if ((index+count) > size())
 273         return BAD_VALUE;
 274    _shrink(index, count);
 275    return index;
 276 }
 277
 278 void VectorImpl::finish_vector()
 279 {
 280     release_storage();
 281     mStorage = 0;
 282     mCount = 0;
 283 }
 284
 285 void VectorImpl::clear()
 286 {
 287     _shrink(0, mCount);
 288 }
 289
 290 void* VectorImpl::editItemLocation(size_t index)
 291 {
 292     LOG_ASSERT(index<capacity(),
 293         "[%p] itemLocation: index=%d, capacity=%d, count=%d",
 294         this, (int)index, (int)capacity(), (int)mCount);
 295
 296     void* buffer = editArrayImpl();
 297     if (buffer)
 298         return reinterpret_cast<char*>(buffer) + index*mItemSize;
 299     return 0;
 300 }
 301
 302 const void* VectorImpl::itemLocation(size_t index) const
 303 {
 304     LOG_ASSERT(index<capacity(),
 305         "[%p] editItemLocation: index=%d, capacity=%d, count=%d",
 306         this, (int)index, (int)capacity(), (int)mCount);
 307
 308     const  void* buffer = arrayImpl();
 309     if (buffer)
 310         return reinterpret_cast<const char*>(buffer) + index*mItemSize;
 311     return 0;
 312 }
 313
 314 ssize_t VectorImpl::setCapacity(size_t new_capacity)
 315 {
 316     size_t current_capacity = capacity();
 317     ssize_t amount = new_capacity - size();
 318     if (amount <= 0) {
 319         // we can't reduce the capacity
 320         return current_capacity;
 321     }
 322     SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
 323     if (sb) {
 324         void* array = sb->data();
 325         _do_copy(array, mStorage, size());
 326         release_storage();
 327         mStorage = const_cast<void*>(array);
 328     } else {
 329         return NO_MEMORY;
 330     }
 331     return new_capacity;
 332 }
 333
 334 void VectorImpl::release_storage()
 335 {
 336     if (mStorage) {
 337         const SharedBuffer* sb = SharedBuffer::sharedBuffer(mStorage);
 338         if (sb->release(SharedBuffer::eKeepStorage) == 1) {
 339             _do_destroy(mStorage, mCount);
 340             SharedBuffer::dealloc(sb);
 341         }
 342     }
 343 }
 344
 345 void* VectorImpl::_grow(size_t where, size_t amount)
 346 {
 347 //    LOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
 348 //        this, (int)where, (int)amount, (int)mCount, (int)capacity());
 349
 350     if (where > mCount)
 351         where = mCount;
 352
 353     const size_t new_size = mCount + amount;
 354     if (capacity() < new_size) {
 355         const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2);
 356 //        LOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity);
 357         if ((mStorage) &&
 358             (mCount==where) &&
 359             (mFlags & HAS_TRIVIAL_COPY) &&
 360             (mFlags & HAS_TRIVIAL_DTOR))
 361         {
 362             const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
 363             SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
 364             mStorage = sb->data();
 365         } else {
 366             SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
 367             if (sb) {
 368                 void* array = sb->data();
 369                 if (where>0) {
 370                     _do_copy(array, mStorage, where);
 371                 }
 372                 if (mCount>where) {
 373                     const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize;
 374                     void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
 375                     _do_copy(dest, from, mCount-where);
 376                 }
 377                 release_storage();
 378                 mStorage = const_cast<void*>(array);
 379             }
 380         }
 381     } else {
 382         ssize_t s = mCount-where;
 383         if (s>0) {
 384             void* array = editArrayImpl();
 385             void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
 386             const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize;
 387             _do_move_forward(to, from, s);
 388         }
 389     }
 390     mCount += amount;
 391     void* free_space = const_cast<void*>(itemLocation(where));
 392     return free_space;
 393 }
 394
 395 void VectorImpl::_shrink(size_t where, size_t amount)
 396 {
 397     if (!mStorage)
 398         return;
 399
 400 //    LOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
 401 //        this, (int)where, (int)amount, (int)mCount, (int)capacity());
 402
 403     if (where >= mCount)
 404         where = mCount - amount;
 405
 406     const size_t new_size = mCount - amount;
 407     if (new_size*3 < capacity()) {
 408         const size_t new_capacity = max(kMinVectorCapacity, new_size*2);
 409 //        LOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity);
 410         if ((where == mCount-amount) &&
 411             (mFlags & HAS_TRIVIAL_COPY) &&
 412             (mFlags & HAS_TRIVIAL_DTOR))
 413         {
 414             const SharedBuffer* cur_sb = SharedBuffer::sharedBuffer(mStorage);
 415             SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
 416             mStorage = sb->data();
 417         } else {
 418             SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
 419             if (sb) {
 420                 void* array = sb->data();
 421                 if (where>0) {
 422                     _do_copy(array, mStorage, where);
 423                 }
 424                 if (mCount > where+amount) {
 425                     const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize;
 426                     void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
 427                     _do_copy(dest, from, mCount-(where+amount));
 428                 }
 429                 release_storage();
 430                 mStorage = const_cast<void*>(array);
 431             }
 432         }
 433     } else {
 434         void* array = editArrayImpl();
 435         void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
 436         _do_destroy(to, amount);
 437         ssize_t s = mCount-(where+amount);
 438         if (s>0) {
 439             const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
 440             _do_move_backward(to, from, s);
 441         }
 442     }
 443
 444     // adjust the number of items...
 445     mCount -= amount;
 446 }
 447
 448 size_t VectorImpl::itemSize() const {
 449     return mItemSize;
 450 }
 451
 452 void VectorImpl::_do_construct(void* storage, size_t num) const
 453 {
 454     if (!(mFlags & HAS_TRIVIAL_CTOR)) {
 455         do_construct(storage, num);
 456     }
 457 }
 458
 459 void VectorImpl::_do_destroy(void* storage, size_t num) const
 460 {
 461     if (!(mFlags & HAS_TRIVIAL_DTOR)) {
 462         do_destroy(storage, num);
 463     }
 464 }
 465
 466 void VectorImpl::_do_copy(void* dest, const void* from, size_t num) const
 467 {
 468     if (!(mFlags & HAS_TRIVIAL_COPY)) {
 469         do_copy(dest, from, num);
 470     } else {
 471         memcpy(dest, from, num*itemSize());
 472     }
 473 }
 474
 475 void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
 476     do_splat(dest, item, num);
 477 }
 478
 479 void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
 480     do_move_forward(dest, from, num);
 481 }
 482
 483 void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
 484     do_move_backward(dest, from, num);
 485 }
 486
 487 void VectorImpl::reservedVectorImpl1() { }
 488 void VectorImpl::reservedVectorImpl2() { }
 489 void VectorImpl::reservedVectorImpl3() { }
 490 void VectorImpl::reservedVectorImpl4() { }
 491 void VectorImpl::reservedVectorImpl5() { }
 492 void VectorImpl::reservedVectorImpl6() { }
 493 void VectorImpl::reservedVectorImpl7() { }
 494 void VectorImpl::reservedVectorImpl8() { }
 495
 496 /*****************************************************************************/
 497
 498 SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
 499     : VectorImpl(itemSize, flags)
 500 {
 501 }
 502
 503 SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
 504 : VectorImpl(rhs)
 505 {
 506 }
 507
 508 SortedVectorImpl::~SortedVectorImpl()
 509 {
 510 }
 511
 512 SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
 513 {
 514     return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
 515 }
 516
 517 ssize_t SortedVectorImpl::indexOf(const void* item) const
 518 {
 519     return _indexOrderOf(item);
 520 }
 521
 522 size_t SortedVectorImpl::orderOf(const void* item) const
 523 {
 524     size_t o;
 525     _indexOrderOf(item, &o);
 526     return o;
 527 }
 528
 529 ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
 530 {
 531     // binary search
 532     ssize_t err = NAME_NOT_FOUND;
 533     ssize_t l = 0;
 534     ssize_t h = size()-1;
 535     ssize_t mid;
 536     const void* a = arrayImpl();
 537     const size_t s = itemSize();
 538     while (l <= h) {
 539         mid = l + (h - l)/2;
 540         const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
 541         const int c = do_compare(curr, item);
 542         if (c == 0) {
 543             err = l = mid;
 544             break;
 545         } else if (c < 0) {
 546             l = mid + 1;
 547         } else {
 548             h = mid - 1;
 549         }
 550     }
 551     if (order) *order = l;
 552     return err;
 553 }
 554
 555 ssize_t SortedVectorImpl::add(const void* item)
 556 {
 557     size_t order;
 558     ssize_t index = _indexOrderOf(item, &order);
 559     if (index < 0) {
 560         index = VectorImpl::insertAt(item, order, 1);
 561     } else {
 562         index = VectorImpl::replaceAt(item, index);
 563     }
 564     return index;
 565 }
 566
 567 ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
 568 {
 569     // naive merge...
 570     if (!vector.isEmpty()) {
 571         const void* buffer = vector.arrayImpl();
 572         const size_t is = itemSize();
 573         size_t s = vector.size();
 574         for (size_t i=0 ; i<s ; i++) {
 575             ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is );
 576             if (err<0) {
 577                 return err;
 578             }
 579         }
 580     }
 581     return NO_ERROR;
 582 }
 583
 584 ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
 585 {
 586     // we've merging a sorted vector... nice!
 587     ssize_t err = NO_ERROR;
 588     if (!vector.isEmpty()) {
 589         // first take care of the case where the vectors are sorted together
 590         if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) {
 591             err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0);
 592         } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) {
 593             err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector));
 594         } else {
 595             // this could be made a little better
 596             err = merge(static_cast<const VectorImpl&>(vector));
 597         }
 598     }
 599     return err;
 600 }
 601
 602 ssize_t SortedVectorImpl::remove(const void* item)
 603 {
 604     ssize_t i = indexOf(item);
 605     if (i>=0) {
 606         VectorImpl::removeItemsAt(i, 1);
 607     }
 608     return i;
 609 }
 610
 611 void SortedVectorImpl::reservedSortedVectorImpl1() { };
 612 void SortedVectorImpl::reservedSortedVectorImpl2() { };
 613 void SortedVectorImpl::reservedSortedVectorImpl3() { };
 614 void SortedVectorImpl::reservedSortedVectorImpl4() { };
 615 void SortedVectorImpl::reservedSortedVectorImpl5() { };
 616 void SortedVectorImpl::reservedSortedVectorImpl6() { };
 617 void SortedVectorImpl::reservedSortedVectorImpl7() { };
 618 void SortedVectorImpl::reservedSortedVectorImpl8() { };
 619
 620
 621 /*****************************************************************************/
 622
 623 }; // namespace android
 624