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 <cutils/log.h>
  24
  25 #include <utils/Errors.h>
  26 #include <utils/SharedBuffer.h>
  27 #include <utils/VectorImpl.h>
  28
  29 /*****************************************************************************/
  30
  31
  32 namespace android {
  33
  34 // ----------------------------------------------------------------------------
  35
  36 const size_t kMinVectorCapacity = 4;
  37
  38 static inline size_t max(size_t a, size_t b) {
  39     return a>b ? a : b;
  40 }
  41
  42 // ----------------------------------------------------------------------------
  43
  44 VectorImpl::VectorImpl(size_t itemSize, uint32_t flags)
  45     : mStorage(0), mCount(0), mFlags(flags), mItemSize(itemSize)
  46 {
  47 }
  48
  49 VectorImpl::VectorImpl(const VectorImpl& rhs)
  50     :   mStorage(rhs.mStorage), mCount(rhs.mCount),
  51         mFlags(rhs.mFlags), mItemSize(rhs.mItemSize)
  52 {
  53     if (mStorage) {
  54         SharedBuffer::bufferFromData(mStorage)->acquire();
  55     }
  56 }
  57
  58 VectorImpl::~VectorImpl()
  59 {
  60     ALOGW_IF(mCount,
  61         "[%p] 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_ALWAYS_FATAL_IF(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::bufferFromData(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::bufferFromData(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::bufferFromData(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     ALOG_ASSERT(index<size(),
 252         "[%p] replace: index=%d, size=%d", this, (int)index, (int)size());
 253
 254     if (index >= size()) {
 255         return BAD_INDEX;
 256     }
 257
 258     void* item = editItemLocation(index);
 259     if (item != prototype) {
 260         if (item == 0)
 261             return NO_MEMORY;
 262         _do_destroy(item, 1);
 263         if (prototype == 0) {
 264             _do_construct(item, 1);
 265         } else {
 266             _do_copy(item, prototype, 1);
 267         }
 268     }
 269     return ssize_t(index);
 270 }
 271
 272 ssize_t VectorImpl::removeItemsAt(size_t index, size_t count)
 273 {
 274     ALOG_ASSERT((index+count)<=size(),
 275         "[%p] remove: index=%d, count=%d, size=%d",
 276                this, (int)index, (int)count, (int)size());
 277
 278     if ((index+count) > size())
 279         return BAD_VALUE;
 280    _shrink(index, count);
 281    return index;
 282 }
 283
 284 void VectorImpl::finish_vector()
 285 {
 286     release_storage();
 287     mStorage = 0;
 288     mCount = 0;
 289 }
 290
 291 void VectorImpl::clear()
 292 {
 293     _shrink(0, mCount);
 294 }
 295
 296 void* VectorImpl::editItemLocation(size_t index)
 297 {
 298     ALOG_ASSERT(index<capacity(),
 299         "[%p] editItemLocation: index=%d, capacity=%d, count=%d",
 300         this, (int)index, (int)capacity(), (int)mCount);
 301
 302     if (index < capacity()) {
 303         void* buffer = editArrayImpl();
 304         if (buffer) {
 305             return reinterpret_cast<char*>(buffer) + index*mItemSize;
 306         }
 307     }
 308     return 0;
 309 }
 310
 311 const void* VectorImpl::itemLocation(size_t index) const
 312 {
 313     ALOG_ASSERT(index<capacity(),
 314         "[%p] itemLocation: index=%d, capacity=%d, count=%d",
 315         this, (int)index, (int)capacity(), (int)mCount);
 316
 317     if (index < capacity()) {
 318         const  void* buffer = arrayImpl();
 319         if (buffer) {
 320             return reinterpret_cast<const char*>(buffer) + index*mItemSize;
 321         }
 322     }
 323     return 0;
 324 }
 325
 326 ssize_t VectorImpl::setCapacity(size_t new_capacity)
 327 {
 328     size_t current_capacity = capacity();
 329     ssize_t amount = new_capacity - size();
 330     if (amount <= 0) {
 331         // we can't reduce the capacity
 332         return current_capacity;
 333     }
 334     SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
 335     if (sb) {
 336         void* array = sb->data();
 337         _do_copy(array, mStorage, size());
 338         release_storage();
 339         mStorage = const_cast<void*>(array);
 340     } else {
 341         return NO_MEMORY;
 342     }
 343     return new_capacity;
 344 }
 345
 346 void VectorImpl::release_storage()
 347 {
 348     if (mStorage) {
 349         const SharedBuffer* sb = SharedBuffer::bufferFromData(mStorage);
 350         if (sb->release(SharedBuffer::eKeepStorage) == 1) {
 351             _do_destroy(mStorage, mCount);
 352             SharedBuffer::dealloc(sb);
 353         }
 354     }
 355 }
 356
 357 void* VectorImpl::_grow(size_t where, size_t amount)
 358 {
 359 //    ALOGV("_grow(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
 360 //        this, (int)where, (int)amount, (int)mCount, (int)capacity());
 361
 362     ALOG_ASSERT(where <= mCount,
 363             "[%p] _grow: where=%d, amount=%d, count=%d",
 364             this, (int)where, (int)amount, (int)mCount); // caller already checked
 365
 366     const size_t new_size = mCount + amount;
 367     if (capacity() < new_size) {
 368         const size_t new_capacity = max(kMinVectorCapacity, ((new_size*3)+1)/2);
 369 //        ALOGV("grow vector %p, new_capacity=%d", this, (int)new_capacity);
 370         if ((mStorage) &&
 371             (mCount==where) &&
 372             (mFlags & HAS_TRIVIAL_COPY) &&
 373             (mFlags & HAS_TRIVIAL_DTOR))
 374         {
 375             const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage);
 376             SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
 377             mStorage = sb->data();
 378         } else {
 379             SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
 380             if (sb) {
 381                 void* array = sb->data();
 382                 if (where != 0) {
 383                     _do_copy(array, mStorage, where);
 384                 }
 385                 if (where != mCount) {
 386                     const void* from = reinterpret_cast<const uint8_t *>(mStorage) + where*mItemSize;
 387                     void* dest = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
 388                     _do_copy(dest, from, mCount-where);
 389                 }
 390                 release_storage();
 391                 mStorage = const_cast<void*>(array);
 392             }
 393         }
 394     } else {
 395         void* array = editArrayImpl();
 396         if (where != mCount) {
 397             const void* from = reinterpret_cast<const uint8_t *>(array) + where*mItemSize;
 398             void* to = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
 399             _do_move_forward(to, from, mCount - where);
 400         }
 401     }
 402     mCount = new_size;
 403     void* free_space = const_cast<void*>(itemLocation(where));
 404     return free_space;
 405 }
 406
 407 void VectorImpl::_shrink(size_t where, size_t amount)
 408 {
 409     if (!mStorage)
 410         return;
 411
 412 //    ALOGV("_shrink(this=%p, where=%d, amount=%d) count=%d, capacity=%d",
 413 //        this, (int)where, (int)amount, (int)mCount, (int)capacity());
 414
 415     ALOG_ASSERT(where + amount <= mCount,
 416             "[%p] _shrink: where=%d, amount=%d, count=%d",
 417             this, (int)where, (int)amount, (int)mCount); // caller already checked
 418
 419     const size_t new_size = mCount - amount;
 420     if (new_size*3 < capacity()) {
 421         const size_t new_capacity = max(kMinVectorCapacity, new_size*2);
 422 //        ALOGV("shrink vector %p, new_capacity=%d", this, (int)new_capacity);
 423         if ((where == new_size) &&
 424             (mFlags & HAS_TRIVIAL_COPY) &&
 425             (mFlags & HAS_TRIVIAL_DTOR))
 426         {
 427             const SharedBuffer* cur_sb = SharedBuffer::bufferFromData(mStorage);
 428             SharedBuffer* sb = cur_sb->editResize(new_capacity * mItemSize);
 429             mStorage = sb->data();
 430         } else {
 431             SharedBuffer* sb = SharedBuffer::alloc(new_capacity * mItemSize);
 432             if (sb) {
 433                 void* array = sb->data();
 434                 if (where != 0) {
 435                     _do_copy(array, mStorage, where);
 436                 }
 437                 if (where != new_size) {
 438                     const void* from = reinterpret_cast<const uint8_t *>(mStorage) + (where+amount)*mItemSize;
 439                     void* dest = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
 440                     _do_copy(dest, from, new_size - where);
 441                 }
 442                 release_storage();
 443                 mStorage = const_cast<void*>(array);
 444             }
 445         }
 446     } else {
 447         void* array = editArrayImpl();
 448         void* to = reinterpret_cast<uint8_t *>(array) + where*mItemSize;
 449         _do_destroy(to, amount);
 450         if (where != new_size) {
 451             const void* from = reinterpret_cast<uint8_t *>(array) + (where+amount)*mItemSize;
 452             _do_move_backward(to, from, new_size - where);
 453         }
 454     }
 455     mCount = new_size;
 456 }
 457
 458 size_t VectorImpl::itemSize() const {
 459     return mItemSize;
 460 }
 461
 462 void VectorImpl::_do_construct(void* storage, size_t num) const
 463 {
 464     if (!(mFlags & HAS_TRIVIAL_CTOR)) {
 465         do_construct(storage, num);
 466     }
 467 }
 468
 469 void VectorImpl::_do_destroy(void* storage, size_t num) const
 470 {
 471     if (!(mFlags & HAS_TRIVIAL_DTOR)) {
 472         do_destroy(storage, num);
 473     }
 474 }
 475
 476 void VectorImpl::_do_copy(void* dest, const void* from, size_t num) const
 477 {
 478     if (!(mFlags & HAS_TRIVIAL_COPY)) {
 479         do_copy(dest, from, num);
 480     } else {
 481         memcpy(dest, from, num*itemSize());
 482     }
 483 }
 484
 485 void VectorImpl::_do_splat(void* dest, const void* item, size_t num) const {
 486     do_splat(dest, item, num);
 487 }
 488
 489 void VectorImpl::_do_move_forward(void* dest, const void* from, size_t num) const {
 490     do_move_forward(dest, from, num);
 491 }
 492
 493 void VectorImpl::_do_move_backward(void* dest, const void* from, size_t num) const {
 494     do_move_backward(dest, from, num);
 495 }
 496
 497 void VectorImpl::reservedVectorImpl1() { }
 498 void VectorImpl::reservedVectorImpl2() { }
 499 void VectorImpl::reservedVectorImpl3() { }
 500 void VectorImpl::reservedVectorImpl4() { }
 501 void VectorImpl::reservedVectorImpl5() { }
 502 void VectorImpl::reservedVectorImpl6() { }
 503 void VectorImpl::reservedVectorImpl7() { }
 504 void VectorImpl::reservedVectorImpl8() { }
 505
 506 /*****************************************************************************/
 507
 508 SortedVectorImpl::SortedVectorImpl(size_t itemSize, uint32_t flags)
 509     : VectorImpl(itemSize, flags)
 510 {
 511 }
 512
 513 SortedVectorImpl::SortedVectorImpl(const VectorImpl& rhs)
 514 : VectorImpl(rhs)
 515 {
 516 }
 517
 518 SortedVectorImpl::~SortedVectorImpl()
 519 {
 520 }
 521
 522 SortedVectorImpl& SortedVectorImpl::operator = (const SortedVectorImpl& rhs)
 523 {
 524     return static_cast<SortedVectorImpl&>( VectorImpl::operator = (static_cast<const VectorImpl&>(rhs)) );
 525 }
 526
 527 ssize_t SortedVectorImpl::indexOf(const void* item) const
 528 {
 529     return _indexOrderOf(item);
 530 }
 531
 532 size_t SortedVectorImpl::orderOf(const void* item) const
 533 {
 534     size_t o;
 535     _indexOrderOf(item, &o);
 536     return o;
 537 }
 538
 539 ssize_t SortedVectorImpl::_indexOrderOf(const void* item, size_t* order) const
 540 {
 541     // binary search
 542     ssize_t err = NAME_NOT_FOUND;
 543     ssize_t l = 0;
 544     ssize_t h = size()-1;
 545     ssize_t mid;
 546     const void* a = arrayImpl();
 547     const size_t s = itemSize();
 548     while (l <= h) {
 549         mid = l + (h - l)/2;
 550         const void* const curr = reinterpret_cast<const char *>(a) + (mid*s);
 551         const int c = do_compare(curr, item);
 552         if (c == 0) {
 553             err = l = mid;
 554             break;
 555         } else if (c < 0) {
 556             l = mid + 1;
 557         } else {
 558             h = mid - 1;
 559         }
 560     }
 561     if (order) *order = l;
 562     return err;
 563 }
 564
 565 ssize_t SortedVectorImpl::add(const void* item)
 566 {
 567     size_t order;
 568     ssize_t index = _indexOrderOf(item, &order);
 569     if (index < 0) {
 570         index = VectorImpl::insertAt(item, order, 1);
 571     } else {
 572         index = VectorImpl::replaceAt(item, index);
 573     }
 574     return index;
 575 }
 576
 577 ssize_t SortedVectorImpl::merge(const VectorImpl& vector)
 578 {
 579     // naive merge...
 580     if (!vector.isEmpty()) {
 581         const void* buffer = vector.arrayImpl();
 582         const size_t is = itemSize();
 583         size_t s = vector.size();
 584         for (size_t i=0 ; i<s ; i++) {
 585             ssize_t err = add( reinterpret_cast<const char*>(buffer) + i*is );
 586             if (err<0) {
 587                 return err;
 588             }
 589         }
 590     }
 591     return NO_ERROR;
 592 }
 593
 594 ssize_t SortedVectorImpl::merge(const SortedVectorImpl& vector)
 595 {
 596     // we've merging a sorted vector... nice!
 597     ssize_t err = NO_ERROR;
 598     if (!vector.isEmpty()) {
 599         // first take care of the case where the vectors are sorted together
 600         if (do_compare(vector.itemLocation(vector.size()-1), arrayImpl()) <= 0) {
 601             err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&>(vector), 0);
 602         } else if (do_compare(vector.arrayImpl(), itemLocation(size()-1)) >= 0) {
 603             err = VectorImpl::appendVector(static_cast<const VectorImpl&>(vector));
 604         } else {
 605             // this could be made a little better
 606             err = merge(static_cast<const VectorImpl&>(vector));
 607         }
 608     }
 609     return err;
 610 }
 611
 612 ssize_t SortedVectorImpl::remove(const void* item)
 613 {
 614     ssize_t i = indexOf(item);
 615     if (i>=0) {
 616         VectorImpl::removeItemsAt(i, 1);
 617     }
 618     return i;
 619 }
 620
 621 void SortedVectorImpl::reservedSortedVectorImpl1() { };
 622 void SortedVectorImpl::reservedSortedVectorImpl2() { };
 623 void SortedVectorImpl::reservedSortedVectorImpl3() { };
 624 void SortedVectorImpl::reservedSortedVectorImpl4() { };
 625 void SortedVectorImpl::reservedSortedVectorImpl5() { };
 626 void SortedVectorImpl::reservedSortedVectorImpl6() { };
 627 void SortedVectorImpl::reservedSortedVectorImpl7() { };
 628 void SortedVectorImpl::reservedSortedVectorImpl8() { };
 629
 630
 631 /*****************************************************************************/
 632
 633 }; // namespace android
 634