Home | History | Annotate | Download | only in zone 
      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.
     31   ZoneAllocator() : ZoneAllocator(nullptr) { UNREACHABLE(); }
     32 #endif
     33   explicit ZoneAllocator(Zone* zone) throw() : zone_(zone) {}
     34   explicit ZoneAllocator(const ZoneAllocator& other) throw()
     35       : ZoneAllocator<T>(other.zone_) {}
     36   template <typename U>
     37   ZoneAllocator(const ZoneAllocator<U>& other) throw()
     38       : ZoneAllocator<T>(other.zone_) {}
     39   template <typename U>
     40   friend class ZoneAllocator;
     41 
     42   T* address(T& x) const { return &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   }
     48   void deallocate(T* p, size_t) { /* noop for Zones */
     49   }
     50 
     51   size_t max_size() const throw() {
     52     return std::numeric_limits<int>::max() / sizeof(T);
     53   }
     54   template <typename U, typename... 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>
     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 
     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.
     91   RecyclingZoneAllocator()
     92       : ZoneAllocator(nullptr, nullptr), free_list_(nullptr) {
     93     UNREACHABLE();
     94   }
     95 #endif
     96   explicit RecyclingZoneAllocator(Zone* zone) throw()
     97       : ZoneAllocator<T>(zone), free_list_(nullptr) {}
     98   explicit RecyclingZoneAllocator(const RecyclingZoneAllocator& other) throw()
     99       : ZoneAllocator<T>(other), free_list_(nullptr) {}
    100   template <typename U>
    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 
    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