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