]>
Commit | Line | Data |
---|---|---|
fd67aa11 | 1 | /* Copyright (C) 2021-2024 Free Software Foundation, Inc. |
bb368aad VM |
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 |