arena.h revision 5821806d5e7f356e8fa4b058a389a808ea183019 
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
25namespace re2 {
26
27// This class is thread-compatible.
28class 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.
92enum AllocateInArenaType { AllocateInArena };
93
94}  // namespace re2
95
96inline 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