| // Copyright 2007-2010 Baptiste Lepilleur |
| // Distributed under MIT license, or public domain if desired and |
| // recognized in your jurisdiction. |
| // See file LICENSE for detail or copy at http://jsoncpp.sourceforge.net/LICENSE |
| |
| // included by json_value.cpp |
| |
| namespace Json { |
| |
| // ////////////////////////////////////////////////////////////////// |
| // ////////////////////////////////////////////////////////////////// |
| // ////////////////////////////////////////////////////////////////// |
| // class ValueInternalArray |
| // ////////////////////////////////////////////////////////////////// |
| // ////////////////////////////////////////////////////////////////// |
| // ////////////////////////////////////////////////////////////////// |
| |
| ValueArrayAllocator::~ValueArrayAllocator() {} |
| |
| // ////////////////////////////////////////////////////////////////// |
| // class DefaultValueArrayAllocator |
| // ////////////////////////////////////////////////////////////////// |
| #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR |
| class DefaultValueArrayAllocator : public ValueArrayAllocator { |
| public: // overridden from ValueArrayAllocator |
| virtual ~DefaultValueArrayAllocator() {} |
| |
| virtual ValueInternalArray* newArray() { return new ValueInternalArray(); } |
| |
| virtual ValueInternalArray* newArrayCopy(const ValueInternalArray& other) { |
| return new ValueInternalArray(other); |
| } |
| |
| virtual void destructArray(ValueInternalArray* array) { delete array; } |
| |
| virtual void |
| reallocateArrayPageIndex(Value**& indexes, |
| ValueInternalArray::PageIndex& indexCount, |
| ValueInternalArray::PageIndex minNewIndexCount) { |
| ValueInternalArray::PageIndex newIndexCount = (indexCount * 3) / 2 + 1; |
| if (minNewIndexCount > newIndexCount) |
| newIndexCount = minNewIndexCount; |
| void* newIndexes = realloc(indexes, sizeof(Value*) * newIndexCount); |
| JSON_ASSERT_MESSAGE(newIndexes, "Couldn't realloc."); |
| indexCount = newIndexCount; |
| indexes = static_cast<Value**>(newIndexes); |
| } |
| virtual void releaseArrayPageIndex(Value** indexes, |
| ValueInternalArray::PageIndex indexCount) { |
| if (indexes) |
| free(indexes); |
| } |
| |
| virtual Value* allocateArrayPage() { |
| return static_cast<Value*>( |
| malloc(sizeof(Value) * ValueInternalArray::itemsPerPage)); |
| } |
| |
| virtual void releaseArrayPage(Value* value) { |
| if (value) |
| free(value); |
| } |
| }; |
| |
| #else // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR |
| /// @todo make this thread-safe (lock when accessign batch allocator) |
| class DefaultValueArrayAllocator : public ValueArrayAllocator { |
| public: // overridden from ValueArrayAllocator |
| virtual ~DefaultValueArrayAllocator() {} |
| |
| virtual ValueInternalArray* newArray() { |
| ValueInternalArray* array = arraysAllocator_.allocate(); |
| new (array) ValueInternalArray(); // placement new |
| return array; |
| } |
| |
| virtual ValueInternalArray* newArrayCopy(const ValueInternalArray& other) { |
| ValueInternalArray* array = arraysAllocator_.allocate(); |
| new (array) ValueInternalArray(other); // placement new |
| return array; |
| } |
| |
| virtual void destructArray(ValueInternalArray* array) { |
| if (array) { |
| array->~ValueInternalArray(); |
| arraysAllocator_.release(array); |
| } |
| } |
| |
| virtual void |
| reallocateArrayPageIndex(Value**& indexes, |
| ValueInternalArray::PageIndex& indexCount, |
| ValueInternalArray::PageIndex minNewIndexCount) { |
| ValueInternalArray::PageIndex newIndexCount = (indexCount * 3) / 2 + 1; |
| if (minNewIndexCount > newIndexCount) |
| newIndexCount = minNewIndexCount; |
| void* newIndexes = realloc(indexes, sizeof(Value*) * newIndexCount); |
| JSON_ASSERT_MESSAGE(newIndexes, "Couldn't realloc."); |
| indexCount = newIndexCount; |
| indexes = static_cast<Value**>(newIndexes); |
| } |
| virtual void releaseArrayPageIndex(Value** indexes, |
| ValueInternalArray::PageIndex indexCount) { |
| if (indexes) |
| free(indexes); |
| } |
| |
| virtual Value* allocateArrayPage() { |
| return static_cast<Value*>(pagesAllocator_.allocate()); |
| } |
| |
| virtual void releaseArrayPage(Value* value) { |
| if (value) |
| pagesAllocator_.release(value); |
| } |
| |
| private: |
| BatchAllocator<ValueInternalArray, 1> arraysAllocator_; |
| BatchAllocator<Value, ValueInternalArray::itemsPerPage> pagesAllocator_; |
| }; |
| #endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR |
| |
| static ValueArrayAllocator*& arrayAllocator() { |
| static DefaultValueArrayAllocator defaultAllocator; |
| static ValueArrayAllocator* arrayAllocator = &defaultAllocator; |
| return arrayAllocator; |
| } |
| |
| static struct DummyArrayAllocatorInitializer { |
| DummyArrayAllocatorInitializer() { |
| arrayAllocator(); // ensure arrayAllocator() statics are initialized before |
| // main(). |
| } |
| } dummyArrayAllocatorInitializer; |
| |
| // ////////////////////////////////////////////////////////////////// |
| // class ValueInternalArray |
| // ////////////////////////////////////////////////////////////////// |
| bool ValueInternalArray::equals(const IteratorState& x, |
| const IteratorState& other) { |
| return x.array_ == other.array_ && |
| x.currentItemIndex_ == other.currentItemIndex_ && |
| x.currentPageIndex_ == other.currentPageIndex_; |
| } |
| |
| void ValueInternalArray::increment(IteratorState& it) { |
| JSON_ASSERT_MESSAGE( |
| it.array_ && (it.currentPageIndex_ - it.array_->pages_) * itemsPerPage + |
| it.currentItemIndex_ != |
| it.array_->size_, |
| "ValueInternalArray::increment(): moving iterator beyond end"); |
| ++(it.currentItemIndex_); |
| if (it.currentItemIndex_ == itemsPerPage) { |
| it.currentItemIndex_ = 0; |
| ++(it.currentPageIndex_); |
| } |
| } |
| |
| void ValueInternalArray::decrement(IteratorState& it) { |
| JSON_ASSERT_MESSAGE( |
| it.array_ && it.currentPageIndex_ == it.array_->pages_ && |
| it.currentItemIndex_ == 0, |
| "ValueInternalArray::decrement(): moving iterator beyond end"); |
| if (it.currentItemIndex_ == 0) { |
| it.currentItemIndex_ = itemsPerPage - 1; |
| --(it.currentPageIndex_); |
| } else { |
| --(it.currentItemIndex_); |
| } |
| } |
| |
| Value& ValueInternalArray::unsafeDereference(const IteratorState& it) { |
| return (*(it.currentPageIndex_))[it.currentItemIndex_]; |
| } |
| |
| Value& ValueInternalArray::dereference(const IteratorState& it) { |
| JSON_ASSERT_MESSAGE( |
| it.array_ && (it.currentPageIndex_ - it.array_->pages_) * itemsPerPage + |
| it.currentItemIndex_ < |
| it.array_->size_, |
| "ValueInternalArray::dereference(): dereferencing invalid iterator"); |
| return unsafeDereference(it); |
| } |
| |
| void ValueInternalArray::makeBeginIterator(IteratorState& it) const { |
| it.array_ = const_cast<ValueInternalArray*>(this); |
| it.currentItemIndex_ = 0; |
| it.currentPageIndex_ = pages_; |
| } |
| |
| void ValueInternalArray::makeIterator(IteratorState& it, |
| ArrayIndex index) const { |
| it.array_ = const_cast<ValueInternalArray*>(this); |
| it.currentItemIndex_ = index % itemsPerPage; |
| it.currentPageIndex_ = pages_ + index / itemsPerPage; |
| } |
| |
| void ValueInternalArray::makeEndIterator(IteratorState& it) const { |
| makeIterator(it, size_); |
| } |
| |
| ValueInternalArray::ValueInternalArray() : pages_(0), size_(0), pageCount_(0) {} |
| |
| ValueInternalArray::ValueInternalArray(const ValueInternalArray& other) |
| : pages_(0), size_(other.size_), pageCount_(0) { |
| PageIndex minNewPages = other.size_ / itemsPerPage; |
| arrayAllocator()->reallocateArrayPageIndex(pages_, pageCount_, minNewPages); |
| JSON_ASSERT_MESSAGE(pageCount_ >= minNewPages, |
| "ValueInternalArray::reserve(): bad reallocation"); |
| IteratorState itOther; |
| other.makeBeginIterator(itOther); |
| Value* value; |
| for (ArrayIndex index = 0; index < size_; ++index, increment(itOther)) { |
| if (index % itemsPerPage == 0) { |
| PageIndex pageIndex = index / itemsPerPage; |
| value = arrayAllocator()->allocateArrayPage(); |
| pages_[pageIndex] = value; |
| } |
| new (value) Value(dereference(itOther)); |
| } |
| } |
| |
| ValueInternalArray& ValueInternalArray::operator=(ValueInternalArray other) { |
| swap(other); |
| return *this; |
| } |
| |
| ValueInternalArray::~ValueInternalArray() { |
| // destroy all constructed items |
| IteratorState it; |
| IteratorState itEnd; |
| makeBeginIterator(it); |
| makeEndIterator(itEnd); |
| for (; !equals(it, itEnd); increment(it)) { |
| Value* value = &dereference(it); |
| value->~Value(); |
| } |
| // release all pages |
| PageIndex lastPageIndex = size_ / itemsPerPage; |
| for (PageIndex pageIndex = 0; pageIndex < lastPageIndex; ++pageIndex) |
| arrayAllocator()->releaseArrayPage(pages_[pageIndex]); |
| // release pages index |
| arrayAllocator()->releaseArrayPageIndex(pages_, pageCount_); |
| } |
| |
| void ValueInternalArray::swap(ValueInternalArray& other) { |
| Value** tempPages = pages_; |
| pages_ = other.pages_; |
| other.pages_ = tempPages; |
| ArrayIndex tempSize = size_; |
| size_ = other.size_; |
| other.size_ = tempSize; |
| PageIndex tempPageCount = pageCount_; |
| pageCount_ = other.pageCount_; |
| other.pageCount_ = tempPageCount; |
| } |
| |
| void ValueInternalArray::clear() { |
| ValueInternalArray dummy; |
| swap(dummy); |
| } |
| |
| void ValueInternalArray::resize(ArrayIndex newSize) { |
| if (newSize == 0) |
| clear(); |
| else if (newSize < size_) { |
| IteratorState it; |
| IteratorState itEnd; |
| makeIterator(it, newSize); |
| makeIterator(itEnd, size_); |
| for (; !equals(it, itEnd); increment(it)) { |
| Value* value = &dereference(it); |
| value->~Value(); |
| } |
| PageIndex pageIndex = (newSize + itemsPerPage - 1) / itemsPerPage; |
| PageIndex lastPageIndex = size_ / itemsPerPage; |
| for (; pageIndex < lastPageIndex; ++pageIndex) |
| arrayAllocator()->releaseArrayPage(pages_[pageIndex]); |
| size_ = newSize; |
| } else if (newSize > size_) |
| resolveReference(newSize); |
| } |
| |
| void ValueInternalArray::makeIndexValid(ArrayIndex index) { |
| // Need to enlarge page index ? |
| if (index >= pageCount_ * itemsPerPage) { |
| PageIndex minNewPages = (index + 1) / itemsPerPage; |
| arrayAllocator()->reallocateArrayPageIndex(pages_, pageCount_, minNewPages); |
| JSON_ASSERT_MESSAGE(pageCount_ >= minNewPages, |
| "ValueInternalArray::reserve(): bad reallocation"); |
| } |
| |
| // Need to allocate new pages ? |
| ArrayIndex nextPageIndex = (size_ % itemsPerPage) != 0 |
| ? size_ - (size_ % itemsPerPage) + itemsPerPage |
| : size_; |
| if (nextPageIndex <= index) { |
| PageIndex pageIndex = nextPageIndex / itemsPerPage; |
| PageIndex pageToAllocate = (index - nextPageIndex) / itemsPerPage + 1; |
| for (; pageToAllocate-- > 0; ++pageIndex) |
| pages_[pageIndex] = arrayAllocator()->allocateArrayPage(); |
| } |
| |
| // Initialize all new entries |
| IteratorState it; |
| IteratorState itEnd; |
| makeIterator(it, size_); |
| size_ = index + 1; |
| makeIterator(itEnd, size_); |
| for (; !equals(it, itEnd); increment(it)) { |
| Value* value = &dereference(it); |
| new (value) Value(); // Construct a default value using placement new |
| } |
| } |
| |
| Value& ValueInternalArray::resolveReference(ArrayIndex index) { |
| if (index >= size_) |
| makeIndexValid(index); |
| return pages_[index / itemsPerPage][index % itemsPerPage]; |
| } |
| |
| Value* ValueInternalArray::find(ArrayIndex index) const { |
| if (index >= size_) |
| return 0; |
| return &(pages_[index / itemsPerPage][index % itemsPerPage]); |
| } |
| |
| ValueInternalArray::ArrayIndex ValueInternalArray::size() const { |
| return size_; |
| } |
| |
| int ValueInternalArray::distance(const IteratorState& x, |
| const IteratorState& y) { |
| return indexOf(y) - indexOf(x); |
| } |
| |
| ValueInternalArray::ArrayIndex |
| ValueInternalArray::indexOf(const IteratorState& iterator) { |
| if (!iterator.array_) |
| return ArrayIndex(-1); |
| return ArrayIndex((iterator.currentPageIndex_ - iterator.array_->pages_) * |
| itemsPerPage + |
| iterator.currentItemIndex_); |
| } |
| |
| int ValueInternalArray::compare(const ValueInternalArray& other) const { |
| int sizeDiff(size_ - other.size_); |
| if (sizeDiff != 0) |
| return sizeDiff; |
| |
| for (ArrayIndex index = 0; index < size_; ++index) { |
| int diff = pages_[index / itemsPerPage][index % itemsPerPage].compare( |
| other.pages_[index / itemsPerPage][index % itemsPerPage]); |
| if (diff != 0) |
| return diff; |
| } |
| return 0; |
| } |
| |
| } // namespace Json |