1 /* Copyright (C) 2021-2023 Free Software Foundation, Inc.
2 Contributed by Oracle.
3
4 This file is part of GNU Binutils.
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, 51 Franklin Street - Fifth Floor, Boston,
19 MA 02110-1301, USA. */
20
21 /*
22 * Cache Map implementation.
23 *
24 * Cache Map makes the following assumptions:
25 * - Cache Map is used for very fast but not guaranteed mapping;
26 * - only REL_EQ Relation can be used;
27 * - all objects used as keys or values has to be managed
28 * outside CacheMap (f.e. deletion);
29 * - (Key_t)0 is invalid key;
30 * - (Value_t)0 is invalid value;
31 * - <TBC>
32 */
33
34 #ifndef _DBE_CACHEMAP_H
35 #define _DBE_CACHEMAP_H
36
37 #include <assert.h>
38 #include <vec.h>
39 #include <Map.h>
40
41 template <typename Key_t, typename Value_t>
42 class CacheMap : public Map<Key_t, Value_t>
43 {
44 public:
45
46 CacheMap ();
47 ~CacheMap ();
48 void put (Key_t key, Value_t val);
49 Value_t get (Key_t key);
50 Value_t get (Key_t key, typename Map<Key_t, Value_t>::Relation rel);
51 Value_t
52 remove (Key_t key);
53
54 private:
55
56 struct Entry
57 {
58 Key_t key;
59 Value_t val;
60
61 Entry ()
62 {
63 key = (Key_t) 0;
64 }
65 };
66
67 static const int INIT_SIZE;
68 static const int MAX_SIZE;
69
70 static unsigned hash (Key_t key);
71 Entry *getEntry (Key_t key);
72
73 int cursize;
74 int nputs;
75 int nchunks;
76 Entry **chunks;
77 };
78
79 template <typename Key_t, typename Value_t>
80 const int CacheMap<Key_t, Value_t>::INIT_SIZE = 1 << 14;
81 template <typename Key_t, typename Value_t>
82 const int CacheMap<Key_t, Value_t>::MAX_SIZE = 1 << 20;
83
84 template <typename Key_t, typename Value_t>CacheMap<Key_t, Value_t>
85 ::CacheMap ()
86 {
87 cursize = INIT_SIZE;
88 chunks = new Entry*[32];
89 nchunks = 0;
90 chunks[nchunks++] = new Entry[cursize];
91 nputs = 0;
92 }
93
94 template <typename Key_t, typename Value_t>
95 CacheMap<Key_t, Value_t>::~CacheMap ()
96 {
97 for (int i = 0; i < nchunks; i++)
98 delete[] chunks[i];
99 delete[] chunks;
100 }
101
102 template <typename Key_t, typename Value_t>
103 unsigned
104 CacheMap<Key_t, Value_t>::hash (Key_t key)
105 {
106 unsigned h = (unsigned) key ^ (unsigned) (key >> 32);
107 h ^= (h >> 20) ^ (h >> 12);
108 return h ^ (h >> 7) ^ (h >> 4);
109 }
110
111 template <typename Key_t, typename Value_t>
112 void
113 CacheMap<Key_t, Value_t>::put (Key_t key, Value_t val)
114 {
115 if (nputs >= cursize && cursize < MAX_SIZE)
116 {
117 // Allocate new chunk for entries.
118 chunks[nchunks++] = new Entry[cursize];
119 cursize *= 2;
120
121 // Copy all old entries to the newly allocated chunk
122 Entry *newchunk = chunks[nchunks - 1];
123 int prevsz = 0;
124 int nextsz = INIT_SIZE;
125 for (int i = 0; i < nchunks - 1; i++)
126 {
127 Entry *oldchunk = chunks[i];
128 for (int j = prevsz; j < nextsz; j++)
129 newchunk[j] = oldchunk[j - prevsz];
130 prevsz = nextsz;
131 nextsz *= 2;
132 }
133 }
134 Entry *entry = getEntry (key);
135 entry->key = key;
136 entry->val = val;
137 nputs++;
138 }
139
140 template <typename Key_t, typename Value_t>
141 typename CacheMap<Key_t, Value_t>::Entry *
142 CacheMap<Key_t, Value_t>::getEntry (Key_t key)
143 {
144 unsigned idx = hash (key);
145 int i = nchunks - 1;
146 int j = cursize / 2;
147 for (; i > 0; i -= 1, j /= 2)
148 if (idx & j)
149 break;
150 if (i == 0)
151 j *= 2;
152 return &chunks[i][idx & (j - 1)];
153 }
154
155 template <typename Key_t, typename Value_t>
156 Value_t
157 CacheMap<Key_t, Value_t>::get (Key_t key)
158 {
159 Entry *entry = getEntry (key);
160 return entry->key == key ? entry->val : (Value_t) 0;
161 }
162
163 template <typename Key_t, typename Value_t>
164 Value_t
165 CacheMap<Key_t, Value_t>::get (Key_t key, typename Map<Key_t, Value_t>::Relation rel)
166 {
167 if (rel != Map<Key_t, Value_t>::REL_EQ)
168 return (Value_t) 0;
169 return get (key);
170 }
171
172 template <typename Key_t, typename Value_t>
173 Value_t
174 CacheMap<Key_t, Value_t>::remove (Key_t key)
175 {
176 Entry *entry = getEntry (key);
177 Value_t res = (Value_t) 0;
178 if (entry->key == key)
179 {
180 res = entry->val;
181 entry->val = (Value_t) 0;
182 }
183 return res;
184 }
185
186 #endif