15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2000 The RE2 Authors. All Rights Reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// license that can be found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Sometimes it is necessary to allocate a large number of small 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// objects. Doing this the usual way (malloc, new) is slow, 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// especially for multithreaded programs. An UnsafeArena provides a 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// mark/release method of memory management: it asks for a large chunk 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// from the operating system and doles it out bit by bit as required. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Then you free all the memory at once by calling UnsafeArena::Reset(). 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The "Unsafe" refers to the fact that UnsafeArena is not safe to 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// call from multiple threads. 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The global operator new that can be used as follows: 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// #include "lib/arena-inl.h" 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// UnsafeArena arena(1000); 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Foo* foo = new (AllocateInArena, &arena) Foo; 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef RE2_UTIL_ARENA_H_ 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define RE2_UTIL_ARENA_H_ 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace re2 { 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This class is thread-compatible. 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class UnsafeArena { 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) UnsafeArena(const size_t block_size); 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual ~UnsafeArena(); 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Reset(); 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This should be the worst-case alignment for any type. This is 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // good for IA-32, SPARC version 7 (the last one I know), and 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // supposedly Alpha. i386 would be more time-efficient with a 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // default alignment of 8, but ::operator new() uses alignment of 4, 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and an assertion will fail below after the call to MakeNewBlock() 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if you try to use a larger alignment. 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef __i386__ 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kDefaultAlignment = 4; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kDefaultAlignment = 8; 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* GetMemoryFallback(const size_t size, const int align); 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* GetMemory(const size_t size, const int align) { 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ( size > 0 && size < remaining_ && align == 1 ) { // common case 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) last_alloc_ = freestart_; 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) freestart_ += size; 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) remaining_ -= size; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return reinterpret_cast<void*>(last_alloc_); 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return GetMemoryFallback(size, align); 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct AllocatedBlock { 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char *mem; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t size; 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The returned AllocatedBlock* is valid until the next call to AllocNewBlock 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // or Reset (i.e. anything that might affect overflow_blocks_). 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocatedBlock *AllocNewBlock(const size_t block_size); 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const AllocatedBlock *IndexToBlock(int index) const; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t block_size_; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char* freestart_; // beginning of the free space in most recent block 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char* freestart_when_empty_; // beginning of the free space when we're empty 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char* last_alloc_; // used to make sure ReturnBytes() is safe 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t remaining_; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // STL vector isn't as efficient as it could be, so we use an array at first 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int blocks_alloced_; // how many of the first_blocks_ have been alloced 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) AllocatedBlock first_blocks_[16]; // the length of this array is arbitrary 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // if the first_blocks_ aren't enough, expand into overflow_blocks_. 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) vector<AllocatedBlock>* overflow_blocks_; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void FreeBlocks(); // Frees all except first block 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DISALLOW_EVIL_CONSTRUCTORS(UnsafeArena); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Operators for allocation on the arena 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Syntax: new (AllocateInArena, arena) MyClass; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// STL containers, etc. 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)enum AllocateInArenaType { AllocateInArena }; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace re2 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline void* operator new(size_t size, 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) re2::AllocateInArenaType /* unused */, 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) re2::UnsafeArena *arena) { 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return reinterpret_cast<char*>(arena->GetMemory(size, 1)); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // RE2_UTIL_ARENA_H_ 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 104