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:
GetMemory(const size_t size,const int align)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
new(size_t size,re2::AllocateInArenaType,re2::UnsafeArena * arena)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