3 * Interface to helper classes for using the remember option
4 * in GiNaC functions */
7 * GiNaC Copyright (C) 1999-2007 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 #ifndef __GINAC_REMEMBER_H__
25 #define __GINAC_REMEMBER_H__
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
40 class remember_table_entry {
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; };
52 mutable unsigned long last_access;
53 mutable unsigned successful_hits;
54 static unsigned long access_counter;
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> {
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;
65 unsigned max_assoc_size;
66 unsigned remember_strategy;
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> {
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();
95 unsigned max_assoc_size;
96 unsigned remember_strategy;
101 #endif // ndef __GINAC_REMEMBER_H__