zone-allocator.h 4.36 KB
Newer Older
1
// Copyright 2014 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5 6
#ifndef V8_ZONE_ZONE_ALLOCATOR_H_
#define V8_ZONE_ZONE_ALLOCATOR_H_
7 8
#include <limits>

9
#include "src/zone/zone.h"
10 11 12 13

namespace v8 {
namespace internal {

14
template <typename T>
15
class ZoneAllocator {
16 17 18 19 20 21 22 23
 public:
  typedef T* pointer;
  typedef const T* const_pointer;
  typedef T& reference;
  typedef const T& const_reference;
  typedef T value_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
24 25
  template <class O>
  struct rebind {
26
    typedef ZoneAllocator<O> other;
27 28
  };

29 30
#ifdef V8_CC_MSVC
  // MSVS unfortunately requires the default constructor to be defined.
31
  ZoneAllocator() : ZoneAllocator(nullptr) { UNREACHABLE(); }
32
#endif
33 34 35
  explicit ZoneAllocator(Zone* zone) throw() : zone_(zone) {}
  explicit ZoneAllocator(const ZoneAllocator& other) throw()
      : ZoneAllocator<T>(other.zone_) {}
36
  template <typename U>
37 38
  ZoneAllocator(const ZoneAllocator<U>& other) throw()
      : ZoneAllocator<T>(other.zone_) {}
39
  template <typename U>
40
  friend class ZoneAllocator;
41

42 43
  T* address(T& x) const { return &x; }
  const T* address(const T& x) const { return &x; }
44

45 46
  T* allocate(size_t n, const void* hint = 0) {
    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 52
  size_t max_size() const throw() {
    return std::numeric_limits<int>::max() / sizeof(T);
53
  }
54 55 56 57 58 59 60 61
  template <typename U, typename... Args>
  void construct(U* p, Args&&... args) {
    void* v_p = const_cast<void*>(static_cast<const void*>(p));
    new (v_p) U(std::forward<Args>(args)...);
  }
  template <typename U>
  void destroy(U* p) {
    p->~U();
62
  }
63

64
  bool operator==(ZoneAllocator const& other) const {
65 66
    return zone_ == other.zone_;
  }
67
  bool operator!=(ZoneAllocator const& other) const {
68 69
    return zone_ != other.zone_;
  }
70

71 72
  Zone* zone() { return zone_; }

73 74 75 76
 private:
  Zone* zone_;
};

77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
// A recycling zone allocator maintains a free list of deallocated chunks
// to reuse on subsiquent allocations. The free list management is purposely
// very simple and works best for data-structures which regularly allocate and
// free blocks of similar sized memory (such as std::deque).
template <typename T>
class RecyclingZoneAllocator : public ZoneAllocator<T> {
 public:
  template <class O>
  struct rebind {
    typedef RecyclingZoneAllocator<O> other;
  };

#ifdef V8_CC_MSVC
  // MSVS unfortunately requires the default constructor to be defined.
  RecyclingZoneAllocator()
      : ZoneAllocator(nullptr, nullptr), free_list_(nullptr) {
    UNREACHABLE();
  }
#endif
  explicit RecyclingZoneAllocator(Zone* zone) throw()
      : ZoneAllocator<T>(zone), free_list_(nullptr) {}
  explicit RecyclingZoneAllocator(const RecyclingZoneAllocator& other) throw()
      : ZoneAllocator<T>(other), free_list_(nullptr) {}
  template <typename U>
  RecyclingZoneAllocator(const RecyclingZoneAllocator<U>& other) throw()
      : ZoneAllocator<T>(other), free_list_(nullptr) {}
  template <typename U>
  friend class RecyclingZoneAllocator;

  T* allocate(size_t n, const void* hint = 0) {
    // Only check top block in free list, since this will be equal to or larger
    // than the other blocks in the free list.
    if (free_list_ && free_list_->size >= n) {
      T* return_val = reinterpret_cast<T*>(free_list_);
      free_list_ = free_list_->next;
      return return_val;
    } else {
      return ZoneAllocator<T>::allocate(n, hint);
    }
  }

  void deallocate(T* p, size_t n) {
    if ((sizeof(T) * n < sizeof(FreeBlock))) return;

    // Only add block to free_list if it is equal or larger than previous block
    // so that allocation stays O(1) only having to look at the top block.
    if (!free_list_ || free_list_->size <= n) {
      // Store the free-list within the block being deallocated.
      DCHECK((sizeof(T) * n >= sizeof(FreeBlock)));
      FreeBlock* new_free_block = reinterpret_cast<FreeBlock*>(p);

      new_free_block->size = n;
      new_free_block->next = free_list_;
      free_list_ = new_free_block;
    }
  }

 private:
  struct FreeBlock {
    FreeBlock* next;
    size_t size;
  };

  FreeBlock* free_list_;
};

typedef ZoneAllocator<bool> ZoneBoolAllocator;
typedef ZoneAllocator<int> ZoneIntAllocator;

146 147
}  // namespace internal
}  // namespace v8
148

149
#endif  // V8_ZONE_ZONE_ALLOCATOR_H_