src/Util/Cache.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_CACHE_HPP
  31 #define XCSOAR_CACHE_HPP
  32
  33 #include "Util/ListHead.hpp"
  34 #include "Compiler.h"
  35
  36 #include <unordered_map>
  37 #include <limits>
  38 #include <assert.h>
  39
  40 template<typename Key, typename Data,
  41          unsigned capacity,
  42          typename Hash=std::hash<Key>,
  43          typename KeyEqual=std::equal_to<Key>>
  44 class Cache {
  45
  46   /**
  47    * Wrapper that holds an uninitialised object, which be be
  48    * initialised and deinitialised on demand.
  49    */
  50   template<typename T>
  51   class Constructible {
  52     char buffer[sizeof(T)];
  53
  54 #ifndef NDEBUG
  55     bool constructed;
  56 #endif
  57
  58   public:
  59 #ifndef NDEBUG
  60     Constructible():constructed(false) {}
  61
  62     ~Constructible() {
  63       assert(!constructed);
  64     }
  65 #endif
  66
  67     const T &Get() const {
  68       assert(constructed);
  69
  70       const void *p = static_cast<const void *>(buffer);
  71       return *static_cast<const T *>(p);
  72     }
  73
  74     T &Get() {
  75       assert(constructed);
  76
  77       void *p = static_cast<void *>(buffer);
  78       return *static_cast<T *>(p);
  79     }
  80
  81     void Construct() {
  82       assert(!constructed);
  83
  84       void *p = static_cast<void *>(buffer);
  85       new (p) T();
  86
  87 #ifndef NDEBUG
  88       constructed = true;
  89 #endif
  90     }
  91
  92     template<typename U>
  93     void Construct(U &&value) {
  94       assert(!constructed);
  95
  96       void *p = static_cast<void *>(buffer);
  97       new (p) T(std::forward<U>(value));
  98
  99 #ifndef NDEBUG
 100       constructed = true;
 101 #endif
 102     }
 103
 104     void Destruct() {
 105       assert(constructed);
 106
 107       T &value = Get();
 108       value.T::~T();
 109
 110 #ifndef NDEBUG
 111       constructed = false;
 112 #endif
 113     }
 114   };
 115
 116   class Item;
 117
 118   /* This is a multimap, even though we use at most one cache item for
 119      a key.  A multimap means less overhead, because insert() does not
 120      need to do a full lookup, and this class  */
 121   typedef std::unordered_multimap<Key, class Item *, Hash, KeyEqual> KeyMap;
 122
 123   class Item : public ListHead {
 124     /**
 125      * This iterator is stored to allow quick removal of outdated
 126      * cache items.  This is safe, because rehashing is disabled in
 127      * #KeyMap.
 128      */
 129     typename KeyMap::iterator iterator;
 130
 131     Constructible<Data> data;
 132
 133   public:
 134     typename KeyMap::iterator GetIterator() {
 135       return iterator;
 136     }
 137
 138     void SetIterator(typename KeyMap::iterator _iterator) {
 139       iterator = _iterator;
 140     }
 141
 142     const Data &GetData() const {
 143       return data.Get();
 144     }
 145
 146     template<typename U>
 147     void Construct(U &&value) {
 148       data.Construct(std::forward<U>(value));
 149     }
 150
 151     void Destruct() {
 152       data.Destruct();
 153     }
 154
 155     template<typename U>
 156     void Replace(U &&value) {
 157       data.Get() = std::forward<U>(value);
 158     }
 159   };
 160
 161   /**
 162    * The number of cached items.
 163    */
 164   unsigned size;
 165
 166   /**
 167    * The list of unallocated items.
 168    */
 169   ListHead unallocated_list;
 170
 171   ListHead chronological_list;
 172
 173   KeyMap map;
 174
 175   Item buffer[capacity];
 176
 177   Item &GetOldest() {
 178     assert(!chronological_list.IsEmpty());
 179
 180     return *(Item *)chronological_list.GetPrevious();
 181   }
 182
 183   /**
 184    * Remove the oldest item from the cache (both from the #map and
 185    * from #chronological_list), but do not destruct it.
 186    */
 187   Item &RemoveOldest() {
 188     Item &item = GetOldest();
 189
 190     map.erase(item.GetIterator());
 191     item.Remove();
 192
 193 #ifndef NDEBUG
 194     --size;
 195 #endif
 196
 197     return item;
 198   }
 199
 200   /**
 201    * Allocate an item from #unallocated_list, but do not construct it.
 202    */
 203   Item &Allocate() {
 204     assert(!unallocated_list.IsEmpty());
 205
 206     Item &item = *(Item *)unallocated_list.GetNext();
 207     item.Remove();
 208     return item;
 209   }
 210
 211   template<typename U>
 212   Item &Make(U &&data) {
 213     if (unallocated_list.IsEmpty()) {
 214       /* cache is full: delete oldest */
 215       Item &item = RemoveOldest();
 216       item.Replace(std::forward<U>(data));
 217       return item;
 218     } else {
 219       /* cache is not full: allocate new item */
 220       Item &item = Allocate();
 221       item.Construct(std::forward<U>(data));
 222       return item;
 223     }
 224   }
 225
 226 public:
 227   Cache()
 228     :size(0),
 229      unallocated_list(ListHead::empty()),
 230      chronological_list(ListHead::empty()) {
 231     for (unsigned i = 0; i < capacity; ++i)
 232       buffer[i].InsertAfter(unallocated_list);
 233
 234     /* allocate enough buckets for the whole lifetime of this
 235        object */
 236     map.rehash(capacity);
 237
 238     /* forcibly disable rehashing, as that would Invalidate existing
 239        iterators */
 240     map.max_load_factor(std::numeric_limits<decltype(map.max_load_factor())>::infinity());
 241   }
 242
 243   ~Cache() {
 244     Clear();
 245   }
 246
 247   bool IsFull() const {
 248     assert(size <= capacity);
 249
 250     return size == capacity;
 251   }
 252
 253   void Clear() {
 254     map.clear();
 255
 256     while (!chronological_list.IsEmpty()) {
 257 #ifndef NDEBUG
 258       assert(size > 0);
 259       --size;
 260 #endif
 261
 262       Item &item = *(Item *)chronological_list.GetNext();
 263       item.Remove();
 264
 265       item.Destruct();
 266       item.InsertAfter(unallocated_list);
 267     }
 268
 269     assert(size == 0);
 270     size = 0;
 271   }
 272
 273   const Data *Get(const Key &key) {
 274     typename KeyMap::iterator i = map.find(key);
 275     if (i == map.end())
 276       return nullptr;
 277
 278     Item &item = *i->second;
 279     assert(item.GetIterator() == i);
 280
 281     /* move to the front of the chronological list */
 282     item.Remove();
 283     item.InsertAfter(chronological_list);
 284
 285     return &item.GetData();
 286   }
 287
 288   template<typename K, typename U>
 289   void Put(K &&key, U &&data) {
 290     assert(map.find(key) == map.end());
 291
 292     Item &item = Make(std::forward<U>(data));
 293     item.InsertAfter(chronological_list);
 294     auto iterator = map.insert(std::make_pair(std::forward<K>(key), &item));
 295     item.SetIterator(iterator);
 296
 297 #ifndef NDEBUG
 298     ++size;
 299 #endif
 300   }
 301 };
 302
 303 #endif