src/lib_json/json_internalarray.inl

// 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