3 * Interface to helper classes for using the remember option
4 * in GiNaC functions */
7 * GiNaC Copyright (C) 1999-2000 Johannes Gutenberg University Mainz, Germany
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.
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.
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
24 #ifndef __GINAC_REMEMBER_H__
25 #define __GINAC_REMEMBER_H__
30 #ifndef NO_NAMESPACE_GINAC
32 #endif // ndef NO_NAMESPACE_GINAC
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
41 class remember_table_entry {
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; };
53 mutable unsigned long last_access;
54 mutable unsigned successful_hits;
55 static unsigned long access_counter;
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 list<remember_table_entry> {
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;
66 unsigned max_assoc_size;
67 unsigned remember_strategy;
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 vector<remember_table_list> {
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(ostream & os, unsigned level) const;
92 static vector<remember_table> & remember_tables(void);
94 void init_table(void);
96 unsigned max_assoc_size;
97 unsigned remember_strategy;
100 #ifndef NO_NAMESPACE_GINAC
102 #endif // ndef NO_NAMESPACE_GINAC
104 #endif // ndef __GINAC_REMEMBER_H__