Home | History | Annotate | Download | only in containers 
      1 // Copyright 2014 The Android Open Source Project
      2 //
      3 // This software is licensed under the terms of the GNU General Public
      4 // License version 2, as published by the Free Software Foundation, and
      5 // may be copied, distributed, and modified under those terms.
      6 //
      7 // This program is distributed in the hope that it will be useful,
      8 // but WITHOUT ANY WARRANTY; without even the implied warranty of
      9 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     10 // GNU General Public License for more details.
     11 
     12 #include "android/base/containers/PodVector.h"
     13 
     14 #include "android/base/Log.h"
     15 #include "android/base/memory/MallocUsableSize.h"
     16 
     17 #include <stdlib.h>
     18 #include <string.h>
     19 
     20 namespace android {
     21 namespace base {
     22 
     23 static inline void swapPointers(char** p1, char** p2) {
     24     char* tmp = *p1;
     25     *p1 = *p2;
     26     *p2 = tmp;
     27 }
     28 
     29 PodVectorBase::PodVectorBase(const PodVectorBase& other) {
     30     initFrom(other.begin(), other.byteSize());
     31 }
     32 
     33 PodVectorBase& PodVectorBase::operator=(const PodVectorBase& other) {
     34     initFrom(other.begin(), other.byteSize());
     35     return *this;
     36 }
     37 
     38 PodVectorBase::~PodVectorBase() {
     39     if (mBegin) {
     40         // Sanity.
     41         ::memset(mBegin, 0xee, byteSize());
     42         ::free(mBegin);
     43         mBegin = NULL;
     44         mEnd = NULL;
     45         mLimit = NULL;
     46     }
     47 }
     48 
     49 void PodVectorBase::initFrom(const void* from, size_t fromLen) {
     50     if (!fromLen || !from) {
     51         mBegin = NULL;
     52         mEnd = NULL;
     53         mLimit = NULL;
     54     } else {
     55         mBegin = static_cast<char*>(::malloc(fromLen));
     56         PCHECK(mBegin)
     57                 << LogString("Could not allocate %zd bytes.", fromLen);
     58         mEnd = mLimit = mBegin + fromLen;
     59         ::memcpy(mBegin, from, fromLen);
     60     }
     61 }
     62 
     63 void PodVectorBase::assignFrom(const PodVectorBase& other) {
     64     resize(other.byteSize(), 1U);
     65     ::memmove(begin(), other.begin(), byteSize());
     66 }
     67 
     68 void PodVectorBase::resize(size_t newSize, size_t itemSize) {
     69     const size_t kMaxSize = maxItemCapacity(itemSize);
     70     CHECK(newSize <= kMaxSize) << LogString(
     71             "Trying to resize vector to %zd items of %zd bytes "
     72             "(%zd max allowed)",
     73             newSize,
     74             kMaxSize);
     75     size_t oldCapacity = itemCapacity(itemSize);
     76     const size_t kMinCapacity = 256 / itemSize;
     77 
     78     if (newSize < oldCapacity) {
     79         // Only shrink if the new size is really small.
     80         if (newSize < oldCapacity / 2 && oldCapacity > kMinCapacity) {
     81             reserve(newSize, itemSize);
     82         }
     83     } else if (newSize > oldCapacity) {
     84         size_t newCapacity = oldCapacity;
     85         while (newCapacity < newSize) {
     86             size_t newCapacity2 = newCapacity + (newCapacity >> 2) + 8;
     87             if (newCapacity2 < newCapacity || newCapacity > kMaxSize) {
     88                 newCapacity = kMaxSize;
     89             } else {
     90                 newCapacity = newCapacity2;
     91             }
     92         }
     93         reserve(newCapacity, itemSize);
     94     }
     95     mEnd = mBegin + newSize * itemSize;
     96 }
     97 
     98 void PodVectorBase::reserve(size_t newSize, size_t itemSize) {
     99     const size_t kMaxSize = maxItemCapacity(itemSize);
    100     CHECK(newSize <= kMaxSize) << LogString(
    101             "Trying to allocate %zd items of %zd bytes (%zd max allowed)",
    102             newSize,
    103             kMaxSize);
    104 
    105     if (newSize == 0) {
    106         ::free(mBegin);
    107         mBegin = NULL;
    108         mEnd = NULL;
    109         mLimit = NULL;
    110         return;
    111     }
    112 
    113     size_t oldByteSize = byteSize();
    114     size_t newByteCapacity = newSize * itemSize;
    115     char* newBegin = static_cast<char*>(::realloc(mBegin, newByteCapacity));
    116     PCHECK(newBegin) << LogString(
    117             "Could not reallocate array from %zd tp %zd items of %zd bytes",
    118             oldByteSize / itemSize,
    119             newSize,
    120             itemSize);
    121 
    122     mBegin = newBegin;
    123     mEnd = newBegin + oldByteSize;
    124 #if USE_MALLOC_USABLE_SIZE
    125     size_t usableSize = malloc_usable_size(mBegin);
    126     if (usableSize > newByteCapacity) {
    127         newByteCapacity = usableSize - (usableSize % itemSize);
    128     }
    129 #endif
    130     mLimit = newBegin + newByteCapacity;
    131     // Sanity.
    132     if (newByteCapacity > oldByteSize) {
    133         ::memset(mBegin + oldByteSize, 0, newByteCapacity - oldByteSize);
    134     }
    135 }
    136 
    137 void PodVectorBase::removeAt(size_t itemPos, size_t itemSize) {
    138     size_t count = itemCount(itemSize);
    139     DCHECK(itemPos <= count) << "Item position is too large!";
    140     if (itemPos < count) {
    141         size_t  pos = itemPos * itemSize;
    142         ::memmove(mBegin + pos,
    143                   mBegin + pos + itemSize,
    144                   byteSize() - pos - itemSize);
    145         resize(count - 1U, itemSize);
    146     }
    147 }
    148 
    149 void* PodVectorBase::insertAt(size_t itemPos, size_t itemSize) {
    150     size_t count = this->itemCount(itemSize);
    151     DCHECK(itemPos <= count) << "Item position is too large";
    152     resize(count + 1, itemSize);
    153     size_t pos = itemPos * itemSize;
    154     if (itemPos < count) {
    155         ::memmove(mBegin + pos + itemSize,
    156                   mBegin + pos,
    157                   count * itemSize - pos);
    158         // Sanity to avoid copying pointers and other bad stuff.
    159         ::memset(mBegin + pos, 0, itemSize);
    160     }
    161     return mBegin + pos;
    162 }
    163 
    164 void PodVectorBase::swapAll(PodVectorBase* other) {
    165     swapPointers(&mBegin, &other->mBegin);
    166     swapPointers(&mEnd, &other->mEnd);
    167     swapPointers(&mLimit, &other->mLimit);
    168 }
    169 
    170 }  // namespace base
    171 }  // namespace android
    172