• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
8namespace Json {
9
10// //////////////////////////////////////////////////////////////////
11// //////////////////////////////////////////////////////////////////
12// //////////////////////////////////////////////////////////////////
13// class ValueInternalArray
14// //////////////////////////////////////////////////////////////////
15// //////////////////////////////////////////////////////////////////
16// //////////////////////////////////////////////////////////////////
17
18ValueArrayAllocator::~ValueArrayAllocator() {}
19
20// //////////////////////////////////////////////////////////////////
21// class DefaultValueArrayAllocator
22// //////////////////////////////////////////////////////////////////
23#ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
24class DefaultValueArrayAllocator : public ValueArrayAllocator {
25public: // 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)
67class DefaultValueArrayAllocator : public ValueArrayAllocator {
68public: // 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
117private:
118  BatchAllocator<ValueInternalArray, 1> arraysAllocator_;
119  BatchAllocator<Value, ValueInternalArray::itemsPerPage> pagesAllocator_;
120};
121#endif // #ifdef JSON_USE_SIMPLE_INTERNAL_ALLOCATOR
122
123static ValueArrayAllocator*& arrayAllocator() {
124  static DefaultValueArrayAllocator defaultAllocator;
125  static ValueArrayAllocator* arrayAllocator = &defaultAllocator;
126  return arrayAllocator;
127}
128
129static struct DummyArrayAllocatorInitializer {
130  DummyArrayAllocatorInitializer() {
131    arrayAllocator(); // ensure arrayAllocator() statics are initialized before
132                      // main().
133  }
134} dummyArrayAllocatorInitializer;
135
136// //////////////////////////////////////////////////////////////////
137// class ValueInternalArray
138// //////////////////////////////////////////////////////////////////
139bool 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
146void 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
159void 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
172Value& ValueInternalArray::unsafeDereference(const IteratorState& it) {
173  return (*(it.currentPageIndex_))[it.currentItemIndex_];
174}
175
176Value& 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
185void ValueInternalArray::makeBeginIterator(IteratorState& it) const {
186  it.array_ = const_cast<ValueInternalArray*>(this);
187  it.currentItemIndex_ = 0;
188  it.currentPageIndex_ = pages_;
189}
190
191void 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
198void ValueInternalArray::makeEndIterator(IteratorState& it) const {
199  makeIterator(it, size_);
200}
201
202ValueInternalArray::ValueInternalArray() : pages_(0), size_(0), pageCount_(0) {}
203
204ValueInternalArray::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
223ValueInternalArray& ValueInternalArray::operator=(ValueInternalArray other) {
224  swap(other);
225  return *this;
226}
227
228ValueInternalArray::~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
246void 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
258void ValueInternalArray::clear() {
259  ValueInternalArray dummy;
260  swap(dummy);
261}
262
263void 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
284void 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
316Value& ValueInternalArray::resolveReference(ArrayIndex index) {
317  if (index >= size_)
318    makeIndexValid(index);
319  return pages_[index / itemsPerPage][index % itemsPerPage];
320}
321
322Value* ValueInternalArray::find(ArrayIndex index) const {
323  if (index >= size_)
324    return 0;
325  return &(pages_[index / itemsPerPage][index % itemsPerPage]);
326}
327
328ValueInternalArray::ArrayIndex ValueInternalArray::size() const {
329  return size_;
330}
331
332int ValueInternalArray::distance(const IteratorState& x,
333                                 const IteratorState& y) {
334  return indexOf(y) - indexOf(x);
335}
336
337ValueInternalArray::ArrayIndex
338ValueInternalArray::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
346int 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