itkTimeSeriesDatabaseHelper.h

Go to the documentation of this file.

#ifndef itkTimeSeriesDatabaseHelper_h
#define itkTimeSeriesDatabaseHelper_h
#include <list>
#include <iostream>
#include <map>
#include <string>
#include <cstdarg>
#include <cassert>

namespace itk {
  namespace TimeSeriesDatabaseHelper {
    /*
     * counted_ptr - simple reference counted pointer.
     *
     * The is a non-intrusive implementation that allocates an additional
     * int and pointer for every counted object.
     */

    template <class ElementType> class counted_ptr
      {
      public:

        explicit counted_ptr(ElementType* p = 0) 
          : m_ItsCounter(0) {if (p) m_ItsCounter = new counter(p);}
        ~counted_ptr()
          {release();}
        counted_ptr(const counted_ptr& r) throw()
          {acquire(r.m_ItsCounter);}
        counted_ptr& operator=(const counted_ptr& r)
          {
            if (this != &r) {
              release();
              acquire(r.m_ItsCounter);
            }
            return *this;
          }

        ElementType& operator*()  const throw()   {return *m_ItsCounter->ptr;}
        ElementType* operator->() const throw()   {return m_ItsCounter->ptr;}
        ElementType* get()        const throw()   {return m_ItsCounter ? m_ItsCounter->ptr : 0;}
        bool unique()   const throw()
        {return (m_ItsCounter ? m_ItsCounter->count == 1 : true);}

      private:

        struct counter {
        counter(ElementType* p = 0, unsigned c = 1) : ptr(p), count(c) {}
          ElementType*          ptr;
          unsigned    count;
        }* m_ItsCounter;

        void acquire(counter* c) throw()
        { 
          m_ItsCounter = c;
          if (c) ++c->count;
        }

        void release()
        { 
          if (m_ItsCounter) {
            if (--m_ItsCounter->count == 0) {
              delete m_ItsCounter->ptr;
              delete m_ItsCounter;
            }
            m_ItsCounter = 0;
          }
        }
      };


    using namespace std;


#ifdef NDEBUG
#define IF_DEBUG(x)
#else
#define IF_DEBUG(x) x
#endif


    template <typename KeyType, typename ValueType>
      class LRUCache
    {
    public:
    LRUCache(unsigned maxsize_ = 100)
      : maxsize(maxsize_)
      {
      }

      void set_maxsize ( unsigned maxsize_ ) {
        maxsize = maxsize_;
      }

      unsigned get_maxsize () {
        return maxsize;
      }

      ~LRUCache()
        {
          clear();
        }

      size_t size()
      {
        return lru_list.size();
      }

      bool empty()
      {
        return lru_list.empty();
      }

      void clear()
      {
        lru_list.clear();
        table.clear();
        IF_DEBUG(stats.clear());
      }

      void insert(const KeyType& key, const ValueType& value)
      {
        //
        ValueType* valptr = find(key);

        //
        if (valptr)
          {
            //
            *valptr = value;
          }
        else
          {
            lru_list.push_front(key);
            cached_value cv(value, lru_list.begin());
            table.insert(make_pair(key, cv));

            //
            if (lru_list.size() > maxsize)
              {
                KeyType lru_key = lru_list.back();
                table.erase(lru_key);
                lru_list.pop_back();

                IF_DEBUG(stats.removed++);
              }
          }
      }

      ValueType* find(const KeyType& key)
      {
        TableIteratorType ti = table.find(key);

        IF_DEBUG(stats.finds++);

        if (ti == table.end())
          return 0;

        IF_DEBUG(stats.finds_hit++);

        //
        ListIteratorType li = ti->second.cache_i;
        lru_list.splice(lru_list.begin(), lru_list, li);

        return &(ti->second.value);
      }

      void debug_dump(ostream& ostr = cerr)
      {
        ostr << "Debug dump of LRUCache\n";
        ostr << "-------------------\n\n";

        if (lru_list.empty())
          {
            ostr << "The cache is empty\n";
          }

        ostr << "Sorted from MRU to LRU:\n\n";

        for (ListIteratorType i = lru_list.begin(); i != lru_list.end(); ++i)
          {
            ostr << "Key: " << *i << endl;

            TableIteratorType ti = table.find(*i);
            assert(ti != table.end());

            ostr << "Value: " << ti->second.value << "\n|\n";
          }

        ostr << endl;
      }

#ifndef NDEBUG
      void statistics(ostream& ostr = cerr) const
      {
        ostr << "LRUCache statistics\n";
        ostr << "----------------\n\n";
        ostr << format_str("Max size: %ld, cur size %ld. Cache is %5.2lf%% full\n\n",
                           maxsize, lru_list.size(), 100.0 * lru_list.size() / maxsize);
        ostr << format_str("Lookups:  %7ld\nHits:     %7ld\nHit rate: %7.2lf%%\n\n",
                           stats.finds, stats.finds_hit, 100.0 * stats.finds_hit / (stats.finds+1e-15));
        ostr << format_str("Items removed by LRU: %ld\n\n", stats.removed);
      }
#else
      void statistics(ostream & vtkNotUsed(ostr) ) const
      {
      }
#endif 

 #ifndef NDEBUG
    string format_str(const char* format, ...) const
    {
      va_list arglist;
      va_start(arglist, format);
      char* buf = new char[10000];

      vsprintf(buf, format, arglist);
      string ret = buf;
      delete [] buf;
      return ret;
    }
#endif 

    private:
      typedef typename list<KeyType>::iterator ListIteratorType;

      struct cached_value
      {
      cached_value(ValueType value_, ListIteratorType cache_i_)
      : value(value_), cache_i(cache_i_)
        {
        }

        ValueType value;
        ListIteratorType cache_i;
      };

      typedef typename map<KeyType, cached_value>::iterator TableIteratorType;

      unsigned maxsize;

      list<KeyType> lru_list;

      map<KeyType, cached_value> table;

#ifndef NDEBUG

      struct cache_statistics
      {
        cache_statistics()
        {
          clear();
        }

        void clear()
        {
          finds = finds_hit = removed = 0;
        }

        unsigned long finds;
        unsigned long finds_hit;
        unsigned long removed;
      } stats;
#endif
    };
  }
}
#endif