ginac/remember.h

   1 /** @file remember.h
   2  *
   3  *  Interface to helper classes for using the remember option
   4  *  in GiNaC functions */
   5
   6 /*
   7  *  GiNaC Copyright (C) 1999-2004 Johannes Gutenberg University Mainz, Germany
   8  *
   9  *  This program is free software; you can redistribute it and/or modify
  10  *  it under the terms of the GNU General Public License as published by
  11  *  the Free Software Foundation; either version 2 of the License, or
  12  *  (at your option) any later version.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with this program; if not, write to the Free Software
  21  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22  */
  23
  24 #ifndef __GINAC_REMEMBER_H__
  25 #define __GINAC_REMEMBER_H__
  26
  27 #include <iosfwd>
  28 #include <vector>
  29 #include <list>
  30
  31 namespace GiNaC {
  32
  33 class function;
  34 class ex;
  35
  36 /** A single entry in the remember table of a function.
  37  *  Needs to be a friend of class function to access 'seq'.
  38  *  'last_access' and 'successful_hits' are updated at each successful
  39  *  'is_equal'. */
  40 class remember_table_entry {
  41 public:
  42         remember_table_entry(function const & f, ex const & r);
  43         bool is_equal(function const & f) const;
  44         ex get_result() const { return result; }
  45         unsigned long get_last_access() const { return last_access; }
  46         unsigned long get_successful_hits() const { return successful_hits; };
  47
  48 protected:
  49         unsigned hashvalue;
  50         exvector seq;
  51         ex result;
  52         mutable unsigned long last_access;
  53         mutable unsigned successful_hits;
  54         static unsigned long access_counter;
  55 };
  56
  57 /** A list of entries in the remember table having some least
  58  *  significant bits of the hashvalue in common. */
  59 class remember_table_list : public std::list<remember_table_entry> {
  60 public:
  61         remember_table_list(unsigned as, unsigned strat);
  62         void add_entry(function const & f, ex const & result);
  63         bool lookup_entry(function const & f, ex & result) const;
  64 protected:
  65         unsigned max_assoc_size;
  66         unsigned remember_strategy;
  67 };
  68
  69 /** The remember table is organized like an n-fold associative cache
  70  *  in a microprocessor.  The table has a width of 's' (which is rounded
  71  *  to table_size, some power of 2 near 's', internally) and a depth of 'as'
  72  *  (unless you choose that entries are never discarded). The place where
  73  *  an entry is stored depends on the hashvalue of the parameters of the
  74  *  function (this corresponds to the address of byte to be cached).
  75  *  The 'log_2(table_size)' least significant bits of this hashvalue
  76  *  give the slot in which the entry will be stored or looked up.
  77  *  Each slot can take up to 'as' entries. If a slot is full, an older
  78  *  entry is removed by one of the following strategies:
  79  *   - oldest entry (the first one in the list)
  80  *   - least recently used (the one with the lowest 'last_access')
  81  *   - least frequently used (the one with the lowest 'successful_hits')
  82  *  or all entries are kept which means that the table grows indefinitely. */
  83 class remember_table : public std::vector<remember_table_list> {
  84 public:
  85         remember_table();
  86         remember_table(unsigned s, unsigned as, unsigned strat);
  87         bool lookup_entry(function const & f, ex & result) const;
  88         void add_entry(function const & f, ex const & result);
  89         void clear_all_entries();
  90         void show_statistics(std::ostream & os, unsigned level) const;
  91         static std::vector<remember_table> & remember_tables();
  92 protected:
  93         void init_table();
  94         unsigned table_size;
  95         unsigned max_assoc_size;
  96         unsigned remember_strategy;
  97 };
  98
  99 } // namespace GiNaC
 100
 101 #endif // ndef __GINAC_REMEMBER_H__