1/* Copyright (C) 2021-2024 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 41template <typename Key_t, typename Value_t> 42class CacheMap : public Map<Key_t, Value_t> 43{ 44public: 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 54private: 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 79template <typename Key_t, typename Value_t> 80const int CacheMap<Key_t, Value_t>::INIT_SIZE = 1 << 14; 81template <typename Key_t, typename Value_t> 82const int CacheMap<Key_t, Value_t>::MAX_SIZE = 1 << 20; 83 84template <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 94template <typename Key_t, typename Value_t> 95CacheMap<Key_t, Value_t>::~CacheMap () 96{ 97 for (int i = 0; i < nchunks; i++) 98 delete[] chunks[i]; 99 delete[] chunks; 100} 101 102template <typename Key_t, typename Value_t> 103unsigned 104CacheMap<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 111template <typename Key_t, typename Value_t> 112void 113CacheMap<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 140template <typename Key_t, typename Value_t> 141typename CacheMap<Key_t, Value_t>::Entry * 142CacheMap<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 155template <typename Key_t, typename Value_t> 156Value_t 157CacheMap<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 163template <typename Key_t, typename Value_t> 164Value_t 165CacheMap<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 172template <typename Key_t, typename Value_t> 173Value_t 174CacheMap<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 187