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.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_