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.
     */
    /* For ANSI-challenged compilers, you may want to #define
     * NO_MEMBER_TEMPLATES or explicit */
#define NO_MEMBER_TEMPLATES
    template <class X> class counted_ptr
      {
      public:
        typedef X element_type;
        
        explicit counted_ptr(X* p = 0) 
          : itsCounter(0) {if (p) itsCounter = new counter(p);}
        ~counted_ptr()
          {release();}
        counted_ptr(const counted_ptr& r) throw()
          {acquire(r.itsCounter);}
        counted_ptr& operator=(const counted_ptr& r)
          {
            if (this != &r) {
              release();
              acquire(r.itsCounter);
            }
            return *this;
          }
        
#ifndef NO_MEMBER_TEMPLATES
        template <class Y> friend class counted_ptr<Y>;
        template <class Y> counted_ptr(const counted_ptr<Y>& r) throw()
          {acquire(r.itsCounter);}
        template <class Y> counted_ptr& operator=(const counted_ptr<Y>& r)
          {
            if (this != &r) {
              release();
              acquire(r.itsCounter);
            }
            return *this;
          }
#endif /// NO_MEMBER_TEMPLATES
        
        X& operator*()  const throw()   {return *itsCounter->ptr;}
        X* operator->() const throw()   {return itsCounter->ptr;}
        X* get()        const throw()   {return itsCounter ? itsCounter->ptr : 0;}
        bool unique()   const throw()
        {return (itsCounter ? itsCounter->count == 1 : true);}
        
      private:
        
        struct counter {
        counter(X* p = 0, unsigned c = 1) : ptr(p), count(c) {}
          X*          ptr;
          unsigned    count;
        }* itsCounter;
        
        void acquire(counter* c) throw()
        { 
          itsCounter = c;
          if (c) ++c->count;
        }

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


    using namespace std;


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


    template <typename key_type, typename value_type>
      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 key_type& key, const value_type& value)
      {
        //
        value_type* 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)
              {
                key_type lru_key = lru_list.back();
                table.erase(lru_key);
                lru_list.pop_back();

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

      value_type* find(const key_type& key)
      {
        table_iter ti = table.find(key);

        IF_DEBUG(stats.finds++);

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

        IF_DEBUG(stats.finds_hit++);

        //
        list_iter 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 (list_iter i = lru_list.begin(); i != lru_list.end(); ++i)
          {
            ostr << "Key: " << *i << endl;

            table_iter 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 /// NDEBUG

 #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 /// NDEBUG

    private:
      typedef typename list<key_type>::iterator list_iter;

      struct cached_value
      {
      cached_value(value_type value_, list_iter cache_i_)
      : value(value_), cache_i(cache_i_)
        {
        }

        value_type value;
        list_iter cache_i;
      };

      typedef typename map<key_type, cached_value>::iterator table_iter;

      unsigned maxsize;

      list<key_type> lru_list;

      map<key_type, cached_value> table;

#ifndef NDEBUG

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

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

        typedef unsigned long ulong;

        ulong finds;
        ulong finds_hit;
        ulong removed;
      } stats;
#endif
    };
  }
}
#endif