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         return New<Type>().scalar( parameter );
  35 }
  36 void destroy( Type* p ){
  37         Delete<Type>().scalar( p );
  38 }
  39 };
  40
  41 template<typename Type>
  42 class SharedValue
  43 {
  44 typedef Type value_type;
  45 typedef value_type* pointer;
  46 typedef value_type& reference;
  47
  48 std::size_t m_count;
  49 pointer m_value;
  50
  51 public:
  52 SharedValue()
  53         : m_count( 0 ), m_value( 0 ){
  54 }
  55 ~SharedValue(){
  56         ASSERT_MESSAGE( m_count == 0, "destroying a referenced object\n" );
  57 }
  58 void set( pointer value ){
  59         m_value = value;
  60 }
  61 pointer get(){
  62         return m_value;
  63 }
  64 std::size_t increment(){
  65         return ++m_count;
  66 }
  67 std::size_t decrement(){
  68         ASSERT_MESSAGE( !empty(), "destroying a non-existent object\n" );
  69         return --m_count;
  70 }
  71 std::size_t count(){
  72         return m_count;
  73 }
  74 bool empty(){
  75         return m_count == 0;
  76 }
  77 reference operator*() const {
  78         ASSERT_NOTNULL( m_value );
  79         return *m_value;
  80 }
  81 pointer operator->() const {
  82         return &( operator*() );
  83 }
  84 };
  85
  86
  87
  88 /// \brief Caches values that are uniquely identified by a key.
  89 ///
  90 /// - Automatically removes objects that are no longer referenced.
  91 ///
  92 /// \param Key Uniquely identifies each element.
  93 /// \param Cached The type to be cached. Must define a constructor that accepts \c Key.
  94 /// \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'.
  95 template<typename Key, typename Cached, typename Hasher, typename KeyEqual = std::equal_to<Key>, typename CreationPolicy = DefaultCreationPolicy<Cached, Key> >
  96 class HashedCache : public CreationPolicy
  97 {
  98 typedef SharedValue<Cached> Element;
  99 typedef HashTable<Key, Element, Hasher, KeyEqual> map_type;
 100
 101 map_type m_map;
 102
 103 public:
 104 explicit HashedCache( const CreationPolicy& creation = CreationPolicy() )
 105         : CreationPolicy( creation ), m_map( 256 ){
 106 }
 107 ~HashedCache(){
 108         ASSERT_MESSAGE( empty(), "HashedCache::~HashedCache: not empty" );
 109 }
 110
 111 typedef typename map_type::iterator iterator;
 112 typedef typename map_type::value_type value_type;
 113
 114 iterator begin(){
 115         return m_map.begin();
 116 }
 117 iterator end(){
 118         return m_map.end();
 119 }
 120
 121 bool empty() const {
 122         return m_map.empty();
 123 }
 124
 125 iterator find( const Key& key ){
 126         return m_map.find( key );
 127 }
 128
 129 void capture( iterator i ){
 130         ( *i ).value.increment();
 131 }
 132 void release( iterator i ){
 133         if ( ( *i ).value.decrement() == 0 ) {
 134                 CreationPolicy::destroy( ( *i ).value.get() );
 135                 m_map.erase( i );
 136         }
 137 }
 138
 139 #if 1
 140 Element& capture( const Key& key ){
 141 #if 0
 142         Element& elem = m_map[key];
 143         if ( elem.increment() == 1 ) {
 144                 elem.set( CreationPolicy::construct( key ) );
 145         }
 146         return elem;
 147 #else
 148         iterator i = m_map.insert( key, Element() );
 149         if ( ( *i ).value.increment() == 1 ) {
 150                 ( *i ).value.set( CreationPolicy::construct( ( *i ).key ) );
 151         }
 152         return ( *i ).value;
 153 #endif
 154 }
 155 #else
 156 value_type& capture( const Key& key ){
 157         iterator i = m_map.find( key );
 158         if ( i == m_map.end() ) {
 159                 i = m_map.insert( key, Element() );
 160                 ( *i ).value.set( CreationPolicy::construct( ( *i ).key ) );
 161         }
 162         ( *i ).value.increment();
 163         return ( *i );
 164 }
 165 #endif
 166 void release( const Key& key ){
 167         iterator i = m_map.find( key );
 168         ASSERT_MESSAGE( i != m_map.end(), "releasing a non-existent object\n" );
 169         release( i );
 170 }
 171
 172 void clear(){
 173         m_map.clear();
 174 }
 175 };
 176
 177
 178 #endif