third_party/re2/util/arena.h

   1 // Copyright 2000 The RE2 Authors.  All Rights Reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Sometimes it is necessary to allocate a large number of small
   6 // objects.  Doing this the usual way (malloc, new) is slow,
   7 // especially for multithreaded programs.  An UnsafeArena provides a
   8 // mark/release method of memory management: it asks for a large chunk
   9 // from the operating system and doles it out bit by bit as required.
  10 // Then you free all the memory at once by calling UnsafeArena::Reset().
  11 // The "Unsafe" refers to the fact that UnsafeArena is not safe to
  12 // call from multiple threads.
  13 //
  14 // The global operator new that can be used as follows:
  15 //
  16 //   #include "lib/arena-inl.h"
  17 //
  18 //   UnsafeArena arena(1000);
  19 //   Foo* foo = new (AllocateInArena, &arena) Foo;
  20 //
  21
  22 #ifndef RE2_UTIL_ARENA_H_
  23 #define RE2_UTIL_ARENA_H_
  24
  25 namespace re2 {
  26
  27 // This class is thread-compatible.
  28 class UnsafeArena {
  29  public:
  30   UnsafeArena(const size_t block_size);
  31   virtual ~UnsafeArena();
  32
  33   void Reset();
  34
  35   // This should be the worst-case alignment for any type.  This is
  36   // good for IA-32, SPARC version 7 (the last one I know), and
  37   // supposedly Alpha.  i386 would be more time-efficient with a
  38   // default alignment of 8, but ::operator new() uses alignment of 4,
  39   // and an assertion will fail below after the call to MakeNewBlock()
  40   // if you try to use a larger alignment.
  41 #ifdef __i386__
  42   static const int kDefaultAlignment = 4;
  43 #else
  44   static const int kDefaultAlignment = 8;
  45 #endif
  46
  47  private:
  48   void* GetMemoryFallback(const size_t size, const int align);
  49
  50  public:
  51   void* GetMemory(const size_t size, const int align) {
  52     if ( size > 0 && size < remaining_ && align == 1 ) {       // common case
  53       last_alloc_ = freestart_;
  54       freestart_ += size;
  55       remaining_ -= size;
  56       return reinterpret_cast<void*>(last_alloc_);
  57     }
  58     return GetMemoryFallback(size, align);
  59   }
  60
  61  private:
  62   struct AllocatedBlock {
  63     char *mem;
  64     size_t size;
  65   };
  66
  67   // The returned AllocatedBlock* is valid until the next call to AllocNewBlock
  68   // or Reset (i.e. anything that might affect overflow_blocks_).
  69   AllocatedBlock *AllocNewBlock(const size_t block_size);
  70
  71   const AllocatedBlock *IndexToBlock(int index) const;
  72
  73   const size_t block_size_;
  74   char* freestart_;         // beginning of the free space in most recent block
  75   char* freestart_when_empty_;  // beginning of the free space when we're empty
  76   char* last_alloc_;         // used to make sure ReturnBytes() is safe
  77   size_t remaining_;
  78   // STL vector isn't as efficient as it could be, so we use an array at first
  79   int blocks_alloced_;       // how many of the first_blocks_ have been alloced
  80   AllocatedBlock first_blocks_[16];   // the length of this array is arbitrary
  81   // if the first_blocks_ aren't enough, expand into overflow_blocks_.
  82   vector<AllocatedBlock>* overflow_blocks_;
  83
  84   void FreeBlocks();         // Frees all except first block
  85
  86   DISALLOW_EVIL_CONSTRUCTORS(UnsafeArena);
  87 };
  88
  89 // Operators for allocation on the arena
  90 // Syntax: new (AllocateInArena, arena) MyClass;
  91 // STL containers, etc.
  92 enum AllocateInArenaType { AllocateInArena };
  93
  94 }  // namespace re2
  95
  96 inline void* operator new(size_t size,
  97                           re2::AllocateInArenaType /* unused */,
  98                           re2::UnsafeArena *arena) {
  99   return reinterpret_cast<char*>(arena->GetMemory(size, 1));
 100 }
 101
 102 #endif  // RE2_UTIL_ARENA_H_
 103