Home | History | Annotate | Download | only in lib_json 
      1 // Copyright 2007-2010 Baptiste Lepilleur
      2 // Distributed under MIT license, or public domain if desired and
      3 // recognized in your jurisdiction.
      4 // See file LICENSE for detail or copy at http://jsoncpp.sourceforge.net/LICENSE
      5 
      6 // included by json_value.cpp
      7 
      8 namespace Json {
      9 
     10 // //////////////////////////////////////////////////////////////////
     11 // //////////////////////////////////////////////////////////////////
     12 // //////////////////////////////////////////////////////////////////
     13 // class ValueInternalArray
     14 // //////////////////////////////////////////////////////////////////
     15 // //////////////////////////////////////////////////////////////////
     16 // //////////////////////////////////////////////////////////////////
     17 
     18 ValueArrayAllocator::~ValueArrayAllocator() {}
     19 
     20 // //////////////////////////////////////////////////////////////////
     21 // class DefaultValueArrayAllocator
     22 // //////////////////////////////////////////////////////////////////
     23 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
     24 class DefaultValueArrayAllocator : public ValueArrayAllocator {
     25 public: // overridden from ValueArrayAllocator
     26   virtual ~DefaultValueArrayAllocator() {}
     27 
     28   virtual ValueInternalArray* newArray() { return new ValueInternalArray(); }
     29 
     30   virtual ValueInternalArray* newArrayCopy(const ValueInternalArray& other) {
     31     return new ValueInternalArray(other);
     32   }
     33 
     34   virtual void destructArray(ValueInternalArray* array) { delete array; }
     35 
     36   virtual void
     37   reallocateArrayPageIndex(Value**& indexes,
     38                            ValueInternalArray::PageIndex& indexCount,
     39                            ValueInternalArray::PageIndex minNewIndexCount) {
     40     ValueInternalArray::PageIndex newIndexCount = (indexCount * 3) / 2 + 1;
     41     if (minNewIndexCount > newIndexCount)
     42       newIndexCount = minNewIndexCount;
     43     void* newIndexes = realloc(indexes, sizeof(Value*) * newIndexCount);
     44     JSON_ASSERT_MESSAGE(newIndexes, "Couldn't realloc.");
     45     indexCount = newIndexCount;
     46     indexes = static_cast<Value**>(newIndexes);
     47   }
     48   virtual void releaseArrayPageIndex(Value** indexes,
     49                                      ValueInternalArray::PageIndex indexCount) {
     50     if (indexes)
     51       free(indexes);
     52   }
     53 
     54   virtual Value* allocateArrayPage() {
     55     return static_cast<Value*>(
     56         malloc(sizeof(Value) * ValueInternalArray::itemsPerPage));
     57   }
     58 
     59   virtual void releaseArrayPage(Value* value) {
     60     if (value)
     61       free(value);
     62   }
     63 };
     64 
     65 #else  // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
     66 /// @todo make this thread-safe (lock when accessign batch allocator)
     67 class DefaultValueArrayAllocator : public ValueArrayAllocator {
     68 public: // overridden from ValueArrayAllocator
     69   virtual ~DefaultValueArrayAllocator() {}
     70 
     71   virtual ValueInternalArray* newArray() {
     72     ValueInternalArray* array = arraysAllocator_.allocate();
     73     new (array) ValueInternalArray(); // placement new
     74     return array;
     75   }
     76 
     77   virtual ValueInternalArray* newArrayCopy(const ValueInternalArray& other) {
     78     ValueInternalArray* array = arraysAllocator_.allocate();
     79     new (array) ValueInternalArray(other); // placement new
     80     return array;
     81   }
     82 
     83   virtual void destructArray(ValueInternalArray* array) {
     84     if (array) {
     85       array->~ValueInternalArray();
     86       arraysAllocator_.release(array);
     87     }
     88   }
     89 
     90   virtual void
     91   reallocateArrayPageIndex(Value**& indexes,
     92                            ValueInternalArray::PageIndex& indexCount,
     93                            ValueInternalArray::PageIndex minNewIndexCount) {
     94     ValueInternalArray::PageIndex newIndexCount = (indexCount * 3) / 2 + 1;
     95     if (minNewIndexCount > newIndexCount)
     96       newIndexCount = minNewIndexCount;
     97     void* newIndexes = realloc(indexes, sizeof(Value*) * newIndexCount);
     98     JSON_ASSERT_MESSAGE(newIndexes, "Couldn't realloc.");
     99     indexCount = newIndexCount;
    100     indexes = static_cast<Value**>(newIndexes);
    101   }
    102   virtual void releaseArrayPageIndex(Value** indexes,
    103                                      ValueInternalArray::PageIndex indexCount) {
    104     if (indexes)
    105       free(indexes);
    106   }
    107 
    108   virtual Value* allocateArrayPage() {
    109     return static_cast<Value*>(pagesAllocator_.allocate());
    110   }
    111 
    112   virtual void releaseArrayPage(Value* value) {
    113     if (value)
    114       pagesAllocator_.release(value);
    115   }
    116 
    117 private:
    118   BatchAllocator<ValueInternalArray, 1> arraysAllocator_;
    119   BatchAllocator<Value, ValueInternalArray::itemsPerPage> pagesAllocator_;
    120 };
    121 #endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
    122 
    123 static ValueArrayAllocator*& arrayAllocator() {
    124   static DefaultValueArrayAllocator defaultAllocator;
    125   static ValueArrayAllocator* arrayAllocator = &defaultAllocator;
    126   return arrayAllocator;
    127 }
    128 
    129 static struct DummyArrayAllocatorInitializer {
    130   DummyArrayAllocatorInitializer() {
    131     arrayAllocator(); // ensure arrayAllocator() statics are initialized before
    132                       // main().
    133   }
    134 } dummyArrayAllocatorInitializer;
    135 
    136 // //////////////////////////////////////////////////////////////////
    137 // class ValueInternalArray
    138 // //////////////////////////////////////////////////////////////////
    139 bool ValueInternalArray::equals(const IteratorState& x,
    140                                 const IteratorState& other) {
    141   return x.array_ == other.array_ &&
    142          x.currentItemIndex_ == other.currentItemIndex_ &&
    143          x.currentPageIndex_ == other.currentPageIndex_;
    144 }
    145 
    146 void ValueInternalArray::increment(IteratorState& it) {
    147   JSON_ASSERT_MESSAGE(
    148       it.array_ && (it.currentPageIndex_ - it.array_->pages_) * itemsPerPage +
    149                            it.currentItemIndex_ !=
    150                        it.array_->size_,
    151       "ValueInternalArray::increment(): moving iterator beyond end");
    152   ++(it.currentItemIndex_);
    153   if (it.currentItemIndex_ == itemsPerPage) {
    154     it.currentItemIndex_ = 0;
    155     ++(it.currentPageIndex_);
    156   }
    157 }
    158 
    159 void ValueInternalArray::decrement(IteratorState& it) {
    160   JSON_ASSERT_MESSAGE(
    161       it.array_ && it.currentPageIndex_ == it.array_->pages_ &&
    162           it.currentItemIndex_ == 0,
    163       "ValueInternalArray::decrement(): moving iterator beyond end");
    164   if (it.currentItemIndex_ == 0) {
    165     it.currentItemIndex_ = itemsPerPage - 1;
    166     --(it.currentPageIndex_);
    167   } else {
    168     --(it.currentItemIndex_);
    169   }
    170 }
    171 
    172 Value& ValueInternalArray::unsafeDereference(const IteratorState& it) {
    173   return (*(it.currentPageIndex_))[it.currentItemIndex_];
    174 }
    175 
    176 Value& ValueInternalArray::dereference(const IteratorState& it) {
    177   JSON_ASSERT_MESSAGE(
    178       it.array_ && (it.currentPageIndex_ - it.array_->pages_) * itemsPerPage +
    179                            it.currentItemIndex_ <
    180                        it.array_->size_,
    181       "ValueInternalArray::dereference(): dereferencing invalid iterator");
    182   return unsafeDereference(it);
    183 }
    184 
    185 void ValueInternalArray::makeBeginIterator(IteratorState& it) const {
    186   it.array_ = const_cast<ValueInternalArray*>(this);
    187   it.currentItemIndex_ = 0;
    188   it.currentPageIndex_ = pages_;
    189 }
    190 
    191 void ValueInternalArray::makeIterator(IteratorState& it,
    192                                       ArrayIndex index) const {
    193   it.array_ = const_cast<ValueInternalArray*>(this);
    194   it.currentItemIndex_ = index % itemsPerPage;
    195   it.currentPageIndex_ = pages_ + index / itemsPerPage;
    196 }
    197 
    198 void ValueInternalArray::makeEndIterator(IteratorState& it) const {
    199   makeIterator(it, size_);
    200 }
    201 
    202 ValueInternalArray::ValueInternalArray() : pages_(0), size_(0), pageCount_(0) {}
    203 
    204 ValueInternalArray::ValueInternalArray(const ValueInternalArray& other)
    205     : pages_(0), size_(other.size_), pageCount_(0) {
    206   PageIndex minNewPages = other.size_ / itemsPerPage;
    207   arrayAllocator()->reallocateArrayPageIndex(pages_, pageCount_, minNewPages);
    208   JSON_ASSERT_MESSAGE(pageCount_ >= minNewPages,
    209                       "ValueInternalArray::reserve(): bad reallocation");
    210   IteratorState itOther;
    211   other.makeBeginIterator(itOther);
    212   Value* value;
    213   for (ArrayIndex index = 0; index < size_; ++index, increment(itOther)) {
    214     if (index % itemsPerPage == 0) {
    215       PageIndex pageIndex = index / itemsPerPage;
    216       value = arrayAllocator()->allocateArrayPage();
    217       pages_[pageIndex] = value;
    218     }
    219     new (value) Value(dereference(itOther));
    220   }
    221 }
    222 
    223 ValueInternalArray& ValueInternalArray::operator=(ValueInternalArray other) {
    224   swap(other);
    225   return *this;
    226 }
    227 
    228 ValueInternalArray::~ValueInternalArray() {
    229   // destroy all constructed items
    230   IteratorState it;
    231   IteratorState itEnd;
    232   makeBeginIterator(it);
    233   makeEndIterator(itEnd);
    234   for (; !equals(it, itEnd); increment(it)) {
    235     Value* value = &dereference(it);
    236     value->~Value();
    237   }
    238   // release all pages
    239   PageIndex lastPageIndex = size_ / itemsPerPage;
    240   for (PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex)
    241     arrayAllocator()->releaseArrayPage(pages_[pageIndex]);
    242   // release pages index
    243   arrayAllocator()->releaseArrayPageIndex(pages_, pageCount_);
    244 }
    245 
    246 void ValueInternalArray::swap(ValueInternalArray& other) {
    247   Value** tempPages = pages_;
    248   pages_ = other.pages_;
    249   other.pages_ = tempPages;
    250   ArrayIndex tempSize = size_;
    251   size_ = other.size_;
    252   other.size_ = tempSize;
    253   PageIndex tempPageCount = pageCount_;
    254   pageCount_ = other.pageCount_;
    255   other.pageCount_ = tempPageCount;
    256 }
    257 
    258 void ValueInternalArray::clear() {
    259   ValueInternalArray dummy;
    260   swap(dummy);
    261 }
    262 
    263 void ValueInternalArray::resize(ArrayIndex newSize) {
    264   if (newSize == 0)
    265     clear();
    266   else if (newSize < size_) {
    267     IteratorState it;
    268     IteratorState itEnd;
    269     makeIterator(it, newSize);
    270     makeIterator(itEnd, size_);
    271     for (; !equals(it, itEnd); increment(it)) {
    272       Value* value = &dereference(it);
    273       value->~Value();
    274     }
    275     PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage;
    276     PageIndex lastPageIndex = size_ / itemsPerPage;
    277     for (; pageIndex < lastPageIndex; ++pageIndex)
    278       arrayAllocator()->releaseArrayPage(pages_[pageIndex]);
    279     size_ = newSize;
    280   } else if (newSize > size_)
    281     resolveReference(newSize);
    282 }
    283 
    284 void ValueInternalArray::makeIndexValid(ArrayIndex index) {
    285   // Need to enlarge page index ?
    286   if (index >= pageCount_ * itemsPerPage) {
    287     PageIndex minNewPages = (index + 1) / itemsPerPage;
    288     arrayAllocator()->reallocateArrayPageIndex(pages_, pageCount_, minNewPages);
    289     JSON_ASSERT_MESSAGE(pageCount_ >= minNewPages,
    290                         "ValueInternalArray::reserve(): bad reallocation");
    291   }
    292 
    293   // Need to allocate new pages ?
    294   ArrayIndex nextPageIndex = (size_ % itemsPerPage) != 0
    295                                  ? size_ - (size_ % itemsPerPage) + itemsPerPage
    296                                  : size_;
    297   if (nextPageIndex <= index) {
    298     PageIndex pageIndex = nextPageIndex / itemsPerPage;
    299     PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1;
    300     for (; pageToAllocate-- > 0; ++pageIndex)
    301       pages_[pageIndex] = arrayAllocator()->allocateArrayPage();
    302   }
    303 
    304   // Initialize all new entries
    305   IteratorState it;
    306   IteratorState itEnd;
    307   makeIterator(it, size_);
    308   size_ = index + 1;
    309   makeIterator(itEnd, size_);
    310   for (; !equals(it, itEnd); increment(it)) {
    311     Value* value = &dereference(it);
    312     new (value) Value(); // Construct a default value using placement new
    313   }
    314 }
    315 
    316 Value& ValueInternalArray::resolveReference(ArrayIndex index) {
    317   if (index >= size_)
    318     makeIndexValid(index);
    319   return pages_[index / itemsPerPage][index % itemsPerPage];
    320 }
    321 
    322 Value* ValueInternalArray::find(ArrayIndex index) const {
    323   if (index >= size_)
    324     return 0;
    325   return &(pages_[index / itemsPerPage][index % itemsPerPage]);
    326 }
    327 
    328 ValueInternalArray::ArrayIndex ValueInternalArray::size() const {
    329   return size_;
    330 }
    331 
    332 int ValueInternalArray::distance(const IteratorState& x,
    333                                  const IteratorState& y) {
    334   return indexOf(y) - indexOf(x);
    335 }
    336 
    337 ValueInternalArray::ArrayIndex
    338 ValueInternalArray::indexOf(const IteratorState& iterator) {
    339   if (!iterator.array_)
    340     return ArrayIndex(-1);
    341   return ArrayIndex((iterator.currentPageIndex_ - iterator.array_->pages_) *
    342                         itemsPerPage +
    343                     iterator.currentItemIndex_);
    344 }
    345 
    346 int ValueInternalArray::compare(const ValueInternalArray& other) const {
    347   int sizeDiff(size_ - other.size_);
    348   if (sizeDiff != 0)
    349     return sizeDiff;
    350 
    351   for (ArrayIndex index = 0; index < size_; ++index) {
    352     int diff = pages_[index / itemsPerPage][index % itemsPerPage].compare(
    353         other.pages_[index / itemsPerPage][index % itemsPerPage]);
    354     if (diff != 0)
    355       return diff;
    356   }
    357   return 0;
    358 }
    359 
    360 } // namespace Json
    361