libs/container/cache.h

   1 /*
   2 Copyright (C) 2001-2006, William Joseph.
   3 All Rights Reserved.
   4
   5 This file is part of GtkRadiant.
   6
   7 GtkRadiant is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GtkRadiant is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GtkRadiant; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22 #if !defined(INCLUDED_CONTAINER_CACHE_H)
  23 #define INCLUDED_CONTAINER_CACHE_H
  24
  25 #include <cstddef>
  26 #include "container/hashtable.h"
  27 #include "memory/allocator.h"
  28
  29 template<typename Type, typename Parameter>
  30 class DefaultCreationPolicy
  31 {
  32 public:
  33   Type* construct(const Parameter& parameter)
  34   {
  35     return New<Type>().scalar(parameter);
  36   }
  37   void destroy(Type* p)
  38   {
  39     Delete<Type>().scalar(p);
  40   }
  41 };
  42
  43 template<typename Type>
  44 class SharedValue
  45 {
  46   typedef Type value_type;
  47   typedef value_type* pointer;
  48   typedef value_type& reference;
  49
  50   std::size_t m_count;
  51   pointer m_value;
  52
  53 public:
  54   SharedValue()
  55     : m_count(0), m_value(0)
  56   {
  57   }
  58   ~SharedValue()
  59   {
  60     ASSERT_MESSAGE(m_count == 0 , "destroying a referenced object\n");
  61   }
  62   void set(pointer value)
  63   {
  64     m_value = value;
  65   }
  66   pointer get()
  67   {
  68     return m_value;
  69   }
  70   std::size_t increment()
  71   {
  72     return ++m_count;
  73   }
  74   std::size_t decrement()
  75   {
  76     ASSERT_MESSAGE(!empty(), "destroying a non-existent object\n");
  77     return --m_count;
  78   }
  79   std::size_t count()
  80   {
  81     return m_count;
  82   }
  83   bool empty()
  84   {
  85     return m_count == 0;
  86   }
  87   reference operator*() const
  88   {
  89     ASSERT_NOTNULL(m_value);
  90     return *m_value;
  91   }
  92   pointer operator->() const
  93   {
  94     return &(operator*());
  95   }
  96 };
  97
  98
  99
 100 /// \brief Caches values that are uniquely identified by a key.
 101 ///
 102 /// - Automatically removes objects that are no longer referenced.
 103 ///
 104 /// \param Key Uniquely identifies each element.
 105 /// \param Cached The type to be cached. Must define a constructor that accepts \c Key.
 106 /// \param CreationPolicy Must define 'Cached* construct(const Key&)' and 'void destroy(Cached*)'. The lifetime of the \c Key passed to 'construct' is guaranteed to be longer than the subsequent matched call to 'destroy'.
 107 template<typename Key, typename Cached, typename Hasher, typename KeyEqual = std::equal_to<Key>, typename CreationPolicy = DefaultCreationPolicy<Cached, Key> >
 108 class HashedCache : public CreationPolicy
 109 {
 110   typedef SharedValue<Cached> Element;
 111   typedef HashTable<Key, Element, Hasher, KeyEqual> map_type;
 112
 113   map_type m_map;
 114
 115 public:
 116   explicit HashedCache(const CreationPolicy& creation = CreationPolicy())
 117     : CreationPolicy(creation), m_map(256)
 118   {
 119   }
 120   ~HashedCache()
 121   {
 122     ASSERT_MESSAGE(empty(), "HashedCache::~HashedCache: not empty");
 123   }
 124
 125   typedef typename map_type::iterator iterator;
 126   typedef typename map_type::value_type value_type;
 127
 128   iterator begin()
 129   {
 130     return m_map.begin();
 131   }
 132   iterator end()
 133   {
 134     return m_map.end();
 135   }
 136
 137   bool empty() const
 138   {
 139     return m_map.empty();
 140   }
 141
 142   iterator find(const Key& key)
 143   {
 144     return m_map.find(key);
 145   }
 146
 147   void capture(iterator i)
 148   {
 149     (*i).value.increment();
 150   }
 151   void release(iterator i)
 152   {
 153     if((*i).value.decrement() == 0)
 154     {
 155       CreationPolicy::destroy((*i).value.get());
 156       m_map.erase(i);
 157     }
 158   }
 159
 160 #if 1
 161   Element& capture(const Key& key)
 162   {
 163 #if 0
 164     Element& elem = m_map[key];
 165     if(elem.increment() == 1)
 166     {
 167       elem.set(CreationPolicy::construct(key));
 168     }
 169     return elem;
 170 #else
 171     iterator i = m_map.insert(key, Element());
 172     if((*i).value.increment() == 1)
 173     {
 174       (*i).value.set(CreationPolicy::construct((*i).key));
 175     }
 176     return (*i).value;
 177 #endif
 178   }
 179 #else
 180   value_type& capture(const Key& key)
 181   {
 182     iterator i = m_map.find(key);
 183     if(i == m_map.end())
 184     {
 185       i = m_map.insert(key, Element());
 186       (*i).value.set(CreationPolicy::construct((*i).key));
 187     }
 188     (*i).value.increment();
 189     return (*i);
 190   }
 191 #endif
 192   void release(const Key& key)
 193   {
 194     iterator i = m_map.find(key);
 195     ASSERT_MESSAGE(i != m_map.end(), "releasing a non-existent object\n");
 196     release(i);
 197   }
 198
 199   void clear()
 200   {
 201     m_map.clear();
 202   }
 203 };
 204
 205
 206 #endif