1 // Copyright 2014 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_ZONE_ZONE_ALLOCATOR_H_ 6 #define V8_ZONE_ZONE_ALLOCATOR_H_ 7 #include <limits> 8 9 #include "src/zone/zone.h" 10 11 namespace v8 { 12 namespace internal { 13 14 template <typename T> 15 class ZoneAllocator { 16 public: 17 typedef T* pointer; 18 typedef const T* const_pointer; 19 typedef T& reference; 20 typedef const T& const_reference; 21 typedef T value_type; 22 typedef size_t size_type; 23 typedef ptrdiff_t difference_type; 24 template <class O> 25 struct rebind { 26 typedef ZoneAllocator<O> other; 27 }; 28 29 #ifdef V8_CC_MSVC 30 // MSVS unfortunately requires the default constructor to be defined. ZoneAllocator()31 ZoneAllocator() : ZoneAllocator(nullptr) { UNREACHABLE(); } 32 #endif ZoneAllocator(Zone * zone)33 explicit ZoneAllocator(Zone* zone) throw() : zone_(zone) {} ZoneAllocator(const ZoneAllocator & other)34 explicit ZoneAllocator(const ZoneAllocator& other) throw() 35 : ZoneAllocator<T>(other.zone_) {} 36 template <typename U> ZoneAllocator(const ZoneAllocator<U> & other)37 ZoneAllocator(const ZoneAllocator<U>& other) throw() 38 : ZoneAllocator<T>(other.zone_) {} 39 template <typename U> 40 friend class ZoneAllocator; 41 address(T & x)42 T* address(T& x) const { return &x; } address(const T & x)43 const T* address(const T& x) const { return &x; } 44 45 T* allocate(size_t n, const void* hint = 0) { 46 return static_cast<T*>(zone_->NewArray<T>(static_cast<int>(n))); 47 } deallocate(T * p,size_t)48 void deallocate(T* p, size_t) { /* noop for Zones */ 49 } 50 max_size()51 size_t max_size() const throw() { 52 return std::numeric_limits<int>::max() / sizeof(T); 53 } 54 template <typename U, typename... Args> construct(U * p,Args &&...args)55 void construct(U* p, Args&&... args) { 56 void* v_p = const_cast<void*>(static_cast<const void*>(p)); 57 new (v_p) U(std::forward<Args>(args)...); 58 } 59 template <typename U> destroy(U * p)60 void destroy(U* p) { 61 p->~U(); 62 } 63 64 bool operator==(ZoneAllocator const& other) const { 65 return zone_ == other.zone_; 66 } 67 bool operator!=(ZoneAllocator const& other) const { 68 return zone_ != other.zone_; 69 } 70 zone()71 Zone* zone() { return zone_; } 72 73 private: 74 Zone* zone_; 75 }; 76 77 // A recycling zone allocator maintains a free list of deallocated chunks 78 // to reuse on subsiquent allocations. The free list management is purposely 79 // very simple and works best for data-structures which regularly allocate and 80 // free blocks of similar sized memory (such as std::deque). 81 template <typename T> 82 class RecyclingZoneAllocator : public ZoneAllocator<T> { 83 public: 84 template <class O> 85 struct rebind { 86 typedef RecyclingZoneAllocator<O> other; 87 }; 88 89 #ifdef V8_CC_MSVC 90 // MSVS unfortunately requires the default constructor to be defined. RecyclingZoneAllocator()91 RecyclingZoneAllocator() 92 : ZoneAllocator(nullptr, nullptr), free_list_(nullptr) { 93 UNREACHABLE(); 94 } 95 #endif RecyclingZoneAllocator(Zone * zone)96 explicit RecyclingZoneAllocator(Zone* zone) throw() 97 : ZoneAllocator<T>(zone), free_list_(nullptr) {} RecyclingZoneAllocator(const RecyclingZoneAllocator & other)98 explicit RecyclingZoneAllocator(const RecyclingZoneAllocator& other) throw() 99 : ZoneAllocator<T>(other), free_list_(nullptr) {} 100 template <typename U> RecyclingZoneAllocator(const RecyclingZoneAllocator<U> & other)101 RecyclingZoneAllocator(const RecyclingZoneAllocator<U>& other) throw() 102 : ZoneAllocator<T>(other), free_list_(nullptr) {} 103 template <typename U> 104 friend class RecyclingZoneAllocator; 105 106 T* allocate(size_t n, const void* hint = 0) { 107 // Only check top block in free list, since this will be equal to or larger 108 // than the other blocks in the free list. 109 if (free_list_ && free_list_->size >= n) { 110 T* return_val = reinterpret_cast<T*>(free_list_); 111 free_list_ = free_list_->next; 112 return return_val; 113 } else { 114 return ZoneAllocator<T>::allocate(n, hint); 115 } 116 } 117 deallocate(T * p,size_t n)118 void deallocate(T* p, size_t n) { 119 if ((sizeof(T) * n < sizeof(FreeBlock))) return; 120 121 // Only add block to free_list if it is equal or larger than previous block 122 // so that allocation stays O(1) only having to look at the top block. 123 if (!free_list_ || free_list_->size <= n) { 124 // Store the free-list within the block being deallocated. 125 DCHECK((sizeof(T) * n >= sizeof(FreeBlock))); 126 FreeBlock* new_free_block = reinterpret_cast<FreeBlock*>(p); 127 128 new_free_block->size = n; 129 new_free_block->next = free_list_; 130 free_list_ = new_free_block; 131 } 132 } 133 134 private: 135 struct FreeBlock { 136 FreeBlock* next; 137 size_t size; 138 }; 139 140 FreeBlock* free_list_; 141 }; 142 143 typedef ZoneAllocator<bool> ZoneBoolAllocator; 144 typedef ZoneAllocator<int> ZoneIntAllocator; 145 146 } // namespace internal 147 } // namespace v8 148 149 #endif // V8_ZONE_ZONE_ALLOCATOR_H_ 150