Squashed 'third_party/ctemplate/' content from commit 6742f62
Change-Id: I828e4e4c906f13ba19944d78a8a78652b62949af
git-subtree-dir: third_party/ctemplate
git-subtree-split: 6742f6233db12f545e90baa8f34f5c29c4eb396a
diff --git a/src/base/small_map.h b/src/base/small_map.h
new file mode 100644
index 0000000..3e17d71
--- /dev/null
+++ b/src/base/small_map.h
@@ -0,0 +1,569 @@
+// Copyright (c) 2006, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+// ---
+//
+// Author: kenton@google.com (Kenton Varda)
+//
+// small_map is a drop-in replacement for map or hash_map. It uses a fixed
+// array to store a certain number of elements, then reverts to using a
+// map or hash_map when it runs out of space. For maps that are typically
+// small, this can be considerably faster than using something like hash_map
+// directly, as hash_map is optimized for large data sets. Of course, in
+// order for this to be a significant win, you have to have a situation where
+// you are using lots and lots of these small maps. One such situation is
+// MessageSet: A set of search results may contain thousands of MessageSets,
+// each containing only a couple items.
+//
+// TODO(kenton): This is very minimal, and was originally written for a
+// very specific use (MessageSet). It only implements a few core methods
+// of the STL associative container interface, though you are welcome to
+// extend it.
+
+#ifndef UTIL_GTL_SMALL_MAP_H_
+#define UTIL_GTL_SMALL_MAP_H_
+
+#include <config.h>
+#include <assert.h>
+#include <utility> // for make_pair()
+#include "base/manual_constructor.h"
+
+namespace ctemplate {
+
+template <bool> struct CompileAssert { };
+#define COMPILE_ASSERT(expr, msg) \
+ typedef CompileAssert<(bool(expr))> msg[bool(expr) ? 1 : -1]
+
+// An STL-like associative container which starts out backed by a simple
+// array but switches to some other container type if it grows beyond a
+// fixed size.
+//
+// NormalMap: The map type to fall back to. This also defines the key
+// and value types for the small_map.
+// kArraySize: The size of the initial array of results. Once the map
+// grows beyond this size, the map type will be used instead.
+// EqualKey: A functor which tests two keys for equality. If the wrapped
+// map type has a "key_equal" member (hash_map does), then that
+// will be used by default. Otherwise you must specify this
+// manually.
+// MapInit: A functor that takes a ManualConstructor<NormalMap>* and uses it to
+// initialize the map. This functor will be called at most once per
+// small_map, when the map exceeds the threshold of kArraySize and we
+// are about to copy values from the array to the map. The functor
+// *must* call one of the Init() methods provided by
+// ManualConstructor, since after it runs we assume that the NormalMap
+// has been initialized.
+//
+// example:
+// small_map<hash_map<string, int> > days;
+// days["sunday" ] = 0;
+// days["monday" ] = 1;
+// days["tuesday" ] = 2;
+// days["wednesday"] = 3;
+// days["thursday" ] = 4;
+// days["friday" ] = 5;
+// days["saturday" ] = 6;
+//
+// You should assume that small_map might invalidate all the iterators
+// on any call to erase(), insert() and operator[].
+template <typename NormalMap>
+class small_map_default_init {
+ public:
+ void operator ()(ManualConstructor<NormalMap>* map) const {
+ map->Init();
+ }
+};
+
+template <typename NormalMap,
+ int kArraySize = 4,
+ typename EqualKey = typename NormalMap::key_equal,
+ typename MapInit = small_map_default_init<NormalMap> >
+class small_map {
+ // We cannot rely on the compiler to reject array of size 0. In
+ // particular, gcc 2.95.3 does it but later versions allow 0-length
+ // arrays. Therefore, we explicitly reject non-positive kArraySize
+ // here.
+ COMPILE_ASSERT(kArraySize > 0, default_initial_size_should_be_positive);
+
+ public:
+ typedef typename NormalMap::key_type key_type;
+ typedef typename NormalMap::mapped_type data_type;
+ typedef typename NormalMap::mapped_type mapped_type;
+ typedef typename NormalMap::value_type value_type;
+ typedef EqualKey key_equal;
+
+ small_map() : size_(0), functor_(MapInit()) {}
+
+ explicit small_map(const MapInit& functor) : size_(0), functor_(functor) {}
+
+ // Allow copy-constructor and assignment, since STL allows them too.
+ small_map(const small_map& src) {
+ // size_ and functor_ are initted in InitFrom()
+ InitFrom(src);
+ }
+ void operator=(const small_map& src) {
+ if (&src == this) return;
+
+ // This is not optimal. If src and dest are both using the small
+ // array, we could skip the teardown and reconstruct. One problem
+ // to be resolved is that the value_type itself is pair<const K,
+ // V>, and const K is not assignable.
+ Destroy();
+ InitFrom(src);
+ }
+ ~small_map() {
+ Destroy();
+ }
+
+ class const_iterator;
+
+ class iterator {
+ public:
+ typedef typename NormalMap::iterator::iterator_category iterator_category;
+ typedef typename NormalMap::iterator::value_type value_type;
+ typedef typename NormalMap::iterator::difference_type difference_type;
+ typedef typename NormalMap::iterator::pointer pointer;
+ typedef typename NormalMap::iterator::reference reference;
+
+ inline iterator(): array_iter_(NULL) {}
+
+ inline iterator& operator++() {
+ if (array_iter_ != NULL) {
+ ++array_iter_;
+ } else {
+ ++hash_iter_;
+ }
+ return *this;
+ }
+ inline iterator operator++(int) {
+ iterator result(*this);
+ ++(*this);
+ return result;
+ }
+ inline iterator& operator--() {
+ if (array_iter_ != NULL) {
+ --array_iter_;
+ } else {
+ --hash_iter_;
+ }
+ return *this;
+ }
+ inline iterator operator--(int) {
+ iterator result(*this);
+ --(*this);
+ return result;
+ }
+ inline value_type* operator->() const {
+ if (array_iter_ != NULL) {
+ return array_iter_->get();
+ } else {
+ return hash_iter_.operator->();
+ }
+ }
+
+ inline value_type& operator*() const {
+ if (array_iter_ != NULL) {
+ return *array_iter_->get();
+ } else {
+ return *hash_iter_;
+ }
+ }
+
+ inline bool operator==(const iterator& other) const {
+ if (array_iter_ != NULL) {
+ return array_iter_ == other.array_iter_;
+ } else {
+ return other.array_iter_ == NULL && hash_iter_ == other.hash_iter_;
+ }
+ }
+
+ inline bool operator!=(const iterator& other) const {
+ return !(*this == other);
+ }
+
+ bool operator==(const const_iterator& other) const;
+ bool operator!=(const const_iterator& other) const;
+
+ private:
+ friend class small_map;
+ friend class const_iterator;
+ inline explicit iterator(ManualConstructor<value_type>* init)
+ : array_iter_(init) {}
+ inline explicit iterator(const typename NormalMap::iterator& init)
+ : array_iter_(NULL), hash_iter_(init) {}
+
+ ManualConstructor<value_type>* array_iter_;
+ typename NormalMap::iterator hash_iter_;
+ };
+
+ class const_iterator {
+ public:
+ typedef typename NormalMap::const_iterator::iterator_category iterator_category;
+ typedef typename NormalMap::const_iterator::value_type value_type;
+ typedef typename NormalMap::const_iterator::difference_type difference_type;
+ typedef typename NormalMap::const_iterator::pointer pointer;
+ typedef typename NormalMap::const_iterator::reference reference;
+
+ inline const_iterator(): array_iter_(NULL) {}
+ inline const_iterator(const iterator& other)
+ : array_iter_(other.array_iter_), hash_iter_(other.hash_iter_) {}
+
+ inline const_iterator& operator++() {
+ if (array_iter_ != NULL) {
+ ++array_iter_;
+ } else {
+ ++hash_iter_;
+ }
+ return *this;
+ }
+ inline const_iterator operator++(int) {
+ const_iterator result(*this);
+ ++(*this);
+ return result;
+ }
+
+ inline const_iterator& operator--() {
+ if (array_iter_ != NULL) {
+ --array_iter_;
+ } else {
+ --hash_iter_;
+ }
+ return *this;
+ }
+ inline const_iterator operator--(int) {
+ const_iterator result(*this);
+ --(*this);
+ return result;
+ }
+
+ inline const value_type* operator->() const {
+ if (array_iter_ != NULL) {
+ return array_iter_->get();
+ } else {
+ return hash_iter_.operator->();
+ }
+ }
+
+ inline const value_type& operator*() const {
+ if (array_iter_ != NULL) {
+ return *array_iter_->get();
+ } else {
+ return *hash_iter_;
+ }
+ }
+
+ inline bool operator==(const const_iterator& other) const {
+ if (array_iter_ != NULL) {
+ return array_iter_ == other.array_iter_;
+ } else {
+ return other.array_iter_ == NULL && hash_iter_ == other.hash_iter_;
+ }
+ }
+
+ inline bool operator!=(const const_iterator& other) const {
+ return !(*this == other);
+ }
+
+ private:
+ friend class small_map;
+ inline explicit const_iterator(
+ const ManualConstructor<value_type>* init)
+ : array_iter_(init) {}
+ inline explicit const_iterator(
+ const typename NormalMap::const_iterator& init)
+ : array_iter_(NULL), hash_iter_(init) {}
+
+ const ManualConstructor<value_type>* array_iter_;
+ typename NormalMap::const_iterator hash_iter_;
+ };
+
+ iterator find(const key_type& key) {
+ key_equal compare;
+ if (size_ >= 0) {
+ for (int i = 0; i < size_; i++) {
+ if (compare(array_[i]->first, key)) {
+ return iterator(array_ + i);
+ }
+ }
+ return iterator(array_ + size_);
+ } else {
+ return iterator(map()->find(key));
+ }
+ }
+
+ const_iterator find(const key_type& key) const {
+ key_equal compare;
+ if (size_ >= 0) {
+ for (int i = 0; i < size_; i++) {
+ if (compare(array_[i]->first, key)) {
+ return const_iterator(array_ + i);
+ }
+ }
+ return const_iterator(array_ + size_);
+ } else {
+ return const_iterator(map()->find(key));
+ }
+ }
+
+ // Invalidates iterators.
+ data_type& operator[](const key_type& key) {
+ key_equal compare;
+
+ if (size_ >= 0) {
+ // operator[] searches backwards, favoring recently-added
+ // elements.
+ for (int i = size_-1; i >= 0; --i) {
+ if (compare(array_[i]->first, key)) {
+ return array_[i]->second;
+ }
+ }
+ if (size_ == kArraySize) {
+ ConvertToRealMap();
+ return (*map_)[key];
+ } else {
+ array_[size_].Init(key, data_type());
+ return array_[size_++]->second;
+ }
+ } else {
+ return (*map_)[key];
+ }
+ }
+
+ // Invalidates iterators.
+ std::pair<iterator, bool> insert(const value_type& x) {
+ key_equal compare;
+
+ if (size_ >= 0) {
+ for (int i = 0; i < size_; i++) {
+ if (compare(array_[i]->first, x.first)) {
+ return std::make_pair(iterator(array_ + i), false);
+ }
+ }
+ if (size_ == kArraySize) {
+ ConvertToRealMap(); // Invalidates all iterators!
+ std::pair<typename NormalMap::iterator, bool> ret = map_->insert(x);
+ return std::make_pair(iterator(ret.first), ret.second);
+ } else {
+ array_[size_].Init(x);
+ return std::make_pair(iterator(array_ + size_++), true);
+ }
+ } else {
+ std::pair<typename NormalMap::iterator, bool> ret = map_->insert(x);
+ return std::make_pair(iterator(ret.first), ret.second);
+ }
+ }
+
+ // Invalidates iterators.
+ template <class InputIterator>
+ void insert(InputIterator f, InputIterator l) {
+ while (f != l) {
+ insert(*f);
+ ++f;
+ }
+ }
+
+ iterator begin() {
+ if (size_ >= 0) {
+ return iterator(array_);
+ } else {
+ return iterator(map_->begin());
+ }
+ }
+ const_iterator begin() const {
+ if (size_ >= 0) {
+ return const_iterator(array_);
+ } else {
+ return const_iterator(map_->begin());
+ }
+ }
+
+ iterator end() {
+ if (size_ >= 0) {
+ return iterator(array_ + size_);
+ } else {
+ return iterator(map_->end());
+ }
+ }
+ const_iterator end() const {
+ if (size_ >= 0) {
+ return const_iterator(array_ + size_);
+ } else {
+ return const_iterator(map_->end());
+ }
+ }
+
+ void clear() {
+ if (size_ >= 0) {
+ for (int i = 0; i < size_; i++) {
+ array_[i].Destroy();
+ }
+ } else {
+ map_.Destroy();
+ }
+ size_ = 0;
+ }
+
+ // Invalidates iterators.
+ void erase(const iterator& position) {
+ if (size_ >= 0) {
+ int i = position.array_iter_ - array_;
+ array_[i].Destroy();
+ --size_;
+ if (i != size_) {
+ array_[i].Init(*array_[size_]);
+ array_[size_].Destroy();
+ }
+ } else {
+ map_->erase(position.hash_iter_);
+ }
+ }
+
+ int erase(const key_type& key) {
+ iterator iter = find(key);
+ if (iter == end()) return 0;
+ erase(iter);
+ return 1;
+ }
+
+ int count(const key_type& key) const {
+ return (find(key) == end()) ? 0 : 1;
+ }
+
+ int size() const {
+ if (size_ >= 0) {
+ return size_;
+ } else {
+ return map_->size();
+ }
+ }
+
+ bool empty() const {
+ if (size_ >= 0) {
+ return (size_ == 0);
+ } else {
+ return map_->empty();
+ }
+ }
+
+ // Returns true if we have fallen back to using the underlying map
+ // representation.
+ bool using_full_map() const {
+ return size_ < 0;
+ }
+
+ inline NormalMap* map() {
+ assert(using_full_map());
+ return map_.get();
+ }
+ inline const NormalMap* map() const {
+ assert(using_full_map());
+ return map_.get();
+ }
+
+ private:
+ int size_; // negative = using hash_map
+
+ MapInit functor_;
+
+ // We want to call constructors and destructors manually, but we don't
+ // want to allocate and deallocate the memory used for them separately.
+ // So, we use this crazy ManualConstructor class.
+ //
+ // Since array_ and map_ are mutually exclusive, we'll put them in a
+ // union, too. We add in a dummy_ value which quiets MSVC (both
+ // 7.1 and 8.0) from otherwise giving an erroneous "union member has
+ // copy constructor" error message (C2621). This dummy member has
+ // to come before array_ to quiet the compiler. Shrug.
+ union {
+ ManualConstructor<value_type> dummy_;
+ ManualConstructor<value_type> array_[kArraySize];
+ ManualConstructor<NormalMap> map_;
+ };
+
+ void ConvertToRealMap() {
+ // Move the current elements into a temporary array.
+ ManualConstructor<value_type> temp_array[kArraySize];
+
+ for (int i = 0; i < kArraySize; i++) {
+ temp_array[i].Init(*array_[i]);
+ array_[i].Destroy();
+ }
+
+ // Initialize the map.
+ size_ = -1;
+ functor_(&map_);
+
+ // Insert elements into it.
+ for (int i = 0; i < kArraySize; i++) {
+ map_->insert(*temp_array[i]);
+ temp_array[i].Destroy();
+ }
+ }
+
+ // Helpers for constructors and destructors.
+ void InitFrom(const small_map& src) {
+ functor_ = src.functor_;
+ size_ = src.size_;
+ if (src.size_ >= 0) {
+ for (int i = 0; i < size_; i++) {
+ array_[i].Init(*src.array_[i]);
+ }
+ } else {
+ functor_(&map_);
+ (*map_.get()) = (*src.map_.get());
+ }
+ }
+ void Destroy() {
+ if (size_ >= 0) {
+ for (int i = 0; i < size_; i++) {
+ array_[i].Destroy();
+ }
+ } else {
+ map_.Destroy();
+ }
+ }
+};
+
+template <typename NormalMap, int kArraySize, typename EqualKey,
+ typename Functor>
+inline bool small_map<NormalMap, kArraySize, EqualKey,
+ Functor>::iterator::operator==(
+ const const_iterator& other) const {
+ return other == *this;
+}
+template <typename NormalMap, int kArraySize, typename EqualKey,
+ typename Functor>
+inline bool small_map<NormalMap, kArraySize, EqualKey,
+ Functor>::iterator::operator!=(
+ const const_iterator& other) const {
+ return other != *this;
+}
+
+}
+
+#endif // UTIL_GTL_SMALL_MAP_H_