12ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Copyright 2000 The RE2 Authors. All Rights Reserved. 22ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Use of this source code is governed by a BSD-style 32ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// license that can be found in the LICENSE file. 42ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 52ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Sometimes it is necessary to allocate a large number of small 62ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// objects. Doing this the usual way (malloc, new) is slow, 72ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// especially for multithreaded programs. An UnsafeArena provides a 82ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// mark/release method of memory management: it asks for a large chunk 92ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// from the operating system and doles it out bit by bit as required. 102ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Then you free all the memory at once by calling UnsafeArena::Reset(). 112ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// The "Unsafe" refers to the fact that UnsafeArena is not safe to 122ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// call from multiple threads. 132ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// 142ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// The global operator new that can be used as follows: 152ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// 162ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// #include "lib/arena-inl.h" 172ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// 182ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// UnsafeArena arena(1000); 192ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Foo* foo = new (AllocateInArena, &arena) Foo; 202ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// 212ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 222ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#ifndef RE2_UTIL_ARENA_H_ 232ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#define RE2_UTIL_ARENA_H_ 242ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 252ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonnamespace re2 { 262ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 272ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// This class is thread-compatible. 282ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonclass UnsafeArena { 292ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson public: 302ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson UnsafeArena(const size_t block_size); 312ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson virtual ~UnsafeArena(); 322ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 332ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson void Reset(); 342ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 352ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // This should be the worst-case alignment for any type. This is 362ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // good for IA-32, SPARC version 7 (the last one I know), and 372ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // supposedly Alpha. i386 would be more time-efficient with a 382ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // default alignment of 8, but ::operator new() uses alignment of 4, 392ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // and an assertion will fail below after the call to MakeNewBlock() 402ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // if you try to use a larger alignment. 412ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#ifdef __i386__ 422ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson static const int kDefaultAlignment = 4; 432ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#else 442ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson static const int kDefaultAlignment = 8; 452ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#endif 462ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 472ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson private: 482ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson void* GetMemoryFallback(const size_t size, const int align); 492ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 502ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson public: 512ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson void* GetMemory(const size_t size, const int align) { 522ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson if ( size > 0 && size < remaining_ && align == 1 ) { // common case 532ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson last_alloc_ = freestart_; 542ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson freestart_ += size; 552ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson remaining_ -= size; 562ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson return reinterpret_cast<void*>(last_alloc_); 572ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 582ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson return GetMemoryFallback(size, align); 592ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson } 602ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 612ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson private: 622ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson struct AllocatedBlock { 632ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson char *mem; 642ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson size_t size; 652ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson }; 662ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 672ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // The returned AllocatedBlock* is valid until the next call to AllocNewBlock 682ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // or Reset (i.e. anything that might affect overflow_blocks_). 692ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson AllocatedBlock *AllocNewBlock(const size_t block_size); 702ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 712ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson const AllocatedBlock *IndexToBlock(int index) const; 722ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 732ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson const size_t block_size_; 742ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson char* freestart_; // beginning of the free space in most recent block 752ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson char* freestart_when_empty_; // beginning of the free space when we're empty 762ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson char* last_alloc_; // used to make sure ReturnBytes() is safe 772ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson size_t remaining_; 782ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // STL vector isn't as efficient as it could be, so we use an array at first 792ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson int blocks_alloced_; // how many of the first_blocks_ have been alloced 802ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson AllocatedBlock first_blocks_[16]; // the length of this array is arbitrary 812ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson // if the first_blocks_ aren't enough, expand into overflow_blocks_. 822ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson vector<AllocatedBlock>* overflow_blocks_; 832ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 842ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson void FreeBlocks(); // Frees all except first block 852ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 862ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson DISALLOW_EVIL_CONSTRUCTORS(UnsafeArena); 872ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson}; 882ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 892ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Operators for allocation on the arena 902ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// Syntax: new (AllocateInArena, arena) MyClass; 912ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson// STL containers, etc. 922ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsonenum AllocateInArenaType { AllocateInArena }; 932ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 942ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} // namespace re2 952ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 962ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodsoninline void* operator new(size_t size, 972ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson re2::AllocateInArenaType /* unused */, 982ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson re2::UnsafeArena *arena) { 992ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson return reinterpret_cast<char*>(arena->GetMemory(size, 1)); 1002ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson} 1012ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 1022ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson#endif // RE2_UTIL_ARENA_H_ 1032ee91b4af4353b9e6a9d591c32fedfc58fd4ef35Ian Hodson 104