it_bus_pdk/bounded_cache.h

#ifndef _BOUNDED_CACHE_H_
#define _BOUNDED_CACHE_H_

// @Copyright 2002 IONA Technologies, Plc. All Rights Reserved.
//
// A hashtable that enforces a maximum
//
// Maximum: if adding an element causes the size to grow beyond the
// maximum, the least recently used values are removed. max==0
// means the cache is unbounded.
//

#include <it_dsa/hash_map.h>
#include <it_dsa/list.h>
#include <it_bus/types.h>

namespace IT_Bus
{ 
    template<class Data>
    class Evictor
    {
      public:
        virtual void evict(Data data) = 0;
    };

    template<class Key, class Data, class HashFn, class Equal>
    class BoundedCache 
    {
      public:
        BoundedCache(
            size_t max_sz, 
            Evictor<Data>* evictor
        ) : m_evictor(evictor), 
            m_max(max_sz)
        {
            // complete
        }

        ~BoundedCache()
        {
            if (size() == 0)
            {
                return;
            }

            QueueIterator queue_iter = m_queue.begin();

            while (queue_iter != m_queue.end())
            {
                DataKeyPair pair = (*queue_iter);
                m_queue.erase(queue_iter++);               
                MapIterator i = m_map.find(*pair.second);
                m_map.erase(i);
            }

        }
    
        Boolean insert(
            const Key& key, 
            const Data& data
        )
        {
            IT_Pair<MapIterator, IT_Bool> result;
            result = m_map.insert(IT_TYPENAME HashMap::value_type(key, data));
            if (result.second)
            {
                DataKeyPair pair(data, &key);
                m_queue.push_back(pair);
                enforce_max();
            }            
            return result.second;
        }    

        Boolean remove(const Key& key)
        {
            if (size() == 0)
            {
               return false;
            }
  
            MapIterator i = m_map.find(key);
            if (i == m_map.end())
            {
                return false;
            }

            m_map.erase(i);

            QueueIterator queue_iter = m_queue.begin();

            while (queue_iter != m_queue.end())
            {
                if (*(*queue_iter).second == key)
                {
                    DataKeyPair pair = (*queue_iter);
                    m_queue.erase(queue_iter);
                    assert(m_queue.size() == m_map.size());
                    return true;
                }
                queue_iter++;
            }

            assert(m_queue.size() == m_map.size());            
            return false;            
        }    

        Data* find(const Key& key)
        {
            if (size() == 0)
            {
               return 0;
            }
  
            MapIterator i = m_map.find(key);
            if (i == m_map.end())
            {
                return 0;
            }
            else
            {
                QueueIterator queue_iter = m_queue.begin();

                while (queue_iter != m_queue.end())
                {
                    if (*(*queue_iter).second == key)
                    {
                        DataKeyPair move = (*queue_iter);
                        m_queue.erase(queue_iter);
                        m_queue.push_back(move);

                        assert(m_queue.size() == m_map.size());
                        return &((*i).second);
                    }
                    queue_iter++;
                }

                assert(0);
                return 0;
            }
        }

        const Data* find(const Key& key) const
        {
            if (size() == 0)
            {
               return 0;
            }
  
            MapIterator i = m_map.find(key);
            if (i == m_map.end())
            {
                return 0;
            }
            else
            {
                QueueIterator queue_iter = m_queue.begin();

                while (queue_iter != m_queue.end())
                {
                    if ((*queue_iter).second == key)
                    {
                        DataKeyPair move = (*queue_iter);
                        m_queue.erase(queue_iter);
                        m_queue.push_back(move);

                        assert(m_queue.size() == m_map.size());
                        return &((*i).second);
                    }
                    queue_iter++;
                }

                assert(0);
                return 0;
            }
        }


        size_t size() const
        {
            return m_map.size();
        }

        size_t max() const
        {
            return m_max;
        }

        void max(size_t max_sz)
        {
            if (m_max > max_sz)
            {
                // Silently ignore change.
                return;
            }

            m_max = max_sz;

            // If we do eventually allow this then the 
            // eviction needs to be done in a batch job
            // to ensure that the queue size is always
            // the same as the map size.
            while (m_map.size() > m_max)
            {
                enforce_max();
            }
        }

      private:
        typedef IT_HashMap<Key, Data, HashFn, Equal> HashMap;
        typedef IT_TYPENAME HashMap::iterator MapIterator;
        typedef IT_Pair<Data, const Key*> DataKeyPair;
        typedef IT_List<DataKeyPair> Queue;
        typedef IT_TYPENAME Queue::iterator QueueIterator;

        void enforce_max()
        {
            if (max() == 0)
            { 
                return;
            }

            if (size() > max())
            {
                DataKeyPair data = m_queue.front();
                m_queue.pop_front();

                MapIterator i = m_map.find(*data.second);
    
                m_map.erase(i);
                m_evictor->evict(data.first);
            }
            assert(m_queue.size() == m_map.size());
        }    


        HashMap             m_map;
        Queue               m_queue;
        Evictor<Data>*      m_evictor;
        size_t              m_max;

        // Not defined prevent accidental use.
        BoundedCache(const BoundedCache&);
        IT_Bus::Boolean operator == (const BoundedCache&);
    };

}

#endif  

---