+
+// A simple chunked vector class--this is a subset of std::vector
+// which stores memory in chunks. We don't provide iterators, because
+// we don't need them.
+
+template<typename Element>
+class Chunked_vector
+{
+ public:
+ Chunked_vector()
+ : chunks_(), size_(0)
+ { }
+
+ // Clear the elements.
+ void
+ clear()
+ {
+ this->chunks_.clear();
+ this->size_ = 0;
+ }
+
+ // Reserve elements.
+ void
+ reserve(unsigned int n)
+ {
+ if (n > this->chunks_.size() * chunk_size)
+ {
+ this->chunks_.resize((n + chunk_size - 1) / chunk_size);
+ // We need to call reserve() of all chunks since changing
+ // this->chunks_ casues Element_vectors to be copied. The
+ // reserved capacity of an Element_vector may be lost in copying.
+ for (size_t i = 0; i < this->chunks_.size(); ++i)
+ this->chunks_[i].reserve(chunk_size);
+ }
+ }
+
+ // Get the number of elements.
+ size_t
+ size() const
+ { return this->size_; }
+
+ // Push a new element on the back of the vector.
+ void
+ push_back(const Element& element)
+ {
+ size_t chunk_index = this->size_ / chunk_size;
+ if (chunk_index >= this->chunks_.size())
+ {
+ this->chunks_.push_back(Element_vector());
+ this->chunks_.back().reserve(chunk_size);
+ gold_assert(chunk_index < this->chunks_.size());
+ }
+ this->chunks_[chunk_index].push_back(element);
+ this->size_++;
+ }
+
+ // Return a reference to an entry in the vector.
+ Element&
+ operator[](size_t i)
+ { return this->chunks_[i / chunk_size][i % chunk_size]; }
+
+ const Element&
+ operator[](size_t i) const
+ { return this->chunks_[i / chunk_size][i % chunk_size]; }
+
+ private:
+ static const unsigned int chunk_size = 8192;
+
+ typedef std::vector<Element> Element_vector;
+ typedef std::vector<Element_vector> Chunk_vector;
+
+ Chunk_vector chunks_;
+ size_t size_;
+};
+
+