src/Util/SliceAllocator.hpp

   1 /*
   2  * Copyright (C) 2011 Max Kellermann <max@duempel.org>
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  *
   8  * - Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *
  11  * - Redistributions in binary form must reproduce the above copyright
  12  * notice, this list of conditions and the following disclaimer in the
  13  * documentation and/or other materials provided with the
  14  * distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  19  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  20  * FOUNDATION OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  23  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  25  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  27  * OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 #ifndef XCSOAR_SLICE_ALLOCATOR_HPP
  31 #define XCSOAR_SLICE_ALLOCATOR_HPP
  32
  33 #include <utility>
  34 #include <cstddef>
  35 #include <assert.h>
  36
  37 /**
  38  * An optimized allocator for many objects of the same size.  It is
  39  * extremely efficient at allocating single objects, but never frees
  40  * up memory to the system heap until it is destructed completely.
  41  * Released slots will be reused, though.
  42  *
  43  * Limitation: this allocator refuses to allocate more than one
  44  * contiguous object.
  45  *
  46  * @param T the type that is wrapped by this allocator
  47  * @param size the number of objects for each area
  48  */
  49 template<typename T, unsigned size>
  50 class SliceAllocator {
  51 public:
  52   typedef std::size_t size_type;
  53   typedef T value_type;
  54   typedef T *pointer;
  55   typedef const T *const_pointer;
  56   typedef T &reference;
  57   typedef const T &const_reference;
  58
  59   template<class O>
  60   struct rebind {
  61     typedef SliceAllocator<O, size> other;
  62   };
  63
  64 private:
  65   /**
  66    * One allocated item in the heap.  When it is on the "available"
  67    * list, the "next" attribute points to the next available slot.
  68    * When it is in use, the whole object is casted statically to "T".
  69    */
  70   struct Item {
  71     Item *next;
  72
  73     char padding[sizeof(T) - sizeof(void *)];
  74   };
  75
  76   /**
  77    * One area holds a certain number of slots.  When all areas are
  78    * full, a new one is allocated, but empty areas are never freed.
  79    */
  80   struct Area {
  81     Area *next;
  82
  83     Item *available;
  84
  85     Item items[size];
  86
  87 #ifndef NDEBUG
  88     unsigned num_available;
  89 #endif
  90
  91     Area()
  92       :next(nullptr), available(&items[0])
  93 #ifndef NDEBUG
  94       , num_available(size)
  95 #endif
  96     {
  97       for (unsigned i = 0; i < size - 1; ++i)
  98         items[i].next = &items[i + 1];
  99       items[size - 1].next = nullptr;
 100     }
 101
 102     ~Area() {
 103       assert(num_available == size);
 104     }
 105
 106     Item *allocate() {
 107       if (available == nullptr)
 108         return nullptr;
 109
 110       Item *i = available;
 111       available = available->next;
 112
 113 #ifndef NDEBUG
 114       assert(num_available > 0);
 115       --num_available;
 116 #endif
 117
 118       return i;
 119     }
 120
 121     bool deallocate(Item *i) {
 122       if (i < &items[0] || i >= &items[size])
 123         return false;
 124
 125       i->next = available;
 126       available = i;
 127
 128 #ifndef NDEBUG
 129       ++num_available;
 130 #endif
 131
 132       return true;
 133     }
 134   };
 135
 136 protected:
 137   /**
 138    * A linked list of areas.
 139    */
 140   Area *head;
 141
 142 public:
 143   constexpr
 144   SliceAllocator():head(nullptr) {}
 145
 146   constexpr
 147   SliceAllocator(const SliceAllocator &other):head(nullptr) {}
 148
 149   ~SliceAllocator() {
 150     while (head != nullptr) {
 151       Area *area = head;
 152       head = head->next;
 153       delete area;
 154     }
 155   }
 156
 157   T *allocate(const size_type n) {
 158     assert(n == 1);
 159
 160     /* try to allocate in one of the existing areas */
 161
 162     Area *area;
 163     for (area = head; area != nullptr; area = area->next) {
 164       Item *i = area->allocate();
 165       if (i != nullptr)
 166         return static_cast<T *>(static_cast<void *>(i));
 167     }
 168
 169     /* no room, create a new Area and insert it into the linked list */
 170
 171     area = new Area();
 172     if (area == nullptr)
 173       /* out of memory */
 174       return nullptr;
 175
 176     area->next = head;
 177     head = area;
 178
 179     /* allocate from the new area */
 180
 181     Item *i = area->allocate();
 182     return static_cast<T *>(static_cast<void *>(i));
 183   }
 184
 185   void deallocate(T *t, const size_type n) {
 186     assert(n == 1);
 187
 188     Item *i = static_cast<Item *>(static_cast<void *>(t));
 189
 190     for (Area *area = head;; area = area->next) {
 191       assert(area != nullptr);
 192
 193       if (area->deallocate(i))
 194         return;
 195     }
 196
 197     /* unreachable */
 198   }
 199
 200   template<typename U, typename... Args>
 201   void construct(U *p, Args&&... args) {
 202     ::new((void *)p) U(std::forward<Args>(args)...);
 203   }
 204
 205   void destroy(T *t) {
 206     t->T::~T();
 207   }
 208 };
 209
 210 /**
 211  * This allocator refers to one global SliceAllocator, instead of
 212  * creating a new SliceAllocator for each container.
 213  *
 214  * @param T the type that is wrapped by this allocator
 215  * @param size the number of objects for each area
 216  */
 217 template<typename T, unsigned size>
 218 class GlobalSliceAllocator {
 219   typedef SliceAllocator<T, size> Allocator;
 220
 221   static Allocator allocator;
 222
 223 public:
 224   typedef size_t size_type;
 225   typedef T value_type;
 226   typedef T *pointer;
 227   typedef const T *const_pointer;
 228   typedef T &reference;
 229   typedef const T &const_reference;
 230
 231   template<typename O>
 232   struct rebind {
 233     typedef GlobalSliceAllocator<O, size> other;
 234   };
 235
 236 public:
 237   GlobalSliceAllocator() = default;
 238
 239   template<typename U>
 240   constexpr
 241   GlobalSliceAllocator(const GlobalSliceAllocator<U, size> &_other) {}
 242
 243   T *allocate(const size_type n) {
 244     return allocator.allocate(n);
 245   }
 246
 247   void deallocate(T *t, const size_type n) {
 248     allocator.deallocate(t, n);
 249   }
 250
 251   template<typename U, typename... Args>
 252   void construct(U *p, Args&&... args) {
 253     allocator.construct(p, std::forward<Args>(args)...);
 254   }
 255
 256   void destroy(T *t) {
 257     allocator.destroy(t);
 258   }
 259 };
 260
 261 #endif