Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2022-08-17 23:57:25

0001 // included by json_value.cpp
0002 // everything is within Json namespace
0003 
0004 // //////////////////////////////////////////////////////////////////
0005 // //////////////////////////////////////////////////////////////////
0006 // //////////////////////////////////////////////////////////////////
0007 // class ValueInternalArray
0008 // //////////////////////////////////////////////////////////////////
0009 // //////////////////////////////////////////////////////////////////
0010 // //////////////////////////////////////////////////////////////////
0011 
0012 ValueArrayAllocator::~ValueArrayAllocator() {}
0013 
0014 // //////////////////////////////////////////////////////////////////
0015 // class DefaultValueArrayAllocator
0016 // //////////////////////////////////////////////////////////////////
0017 #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
0018 class DefaultValueArrayAllocator : public ValueArrayAllocator {
0019 public:  // overridden from ValueArrayAllocator
0020   virtual ~DefaultValueArrayAllocator() {}
0021 
0022   virtual ValueInternalArray *newArray() { return new ValueInternalArray(); }
0023 
0024   virtual ValueInternalArray *newArrayCopy(const ValueInternalArray &other) { return new ValueInternalArray(other); }
0025 
0026   virtual void destructArray(ValueInternalArray *array) { delete array; }
0027 
0028   virtual void reallocateArrayPageIndex(Value **&indexes,
0029                                         ValueInternalArray::PageIndex &indexCount,
0030                                         ValueInternalArray::PageIndex minNewIndexCount) {
0031     ValueInternalArray::PageIndex newIndexCount = (indexCount * 3) / 2 + 1;
0032     if (minNewIndexCount > newIndexCount)
0033       newIndexCount = minNewIndexCount;
0034     void *newIndexes = realloc(indexes, sizeof(Value *) * newIndexCount);
0035     if (!newIndexes)
0036       throw std::bad_alloc();
0037     indexCount = newIndexCount;
0038     indexes = static_cast<Value **>(newIndexes);
0039   }
0040   virtual void releaseArrayPageIndex(Value **indexes, ValueInternalArray::PageIndex indexCount) {
0041     if (indexes)
0042       free(indexes);
0043   }
0044 
0045   virtual Value *allocateArrayPage() {
0046     return static_cast<Value *>(malloc(sizeof(Value) * ValueInternalArray::itemsPerPage));
0047   }
0048 
0049   virtual void releaseArrayPage(Value *value) {
0050     if (value)
0051       free(value);
0052   }
0053 };
0054 
0055 #else   // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
0056 /// @todo make this thread-safe (lock when accessign batch allocator)
0057 class DefaultValueArrayAllocator : public ValueArrayAllocator {
0058 public:  // overridden from ValueArrayAllocator
0059   virtual ~DefaultValueArrayAllocator() {}
0060 
0061   virtual ValueInternalArray *newArray() {
0062     ValueInternalArray *array = arraysAllocator_.allocate();
0063     new (array) ValueInternalArray();  // placement new
0064     return array;
0065   }
0066 
0067   virtual ValueInternalArray *newArrayCopy(const ValueInternalArray &other) {
0068     ValueInternalArray *array = arraysAllocator_.allocate();
0069     new (array) ValueInternalArray(other);  // placement new
0070     return array;
0071   }
0072 
0073   virtual void destructArray(ValueInternalArray *array) {
0074     if (array) {
0075       array->~ValueInternalArray();
0076       arraysAllocator_.release(array);
0077     }
0078   }
0079 
0080   virtual void reallocateArrayPageIndex(Value **&indexes,
0081                                         ValueInternalArray::PageIndex &indexCount,
0082                                         ValueInternalArray::PageIndex minNewIndexCount) {
0083     ValueInternalArray::PageIndex newIndexCount = (indexCount * 3) / 2 + 1;
0084     if (minNewIndexCount > newIndexCount)
0085       newIndexCount = minNewIndexCount;
0086     void *newIndexes = realloc(indexes, sizeof(Value *) * newIndexCount);
0087     if (!newIndexes)
0088       throw std::bad_alloc();
0089     indexCount = newIndexCount;
0090     indexes = static_cast<Value **>(newIndexes);
0091   }
0092   virtual void releaseArrayPageIndex(Value **indexes, ValueInternalArray::PageIndex indexCount) {
0093     if (indexes)
0094       free(indexes);
0095   }
0096 
0097   virtual Value *allocateArrayPage() { return static_cast<Value *>(pagesAllocator_.allocate()); }
0098 
0099   virtual void releaseArrayPage(Value *value) {
0100     if (value)
0101       pagesAllocator_.release(value);
0102   }
0103 
0104 private:
0105   BatchAllocator<ValueInternalArray, 1> arraysAllocator_;
0106   BatchAllocator<Value, ValueInternalArray::itemsPerPage> pagesAllocator_;
0107 };
0108 #endif  // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
0109 
0110 static ValueArrayAllocator *&arrayAllocator() {
0111   static DefaultValueArrayAllocator defaultAllocator;
0112   static ValueArrayAllocator *arrayAllocator = &defaultAllocator;
0113   return arrayAllocator;
0114 }
0115 
0116 static struct DummyArrayAllocatorInitializer {
0117   DummyArrayAllocatorInitializer() {
0118     arrayAllocator();  // ensure arrayAllocator() statics are initialized before main().
0119   }
0120 } dummyArrayAllocatorInitializer;
0121 
0122 // //////////////////////////////////////////////////////////////////
0123 // class ValueInternalArray
0124 // //////////////////////////////////////////////////////////////////
0125 bool ValueInternalArray::equals(const IteratorState &x, const IteratorState &other) {
0126   return x.array_ == other.array_ && x.currentItemIndex_ == other.currentItemIndex_ &&
0127          x.currentPageIndex_ == other.currentPageIndex_;
0128 }
0129 
0130 void ValueInternalArray::increment(IteratorState &it) {
0131   JSON_ASSERT_MESSAGE(
0132       it.array_ && (it.currentPageIndex_ - it.array_->pages_) * itemsPerPage + it.currentItemIndex_ != it.array_->size_,
0133       "ValueInternalArray::increment(): moving iterator beyond end");
0134   ++(it.currentItemIndex_);
0135   if (it.currentItemIndex_ == itemsPerPage) {
0136     it.currentItemIndex_ = 0;
0137     ++(it.currentPageIndex_);
0138   }
0139 }
0140 
0141 void ValueInternalArray::decrement(IteratorState &it) {
0142   JSON_ASSERT_MESSAGE(it.array_ && it.currentPageIndex_ == it.array_->pages_ && it.currentItemIndex_ == 0,
0143                       "ValueInternalArray::decrement(): moving iterator beyond end");
0144   if (it.currentItemIndex_ == 0) {
0145     it.currentItemIndex_ = itemsPerPage - 1;
0146     --(it.currentPageIndex_);
0147   } else {
0148     --(it.currentItemIndex_);
0149   }
0150 }
0151 
0152 Value &ValueInternalArray::unsafeDereference(const IteratorState &it) {
0153   return (*(it.currentPageIndex_))[it.currentItemIndex_];
0154 }
0155 
0156 Value &ValueInternalArray::dereference(const IteratorState &it) {
0157   JSON_ASSERT_MESSAGE(
0158       it.array_ && (it.currentPageIndex_ - it.array_->pages_) * itemsPerPage + it.currentItemIndex_ < it.array_->size_,
0159       "ValueInternalArray::dereference(): dereferencing invalid iterator");
0160   return unsafeDereference(it);
0161 }
0162 
0163 void ValueInternalArray::makeBeginIterator(IteratorState &it) const {
0164   it.array_ = const_cast<ValueInternalArray *>(this);
0165   it.currentItemIndex_ = 0;
0166   it.currentPageIndex_ = pages_;
0167 }
0168 
0169 void ValueInternalArray::makeIterator(IteratorState &it, ArrayIndex index) const {
0170   it.array_ = const_cast<ValueInternalArray *>(this);
0171   it.currentItemIndex_ = index % itemsPerPage;
0172   it.currentPageIndex_ = pages_ + index / itemsPerPage;
0173 }
0174 
0175 void ValueInternalArray::makeEndIterator(IteratorState &it) const { makeIterator(it, size_); }
0176 
0177 ValueInternalArray::ValueInternalArray() : pages_(0), size_(0), pageCount_(0) {}
0178 
0179 ValueInternalArray::ValueInternalArray(const ValueInternalArray &other) : pages_(0), pageCount_(0), size_(other.size_) {
0180   PageIndex minNewPages = other.size_ / itemsPerPage;
0181   arrayAllocator()->reallocateArrayPageIndex(pages_, pageCount_, minNewPages);
0182   JSON_ASSERT_MESSAGE(pageCount_ >= minNewPages, "ValueInternalArray::reserve(): bad reallocation");
0183   IteratorState itOther;
0184   other.makeBeginIterator(itOther);
0185   Value *value;
0186   for (ArrayIndex index = 0; index < size_; ++index, increment(itOther)) {
0187     if (index % itemsPerPage == 0) {
0188       PageIndex pageIndex = index / itemsPerPage;
0189       value = arrayAllocator()->allocateArrayPage();
0190       pages_[pageIndex] = value;
0191     }
0192     new (value) Value(dereference(itOther));
0193   }
0194 }
0195 
0196 ValueInternalArray &ValueInternalArray::operator=(const ValueInternalArray &other) {
0197   ValueInternalArray temp(other);
0198   swap(temp);
0199   return *this;
0200 }
0201 
0202 ValueInternalArray::~ValueInternalArray() {
0203   // destroy all constructed items
0204   IteratorState it;
0205   IteratorState itEnd;
0206   makeBeginIterator(it);
0207   makeEndIterator(itEnd);
0208   for (; !equals(it, itEnd); increment(it)) {
0209     Value *value = &dereference(it);
0210     value->~Value();
0211   }
0212   // release all pages
0213   PageIndex lastPageIndex = size_ / itemsPerPage;
0214   for (PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex)
0215     arrayAllocator()->releaseArrayPage(pages_[pageIndex]);
0216   // release pages index
0217   arrayAllocator()->releaseArrayPageIndex(pages_, pageCount_);
0218 }
0219 
0220 void ValueInternalArray::swap(ValueInternalArray &other) {
0221   Value **tempPages = pages_;
0222   pages_ = other.pages_;
0223   other.pages_ = tempPages;
0224   ArrayIndex tempSize = size_;
0225   size_ = other.size_;
0226   other.size_ = tempSize;
0227   PageIndex tempPageCount = pageCount_;
0228   pageCount_ = other.pageCount_;
0229   other.pageCount_ = tempPageCount;
0230 }
0231 
0232 void ValueInternalArray::clear() {
0233   ValueInternalArray dummy;
0234   swap(dummy);
0235 }
0236 
0237 void ValueInternalArray::resize(ArrayIndex newSize) {
0238   if (newSize == 0)
0239     clear();
0240   else if (newSize < size_) {
0241     IteratorState it;
0242     IteratorState itEnd;
0243     makeIterator(it, newSize);
0244     makeIterator(itEnd, size_);
0245     for (; !equals(it, itEnd); increment(it)) {
0246       Value *value = &dereference(it);
0247       value->~Value();
0248     }
0249     PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage;
0250     PageIndex lastPageIndex = size_ / itemsPerPage;
0251     for (; pageIndex < lastPageIndex; ++pageIndex)
0252       arrayAllocator()->releaseArrayPage(pages_[pageIndex]);
0253     size_ = newSize;
0254   } else if (newSize > size_)
0255     resolveReference(newSize);
0256 }
0257 
0258 void ValueInternalArray::makeIndexValid(ArrayIndex index) {
0259   // Need to enlarge page index ?
0260   if (index >= pageCount_ * itemsPerPage) {
0261     PageIndex minNewPages = (index + 1) / itemsPerPage;
0262     arrayAllocator()->reallocateArrayPageIndex(pages_, pageCount_, minNewPages);
0263     JSON_ASSERT_MESSAGE(pageCount_ >= minNewPages, "ValueInternalArray::reserve(): bad reallocation");
0264   }
0265 
0266   // Need to allocate new pages ?
0267   ArrayIndex nextPageIndex = (size_ % itemsPerPage) != 0 ? size_ - (size_ % itemsPerPage) + itemsPerPage : size_;
0268   if (nextPageIndex <= index) {
0269     PageIndex pageIndex = nextPageIndex / itemsPerPage;
0270     PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1;
0271     for (; pageToAllocate-- > 0; ++pageIndex)
0272       pages_[pageIndex] = arrayAllocator()->allocateArrayPage();
0273   }
0274 
0275   // Initialize all new entries
0276   IteratorState it;
0277   IteratorState itEnd;
0278   makeIterator(it, size_);
0279   size_ = index + 1;
0280   makeIterator(itEnd, size_);
0281   for (; !equals(it, itEnd); increment(it)) {
0282     Value *value = &dereference(it);
0283     new (value) Value();  // Construct a default value using placement new
0284   }
0285 }
0286 
0287 Value &ValueInternalArray::resolveReference(ArrayIndex index) {
0288   if (index >= size_)
0289     makeIndexValid(index);
0290   return pages_[index / itemsPerPage][index % itemsPerPage];
0291 }
0292 
0293 Value *ValueInternalArray::find(ArrayIndex index) const {
0294   if (index >= size_)
0295     return 0;
0296   return &(pages_[index / itemsPerPage][index % itemsPerPage]);
0297 }
0298 
0299 ValueInternalArray::ArrayIndex ValueInternalArray::size() const { return size_; }
0300 
0301 int ValueInternalArray::distance(const IteratorState &x, const IteratorState &y) { return indexOf(y) - indexOf(x); }
0302 
0303 ValueInternalArray::ArrayIndex ValueInternalArray::indexOf(const IteratorState &iterator) {
0304   if (!iterator.array_)
0305     return ArrayIndex(-1);
0306   return ArrayIndex((iterator.currentPageIndex_ - iterator.array_->pages_) * itemsPerPage + iterator.currentItemIndex_);
0307 }
0308 
0309 int ValueInternalArray::compare(const ValueInternalArray &other) const {
0310   int sizeDiff(size_ - other.size_);
0311   if (sizeDiff != 0)
0312     return sizeDiff;
0313 
0314   for (ArrayIndex index = 0; index < size_; ++index) {
0315     int diff = pages_[index / itemsPerPage][index % itemsPerPage].compare(
0316         other.pages_[index / itemsPerPage][index % itemsPerPage]);
0317     if (diff != 0)
0318       return diff;
0319   }
0320   return 0;
0321 }