Update copyright to LGPL on all files
[dyninst.git] / common / h / lru_cache.h
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #include <vector>
33 #include <assert.h>
34 #include "dyntypes.h"
35
36 #if !defined LRUCache_h_
37 #define LRUCache_h_
38
39 template<class K, class V>
40 class LRUCache {
41  public:
42    typedef int (*lru_hash_func)(K key);
43  private:
44    struct LRUCacheElement {
45       int next;
46       int prev;
47       K key;
48       V value;
49    };
50    //Using vectors for storage so that we can have tight
51    // control over the memory used.  We don't want unnecessary
52    // dynamic allocation, as this may be used under a signal handler.
53    std::vector<LRUCacheElement> list_elems;
54    std::vector<int> map_elems;
55    int next_free;
56    int max_size;
57    int max_hash_size;
58    int head;
59    int tail;
60    lru_hash_func hash_func;
61
62    int bar;
63    static const int lru_undefined = -1;
64    static const int lru_tombstone = -2;
65
66  private:
67    void hash_reorg()
68    {
69       assert(next_free == max_size);
70       //Clear out tombstone values for faster searches
71       for (int i=0; i<max_hash_size; i++) {
72          map_elems[i] = lru_undefined;
73       }
74       int cur = head;
75       while (cur != lru_undefined) {
76          hash_insert(list_elems[cur].key, cur);
77          cur = list_elems[cur].next;
78       }
79    }
80
81    int hash_find(K key)
82    {
83       int index = hash_func(key);
84       index %= max_hash_size;
85       int start = index;
86       for (;;) {
87          if (map_elems[index] == lru_undefined) {
88             return lru_undefined;
89          }
90          if (map_elems[index] != lru_tombstone) {
91             int elem = map_elems[index];
92             if (list_elems[elem].key == key)
93                return index;
94          }
95          if (++index == max_hash_size)
96             index = 0;
97          if (start == index) {
98             hash_reorg();
99          }
100       }
101    }
102
103    void hash_insert(K key, int val) 
104    {
105       int index = hash_func(key);
106       index %= max_hash_size;
107       int start = index;
108       for (;;) {
109          if ((map_elems[index] == lru_undefined) || 
110              (map_elems[index] == lru_tombstone))
111          {
112             map_elems[index] = val;
113             return;
114          }
115          if (++index == max_hash_size)
116             index = 0;
117          assert(start != index);
118       }
119    }
120
121    void hash_remove(K key)
122    {
123       int index = hash_find(key);
124       assert(index != lru_undefined);
125       map_elems[index] = lru_tombstone;
126    }
127    
128    void list_move_to_front(int index)
129    {
130       assert(head != lru_undefined);
131       assert(tail != lru_undefined);
132       assert(index < max_size);
133
134       if (index == head)
135          return;
136
137       int prev_elem = list_elems[index].prev;
138       int next_elem = list_elems[index].next;
139       //Disconnect from current place
140       if (prev_elem != lru_undefined)
141          list_elems[prev_elem].next = next_elem;
142       if (next_elem != lru_undefined)
143          list_elems[next_elem].prev = prev_elem;
144       
145       //Move to front
146       list_elems[index].prev = lru_undefined;
147       list_elems[index].next = head;
148       list_elems[head].prev = index;
149
150       //Update head and tail
151       head = index;
152       if (tail == index && prev_elem != lru_undefined)
153          tail = prev_elem;
154    }
155
156    int list_delete_last() {
157       assert(head != lru_undefined);
158       assert(tail != lru_undefined);
159       assert(next_free == max_size);
160
161       int elem_to_delete = tail;
162       int prev_elem = list_elems[elem_to_delete].prev;
163       if (prev_elem != lru_undefined)
164          list_elems[prev_elem].next = lru_undefined;
165       tail = prev_elem;
166
167       return elem_to_delete;
168    }
169
170    void list_insert_new(int pos) {
171       if (head == lru_undefined) {
172          assert(tail == lru_undefined);
173          head = pos;
174          tail = pos;
175          list_elems[pos].next = lru_undefined;
176          list_elems[pos].prev = lru_undefined;
177          return;
178       }
179       
180       list_elems[pos].prev = lru_undefined;
181       list_elems[pos].next = head;
182       list_elems[head].prev = pos;
183       head = pos;
184    }
185    
186    void list_set_keyval(int pos, K key, V value) {
187       list_elems[pos].key = key;
188       list_elems[pos].value = value;
189    }
190
191    K get_key(int index) {
192       return list_elems[index].key;
193    }
194    
195    V get_value(int index) {
196       return list_elems[index].value;
197    }
198
199  public:
200    LRUCache(int initial_size, lru_hash_func f) :
201       next_free(0),
202       max_size(initial_size),
203       head(lru_undefined),
204       tail(lru_undefined),
205       hash_func(f)
206    {
207       list_elems.reserve(max_size);
208       //Leave some empty space for better hash performance
209       max_hash_size = (int) (max_size * 1.5);
210       map_elems.reserve(max_hash_size);
211       map_elems.resize(max_hash_size);
212       for (int i=0; i<max_hash_size; i++) {
213          map_elems[i] = lru_undefined;
214       }
215    }
216
217    void insert(K key, V value)
218    {
219       int result = hash_find(key);
220       if (result != lru_undefined) {
221          int list_elem = map_elems[result];
222          list_set_keyval(list_elem, key, value);
223          list_move_to_front(list_elem);
224       }
225       
226       int elem_to_insert;
227       if (next_free < max_size)
228          elem_to_insert = next_free++;
229       else {
230          //We have to delete an old item.
231          int lru_item = list_delete_last();
232          assert(lru_item != lru_undefined);
233          hash_remove(get_key(lru_item));
234          elem_to_insert = lru_item;
235       }
236          
237       list_insert_new(elem_to_insert);
238       list_set_keyval(elem_to_insert, key, value);
239       hash_insert(key, elem_to_insert);
240    }
241
242    bool lookup(K key, V &value)
243    {
244       int result = hash_find(key);
245       if (result == lru_undefined) {
246          return false;
247       }
248       int list_elem = map_elems[result];
249
250       list_move_to_front(list_elem);
251       value = get_value(list_elem);
252       return true;
253    }
254 };
255
256 #endif