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/arena-inl.h b/src/base/arena-inl.h
new file mode 100644
index 0000000..d4aee74
--- /dev/null
+++ b/src/base/arena-inl.h
@@ -0,0 +1,351 @@
+// Copyright (c) 2000, 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.
+// ---
+//
+// Reorganized by Craig Silverstein
+//
+// In this file we define the arena template code. This includes the
+// ArenaAllocator, which is meant only to be used with STL, and also
+// the Gladiator (which needs to know how to new and delete various
+// types of objects).
+//
+// If you're only using the MALLOC-LIKE functionality of the arena,
+// you don't need to include this file at all! You do need to include
+// it (in your own .cc file) if you want to use the STRING, STL, or
+// NEW aspects of the arena. See arena.h for details on these types.
+//
+// ArenaAllocator is an STL allocator, but because it relies on unequal
+// instances, it may not work with all standards-conforming STL
+// implementations. But it works with SGI STL so we're happy.
+//
+// Here's an example of how the ArenaAllocator would be used.
+// Say we have a vector of ints that we want to have use the arena
+// for memory allocation. Here's one way to do it:
+// UnsafeArena* arena = new UnsafeArena(1000); // or SafeArena(), or 10000
+// vector<int, ArenaAllocator<int, UnsafeArena> > v(arena);
+//
+// Note that every STL type always allows the allocator (in this case,
+// the arena, which is automatically promoted to an allocator) as the last
+// arg to the constructor. So if you would normally do
+// vector<...> v(foo, bar),
+// with the arena you can do
+// vector<...> v(foo, bar, arena);
+
+#ifndef BASE_ARENA_INL_H_
+#define BASE_ARENA_INL_H_
+
+#include <config.h>
+#include "base/arena.h"
+#include <assert.h>
+#include <stddef.h>
+#include <new>
+#include <memory>
+
+namespace ctemplate {
+
+// T is the type we want to allocate, and C is the type of the arena.
+// ArenaAllocator has the thread-safety characteristics of C.
+template <class T, class C> class ArenaAllocator {
+ public:
+ typedef T value_type;
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+
+ typedef T* pointer;
+ typedef const T* const_pointer;
+ typedef T& reference;
+ typedef const T& const_reference;
+ pointer address(reference r) const { return &r; }
+ const_pointer address(const_reference r) const { return &r; }
+ size_type max_size() const { return size_t(-1) / sizeof(T); }
+
+ // DO NOT USE! The default constructor is for gcc3 compatibility only.
+ ArenaAllocator() : arena_(0) { }
+ // This is not an explicit constructor! So you can pass in an arena*
+ // to functions needing an ArenaAllocator (like the astring constructor)
+ // and everything will work ok.
+ ArenaAllocator(C* arena) : arena_(arena) { } // NOLINT
+ ~ArenaAllocator() { }
+
+ pointer allocate(size_type n,
+ std::allocator<void>::const_pointer /*hint*/ = 0) {
+ assert(arena_ && "No arena to allocate from!");
+ return reinterpret_cast<T*>(arena_->AllocAligned(n * sizeof(T),
+ kAlignment));
+ }
+ void deallocate(pointer p, size_type n) {
+ arena_->Free(p, n * sizeof(T));
+ }
+ void construct(pointer p, const T & val) {
+ new(reinterpret_cast<void*>(p)) T(val);
+ }
+ void construct(pointer p) {
+ new(reinterpret_cast<void*>(p)) T();
+ }
+ void destroy(pointer p) { p->~T(); }
+
+ C* arena(void) const { return arena_; }
+
+ template<class U> struct rebind {
+ typedef ArenaAllocator<U, C> other;
+ };
+
+ template<class U> ArenaAllocator(const ArenaAllocator<U, C>& other)
+ : arena_(other.arena()) { }
+
+ template<class U> bool operator==(const ArenaAllocator<U, C>& other) const {
+ return arena_ == other.arena();
+ }
+
+ template<class U> bool operator!=(const ArenaAllocator<U, C>& other) const {
+ return arena_ != other.arena();
+ }
+
+ protected:
+ static const int kAlignment;
+ C* arena_;
+};
+
+template<class T, class C> const int ArenaAllocator<T, C>::kAlignment =
+ (1 == sizeof(T) ? 1 : BaseArena::kDefaultAlignment);
+
+
+// 'new' must be in the global namespace.
+}
+using GOOGLE_NAMESPACE::UnsafeArena;
+
+
+// Operators for allocation on the arena
+// Syntax: new (AllocateInArena, arena) MyClass;
+// new (AllocateInArena, arena) MyClass[num];
+// Useful for classes you can't descend from Gladiator, such as POD,
+// STL containers, etc.
+enum AllocateInArenaType { AllocateInArena };
+
+inline void* operator new(size_t size,
+ AllocateInArenaType /* unused */,
+ UnsafeArena *arena) {
+ return arena->Alloc(size);
+}
+
+inline void* operator new[](size_t size,
+ AllocateInArenaType /* unused */,
+ UnsafeArena *arena) {
+ return arena->Alloc(size);
+}
+
+namespace ctemplate {
+
+// Ordinarily in C++, one allocates all instances of a class from an
+// arena. If that's what you want to do, you don't need Gladiator.
+// (However you may find ArenaOnlyGladiator useful.)
+//
+// However, for utility classes that are used by multiple clients, the
+// everything-in-one-arena model may not work. Some clients may wish
+// not to use an arena at all. Or perhaps a composite structure
+// (tree) will contain multiple objects (nodes) and some of those
+// objects will be created by a factory, using an arena, while other
+// objects will be created on-the-fly by an unsuspecting user who
+// doesn't know anything about the arena.
+//
+// To support that, have the arena-allocated class inherit from
+// Gladiator. The ordinary operator new will continue to allocate
+// from the heap. To allocate from an arena, do
+// Myclass * m = new (AllocateInArena, a) Myclass (args, to, constructor);
+// where a is either an arena or an allocator. Now you can call
+// delete on all the objects, whether they are allocated from an arena
+// or on the heap. Heap memory will be released, while arena memory will
+// not be.
+//
+// If a client knows that no objects were allocated on the heap, it
+// need not delete any objects (but it may if it wishes). The only
+// objects that must be deleted are those that were actually allocated
+// from the heap.
+//
+// NOTE: an exception to the google C++ style guide rule for "No multiple
+// implementation inheritance" is granted for this class: you can treat this
+// class as an "Interface" class, and use it in a multiple inheritence context,
+// even though it implements operator new/delete.
+
+class Gladiator {
+ public:
+ Gladiator() { }
+ virtual ~Gladiator() { }
+
+ // We do not override the array allocators, so array allocation and
+ // deallocation will always be from the heap. Typically, arrays are
+ // larger, and thus the costs of arena allocation are higher and the
+ // benefits smaller. Since arrays are typically allocated and deallocated
+ // very differently from scalars, this may not interfere too much with
+ // the arena concept. If it does pose a problem, flesh out the
+ // ArrayGladiator class below.
+
+ void* operator new(size_t size) {
+ void* ret = ::operator new(1 + size);
+ static_cast<char *>(ret)[size] = 1; // mark as heap-allocated
+ return ret;
+ }
+ // the ignored parameter keeps us from stepping on placement new
+ template<class T> void* operator new(size_t size, const int ignored,
+ T* allocator) {
+ if (allocator) {
+ void* ret = allocator->AllocAligned(1 + size,
+ BaseArena::kDefaultAlignment);
+ static_cast<char*>(ret)[size] = 0; // mark as arena-allocated
+ return ret;
+ } else {
+ return operator new(size); // this is the function above
+ }
+ }
+ void operator delete(void* memory, size_t size) {
+ if (static_cast<char*>(memory)[size]) {
+ assert (1 == static_cast<char *>(memory)[size]);
+ ::operator delete(memory);
+ } else {
+ // We never call the allocator's Free method. If we need to do
+ // that someday, we can store a pointer to the arena instead of
+ // the Boolean marker flag.
+ }
+ }
+ template<class T> void operator delete(void* memory, size_t size,
+ const int ign, T* allocator) {
+ // This "placement delete" can only be called if the constructor
+ // throws an exception.
+ if (allocator) {
+ allocator->Free(memory, 1 + size);
+ } else {
+ ::operator delete(memory);
+ }
+ }
+};
+
+// This avoids the space overhead of Gladiator if you just want to
+// override new and delete. It helps avoid some of the more common
+// problems that can occur when overriding new and delete.
+
+class ArenaOnlyGladiator {
+ public:
+ ArenaOnlyGladiator() { }
+ // No virtual destructor is needed because we ignore the size
+ // parameter in all the delete functions.
+ // virtual ~ArenaOnlyGladiator() { }
+
+ // can't just return NULL here -- compiler gives a warning. :-|
+ void* operator new(size_t /*size*/) {
+ assert(0);
+ return reinterpret_cast<void *>(1);
+ }
+ void* operator new[](size_t /*size*/) {
+ assert(0);
+ return reinterpret_cast<void *>(1);
+ }
+
+ // the ignored parameter keeps us from stepping on placement new
+ template<class T> void* operator new(size_t size, const int ignored,
+ T* allocator) {
+ assert(allocator);
+ return allocator->AllocAligned(size, BaseArena::kDefaultAlignment);
+ }
+ template<class T> void* operator new[](size_t size,
+ const int ignored, T* allocator) {
+ assert(allocator);
+ return allocator->AllocAligned (size, BaseArena::kDefaultAlignment);
+ }
+ void operator delete(void* /*memory*/, size_t /*size*/) { }
+ template<class T> void operator delete(void* memory, size_t size,
+ const int ign, T* allocator) { }
+ void operator delete [](void* /*memory*/) { }
+ template<class T> void operator delete(void* memory,
+ const int ign, T* allocator) { }
+};
+
+#if 0 // ********** for example purposes only; 100% untested.
+
+// Note that this implementation incurs an overhead of kHeaderSize for
+// every array that is allocated. *Before* the space is returned to the
+// user, we store the address of the Arena that owns the space, and
+// the length of th space itself.
+
+class ArrayGladiator : public Gladiator {
+ public:
+ void * operator new[] (size_t size) {
+ const int sizeplus = size + kHeaderSize;
+ void * const ret = ::operator new(sizeplus);
+ *static_cast<Arena **>(ret) = NULL; // mark as heap-allocated
+ *static_cast<size_t *>(ret + sizeof(Arena *)) = sizeplus;
+ return ret + kHeaderSize;
+ }
+ // the ignored parameter keeps us from stepping on placement new
+ template<class T> void * operator new[] (size_t size,
+ const int ignored, T * allocator) {
+ if (allocator) {
+ const int sizeplus = size + kHeaderSize;
+ void * const ret =
+ allocator->AllocAligned(sizeplus, BaseArena::kDefaultAlignment);
+ *static_cast<Arena **>(ret) = allocator->arena();
+ *static_cast<size_t *>(ret + sizeof(Arena *)) = sizeplus;
+ return ret + kHeaderSize;
+ } else {
+ return operator new[](size); // this is the function above
+ }
+ }
+ void operator delete [] (void * memory) {
+ memory -= kHeaderSize;
+ Arena * const arena = *static_cast<Arena **>(memory);
+ size_t sizeplus = *static_cast<size_t *>(memory + sizeof(arena));
+ if (arena) {
+ arena->SlowFree(memory, sizeplus);
+ } else {
+ ::operator delete (memory);
+ }
+ }
+ template<class T> void * operator delete (void * memory,
+ const int ign, T * allocator) {
+ // This "placement delete" can only be called if the constructor
+ // throws an exception.
+ memory -= kHeaderSize;
+ size_t sizeplus = *static_cast<size_t *>(memory + sizeof(Arena *));
+ if (allocator) {
+ allocator->Free(memory, 1 + size);
+ } else {
+ operator delete (memory);
+ }
+ }
+
+ protected:
+ static const int kMinSize = sizeof size_t + sizeof(Arena *);
+ static const int kHeaderSize = kMinSize > BaseArena::kDefaultAlignment ?
+ 2 * BaseArena::kDefaultAlignment : BaseArena::kDefaultAlignment;
+};
+
+#endif // ********** example
+
+}
+
+#endif // BASE_ARENA_INL_H_
diff --git a/src/base/arena.cc b/src/base/arena.cc
new file mode 100644
index 0000000..62df770
--- /dev/null
+++ b/src/base/arena.cc
@@ -0,0 +1,505 @@
+// Copyright (c) 2000, 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.
+// ---
+//
+// Reorganized by Craig Silverstein
+// "Handles" by Ilan Horn
+//
+// This approach to arenas overcomes many of the limitations described
+// in the "Specialized allocators" section of
+// http://www.pdos.lcs.mit.edu/~dm/c++-new.html
+//
+// A somewhat similar approach to Gladiator, but for heap-detection, was
+// suggested by Ron van der Wal and Scott Meyers at
+// http://www.aristeia.com/BookErrata/M27Comments_frames.html
+
+#include <config.h>
+#include "base/arena.h"
+#include "base/arena-inl.h"
+#include <assert.h>
+#include <algorithm>
+#ifdef HAVE_UNISTD_H
+# include <unistd.h>
+#endif
+#include <vector>
+#include <sys/types.h> // one place uintptr_t might be
+#ifdef HAVE_INTTYPES_H
+# include <inttypes.h>
+#endif // another place uintptr_t might be
+#ifdef HAVE_UNISTD_H
+# include <unistd.h>
+#endif // last place uintptr_t might be
+#include "base/macros.h" // for uint64
+#include "base/mutex.h"
+#include "base/util.h" // for DCHECK_*
+
+using std::min;
+using std::vector;
+
+// TODO(csilvers): add in a portable implementation of aligned_malloc
+static void* aligned_malloc(size_t size, size_t alignment) {
+ LOG(FATAL) << "page_aligned_ not currently supported\n";
+}
+
+// The value here doesn't matter until page_aligned_ is supported.
+static const int kPageSize = 8192; // should be getpagesize()
+
+namespace ctemplate {
+
+// We used to only keep track of how much space has been allocated in
+// debug mode. Now we track this for optimized builds, as well. If you
+// want to play with the old scheme to see if this helps performance,
+// change this ARENASET() macro to a NOP. However, NOTE: some
+// applications of arenas depend on this space information (exported
+// via bytes_allocated()).
+#define ARENASET(x) (x)
+
+// ----------------------------------------------------------------------
+// BaseArena::BaseArena()
+// BaseArena::~BaseArena()
+// Destroying the arena automatically calls Reset()
+// ----------------------------------------------------------------------
+
+
+BaseArena::BaseArena(char* first, const size_t block_size, bool align_to_page)
+ : remaining_(0),
+ first_block_we_own_(first ? 1 : 0),
+ block_size_(block_size),
+ freestart_(NULL), // set for real in Reset()
+ last_alloc_(NULL),
+ blocks_alloced_(1),
+ overflow_blocks_(NULL),
+ page_aligned_(align_to_page),
+ handle_alignment_(1),
+ handle_alignment_bits_(0),
+ block_size_bits_(0) {
+ assert(block_size > kDefaultAlignment);
+
+ while ((static_cast<size_t>(1) << block_size_bits_) < block_size_) {
+ ++block_size_bits_;
+ }
+
+ if (page_aligned_) {
+ // kPageSize must be power of 2, so make sure of this.
+ CHECK(kPageSize > 0 && 0 == (kPageSize & (kPageSize - 1)))
+ << "kPageSize[ " << kPageSize << "] is not "
+ << "correctly initialized: not a power of 2.";
+ }
+
+ if (first) {
+ CHECK(!page_aligned_ ||
+ (reinterpret_cast<uintptr_t>(first) & (kPageSize - 1)) == 0);
+ first_blocks_[0].mem = first;
+ } else {
+ if (page_aligned_) {
+ // Make sure the blocksize is page multiple, as we need to end on a page
+ // boundary.
+ CHECK_EQ(block_size & (kPageSize - 1), 0) << "block_size is not a"
+ << "multiple of kPageSize";
+ first_blocks_[0].mem = reinterpret_cast<char*>(aligned_malloc(block_size_,
+ kPageSize));
+ PCHECK(NULL != first_blocks_[0].mem);
+ } else {
+ first_blocks_[0].mem = reinterpret_cast<char*>(malloc(block_size_));
+ }
+ }
+ first_blocks_[0].size = block_size_;
+
+ Reset();
+}
+
+BaseArena::~BaseArena() {
+ FreeBlocks();
+ assert(overflow_blocks_ == NULL); // FreeBlocks() should do that
+ // The first X blocks stay allocated always by default. Delete them now.
+ for ( int i = first_block_we_own_; i < blocks_alloced_; ++i )
+ free(first_blocks_[i].mem);
+}
+
+// ----------------------------------------------------------------------
+// BaseArena::block_count()
+// Only reason this is in .cc file is because it involves STL.
+// ----------------------------------------------------------------------
+
+int BaseArena::block_count() const {
+ return (blocks_alloced_ +
+ (overflow_blocks_ ? static_cast<int>(overflow_blocks_->size()) : 0));
+}
+
+// ----------------------------------------------------------------------
+// BaseArena::Reset()
+// Clears all the memory an arena is using.
+// ----------------------------------------------------------------------
+
+void BaseArena::Reset() {
+ FreeBlocks();
+ freestart_ = first_blocks_[0].mem;
+ remaining_ = first_blocks_[0].size;
+ last_alloc_ = NULL;
+
+ ARENASET(status_.bytes_allocated_ = block_size_);
+
+ // We do not know for sure whether or not the first block is aligned,
+ // so we fix that right now.
+ const int overage = reinterpret_cast<uintptr_t>(freestart_) &
+ (kDefaultAlignment-1);
+ if (overage > 0) {
+ const int waste = kDefaultAlignment - overage;
+ freestart_ += waste;
+ remaining_ -= waste;
+ }
+ freestart_when_empty_ = freestart_;
+ assert(!(reinterpret_cast<uintptr_t>(freestart_)&(kDefaultAlignment-1)));
+}
+
+// ----------------------------------------------------------------------
+// BaseArena::MakeNewBlock()
+// Our sbrk() equivalent. We always make blocks of the same size
+// (though GetMemory() can also make a new block for really big
+// data.
+// ----------------------------------------------------------------------
+
+void BaseArena::MakeNewBlock() {
+ AllocatedBlock *block = AllocNewBlock(block_size_);
+ freestart_ = block->mem;
+ remaining_ = block->size;
+}
+
+// -------------------------------------------------------------
+// BaseArena::AllocNewBlock()
+// Adds and returns an AllocatedBlock.
+// The returned AllocatedBlock* is valid until the next call
+// to AllocNewBlock or Reset. (i.e. anything that might
+// affect overflow_blocks_).
+// -------------------------------------------------------------
+
+BaseArena::AllocatedBlock* BaseArena::AllocNewBlock(const size_t block_size) {
+ AllocatedBlock *block;
+ // Find the next block.
+ if ( blocks_alloced_ < ARRAYSIZE(first_blocks_) ) {
+ // Use one of the pre-allocated blocks
+ block = &first_blocks_[blocks_alloced_++];
+ } else { // oops, out of space, move to the vector
+ if (overflow_blocks_ == NULL) overflow_blocks_ = new vector<AllocatedBlock>;
+ // Adds another block to the vector.
+ overflow_blocks_->resize(overflow_blocks_->size()+1);
+ // block points to the last block of the vector.
+ block = &overflow_blocks_->back();
+ }
+
+ if (page_aligned_) {
+ // We need the size to be multiple of kPageSize to mprotect it later.
+ size_t num_pages = ((block_size - 1) / kPageSize) + 1;
+ size_t new_block_size = num_pages * kPageSize;
+ block->mem = reinterpret_cast<char*>(aligned_malloc(new_block_size,
+ kPageSize));
+ PCHECK(NULL != block->mem);
+ block->size = new_block_size;
+ } else {
+ block->mem = reinterpret_cast<char*>(malloc(block_size));
+ block->size = block_size;
+ }
+
+ ARENASET(status_.bytes_allocated_ += block_size);
+
+ return block;
+}
+
+// ----------------------------------------------------------------------
+// BaseArena::IndexToBlock()
+// Index encoding is as follows:
+// For blocks in the first_blocks_ array, we use index of the block in
+// the array.
+// For blocks in the overflow_blocks_ vector, we use the index of the
+// block in iverflow_blocks_, plus the size of the first_blocks_ array.
+// ----------------------------------------------------------------------
+
+const BaseArena::AllocatedBlock *BaseArena::IndexToBlock(int index) const {
+ if (index < ARRAYSIZE(first_blocks_)) {
+ return &first_blocks_[index];
+ }
+ CHECK(overflow_blocks_ != NULL);
+ int index_in_overflow_blocks = index - ARRAYSIZE(first_blocks_);
+ CHECK_GE(index_in_overflow_blocks, 0);
+ CHECK_LT(static_cast<size_t>(index_in_overflow_blocks),
+ overflow_blocks_->size());
+ return &(*overflow_blocks_)[index_in_overflow_blocks];
+}
+
+// ----------------------------------------------------------------------
+// BaseArena::GetMemoryFallback()
+// We take memory out of our pool, aligned on the byte boundary
+// requested. If we don't have space in our current pool, we
+// allocate a new block (wasting the remaining space in the
+// current block) and give you that. If your memory needs are
+// too big for a single block, we make a special your-memory-only
+// allocation -- this is equivalent to not using the arena at all.
+// ----------------------------------------------------------------------
+
+void* BaseArena::GetMemoryFallback(const size_t size, const int align_as_int) {
+ if (0 == size) {
+ return NULL; // stl/stl_alloc.h says this is okay
+ }
+ // This makes the type-checker happy.
+ const size_t align = static_cast<size_t>(align_as_int);
+
+ assert(align_as_int > 0 && 0 == (align & (align - 1))); // must be power of 2
+
+ // If the object is more than a quarter of the block size, allocate
+ // it separately to avoid wasting too much space in leftover bytes
+ if (block_size_ == 0 || size > block_size_/4) {
+ // then it gets its own block in the arena
+ assert(align <= kDefaultAlignment); // because that's what new gives us
+ // This block stays separate from the rest of the world; in particular
+ // we don't update last_alloc_ so you can't reclaim space on this block.
+ return AllocNewBlock(size)->mem;
+ }
+
+ const size_t overage =
+ (reinterpret_cast<uintptr_t>(freestart_) & (align-1));
+ if (overage) {
+ const size_t waste = align - overage;
+ freestart_ += waste;
+ if (waste < remaining_) {
+ remaining_ -= waste;
+ } else {
+ remaining_ = 0;
+ }
+ }
+ if (size > remaining_) {
+ MakeNewBlock();
+ }
+ remaining_ -= size;
+ last_alloc_ = freestart_;
+ freestart_ += size;
+ assert(0 == (reinterpret_cast<uintptr_t>(last_alloc_) & (align-1)));
+ return reinterpret_cast<void*>(last_alloc_);
+}
+
+// ----------------------------------------------------------------------
+// BaseArena::ReturnMemoryFallback()
+// BaseArena::FreeBlocks()
+// Unlike GetMemory(), which does actual work, ReturnMemory() is a
+// no-op: we don't "free" memory until Reset() is called. We do
+// update some stats, though. Note we do no checking that the
+// pointer you pass in was actually allocated by us, or that it
+// was allocated for the size you say, so be careful here!
+// FreeBlocks() does the work for Reset(), actually freeing all
+// memory allocated in one fell swoop.
+// ----------------------------------------------------------------------
+
+void BaseArena::FreeBlocks() {
+ for ( int i = 1; i < blocks_alloced_; ++i ) { // keep first block alloced
+ free(first_blocks_[i].mem);
+ first_blocks_[i].mem = NULL;
+ first_blocks_[i].size = 0;
+ }
+ blocks_alloced_ = 1;
+ if (overflow_blocks_ != NULL) {
+ vector<AllocatedBlock>::iterator it;
+ for (it = overflow_blocks_->begin(); it != overflow_blocks_->end(); ++it) {
+ free(it->mem);
+ }
+ delete overflow_blocks_; // These should be used very rarely
+ overflow_blocks_ = NULL;
+ }
+}
+
+// ----------------------------------------------------------------------
+// BaseArena::AdjustLastAlloc()
+// If you realize you didn't want your last alloc to be for
+// the size you asked, after all, you can fix it by calling
+// this. We'll grow or shrink the last-alloc region if we
+// can (we can always shrink, but we might not be able to
+// grow if you want to grow too big.
+// RETURNS true if we successfully modified the last-alloc
+// region, false if the pointer you passed in wasn't actually
+// the last alloc or if you tried to grow bigger than we could.
+// ----------------------------------------------------------------------
+
+bool BaseArena::AdjustLastAlloc(void *last_alloc, const size_t newsize) {
+ // It's only legal to call this on the last thing you alloced.
+ if (last_alloc == NULL || last_alloc != last_alloc_) return false;
+ // last_alloc_ should never point into a "big" block, w/ size >= block_size_
+ assert(freestart_ >= last_alloc_ && freestart_ <= last_alloc_ + block_size_);
+ assert(remaining_ >= 0); // should be: it's a size_t!
+ if (newsize > (freestart_ - last_alloc_) + remaining_)
+ return false; // not enough room, even after we get back last_alloc_ space
+ const char* old_freestart = freestart_; // where last alloc used to end
+ freestart_ = last_alloc_ + newsize; // where last alloc ends now
+ remaining_ -= (freestart_ - old_freestart); // how much new space we've taken
+ return true;
+}
+
+// ----------------------------------------------------------------------
+// BaseArena::GetMemoryWithHandle()
+// First, memory is allocated using GetMemory, using handle_alignment_.
+// Since using different alignments for different handles would make
+// the handles incompatible (e.g., we could end up with the same handle
+// value referencing two different allocations, the alignment is not passed
+// as an argument to GetMemoryWithHandle, and handle_alignment_ is used
+// automatically for all GetMemoryWithHandle calls.
+// Then we go about building a handle to reference the allocated memory.
+// The block index used for the allocation, along with the offset inside
+// the block, are encoded into the handle as follows:
+// (block_index*block_size)+offset
+// offset is simply the difference between the pointer returned by
+// GetMemory and the starting pointer of the block.
+// The above value is then divided by the alignment. As we know that
+// both offset and the block_size are divisable by the alignment (this is
+// enforced by set_handle_alignment() for block_size, and by GetMemory()
+// for the offset), this does not lose any information, but allows to cram
+// more into the limited space in handle.
+// If the result does not fit into an unsigned 32-bit integer, we
+// have run out of space that the handle can represent, and return
+// an invalid handle. Note that the returned pointer is still usable,
+// but this allocation cannot be referenced by a handle.
+// ----------------------------------------------------------------------
+
+void* BaseArena::GetMemoryWithHandle(
+ const size_t size, BaseArena::Handle* handle) {
+ CHECK(handle != NULL);
+ // For efficiency, handles are always allocated aligned to a power of 2.
+ void* p = GetMemory(size, (1 << handle_alignment_bits_));
+ // Find the index of the block the memory was allocated from. In most
+ // cases, this will be the last block, so the following loop will
+ // iterate exactly once.
+ int block_index;
+ const AllocatedBlock* block = NULL;
+ for (block_index = block_count() - 1; block_index >= 0; --block_index) {
+ block = IndexToBlock(block_index);
+ if ((p >= block->mem) && (p < (block->mem + block->size))) {
+ break;
+ }
+ }
+ CHECK_GE(block_index, 0) << "Failed to find block that was allocated from";
+ CHECK(block != NULL) << "Failed to find block that was allocated from";
+ const uint64 offset = reinterpret_cast<char*>(p) - block->mem;
+ DCHECK_LT(offset, block_size_);
+ DCHECK((offset & ((1 << handle_alignment_bits_) - 1)) == 0);
+ DCHECK((block_size_ & ((1 << handle_alignment_bits_) - 1)) == 0);
+ uint64 handle_value =
+ ((static_cast<uint64>(block_index) << block_size_bits_) + offset) >>
+ handle_alignment_bits_;
+ if (handle_value >= static_cast<uint64>(0xFFFFFFFF)) {
+ // We ran out of space to be able to return a handle, so return an invalid
+ // handle.
+ handle_value = Handle::kInvalidValue;
+ }
+ handle->handle_ = static_cast<uint32>(handle_value);
+ return p;
+}
+
+// ----------------------------------------------------------------------
+// BaseArena::set_handle_alignment()
+// Set the alignment to be used when Handles are requested. This can only
+// be set for an arena that is empty - it cannot be changed on the fly.
+// The alignment must be a power of 2 that the block size is divisable by.
+// The default alignment is 1.
+// Trying to set an alignment that does not meet the above constraints will
+// cause a CHECK-failure.
+// ----------------------------------------------------------------------
+
+void BaseArena::set_handle_alignment(int align) {
+ CHECK(align > 0 && 0 == (align & (align - 1))); // must be power of 2
+ CHECK(static_cast<size_t>(align) < block_size_);
+ CHECK((block_size_ % align) == 0);
+ CHECK(is_empty());
+ handle_alignment_ = align;
+ handle_alignment_bits_ = 0;
+ while ((1 << handle_alignment_bits_) < handle_alignment_) {
+ ++handle_alignment_bits_;
+ }
+}
+
+// ----------------------------------------------------------------------
+// BaseArena::HandleToPointer()
+// First, the handle value needs to gain back the alignment factor that
+// was divided out of it by GetMemoryWithHandle. Once this is done, it
+// becomes trivial to extract the block index and offset in the block out
+// of it, and calculate the pointer.
+// ----------------------------------------------------------------------
+
+void* BaseArena::HandleToPointer(const Handle& h) const {
+ CHECK(h.valid());
+ uint64 handle = static_cast<uint64>(h.handle_) << handle_alignment_bits_;
+ int block_index = static_cast<int>(handle >> block_size_bits_);
+ size_t block_offset =
+ static_cast<size_t>(handle & ((1 << block_size_bits_) - 1));
+ const AllocatedBlock* block = IndexToBlock(block_index);
+ CHECK(block != NULL);
+ return reinterpret_cast<void*>(block->mem + block_offset);
+}
+
+
+// ----------------------------------------------------------------------
+// UnsafeArena::Realloc()
+// SafeArena::Realloc()
+// If you decide you want to grow -- or shrink -- a memory region,
+// we'll do it for you here. Typically this will involve copying
+// the existing memory to somewhere else on the arena that has
+// more space reserved. But if you're reallocing the last-allocated
+// block, we may be able to accomodate you just by updating a
+// pointer. In any case, we return a pointer to the new memory
+// location, which may be the same as the pointer you passed in.
+// Here's an example of how you might use Realloc():
+//
+// compr_buf = arena->Alloc(uncompr_size); // get too-much space
+// int compr_size;
+// zlib.Compress(uncompr_buf, uncompr_size, compr_buf, &compr_size);
+// compr_buf = arena->Realloc(compr_buf, uncompr_size, compr_size);
+// ----------------------------------------------------------------------
+
+char* UnsafeArena::Realloc(char* s, size_t oldsize, size_t newsize) {
+ assert(oldsize >= 0 && newsize >= 0);
+ if ( AdjustLastAlloc(s, newsize) ) // in case s was last alloc
+ return s;
+ if ( newsize <= oldsize ) {
+ return s; // no need to do anything; we're ain't reclaiming any memory!
+ }
+ char * newstr = Alloc(newsize);
+ memcpy(newstr, s, min(oldsize, newsize));
+ return newstr;
+}
+
+char* SafeArena::Realloc(char* s, size_t oldsize, size_t newsize) {
+ assert(oldsize >= 0 && newsize >= 0);
+ { MutexLock lock(&mutex_);
+ if ( AdjustLastAlloc(s, newsize) ) // in case s was last alloc
+ return s;
+ }
+ if ( newsize <= oldsize ) {
+ return s; // no need to do anything; we're ain't reclaiming any memory!
+ }
+ char * newstr = Alloc(newsize);
+ memcpy(newstr, s, min(oldsize, newsize));
+ return newstr;
+}
+
+}
diff --git a/src/base/arena.h b/src/base/arena.h
new file mode 100644
index 0000000..049a6b5
--- /dev/null
+++ b/src/base/arena.h
@@ -0,0 +1,698 @@
+// Copyright (c) 2000, 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.
+// ---
+//
+// Reorganized by Craig Silverstein
+// "Handles" by Ilan Horn
+//
+// Sometimes it is necessary to allocate a large number of small
+// objects. Doing this the usual way (malloc, new) is slow,
+// especially for multithreaded programs. A BaseArena provides a
+// mark/release method of memory management: it asks for a large chunk
+// from the operating system and doles it out bit by bit as required.
+// Then you free all the memory at once by calling BaseArena::Reset().
+//
+// Use SafeArena for multi-threaded programs where multiple threads
+// could access the same arena at once. Use UnsafeArena otherwise.
+// Usually you'll want UnsafeArena.
+//
+// There are four ways to use the arena. arena.h and arena.cc are
+// sufficient for the MALLOC and STRINGS uses. For NEW and STL you'll
+// also need to include arena-inl.h in the appropriate .cc file.
+// However, we do *declare* (but not define) the template types here.
+//
+// LIKE MALLOC: --Uses UnsafeArena (or SafeArena)--
+// This is the simplest way. Just create an arena, and whenever you
+// need a block of memory to put something in, call BaseArena::Alloc(). eg
+// s = arena.Alloc(100);
+// snprintf(s, 100, "%s:%d", host, port);
+// arena.Shrink(strlen(s)+1); // optional; see below for use
+//
+// You'll probably use the convenience routines more often:
+// s = arena.Strdup(host); // a copy of host lives in the arena
+// s = arena.Strndup(host, 100); // we guarantee to NUL-terminate!
+// s = arena.Memdup(protobuf, sizeof(protobuf);
+//
+// If you go the Alloc() route, you'll probably allocate too-much-space.
+// You can reclaim the extra space by calling Shrink() before the next
+// Alloc() (or Strdup(), or whatever), with the #bytes you actually used.
+// If you use this method, memory management is easy: just call Alloc()
+// and friends a lot, and call Reset() when you're done with the data.
+//
+// FOR STRINGS: --Uses UnsafeArena (or SafeArena)--
+// This is a special case of STL (below), but is simpler. Use an
+// astring, which acts like a string but allocates from the passed-in
+// arena:
+// astring s(arena); // or "sastring" to use a SafeArena
+// s.assign(host);
+// astring s2(host, hostlen, arena);
+//
+// WITH NEW: --Uses BaseArena, Gladiator (or ArenaOnlyGladiator)--
+// Use this to allocate a C++ class object (or any other object you
+// have to get via new/delete rather than malloc/free).
+// There are several things you have to do in this case:
+// 1) Your class (the one you new) must inherit from Gladiator.
+// 2) To actually allocate this class on the arena, use
+// myclass = new (AllocateInArena, arena) MyClass(constructor, args)
+//
+// Note that MyClass doesn't need to have the arena passed in.
+// But if it, in turn, wants to call "new" on some of its member
+// variables, and you want those member vars to be on the arena
+// too, you better pass in an arena so it can call new(0,arena).
+//
+// If you can guarantee that everyone who ever calls new on
+// MyClass uses the new(0,arena) form (ie nobody ever just says
+// new), you can have MyClass subclass from ArenaOnlyGladiator
+// rather than from Gladiator. ArenaOnlyGladiator is a bit more
+// efficient (faster and smaller), but is otherwise identical.
+//
+// If you allocate myclass using new(0,arena), and MyClass only
+// does memory management in the destructor, it's not necessary
+// to even call "delete myclass;", you can just call arena.Reset();
+// If the destructor does something else (closes a file, logs
+// a message, whatever), you'll have to call destructor and Reset()
+// both: "delete myclass; arena.Reset();"
+//
+// Note that you can not allocate an array of classes this way:
+// noway = new (AllocateInArena, arena) MyClass[5]; // not supported!
+// It's not difficult to program, we just haven't done it. Arrays
+// are typically big and so there's little point to arena-izing them.
+//
+// WITH NEW: --Uses UnsafeArena--
+// There are cases where you can't inherit the class from Gladiator,
+// or inheriting would be too expensive. Examples of this include
+// plain-old-data (allocated using new) and third-party classes (such
+// as STL containers). arena-inl.h provides a global operator new
+// that can be used as follows:
+//
+// #include "base/arena-inl.h"
+//
+// UnsafeArena arena(1000);
+// Foo* foo = new (AllocateInArena, &arena) Foo;
+// Foo* foo_array = new (AllocateInArena, &arena) Foo[10];
+//
+// IN STL: --Uses BaseArena, ArenaAllocator--
+// All STL containers (vector, hash_map, etc) take an allocator.
+// You can use the arena as an allocator. Then whenever the vector
+// (or whatever) wants to allocate memory, it will take it from the
+// arena. To use, you just indicate in the type that you want to use the
+// arena, and then actually give a pointer to the arena as the last
+// constructor arg:
+// vector<int, ArenaAllocator<int, UnsafeArena> > v(&arena);
+// v.push_back(3);
+//
+// WARNING: Careless use of STL within an arena-allocated object can
+// result in memory leaks if you rely on arena.Reset() to free
+// memory and do not call the object destructor. This is actually
+// a subclass of a more general hazard: If an arena-allocated
+// object creates (and owns) objects that are not also
+// arena-allocated, then the creating object must have a
+// destructor that deletes them, or they will not be deleted.
+// However, since the outer object is arena allocated, it's easy to
+// forget to call delete on it, and needing to do so may seem to
+// negate much of the benefit of arena allocation. A specific
+// example is use of vector<string> in an arena-allocated object,
+// since type string is not atomic and is always allocated by the
+// default runtime allocator. The arena definition provided here
+// allows for much flexibility, but you ought to carefully consider
+// before defining arena-allocated objects which in turn create
+// non-arena allocated objects.
+//
+// WITH HANDLES:
+// The various arena classes can supply compact handles to data kept
+// in the arena. These handles consume only 4 bytes each, and are thus
+// more efficient than pointers - this may be interesting in cases
+// where a very large number of references to memory in the arena need
+// to be kept.
+// Note that handles are limited in the amount of data that can be reference
+// in the arena, typically to 4GB*the number given to set_handle_alignment()
+// (which defaults to 1). The number of allocations that can have handles
+// is, of course, smaller than 4G (that's what's representable by 32 bits).
+// It does depend on their sizes, however. In a worst-case scenario each
+// allocation consumes a page of its own, and we will run out of handles
+// after approximately (4G/block_size)*handle_alignment allocations.
+// When we run out of handles or allocate data over the amount of memory
+// that handles can reference, an invalid handle will be returned (but
+// the requested memory will still be allocated in the arena).
+// Handles memory use is most efficient when the arena block size is a power
+// of two. When this is not the case, we can run out of handles when at
+// most half of the addressable space (as described above) is not in use.
+// At worst handles can reference at least 2GB*handle_alignment.
+// Example use:
+// UnsafeArena arena(16384);
+// arena.set_handle_alignment(4);
+// // Assume you want to keep the string s in the arena.
+// Handle h = arena.MemdupWithHandle(s.c_str(), s.length());
+// // Later, to get the memory from the handle, use:
+// void* p = arena.HandleToPointer(h);
+// // Note that there's no way to retrieve the size from the handle.
+// // It probably makes sense to encode the size into the buffer saved,
+// // unless the size is known/fixed.
+// Internal machinery of handles:
+// The handle consists of the block index in the arena and the offset
+// inside the block, encoded into a single unsigned uint32 value.
+// Note that, the rightmost alignment bits (controlled by
+// set_handle_alignment()) are shaved off the saved offset in the Handle,
+// to give some extra capacity :)
+// set_handle_alignment() can only be called when the arena is empty,
+// as changing it invalidates any handles that are still in flight.
+//
+//
+// PUTTING IT ALL TOGETHER
+// Here's a program that uses all of the above. Note almost all the
+// examples are the various ways to use "new" and STL. Using the
+// malloc-like features and the string type are much easier!
+//
+// Class A : public Gladiator {
+// public:
+// int i;
+// vector<int> v1;
+// vector<int, ArenaAllocator<int, UnsafeArena> >* v3;
+// vector<int, ArenaAllocator<int, UnsafeArena> >* v4;
+// vector<int>* v5;
+// vector<string> vs;
+// vector<astring> va;
+// char *s;
+// A() : v1(), v3(NULL), v4(NULL), vs(), va(), s(NULL) {
+// // v1 is allocated on the arena whenever A is. Its ints never are.
+// v5 = new vector<int>;
+// // v5 is not allocated on the arena, and neither are any of its ints.
+// }
+// ~A() {
+// delete v5; // needed since v5 wasn't allocated on the arena
+// printf("I'm done!\n");
+// }
+// };
+//
+// class B : public A { // we inherit from Gladiator, but indirectly
+// public:
+// UnsafeArena* arena_;
+// vector<int, ArenaAllocator<int, UnsafeArena> > v2;
+// vector<A> va1;
+// vector<A, ArenaAllocator<A, UnsafeArena> > va2;
+// vector<A>* pva;
+// vector<A, ArenaAllocator<A, UnsafeArena> >* pva2;
+// astring a;
+//
+// B(UnsafeArena * arena)
+// : arena_(arena), v2(arena_), va1(), va2(arena_), a("initval", arena_) {
+// v3 = new vector<int, ArenaAllocator<int, UnsafeArena> >(arena_);
+// v4 = new (AllocateInArena, arena_) vector<int, ArenaAllocator<int, UnsafeArena> >(arena_);
+// v5 = new (AllocateInArena, arena_) vector<int>;
+// // v2 is allocated on the arena whenever B is. Its ints always are.
+// // v3 is not allocated on the arena, but the ints you give it are
+// // v4 is allocated on the arena, and so are the ints you give it
+// // v5 is allocated on the arena, but the ints you give it are not
+// // va1 is allocated on the arena whenever B is. No A ever is.
+// // va2 is allocated on the arena whenever B is. Its A's always are.
+// pva = new (AllocateInArena, arena_) vector<A>;
+// pva2 = new (AllocateInArena, arena_) vector<A, ArenaAllocator<A, UnsafeArena> >(arena_);
+// // pva is allocated on the arena, but its A's are not
+// // pva2 is allocated on the arena, and so are its A's.
+// // a's value "initval" is stored on the arena. If we reassign a,
+// // the new value will be stored on the arena too.
+// }
+// ~B() {
+// delete v3; // necessary to free v3's memory, though not its ints'
+// // don't need to delete v4: arena_.Reset() will do as good
+// delete v5; // necessary to free v5's ints memory, though not v5 itself
+// delete pva; // necessary to make sure you reclaim space used by A's
+// delete pva2; // safe to call this; needed if you want to see the printfs
+// // pva2->clear() -- not necessary, arena_.Reset() will do just as good
+// }
+// };
+//
+// main() {
+// UnsafeArena arena(1000);
+// A a1; // a1 is not on the arena
+// a1.vs.push_back(string("hello")); // hello is not copied onto the arena
+// a1.va.push_back(astring("hello", &arena)); // hello is on the arena,
+// // astring container isn't
+// a1.s = arena.Strdup("hello"); // hello is on the arena
+//
+// A* a2 = new (AllocateInArena, arena) A; // a2 is on the arena
+// a2.vs.push_back(string("hello")); // hello is *still* not on the arena
+// a2.s = arena.Strdup("world"); // world is on the arena. a1.s is ok
+//
+// B b1(&arena); // B is not allocated on the arena
+// b1.a.assign("hello"); // hello is on the arena
+// b1.pva2.push_back(a1); // our copy of a1 will be stored on
+// // the arena, though a1 itself wasn't
+// arena.Reset(); // all done with our memory!
+// }
+
+#ifndef BASE_ARENA_H_
+#define BASE_ARENA_H_
+
+#include <config.h>
+#include "base/mutex.h" // must go first to get _XOPEN_SOURCE
+#include <assert.h>
+#include <string.h>
+#include <vector>
+#include "base/thread_annotations.h"
+#include "base/macros.h" // for uint32
+#include "base/util.h" // for CHECK, etc
+
+namespace ctemplate {
+
+// Annoying stuff for windows -- make sure clients (in this case
+// unittests) can import the class definitions and variables.
+#ifndef CTEMPLATE_DLL_DECL
+# ifdef _MSC_VER
+# define CTEMPLATE_DLL_DECL __declspec(dllimport)
+# else
+# define CTEMPLATE_DLL_DECL /* should be the empty string for non-windows */
+# endif
+#endif
+
+// This class is "thread-compatible": different threads can access the
+// arena at the same time without locking, as long as they use only
+// const methods.
+class CTEMPLATE_DLL_DECL BaseArena {
+ protected: // You can't make an arena directly; only a subclass of one
+ BaseArena(char* first_block, const size_t block_size, bool align_to_page);
+ public:
+ virtual ~BaseArena();
+
+ virtual void Reset();
+
+ // A handle to a pointer in an arena. An opaque type, with default
+ // copy and assignment semantics.
+ class Handle {
+ public:
+ static const uint32 kInvalidValue = 0xFFFFFFFF; // int32-max
+
+ Handle() : handle_(kInvalidValue) { }
+ // Default copy constructors are fine here.
+ bool operator==(const Handle& h) const { return handle_ == h.handle_; }
+ bool operator!=(const Handle& h) const { return handle_ != h.handle_; }
+
+ uint32 hash() const { return handle_; }
+ bool valid() const { return handle_ != kInvalidValue; }
+
+ private:
+ // Arena needs to be able to access the internal data.
+ friend class BaseArena;
+
+ explicit Handle(uint32 handle) : handle_(handle) { }
+
+ uint32 handle_;
+ };
+
+ // they're "slow" only 'cause they're virtual (subclasses define "fast" ones)
+ virtual char* SlowAlloc(size_t size) = 0;
+ virtual void SlowFree(void* memory, size_t size) = 0;
+ virtual char* SlowRealloc(char* memory, size_t old_size, size_t new_size) = 0;
+ virtual char* SlowAllocWithHandle(const size_t size, Handle* handle) = 0;
+
+ // Set the alignment to be used when Handles are requested. This can only
+ // be set for an arena that is empty - it cannot be changed on the fly.
+ // The alignment must be a power of 2 that the block size is divisable by.
+ // The default alignment is 1.
+ // Trying to set an alignment that does not meet the above constraints will
+ // cause a CHECK-failure.
+ void set_handle_alignment(int align);
+
+ // Retrieve the memory pointer that the supplied handle refers to.
+ // Calling this with an invalid handle will CHECK-fail.
+ void* HandleToPointer(const Handle& h) const;
+
+
+ class Status {
+ private:
+ friend class BaseArena;
+ size_t bytes_allocated_;
+ public:
+ Status() : bytes_allocated_(0) { }
+ size_t bytes_allocated() const {
+ return bytes_allocated_;
+ }
+ };
+
+ // Accessors and stats counters
+ // This accessor isn't so useful here, but is included so we can be
+ // type-compatible with ArenaAllocator (in arena-inl.h). That is,
+ // we define arena() because ArenaAllocator does, and that way you
+ // can template on either of these and know it's safe to call arena().
+ virtual BaseArena* arena() { return this; }
+ size_t block_size() const { return block_size_; }
+ int block_count() const;
+ bool is_empty() const {
+ // must check block count in case we allocated a block larger than blksize
+ return freestart_ == freestart_when_empty_ && 1 == block_count();
+ }
+
+ // This should be the worst-case alignment for any type. This is
+ // good for IA-32, SPARC version 7 (the last one I know), and
+ // supposedly Alpha. i386 would be more time-efficient with a
+ // default alignment of 8, but ::operator new() uses alignment of 4,
+ // and an assertion will fail below after the call to MakeNewBlock()
+ // if you try to use a larger alignment.
+#ifdef __i386__
+ static const int kDefaultAlignment = 4;
+#else
+ static const int kDefaultAlignment = 8;
+#endif
+
+ protected:
+ void MakeNewBlock();
+ void* GetMemoryFallback(const size_t size, const int align);
+ void* GetMemory(const size_t size, const int align) {
+ assert(remaining_ <= block_size_); // an invariant
+ if ( size > 0 && size < remaining_ && align == 1 ) { // common case
+ last_alloc_ = freestart_;
+ freestart_ += size;
+ remaining_ -= size;
+ return reinterpret_cast<void*>(last_alloc_);
+ }
+ return GetMemoryFallback(size, align);
+ }
+
+ // This doesn't actually free any memory except for the last piece allocated
+ void ReturnMemory(void* memory, const size_t size) {
+ if ( memory == last_alloc_ && size == freestart_ - last_alloc_ ) {
+ remaining_ += size;
+ freestart_ = last_alloc_;
+ }
+ }
+
+ // This is used by Realloc() -- usually we Realloc just by copying to a
+ // bigger space, but for the last alloc we can realloc by growing the region.
+ bool AdjustLastAlloc(void* last_alloc, const size_t newsize);
+
+ // Since using different alignments for different handles would make
+ // the handles incompatible (e.g., we could end up with the same handle
+ // value referencing two different allocations, the alignment is not passed
+ // as an argument to GetMemoryWithHandle, and handle_alignment_ is used
+ // automatically for all GetMemoryWithHandle calls.
+ void* GetMemoryWithHandle(const size_t size, Handle* handle);
+
+ Status status_;
+ size_t remaining_;
+
+ private:
+ struct AllocatedBlock {
+ char *mem;
+ size_t size;
+ };
+
+ // The returned AllocatedBlock* is valid until the next call to AllocNewBlock
+ // or Reset (i.e. anything that might affect overflow_blocks_).
+ AllocatedBlock *AllocNewBlock(const size_t block_size);
+
+ const AllocatedBlock *IndexToBlock(int index) const;
+
+ const int first_block_we_own_; // 1 if they pass in 1st block, 0 else
+ const size_t block_size_;
+ char* freestart_; // beginning of the free space in most recent block
+ char* freestart_when_empty_; // beginning of the free space when we're empty
+ char* last_alloc_; // used to make sure ReturnBytes() is safe
+ // STL vector isn't as efficient as it could be, so we use an array at first
+ int blocks_alloced_; // how many of the first_blocks_ have been alloced
+ AllocatedBlock first_blocks_[16]; // the length of this array is arbitrary
+ // if the first_blocks_ aren't enough, expand into overflow_blocks_.
+ std::vector<AllocatedBlock>* overflow_blocks_;
+ const bool page_aligned_; // when true, all blocks need to be page aligned
+ int handle_alignment_; // Alignment to be used when Handles are requested.
+ int handle_alignment_bits_; // log2(handle_alignment_).
+ // The amount of bits required to keep block_size_ (ceil(log2(block_size_))).
+ size_t block_size_bits_;
+
+ void FreeBlocks(); // Frees all except first block
+
+ // This subclass needs to alter permissions for all allocated blocks.
+ friend class ProtectableUnsafeArena;
+
+ DISALLOW_COPY_AND_ASSIGN(BaseArena);
+};
+
+class CTEMPLATE_DLL_DECL UnsafeArena : public BaseArena {
+ public:
+ // Allocates a thread-compatible arena with the specified block size.
+ explicit UnsafeArena(const size_t block_size)
+ : BaseArena(NULL, block_size, false) { }
+ UnsafeArena(const size_t block_size, bool align)
+ : BaseArena(NULL, block_size, align) { }
+
+ // Allocates a thread-compatible arena with the specified block
+ // size. "first_block" must have size "block_size". Memory is
+ // allocated from "first_block" until it is exhausted; after that
+ // memory is allocated by allocating new blocks from the heap.
+ UnsafeArena(char* first_block, const size_t block_size)
+ : BaseArena(first_block, block_size, false) { }
+ UnsafeArena(char* first_block, const size_t block_size, bool align)
+ : BaseArena(first_block, block_size, align) { }
+
+ char* Alloc(const size_t size) {
+ return reinterpret_cast<char*>(GetMemory(size, 1));
+ }
+ void* AllocAligned(const size_t size, const int align) {
+ return GetMemory(size, align);
+ }
+ char* Calloc(const size_t size) {
+ void* return_value = Alloc(size);
+ memset(return_value, 0, size);
+ return reinterpret_cast<char*>(return_value);
+ }
+ void* CallocAligned(const size_t size, const int align) {
+ void* return_value = AllocAligned(size, align);
+ memset(return_value, 0, size);
+ return return_value;
+ }
+ // Free does nothing except for the last piece allocated.
+ void Free(void* memory, size_t size) {
+ ReturnMemory(memory, size);
+ }
+ typedef BaseArena::Handle Handle;
+ char* AllocWithHandle(const size_t size, Handle* handle) {
+ return reinterpret_cast<char*>(GetMemoryWithHandle(size, handle));
+ }
+ virtual char* SlowAlloc(size_t size) { // "slow" 'cause it's virtual
+ return Alloc(size);
+ }
+ virtual void SlowFree(void* memory, size_t size) { // "slow" 'cause it's virt
+ Free(memory, size);
+ }
+ virtual char* SlowRealloc(char* memory, size_t old_size, size_t new_size) {
+ return Realloc(memory, old_size, new_size);
+ }
+ virtual char* SlowAllocWithHandle(const size_t size, Handle* handle) {
+ return AllocWithHandle(size, handle);
+ }
+
+ char* Memdup(const char* s, size_t bytes) {
+ char* newstr = Alloc(bytes);
+ memcpy(newstr, s, bytes);
+ return newstr;
+ }
+ char* MemdupPlusNUL(const char* s, size_t bytes) { // like "string(s, len)"
+ char* newstr = Alloc(bytes+1);
+ memcpy(newstr, s, bytes);
+ newstr[bytes] = '\0';
+ return newstr;
+ }
+ Handle MemdupWithHandle(const char* s, size_t bytes) {
+ Handle handle;
+ char* newstr = AllocWithHandle(bytes, &handle);
+ memcpy(newstr, s, bytes);
+ return handle;
+ }
+ char* Strdup(const char* s) {
+ return Memdup(s, strlen(s) + 1);
+ }
+ // Unlike libc's strncpy, I always NUL-terminate. libc's semantics are dumb.
+ // This will allocate at most n+1 bytes (+1 is for the NULL terminator).
+ char* Strndup(const char* s, size_t n) {
+ // Use memchr so we don't walk past n.
+ // We can't use the one in //strings since this is the base library,
+ // so we have to reinterpret_cast from the libc void *.
+ const char* eos = reinterpret_cast<const char*>(memchr(s, '\0', n));
+ // if no null terminator found, use full n
+ const size_t bytes = (eos == NULL) ? n + 1 : eos - s + 1;
+ char* ret = Memdup(s, bytes);
+ ret[bytes-1] = '\0'; // make sure the string is NUL-terminated
+ return ret;
+ }
+
+ // You can realloc a previously-allocated string either bigger or smaller.
+ // We can be more efficient if you realloc a string right after you allocate
+ // it (eg allocate way-too-much space, fill it, realloc to just-big-enough)
+ char* Realloc(char* s, size_t oldsize, size_t newsize);
+ // If you know the new size is smaller (or equal), you don't need to know
+ // oldsize. We don't check that newsize is smaller, so you'd better be sure!
+ char* Shrink(char* s, size_t newsize) {
+ AdjustLastAlloc(s, newsize); // reclaim space if we can
+ return s; // never need to move if we go smaller
+ }
+
+ // We make a copy so you can keep track of status at a given point in time
+ Status status() const { return status_; }
+
+ // Number of bytes remaining before the arena has to allocate another block.
+ size_t bytes_until_next_allocation() const { return remaining_; }
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(UnsafeArena);
+};
+
+
+
+// we inherit from BaseArena instead of UnsafeArena so that we don't need
+// virtual methods for allocation/deallocation. This means, however,
+// I have to copy the definitions of strdup, strndup, etc. :-(
+
+class CTEMPLATE_DLL_DECL SafeArena : public BaseArena {
+ public:
+ // Allocates a thread-safe arena with the specified block size.
+ explicit SafeArena(const size_t block_size)
+ : BaseArena(NULL, block_size, false) { }
+
+ // Allocates a thread-safe arena with the specified block size.
+ // "first_block" must have size "block_size". Memory is allocated
+ // from "first_block" until it is exhausted; after that memory is
+ // allocated by allocating new blocks from the heap.
+ SafeArena(char* first_block, const size_t block_size)
+ : BaseArena(first_block, block_size, false) { }
+
+ virtual void Reset() LOCKS_EXCLUDED(mutex_) {
+ MutexLock lock(&mutex_); // in case two threads Reset() at same time
+ BaseArena::Reset();
+ }
+
+ char* Alloc(const size_t size) LOCKS_EXCLUDED(mutex_) {
+ MutexLock lock(&mutex_);
+ return reinterpret_cast<char*>(GetMemory(size, 1));
+ }
+ void* AllocAligned(const size_t size, const int align)
+ LOCKS_EXCLUDED(mutex_) {
+ MutexLock lock(&mutex_);
+ return GetMemory(size, align);
+ }
+ char* Calloc(const size_t size) {
+ void* return_value = Alloc(size);
+ memset(return_value, 0, size);
+ return reinterpret_cast<char*>(return_value);
+ }
+ void* CallocAligned(const size_t size, const int align) {
+ void* return_value = AllocAligned(size, align);
+ memset(return_value, 0, size);
+ return return_value;
+ }
+ // Free does nothing except for the last piece allocated.
+ void Free(void* memory, size_t size) LOCKS_EXCLUDED(mutex_) {
+ MutexLock lock(&mutex_);
+ ReturnMemory(memory, size);
+ }
+ typedef BaseArena::Handle Handle;
+ char* AllocWithHandle(const size_t size, Handle* handle)
+ LOCKS_EXCLUDED(mutex_) {
+ MutexLock lock(&mutex_);
+ return reinterpret_cast<char*>(GetMemoryWithHandle(size, handle));
+ }
+ virtual char* SlowAlloc(size_t size) { // "slow" 'cause it's virtual
+ return Alloc(size);
+ }
+ virtual void SlowFree(void* memory, size_t size) { // "slow" 'cause it's virt
+ Free(memory, size);
+ }
+ virtual char* SlowRealloc(char* memory, size_t old_size, size_t new_size) {
+ return Realloc(memory, old_size, new_size);
+ }
+ virtual char* SlowAllocWithHandle(const size_t size, Handle* handle) {
+ return AllocWithHandle(size, handle);
+ }
+
+ char* Memdup(const char* s, size_t bytes) {
+ char* newstr = Alloc(bytes);
+ memcpy(newstr, s, bytes);
+ return newstr;
+ }
+ char* MemdupPlusNUL(const char* s, size_t bytes) { // like "string(s, len)"
+ char* newstr = Alloc(bytes+1);
+ memcpy(newstr, s, bytes);
+ newstr[bytes] = '\0';
+ return newstr;
+ }
+ Handle MemdupWithHandle(const char* s, size_t bytes) {
+ Handle handle;
+ char* newstr = AllocWithHandle(bytes, &handle);
+ memcpy(newstr, s, bytes);
+ return handle;
+ }
+ char* Strdup(const char* s) {
+ return Memdup(s, strlen(s) + 1);
+ }
+ // Unlike libc's strncpy, I always NUL-terminate. libc's semantics are dumb.
+ // This will allocate at most n+1 bytes (+1 is for the NULL terminator).
+ char* Strndup(const char* s, size_t n) {
+ // Use memchr so we don't walk past n.
+ // We can't use the one in //strings since this is the base library,
+ // so we have to reinterpret_cast from the libc void *.
+ const char* eos = reinterpret_cast<const char*>(memchr(s, '\0', n));
+ // if no null terminator found, use full n
+ const size_t bytes = (eos == NULL) ? n + 1 : eos - s + 1;
+ char* ret = Memdup(s, bytes);
+ ret[bytes-1] = '\0'; // make sure the string is NUL-terminated
+ return ret;
+ }
+
+ // You can realloc a previously-allocated string either bigger or smaller.
+ // We can be more efficient if you realloc a string right after you allocate
+ // it (eg allocate way-too-much space, fill it, realloc to just-big-enough)
+ char* Realloc(char* s, size_t oldsize, size_t newsize)
+ LOCKS_EXCLUDED(mutex_);
+ // If you know the new size is smaller (or equal), you don't need to know
+ // oldsize. We don't check that newsize is smaller, so you'd better be sure!
+ char* Shrink(char* s, size_t newsize) LOCKS_EXCLUDED(mutex_) {
+ MutexLock lock(&mutex_);
+ AdjustLastAlloc(s, newsize); // reclaim space if we can
+ return s; // we never need to move if we go smaller
+ }
+
+ Status status() LOCKS_EXCLUDED(mutex_) {
+ MutexLock lock(&mutex_);
+ return status_;
+ }
+
+ // Number of bytes remaining before the arena has to allocate another block.
+ size_t bytes_until_next_allocation() LOCKS_EXCLUDED(mutex_) {
+ MutexLock lock(&mutex_);
+ return remaining_;
+ }
+
+ protected:
+ Mutex mutex_;
+
+ private:
+ DISALLOW_COPY_AND_ASSIGN(SafeArena);
+};
+
+}
+
+#endif // BASE_ARENA_H_
diff --git a/src/base/fileutil.h b/src/base/fileutil.h
new file mode 100644
index 0000000..4a207bb
--- /dev/null
+++ b/src/base/fileutil.h
@@ -0,0 +1,106 @@
+// Copyright (c) 2011, 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: csilvers@google.com (Craig Silverstein)
+//
+// A tiny wrapper around struct stat and FILE*.
+
+#ifndef TEMPLATE_OPENSOURCE_FILEUTIL_H_
+#define TEMPLATE_OPENSOURCE_FILEUTIL_H_
+
+#include <config.h>
+#include <stdio.h>
+#include <sys/stat.h>
+#include <time.h>
+#ifdef HAVE_UNISTD_H
+# include <unistd.h>
+#endif
+#include <string>
+
+namespace ctemplate {
+
+class FileStat {
+ public:
+ time_t mtime;
+ off_t length;
+ bool IsDirectory() { return S_ISDIR(internal_statbuf.st_mode); }
+
+ private:
+ friend class File;
+ struct stat internal_statbuf;
+};
+
+class File {
+ public:
+ static bool Stat(const std::string& filename, FileStat* statbuf) {
+ if (stat(filename.c_str(), &statbuf->internal_statbuf) != 0)
+ return false;
+ statbuf->mtime = statbuf->internal_statbuf.st_mtime;
+ statbuf->length = statbuf->internal_statbuf.st_size;
+ return true;
+ }
+
+ static bool Readable(const char* filename) {
+ return access(filename, R_OK) == 0;
+ }
+
+ static File* Open(const char* filename, const char* mode) {
+ char binary_mode[3];
+ const char* mode_to_use = mode;
+ if ((mode[0] == 'r' || mode[0] == 'w') && mode[1] == '\0') {
+ // We add a 'b' to make sure we do the right thing even on
+ // Windows. On unix, this will be a noop.
+ binary_mode[0] = mode[0];
+ binary_mode[1] = 'b';
+ binary_mode[2] = '\0';
+ mode_to_use = binary_mode;
+ }
+ FILE* fp = fopen(filename, mode_to_use);
+ if (!fp) return NULL;
+ return new File(fp);
+ }
+
+ size_t Read(char* buf, size_t size) {
+ return fread(buf, 1, size, fp_);
+ }
+
+ void Close() {
+ fclose(fp_);
+ delete this; // naughty naughty!
+ }
+
+ private:
+ explicit File(FILE* fp) : fp_(fp) { }
+ FILE* fp_;
+};
+
+}
+
+#endif // TEMPLATE_OPENSOURCE_FILEUTIL_H_
diff --git a/src/base/macros.h b/src/base/macros.h
new file mode 100644
index 0000000..9d0327c
--- /dev/null
+++ b/src/base/macros.h
@@ -0,0 +1,114 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+// Author: csilvers@google.com (Craig Silverstein)
+//
+// Provides macros and typedefs based on config.h settings.
+// Provides the following macros:
+// UNALIGNED_LOAD32 (may be an inline function on some architectures)
+// and the following typedefs:
+// uint32
+// uint64
+
+#ifndef CTEMPLATE_MACROS_H_
+#define CTEMPLATE_MACROS_H_
+
+#include <config.h>
+#ifdef HAVE_STDINT_H
+#include <stdint.h> // the normal place uint32_t is defined
+#endif
+#ifdef HAVE_SYS_TYPES_H
+#include <sys/types.h> // the normal place u_int32_t is defined
+#endif
+#ifdef HAVE_INTTYPES_H
+#ifdef HAVE_INTTYPES_H
+# include <inttypes.h>
+#endif // a third place for uint32_t or u_int32_t
+#endif
+
+#if defined(HAVE_U_INT32_T)
+typedef u_int32_t uint32;
+#elif defined(HAVE_UINT32_T)
+typedef uint32_t uint32;
+#elif defined(HAVE___INT32)
+typedef unsigned __int32 uint32;
+#endif
+
+#if defined(HAVE_U_INT64_T)
+typedef u_int64_t uint64;
+#elif defined(HAVE_UINT64_T)
+typedef uint64_t uint64;
+#elif defined(HAVE___INT64)
+typedef unsigned __int64 uint64;
+#endif
+
+
+// This is all to figure out endian-ness and byte-swapping on various systems
+#if defined(HAVE_ENDIAN_H)
+#include <endian.h> // for the __BYTE_ORDER use below
+#elif defined(HAVE_SYS_ENDIAN_H)
+#include <sys/endian.h> // location on FreeBSD
+#elif defined(HAVE_MACHINE_ENDIAN_H)
+#include <machine/endian.h> // location on OS X
+#endif
+#if defined(HAVE_SYS_BYTEORDER_H)
+#include <sys/byteorder.h> // BSWAP_32 on Solaris 10
+#endif
+#ifdef HAVE_SYS_ISA_DEFS_H
+#include <sys/isa_defs.h> // _BIG_ENDIAN/_LITTLE_ENDIAN on Solaris 10
+#endif
+
+// MurmurHash does a lot of 4-byte unaligned integer access. It
+// interprets these integers in little-endian order. This is perfect
+// on x86, for which this is a natural memory access; for other systems
+// we do what we can to make this as efficient as possible.
+#if defined(HAVE_BYTESWAP_H)
+# include <byteswap.h> // GNU (especially linux)
+# define BSWAP32(x) bswap_32(x)
+#elif defined(HAVE_LIBKERN_OSBYTEORDER_H)
+# include <libkern/OSByteOrder.h> // OS X
+# define BSWAP32(x) OSSwapInt32(x)
+#elif defined(bswap32) // FreeBSD
+ // FreeBSD defines bswap32 as a macro in sys/endian.h (already #included)
+# define BSWAP32(x) bswap32(x)
+#elif defined(BSWAP_32) // Solaris 10
+ // Solaris defines BSWSAP_32 as a macro in sys/byteorder.h (already #included)
+# define BSWAP32(x) BSWAP_32(x)
+#elif !defined(BSWAP32)
+# define BSWAP32(x) ((((x) & 0x000000ff) << 24) | \
+ (((x) & 0x0000ff00) << 8) | \
+ (((x) & 0x00ff0000) >> 8) | \
+ (((x) & 0xff000000) >> 24));
+#else
+# define CTEMPLATE_BSWAP32_ALREADY_DEFINED
+#endif
+
+#if defined(__i386__) || defined(__x86_64__) || defined(_M_IX86) || defined(_M_X64)
+ // We know they allow unaligned memory access and are little-endian
+# define UNALIGNED_LOAD32(_p) (*reinterpret_cast<const uint32 *>(_p))
+#elif defined(__ppc__) || defined(__ppc64__)
+ // We know they allow unaligned memory access and are big-endian
+# define UNALIGNED_LOAD32(_p) BSWAP32(*reinterpret_cast<const uint32 *>(_p))
+#elif (BYTE_ORDER == 1234) || (_BYTE_ORDER == 1234) || defined(_LITTLE_ENDIAN)
+ // Use memcpy to align the memory properly
+ inline uint32 UNALIGNED_LOAD32(const void *p) {
+ uint32 t;
+ memcpy(&t, p, sizeof(t));
+ return t;
+ }
+#elif (BYTE_ORDER == 4321) || (_BYTE_ORDER == 4321) || defined(_BIG_ENDIAN)
+ inline uint32 UNALIGNED_LOAD32(const void *p) {
+ uint32 t;
+ memcpy(&t, p, sizeof(t));
+ return BSWAP32(t);
+ }
+#else
+ // Means we can't find find endian.h on this machine:
+# error Need to define UNALIGNED_LOAD32 for this architecture
+#endif
+
+#ifndef CTEMPLATE_BSWAP32_ALREADY_DEFINED
+# undef BSWAP32 // don't leak outside this file
+#else
+# undef CTEMPLATE_BSWAP32_ALREADY_DEFINED // just cleaning up
+#endif
+
+#endif // CTEMPLATE_MACROS_H_
diff --git a/src/base/manual_constructor.h b/src/base/manual_constructor.h
new file mode 100644
index 0000000..a5d430c
--- /dev/null
+++ b/src/base/manual_constructor.h
@@ -0,0 +1,237 @@
+// 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)
+//
+// ManualConstructor statically-allocates space in which to store some
+// object, but does not initialize it. You can then call the constructor
+// and destructor for the object yourself as you see fit. This is useful
+// for memory management optimizations, where you want to initialize and
+// destroy an object multiple times but only allocate it once.
+//
+// (When I say ManualConstructor statically allocates space, I mean that
+// the ManualConstructor object itself is forced to be the right size.)
+//
+// For example usage, check out util/gtl/small_map.h.
+
+#ifndef UTIL_GTL_MANUAL_CONSTRUCTOR_H_
+#define UTIL_GTL_MANUAL_CONSTRUCTOR_H_
+
+#include <config.h>
+
+namespace ctemplate {
+
+namespace util {
+namespace gtl {
+namespace internal {
+
+//
+// Provides a char array with the exact same alignment as another type. The
+// first parameter must be a complete type, the second parameter is how many
+// of that type to provide space for.
+//
+// UTIL_GTL_ALIGNED_CHAR_ARRAY(struct stat, 16) storage_;
+//
+// Because MSVC and older GCCs require that the argument to their alignment
+// construct to be a literal constant integer, we use a template instantiated
+// at all the possible powers of two.
+#ifndef SWIG
+template<int alignment, int size> struct AlignType { };
+template<int size> struct AlignType<0, size> { typedef char result[size]; };
+#if defined(_MSC_VER)
+#define UTIL_GTL_ALIGN_ATTRIBUTE(X) __declspec(align(X))
+#define UTIL_GTL_ALIGN_OF(T) __alignof(T)
+#elif defined(__GNUC__) || defined(__APPLE__) || defined(__INTEL_COMPILER) \
+ || defined(__nacl__)
+#define UTIL_GTL_ALIGN_ATTRIBUTE(X) __attribute__((aligned(X)))
+#define UTIL_GTL_ALIGN_OF(T) __alignof__(T)
+#endif
+
+#if defined(UTIL_GTL_ALIGN_ATTRIBUTE)
+
+#define UTIL_GTL_ALIGNTYPE_TEMPLATE(X) \
+ template<int size> struct AlignType<X, size> { \
+ typedef UTIL_GTL_ALIGN_ATTRIBUTE(X) char result[size]; \
+ }
+
+UTIL_GTL_ALIGNTYPE_TEMPLATE(1);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(2);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(4);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(8);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(16);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(32);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(64);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(128);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(256);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(512);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(1024);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(2048);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(4096);
+UTIL_GTL_ALIGNTYPE_TEMPLATE(8192);
+// Any larger and MSVC++ will complain.
+
+#define UTIL_GTL_ALIGNED_CHAR_ARRAY(T, Size) \
+ typename util::gtl::internal::AlignType<UTIL_GTL_ALIGN_OF(T), \
+ sizeof(T) * Size>::result
+
+#undef UTIL_GTL_ALIGNTYPE_TEMPLATE
+#undef UTIL_GTL_ALIGN_ATTRIBUTE
+
+#else // defined(UTIL_GTL_ALIGN_ATTRIBUTE)
+#error "You must define UTIL_GTL_ALIGNED_CHAR_ARRAY for your compiler."
+#endif // defined(UTIL_GTL_ALIGN_ATTRIBUTE)
+
+#else // !SWIG
+
+// SWIG can't represent alignment and doesn't care about alignment on data
+// members (it works fine without it).
+template<typename Size>
+struct AlignType { typedef char result[Size]; };
+#define UTIL_GTL_ALIGNED_CHAR_ARRAY(T, Size) \
+ util::gtl::internal::AlignType<Size * sizeof(T)>::result
+
+#endif // !SWIG
+
+} // namespace internal
+} // namespace gtl
+} // namespace util
+
+template <typename Type>
+class ManualConstructor {
+ public:
+ // No constructor or destructor because one of the most useful uses of
+ // this class is as part of a union, and members of a union cannot have
+ // constructors or destructors. And, anyway, the whole point of this
+ // class is to bypass these.
+
+ inline Type* get() {
+ return reinterpret_cast<Type*>(space_);
+ }
+ inline const Type* get() const {
+ return reinterpret_cast<const Type*>(space_);
+ }
+
+ inline Type* operator->() { return get(); }
+ inline const Type* operator->() const { return get(); }
+
+ inline Type& operator*() { return *get(); }
+ inline const Type& operator*() const { return *get(); }
+
+ // You can pass up to four constructor arguments as arguments of Init().
+ inline void Init() {
+ new(space_) Type;
+ }
+
+ template <typename T1>
+ inline void Init(const T1& p1) {
+ new(space_) Type(p1);
+ }
+
+ template <typename T1, typename T2>
+ inline void Init(const T1& p1, const T2& p2) {
+ new(space_) Type(p1, p2);
+ }
+
+ template <typename T1, typename T2, typename T3>
+ inline void Init(const T1& p1, const T2& p2, const T3& p3) {
+ new(space_) Type(p1, p2, p3);
+ }
+
+ template <typename T1, typename T2, typename T3, typename T4>
+ inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4) {
+ new(space_) Type(p1, p2, p3, p4);
+ }
+
+ template <typename T1, typename T2, typename T3, typename T4, typename T5>
+ inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
+ const T5& p5) {
+ new(space_) Type(p1, p2, p3, p4, p5);
+ }
+
+ template <typename T1, typename T2, typename T3, typename T4, typename T5,
+ typename T6>
+ inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
+ const T5& p5, const T6& p6) {
+ new(space_) Type(p1, p2, p3, p4, p5, p6);
+ }
+
+ template <typename T1, typename T2, typename T3, typename T4, typename T5,
+ typename T6, typename T7>
+ inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
+ const T5& p5, const T6& p6, const T7& p7) {
+ new(space_) Type(p1, p2, p3, p4, p5, p6, p7);
+ }
+
+ template <typename T1, typename T2, typename T3, typename T4, typename T5,
+ typename T6, typename T7, typename T8>
+ inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
+ const T5& p5, const T6& p6, const T7& p7, const T8& p8) {
+ new(space_) Type(p1, p2, p3, p4, p5, p6, p7, p8);
+ }
+
+ template <typename T1, typename T2, typename T3, typename T4, typename T5,
+ typename T6, typename T7, typename T8, typename T9>
+ inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
+ const T5& p5, const T6& p6, const T7& p7, const T8& p8,
+ const T9& p9) {
+ new(space_) Type(p1, p2, p3, p4, p5, p6, p7, p8, p9);
+ }
+
+ template <typename T1, typename T2, typename T3, typename T4, typename T5,
+ typename T6, typename T7, typename T8, typename T9, typename T10>
+ inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
+ const T5& p5, const T6& p6, const T7& p7, const T8& p8,
+ const T9& p9, const T10& p10) {
+ new(space_) Type(p1, p2, p3, p4, p5, p6, p7, p8, p9, p10);
+ }
+
+ template <typename T1, typename T2, typename T3, typename T4, typename T5,
+ typename T6, typename T7, typename T8, typename T9, typename T10,
+ typename T11>
+ inline void Init(const T1& p1, const T2& p2, const T3& p3, const T4& p4,
+ const T5& p5, const T6& p6, const T7& p7, const T8& p8,
+ const T9& p9, const T10& p10, const T11& p11) {
+ new(space_) Type(p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11);
+ }
+
+ inline void Destroy() {
+ get()->~Type();
+ }
+
+ private:
+ UTIL_GTL_ALIGNED_CHAR_ARRAY(Type, 1) space_;
+};
+
+#undef UTIL_GTL_ALIGNED_CHAR_ARRAY
+#undef UTIL_GTL_ALIGN_OF
+
+}
+
+#endif // UTIL_GTL_MANUAL_CONSTRUCTOR_H_
diff --git a/src/base/mutex.h b/src/base/mutex.h
new file mode 100644
index 0000000..3962a6d
--- /dev/null
+++ b/src/base/mutex.h
@@ -0,0 +1,408 @@
+// Copyright (c) 2007, 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.
+//
+// ---
+//
+// A simple mutex wrapper, supporting locks and read-write locks.
+// You should assume the locks are *not* re-entrant.
+//
+// To use: you should define the following macros in your configure.ac:
+// ACX_PTHREAD
+// AC_RWLOCK
+// The latter is defined in ../autoconf.
+//
+// This class is meant to be internal-only and should be wrapped by an
+// internal namespace. Before you use this module, please give the
+// name of your internal namespace for this module. Or, if you want
+// to expose it, you'll want to move it to the Google namespace. We
+// cannot put this class in global namespace because there can be some
+// problems when we have multiple versions of Mutex in each shared object.
+//
+// NOTE: by default, we have #ifdef'ed out the TryLock() method.
+// This is for two reasons:
+// 1) TryLock() under Windows is a bit annoying (it requires a
+// #define to be defined very early).
+// 2) TryLock() is broken for NO_THREADS mode, at least in NDEBUG
+// mode.
+// If you need TryLock(), and either these two caveats are not a
+// problem for you, or you're willing to work around them, then
+// feel free to #define GMUTEX_TRYLOCK, or to remove the #ifdefs
+// in the code below.
+//
+// CYGWIN NOTE: Cygwin support for rwlock seems to be buggy:
+// http://www.cygwin.com/ml/cygwin/2008-12/msg00017.html
+// Because of that, we might as well use windows locks for
+// cygwin. They seem to be more reliable than the cygwin pthreads layer.
+//
+// TRICKY IMPLEMENTATION NOTE:
+// This class is designed to be safe to use during
+// dynamic-initialization -- that is, by global constructors that are
+// run before main() starts. The issue in this case is that
+// dynamic-initialization happens in an unpredictable order, and it
+// could be that someone else's dynamic initializer could call a
+// function that tries to acquire this mutex -- but that all happens
+// before this mutex's constructor has run. (This can happen even if
+// the mutex and the function that uses the mutex are in the same .cc
+// file.) Basically, because Mutex does non-trivial work in its
+// constructor, it's not, in the naive implementation, safe to use
+// before dynamic initialization has run on it.
+//
+// The solution used here is to pair the actual mutex primitive with a
+// bool that is set to true when the mutex is dynamically initialized.
+// (Before that it's false.) Then we modify all mutex routines to
+// look at the bool, and not try to lock/unlock until the bool makes
+// it to true (which happens after the Mutex constructor has run.)
+//
+// This works because before main() starts -- particularly, during
+// dynamic initialization -- there are no threads, so a) it's ok that
+// the mutex operations are a no-op, since we don't need locking then
+// anyway; and b) we can be quite confident our bool won't change
+// state between a call to Lock() and a call to Unlock() (that would
+// require a global constructor in one translation unit to call Lock()
+// and another global constructor in another translation unit to call
+// Unlock() later, which is pretty perverse).
+//
+// That said, it's tricky, and can conceivably fail; it's safest to
+// avoid trying to acquire a mutex in a global constructor, if you
+// can. One way it can fail is that a really smart compiler might
+// initialize the bool to true at static-initialization time (too
+// early) rather than at dynamic-initialization time. To discourage
+// that, we set is_safe_ to true in code (not the constructor
+// colon-initializer) and set it to true via a function that always
+// evaluates to true, but that the compiler can't know always
+// evaluates to true. This should be good enough.
+//
+// A related issue is code that could try to access the mutex
+// after it's been destroyed in the global destructors (because
+// the Mutex global destructor runs before some other global
+// destructor, that tries to acquire the mutex). The way we
+// deal with this is by taking a constructor arg that global
+// mutexes should pass in, that causes the destructor to do no
+// work. We still depend on the compiler not doing anything
+// weird to a Mutex's memory after it is destroyed, but for a
+// static global variable, that's pretty safe.
+
+#ifndef GOOGLE_MUTEX_H_
+#define GOOGLE_MUTEX_H_
+
+#include <config.h>
+#if defined(NO_THREADS)
+ typedef int MutexType; // to keep a lock-count
+#elif defined(_WIN32) || defined(__CYGWIN32__) || defined(__CYGWIN64__)
+# ifndef WIN32_LEAN_AND_MEAN
+# define WIN32_LEAN_AND_MEAN // We only need minimal includes
+# endif
+# ifndef NOMINMAX
+# define NOMINMAX // Don't want windows to override min()/max()
+# endif
+# ifdef GMUTEX_TRYLOCK
+ // We need Windows NT or later for TryEnterCriticalSection(). If you
+ // don't need that functionality, you can remove these _WIN32_WINNT
+ // lines, and change TryLock() to assert(0) or something.
+# ifndef _WIN32_WINNT
+# define _WIN32_WINNT 0x0400
+# endif
+# endif
+# include <windows.h>
+ typedef CRITICAL_SECTION MutexType;
+#elif defined(HAVE_PTHREAD) && defined(HAVE_RWLOCK)
+ // Needed for pthread_rwlock_*. If it causes problems, you could take it
+ // out, but then you'd have to unset HAVE_RWLOCK (at least on linux -- it
+ // *does* cause problems for FreeBSD, or MacOSX, but isn't needed
+ // for locking there.)
+# ifdef __linux__
+# if _XOPEN_SOURCE < 500 // including not being defined at all
+# undef _XOPEN_SOURCE
+# define _XOPEN_SOURCE 500 // may be needed to get the rwlock calls
+# endif
+# endif
+#if defined(HAVE_PTHREAD) && !defined(NO_THREADS)
+# include <pthread.h>
+#endif
+ typedef pthread_rwlock_t MutexType;
+#elif defined(HAVE_PTHREAD)
+#if defined(HAVE_PTHREAD) && !defined(NO_THREADS)
+# include <pthread.h>
+#endif
+ typedef pthread_mutex_t MutexType;
+#else
+# error Need to implement mutex.h for your architecture, or #define NO_THREADS
+#endif
+
+#include <assert.h>
+#include <stdlib.h> // for abort()
+
+namespace ctemplate {
+
+namespace base {
+// This is used for the single-arg constructor
+enum LinkerInitialized { LINKER_INITIALIZED };
+}
+
+class Mutex {
+ public:
+ // Create a Mutex that is not held by anybody. This constructor is
+ // typically used for Mutexes allocated on the heap or the stack.
+ inline Mutex();
+ // This constructor should be used for global, static Mutex objects.
+ // It inhibits work being done by the destructor, which makes it
+ // safer for code that tries to acqiure this mutex in their global
+ // destructor.
+ inline Mutex(base::LinkerInitialized);
+
+ // Destructor
+ inline ~Mutex();
+
+ inline void Lock(); // Block if needed until free then acquire exclusively
+ inline void Unlock(); // Release a lock acquired via Lock()
+#ifdef GMUTEX_TRYLOCK
+ inline bool TryLock(); // If free, Lock() and return true, else return false
+#endif
+ // Note that on systems that don't support read-write locks, these may
+ // be implemented as synonyms to Lock() and Unlock(). So you can use
+ // these for efficiency, but don't use them anyplace where being able
+ // to do shared reads is necessary to avoid deadlock.
+ inline void ReaderLock(); // Block until free or shared then acquire a share
+ inline void ReaderUnlock(); // Release a read share of this Mutex
+ inline void WriterLock() { Lock(); } // Acquire an exclusive lock
+ inline void WriterUnlock() { Unlock(); } // Release a lock from WriterLock()
+
+ private:
+ MutexType mutex_;
+ // We want to make sure that the compiler sets is_safe_ to true only
+ // when we tell it to, and never makes assumptions is_safe_ is
+ // always true. volatile is the most reliable way to do that.
+ volatile bool is_safe_;
+ // This indicates which constructor was called.
+ bool destroy_;
+
+ inline void SetIsSafe() { is_safe_ = true; }
+
+ // Catch the error of writing Mutex when intending MutexLock.
+ Mutex(Mutex* /*ignored*/) {}
+ // Disallow "evil" constructors
+ Mutex(const Mutex&);
+ void operator=(const Mutex&);
+};
+
+// We will also define GoogleOnceType, GOOGLE_ONCE_INIT, and
+// GoogleOnceInit, which are portable versions of pthread_once_t,
+// PTHREAD_ONCE_INIT, and pthread_once.
+
+// Now the implementation of Mutex for various systems
+#if defined(NO_THREADS)
+
+// When we don't have threads, we can be either reading or writing,
+// but not both. We can have lots of readers at once (in no-threads
+// mode, that's most likely to happen in recursive function calls),
+// but only one writer. We represent this by having mutex_ be -1 when
+// writing and a number > 0 when reading (and 0 when no lock is held).
+//
+// In debug mode, we assert these invariants, while in non-debug mode
+// we do nothing, for efficiency. That's why everything is in an
+// assert.
+
+Mutex::Mutex() : mutex_(0) { }
+Mutex::Mutex(base::LinkerInitialized) : mutex_(0) { }
+Mutex::~Mutex() { assert(mutex_ == 0); }
+void Mutex::Lock() { assert(--mutex_ == -1); }
+void Mutex::Unlock() { assert(mutex_++ == -1); }
+#ifdef GMUTEX_TRYLOCK
+bool Mutex::TryLock() { if (mutex_) return false; Lock(); return true; }
+#endif
+void Mutex::ReaderLock() { assert(++mutex_ > 0); }
+void Mutex::ReaderUnlock() { assert(mutex_-- > 0); }
+
+typedef int GoogleOnceType;
+const GoogleOnceType GOOGLE_ONCE_INIT = 0;
+inline int GoogleOnceInit(GoogleOnceType* once_control,
+ void (*init_routine)(void)) {
+ if ((*once_control)++ == 0)
+ (*init_routine)();
+ return 0;
+}
+
+#elif defined(_WIN32) || defined(__CYGWIN32__) || defined(__CYGWIN64__)
+
+Mutex::Mutex() : destroy_(true) {
+ InitializeCriticalSection(&mutex_);
+ SetIsSafe();
+}
+Mutex::Mutex(base::LinkerInitialized) : destroy_(false) {
+ InitializeCriticalSection(&mutex_);
+ SetIsSafe();
+}
+Mutex::~Mutex() { if (destroy_) DeleteCriticalSection(&mutex_); }
+void Mutex::Lock() { if (is_safe_) EnterCriticalSection(&mutex_); }
+void Mutex::Unlock() { if (is_safe_) LeaveCriticalSection(&mutex_); }
+#ifdef GMUTEX_TRYLOCK
+bool Mutex::TryLock() { return is_safe_ ?
+ TryEnterCriticalSection(&mutex_) != 0 : true; }
+#endif
+void Mutex::ReaderLock() { Lock(); } // we don't have read-write locks
+void Mutex::ReaderUnlock() { Unlock(); }
+
+// We do a simple spinlock for pthread_once_t. See
+// http://www.ddj.com/cpp/199203083?pgno=3
+#ifdef INTERLOCKED_EXCHANGE_NONVOLATILE
+typedef LONG GoogleOnceType;
+#else
+typedef volatile LONG GoogleOnceType;
+#endif
+const GoogleOnceType GOOGLE_ONCE_INIT = 0;
+inline int GoogleOnceInit(GoogleOnceType* once_control,
+ void (*init_routine)(void)) {
+ while (1) {
+ LONG prev = InterlockedCompareExchange(once_control, 1, 0);
+ if (prev == 2) { // We've successfully initted in the past.
+ return 0;
+ } else if (prev == 0) { // No init yet, but we have the lock.
+ (*init_routine)();
+ InterlockedExchange(once_control, 2);
+ return 0;
+ } else { // Someone else is holding the lock, so wait.
+ assert(1 == prev);
+ Sleep(1); // sleep for 1ms
+ }
+ }
+ return 1; // unreachable
+}
+
+#elif defined(HAVE_PTHREAD) && defined(HAVE_RWLOCK)
+
+#define SAFE_PTHREAD(fncall) do { /* run fncall if is_safe_ is true */ \
+ if (is_safe_ && fncall(&mutex_) != 0) abort(); \
+} while (0)
+
+Mutex::Mutex() : destroy_(true) {
+ SetIsSafe();
+ if (is_safe_ && pthread_rwlock_init(&mutex_, NULL) != 0) abort();
+}
+Mutex::Mutex(base::LinkerInitialized) : destroy_(false) {
+ SetIsSafe();
+ if (is_safe_ && pthread_rwlock_init(&mutex_, NULL) != 0) abort();
+}
+Mutex::~Mutex() { if (destroy_) SAFE_PTHREAD(pthread_rwlock_destroy); }
+void Mutex::Lock() { SAFE_PTHREAD(pthread_rwlock_wrlock); }
+void Mutex::Unlock() { SAFE_PTHREAD(pthread_rwlock_unlock); }
+#ifdef GMUTEX_TRYLOCK
+bool Mutex::TryLock() { return is_safe_ ?
+ pthread_rwlock_trywrlock(&mutex_) == 0 : true; }
+#endif
+void Mutex::ReaderLock() { SAFE_PTHREAD(pthread_rwlock_rdlock); }
+void Mutex::ReaderUnlock() { SAFE_PTHREAD(pthread_rwlock_unlock); }
+#undef SAFE_PTHREAD
+
+typedef pthread_once_t GoogleOnceType;
+const GoogleOnceType GOOGLE_ONCE_INIT = PTHREAD_ONCE_INIT;
+inline int GoogleOnceInit(GoogleOnceType* once_control,
+ void (*init_routine)(void)) {
+ return pthread_once(once_control, init_routine);
+}
+
+#elif defined(HAVE_PTHREAD)
+
+#define SAFE_PTHREAD(fncall) do { /* run fncall if is_safe_ is true */ \
+ if (is_safe_ && fncall(&mutex_) != 0) abort(); \
+} while (0)
+
+Mutex::Mutex() : destroy_(true) {
+ SetIsSafe();
+ if (is_safe_ && pthread_mutex_init(&mutex_, NULL) != 0) abort();
+}
+Mutex::Mutex(base::LinkerInitialized) : destroy_(false) {
+ SetIsSafe();
+ if (is_safe_ && pthread_mutex_init(&mutex_, NULL) != 0) abort();
+}
+Mutex::~Mutex() { if (destroy_) SAFE_PTHREAD(pthread_mutex_destroy); }
+void Mutex::Lock() { SAFE_PTHREAD(pthread_mutex_lock); }
+void Mutex::Unlock() { SAFE_PTHREAD(pthread_mutex_unlock); }
+#ifdef GMUTEX_TRYLOCK
+bool Mutex::TryLock() { return is_safe_ ?
+ pthread_mutex_trylock(&mutex_) == 0 : true; }
+#endif
+void Mutex::ReaderLock() { Lock(); }
+void Mutex::ReaderUnlock() { Unlock(); }
+#undef SAFE_PTHREAD
+
+typedef pthread_once_t GoogleOnceType;
+const GoogleOnceType GOOGLE_ONCE_INIT = PTHREAD_ONCE_INIT;
+inline int GoogleOnceInit(GoogleOnceType* once_control,
+ void (*init_routine)(void)) {
+ return pthread_once(once_control, init_routine);
+}
+
+#endif
+
+// --------------------------------------------------------------------------
+// Some helper classes
+
+// MutexLock(mu) acquires mu when constructed and releases it when destroyed.
+class MutexLock {
+ public:
+ explicit MutexLock(Mutex *mu) : mu_(mu) { mu_->Lock(); }
+ ~MutexLock() { mu_->Unlock(); }
+ private:
+ Mutex * const mu_;
+ // Disallow "evil" constructors
+ MutexLock(const MutexLock&);
+ void operator=(const MutexLock&);
+};
+
+// ReaderMutexLock and WriterMutexLock do the same, for rwlocks
+class ReaderMutexLock {
+ public:
+ explicit ReaderMutexLock(Mutex *mu) : mu_(mu) { mu_->ReaderLock(); }
+ ~ReaderMutexLock() { mu_->ReaderUnlock(); }
+ private:
+ Mutex * const mu_;
+ // Disallow "evil" constructors
+ ReaderMutexLock(const ReaderMutexLock&);
+ void operator=(const ReaderMutexLock&);
+};
+
+class WriterMutexLock {
+ public:
+ explicit WriterMutexLock(Mutex *mu) : mu_(mu) { mu_->WriterLock(); }
+ ~WriterMutexLock() { mu_->WriterUnlock(); }
+ private:
+ Mutex * const mu_;
+ // Disallow "evil" constructors
+ WriterMutexLock(const WriterMutexLock&);
+ void operator=(const WriterMutexLock&);
+};
+
+// Catch bug where variable name is omitted, e.g. MutexLock (&mu);
+#define MutexLock(x) COMPILE_ASSERT(0, mutex_lock_decl_missing_var_name)
+#define ReaderMutexLock(x) COMPILE_ASSERT(0, rmutex_lock_decl_missing_var_name)
+#define WriterMutexLock(x) COMPILE_ASSERT(0, wmutex_lock_decl_missing_var_name)
+
+}
+
+#endif /* #define GOOGLE_MUTEX_H__ */
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_
diff --git a/src/base/thread_annotations.h b/src/base/thread_annotations.h
new file mode 100644
index 0000000..b6db61b
--- /dev/null
+++ b/src/base/thread_annotations.h
@@ -0,0 +1,130 @@
+// Copyright (c) 2008, 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.
+// ---
+//
+//
+// This header file contains the macro definitions for thread safety
+// annotations that allow the developers to document the locking policies
+// of their multi-threaded code. The annotations can also help program
+// analysis tools to identify potential thread safety issues.
+//
+//
+// The annotations are implemented using GCC's "attributes" extension.
+// Using the macros defined here instead of the raw GCC attributes allows
+// for portability and future compatibility.
+//
+
+#ifndef BASE_THREAD_ANNOTATIONS_H_
+#define BASE_THREAD_ANNOTATIONS_H_
+
+
+#include <config.h>
+#if defined(__GNUC__) && defined(__SUPPORT_TS_ANNOTATION__) && !defined(SWIG)
+#define THREAD_ANNOTATION_ATTRIBUTE__(x) __attribute__((x))
+#else
+#define THREAD_ANNOTATION_ATTRIBUTE__(x) // no-op
+#endif
+
+
+// Document if a shared variable/field needs to be protected by a lock.
+// GUARDED_BY allows the user to specify a particular lock that should be
+// held when accessing the annotated variable, while GUARDED_VAR only
+// indicates a shared variable should be guarded (by any lock). GUARDED_VAR
+// is primarily used when the client cannot express the name of the lock.
+#define GUARDED_BY(x) THREAD_ANNOTATION_ATTRIBUTE__(guarded_by(x))
+#define GUARDED_VAR THREAD_ANNOTATION_ATTRIBUTE__(guarded)
+
+// Document if the memory location pointed to by a pointer should be guarded
+// by a lock when dereferencing the pointer. Similar to GUARDED_VAR,
+// PT_GUARDED_VAR is primarily used when the client cannot express the name
+// of the lock. Note that a pointer variable to a shared memory location
+// could itself be a shared variable. For example, if a shared global pointer
+// q, which is guarded by mu1, points to a shared memory location that is
+// guarded by mu2, q should be annotated as follows:
+// int *q GUARDED_BY(mu1) PT_GUARDED_BY(mu2);
+#define PT_GUARDED_BY(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(point_to_guarded_by(x))
+#define PT_GUARDED_VAR \
+ THREAD_ANNOTATION_ATTRIBUTE__(point_to_guarded)
+
+// Document the acquisition order between locks that can be held
+// simultaneously by a thread. For any two locks that need to be annotated
+// to establish an acquisition order, only one of them needs the annotation.
+// (i.e. You don't have to annotate both locks with both ACQUIRED_AFTER
+// and ACQUIRED_BEFORE.)
+#define ACQUIRED_AFTER(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(acquired_after(x))
+#define ACQUIRED_BEFORE(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(acquired_before(x))
+
+// The following three annotations document the lock requirements for
+// functions/methods.
+
+// Document if a function expects certain locks to be held before it is called
+#define EXCLUSIVE_LOCKS_REQUIRED(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(exclusive_locks_required(x))
+
+#define SHARED_LOCKS_REQUIRED(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(shared_locks_required(x))
+
+// Document the locks acquired in the body of the function. These locks
+// non-reentrant).
+#define LOCKS_EXCLUDED(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(locks_excluded(x))
+
+// Document the lock the annotated function returns without acquiring it.
+#define LOCK_RETURNED(x) THREAD_ANNOTATION_ATTRIBUTE__(lock_returned(x))
+
+// Document if a class/type is a lockable type (such as the Mutex class).
+#define LOCKABLE THREAD_ANNOTATION_ATTRIBUTE__(lockable)
+
+// Document if a class is a scoped lockable type (such as the MutexLock class).
+#define SCOPED_LOCKABLE THREAD_ANNOTATION_ATTRIBUTE__(scoped_lockable)
+
+// The following annotations specify lock and unlock primitives.
+#define EXCLUSIVE_LOCK_FUNCTION(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(exclusive_lock(x))
+
+#define SHARED_LOCK_FUNCTION(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(shared_lock(x))
+
+#define EXCLUSIVE_TRYLOCK_FUNCTION(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(exclusive_trylock(x))
+
+#define SHARED_TRYLOCK_FUNCTION(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(shared_trylock(x))
+
+#define UNLOCK_FUNCTION(x) \
+ THREAD_ANNOTATION_ATTRIBUTE__(unlock(x))
+
+// An escape hatch for thread safety analysis to ignore the annotated function.
+#define NO_THREAD_SAFETY_ANALYSIS \
+ THREAD_ANNOTATION_ATTRIBUTE__(no_thread_safety_analysis)
+
+#endif // BASE_THREAD_ANNOTATIONS_H_
diff --git a/src/base/util.h b/src/base/util.h
new file mode 100644
index 0000000..2d9f1db
--- /dev/null
+++ b/src/base/util.h
@@ -0,0 +1,235 @@
+// Copyright (c) 2011, 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.
+// ---
+//
+// Some generically useful utility routines that in google-land would
+// be their own projects. We make a shortened version here.
+
+#ifndef TEMPLATE_UTIL_H_
+#define TEMPLATE_UTIL_H_
+
+#include <config.h>
+#include <ctype.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <iostream>
+#include <string>
+#include <utility>
+#include <vector>
+
+// -- utility macros ---------------------------------------------------------
+
+#define DISALLOW_COPY_AND_ASSIGN(TypeName) \
+ TypeName(const TypeName&); \
+ void operator=(const TypeName&)
+
+// Starting with Visual C++ 2005, WinNT.h includes ARRAYSIZE.
+#if !defined(_MSC_VER) || _MSC_VER < 1400
+#define ARRAYSIZE(a) \
+ ((sizeof(a) / sizeof(*(a))) / \
+ static_cast<size_t>(!(sizeof(a) % sizeof(*(a)))))
+#endif
+
+template<typename To, typename From> // use like this: down_cast<T*>(foo);
+inline To down_cast(From* f) { // so we only accept pointers
+ return static_cast<To>(f);
+}
+
+// -- CHECK macros ---------------------------------------------------------
+
+// CHECK dies with a fatal error if condition is not true. It is *not*
+// controlled by NDEBUG, so the check will be executed regardless of
+// compilation mode. Therefore, it is safe to do things like:
+// CHECK(fp->Write(x) == 4)
+// We allow stream-like objects after this for debugging, but they're ignored.
+#define CHECK(condition) \
+ if (true) { \
+ if (!(condition)) { \
+ fprintf(stderr, "Check failed: %s\n", #condition); \
+ exit(1); \
+ } \
+ } else std::cerr << ""
+
+#define CHECK_OP(op, val1, val2) \
+ if (true) { \
+ if (!((val1) op (val2))) { \
+ fprintf(stderr, "Check failed: %s %s %s\n", #val1, #op, #val2); \
+ exit(1); \
+ } \
+ } else std::cerr << ""
+
+#define CHECK_EQ(val1, val2) CHECK_OP(==, val1, val2)
+#define CHECK_NE(val1, val2) CHECK_OP(!=, val1, val2)
+#define CHECK_LE(val1, val2) CHECK_OP(<=, val1, val2)
+#define CHECK_LT(val1, val2) CHECK_OP(< , val1, val2)
+#define CHECK_GE(val1, val2) CHECK_OP(>=, val1, val2)
+#define CHECK_GT(val1, val2) CHECK_OP(> , val1, val2)
+// Synonyms for CHECK_* that are used in some unittests.
+#define EXPECT_EQ(val1, val2) CHECK_EQ(val1, val2)
+#define EXPECT_NE(val1, val2) CHECK_NE(val1, val2)
+#define EXPECT_LE(val1, val2) CHECK_LE(val1, val2)
+#define EXPECT_LT(val1, val2) CHECK_LT(val1, val2)
+#define EXPECT_GE(val1, val2) CHECK_GE(val1, val2)
+#define EXPECT_GT(val1, val2) CHECK_GT(val1, val2)
+#define EXPECT_TRUE(cond) CHECK(cond)
+#define EXPECT_FALSE(cond) CHECK(!(cond))
+#define EXPECT_STREQ(a, b) CHECK(strcmp(a, b) == 0)
+#define ASSERT_TRUE(cond) EXPECT_TRUE(cond)
+// LOG(FATAL) is an alias for CHECK(FALSE). We define FATAL, but no
+// other value that is reasonable inside LOG(), so the compile will
+// fail if someone tries to use LOG(DEBUG) or the like.
+#define LOG(x) INTERNAL_DO_LOG_ ## x
+#define INTERNAL_DO_LOG_FATAL CHECK(false)
+
+// These are used only in debug mode.
+#ifdef NDEBUG
+#define DCHECK(condition) CHECK(condition)
+#define DCHECK_EQ(val1, val2) CHECK_EQ(val1, val2)
+#define DCHECK_NE(val1, val2) CHECK_NE(val1, val2)
+#define DCHECK_LE(val1, val2) CHECK_LE(val1, val2)
+#define DCHECK_LT(val1, val2) CHECK_LT(val1, val2)
+#define DCHECK_GE(val1, val2) CHECK_GE(val1, val2)
+#define DCHECK_GT(val1, val2) CHECK_GT(val1, val2)
+#else
+#define DCHECK(condition) if (true) {} else std::cerr << ""
+#define DCHECK_EQ(val1, val2) if (true) {} else std::cerr << ""
+#define DCHECK_NE(val1, val2) if (true) {} else std::cerr << ""
+#define DCHECK_LE(val1, val2) if (true) {} else std::cerr << ""
+#define DCHECK_LT(val1, val2) if (true) {} else std::cerr << ""
+#define DCHECK_GE(val1, val2) if (true) {} else std::cerr << ""
+#define DCHECK_GT(val1, val2) if (true) {} else std::cerr << ""
+#endif
+
+#define PCHECK(cond) CHECK(cond) << ": " << strerror(errno)
+#define PFATAL(s) do { perror(s); exit(1); } while (0)
+
+// -- testing-related macros --------------------------------------------------
+
+// Call this in a .cc file where you will later call RUN_ALL_TESTS in main().
+#define TEST_INIT \
+ static std::vector<void (*)()> g_testlist; /* the tests to run */ \
+ static int RUN_ALL_TESTS() { \
+ std::vector<void (*)()>::const_iterator it; \
+ for (it = g_testlist.begin(); it != g_testlist.end(); ++it) { \
+ (*it)(); /* The test will error-exit if there's a problem. */ \
+ } \
+ fprintf(stderr, "\nPassed %d tests\n\nPASS\n", \
+ static_cast<int>(g_testlist.size())); \
+ return 0; \
+ }
+
+#define TEST(a, b) \
+ class Test_##a##_##b { \
+ public: \
+ Test_##a##_##b() { g_testlist.push_back(&Run); } \
+ static void Run(); \
+ }; \
+ static Test_##a##_##b g_test_##a##_##b; \
+ void Test_##a##_##b::Run()
+
+// This is a dummy class that eases the google->opensource transition.
+namespace testing {
+class Test {};
+}
+
+// -- template-related macros ----------------------------------------------
+
+#ifndef DEFAULT_TEMPLATE_ROOTDIR
+# define DEFAULT_TEMPLATE_ROOTDIR "."
+#endif
+
+// -- string-related functions ----------------------------------------------
+
+inline bool safe_strto32(const std::string& s, int* i) {
+ char* error_pos;
+ if (s.empty()) return false; // no input at all
+ errno = 0; // just to be sure
+ *i = strtol(s.c_str(), &error_pos, 10);
+ return *error_pos == '\0' && errno == 0;
+}
+
+inline int atoi32(const char* s) {
+ return atoi(s);
+}
+
+inline void StripWhiteSpace(std::string* str) {
+ int str_length = str->length();
+
+ // Strip off leading whitespace.
+ int first = 0;
+ while (first < str_length && isspace(str->at(first))) {
+ ++first;
+ }
+ // If entire string is white space.
+ if (first == str_length) {
+ str->clear();
+ return;
+ }
+ if (first > 0) {
+ str->erase(0, first);
+ str_length -= first;
+ }
+
+ // Strip off trailing whitespace.
+ int last = str_length - 1;
+ while (last >= 0 && isspace(str->at(last))) {
+ --last;
+ }
+ if (last != (str_length - 1) && last >= 0) {
+ str->erase(last + 1, std::string::npos);
+ }
+}
+
+inline void SplitStringIntoKeyValuePairs(
+ const std::string& s,
+ const char* kv_split, // For instance: "="
+ const char* pair_split, // For instance: ","
+ std::vector< std::pair<std::string, std::string> > *pairs) {
+ std::string key, value;
+ std::string* add_to = &key;
+ for (std::string::size_type i = 0; i < s.length(); ++i) {
+ if (s[i] == kv_split[0]) {
+ add_to = &value;
+ } else if (s[i] == pair_split[0]) {
+ if (!key.empty())
+ pairs->push_back(std::pair<std::string, std::string>(key, value));
+ key.clear();
+ value.clear();
+ add_to = &key;
+ } else {
+ *add_to += s[i];
+ }
+ }
+ if (!key.empty())
+ pairs->push_back(std::pair<std::string, std::string>(key, value));
+}
+
+#endif // TEMPLATE_UTIL_H_