- See if __GNUC__ < 2.97 before using std::vector<..,malloc_alloc>. Sorry,
[ginac.git] / 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-2001 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 <vector>
28 #include <list>
29
30 #ifndef NO_NAMESPACE_GINAC
31 namespace GiNaC {
32 #endif // ndef NO_NAMESPACE_GINAC
33
34 class function;
35 class ex;
36         
37 /** A single entry in the remember table of a function.
38  *  Needs to be a friend of class function to access 'seq'.
39  *  'last_access' and 'successful_hits' are updated at each successful
40  *  'is_equal'. */
41 class remember_table_entry {
42 public:
43         remember_table_entry(function const & f, ex const & r);
44         bool is_equal(function const & f) const;
45         ex get_result(void) const { return result; }
46         unsigned long get_last_access(void) const { return last_access; }
47         unsigned long get_successful_hits(void) const { return successful_hits; };
48
49 protected:
50         unsigned hashvalue;
51         exvector seq;
52         ex result;
53         mutable unsigned long last_access;
54         mutable unsigned successful_hits;
55         static unsigned long access_counter;
56 };    
57
58 /** A list of entries in the remember table having some least
59  *  significant bits of the hashvalue in common. */
60 class remember_table_list : public std::list<remember_table_entry> {
61 public:
62         remember_table_list(unsigned as, unsigned strat);
63         void add_entry(function const & f, ex const & result);
64         bool lookup_entry(function const & f, ex & result) const;
65 protected:
66         unsigned max_assoc_size;
67         unsigned remember_strategy;
68 };
69
70 /** The remember table is organized like an n-fold associative cache
71  *  in a microprocessor.  The table has a width of 's' (which is rounded
72  *  to table_size, some power of 2 near 's', internally) and a depth of 'as'
73  *  (unless you choose that entries are never discarded). The place where
74  *  an entry is stored depends on the hashvalue of the parameters of the
75  *  function (this corresponds to the address of byte to be cached).
76  *  The 'log_2(table_size)' least significant bits of this hashvalue
77  *  give the slot in which the entry will be stored or looked up.
78  *  Each slot can take up to 'as' entries. If a slot is full, an older
79  *  entry is removed by one of the following strategies:
80  *   - oldest entry (the first one in the list)
81  *   - least recently used (the one with the lowest 'last_access')
82  *   - least frequently used (the one with the lowest 'successful_hits')
83  *  or all entries are kept which means that the table grows indefinitely. */
84 class remember_table : public std::vector<remember_table_list> {
85 public:
86         remember_table();
87         remember_table(unsigned s, unsigned as, unsigned strat);
88         bool lookup_entry(function const & f, ex & result) const;
89         void add_entry(function const & f, ex const & result);
90         void clear_all_entries(void);
91         void show_statistics(std::ostream & os, unsigned level) const;
92         static std::vector<remember_table> & remember_tables(void);
93 protected:
94         void init_table(void);
95         unsigned table_size;
96         unsigned max_assoc_size;
97         unsigned remember_strategy;
98 };      
99
100 #ifndef NO_NAMESPACE_GINAC
101 } // namespace GiNaC
102 #endif // ndef NO_NAMESPACE_GINAC
103
104 #endif // ndef __GINAC_REMEMBER_H__