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 104
