1 /* Copyright (C) 2021 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 #ifndef _DBE_DEFAULTMAP_H 22 #define _DBE_DEFAULTMAP_H 23 24 #include <assert.h> 25 #include <vec.h> 26 #include <Map.h> 27 28 template <typename Key_t, typename Value_t> 29 class DefaultMap : public Map<Key_t, Value_t> 30 { 31 public: 32 33 DefaultMap (); 34 ~DefaultMap (); 35 void clear (); 36 void put (Key_t key, Value_t val); 37 Value_t get (Key_t key); 38 Value_t get (Key_t key, typename Map<Key_t, Value_t>::Relation rel); 39 Value_t remove (Key_t); 40 Vector<Key_t> *keySet (); 41 Vector<Value_t> *values (); 42 43 private: 44 45 struct Entry 46 { 47 Key_t key; 48 Value_t val; 49 }; 50 51 static const int CHUNK_SIZE; 52 static const int HTABLE_SIZE; 53 54 int entries; 55 int nchunks; 56 Entry **chunks; 57 Vector<Entry*> *index; 58 Entry **hashTable; 59 }; 60 61 62 template <typename Key_t, typename Value_t> 63 const int DefaultMap<Key_t, Value_t>::CHUNK_SIZE = 16384; 64 template <typename Key_t, typename Value_t> 65 const int DefaultMap<Key_t, Value_t>::HTABLE_SIZE = 1024; 66 67 template <typename Key_t, typename Value_t> 68 DefaultMap<Key_t, Value_t>::DefaultMap () 69 { 70 entries = 0; 71 nchunks = 0; 72 chunks = NULL; 73 index = new Vector<Entry*>; 74 hashTable = new Entry*[HTABLE_SIZE]; 75 for (int i = 0; i < HTABLE_SIZE; i++) 76 hashTable[i] = NULL; 77 } 78 79 template <typename Key_t, typename Value_t> 80 DefaultMap<Key_t, Value_t>::~DefaultMap () 81 { 82 for (int i = 0; i < nchunks; i++) 83 delete[] chunks[i]; 84 delete[] chunks; 85 delete index; 86 delete[] hashTable; 87 } 88 89 template <typename Key_t, typename Value_t> 90 void 91 DefaultMap<Key_t, Value_t>::clear () 92 { 93 entries = 0; 94 index->reset (); 95 for (int i = 0; i < HTABLE_SIZE; i++) 96 hashTable[i] = NULL; 97 } 98 99 template <typename Key_t> 100 inline unsigned 101 hash (Key_t key) 102 { 103 unsigned h = (unsigned) ((unsigned long) key); 104 h ^= (h >> 20) ^ (h >> 12); 105 return (h ^ (h >> 7) ^ (h >> 4)); 106 } 107 108 template <typename Key_t, typename Value_t> 109 void 110 DefaultMap<Key_t, Value_t>::put (Key_t key, Value_t val) 111 { 112 unsigned idx = hash (key) % HTABLE_SIZE; 113 Entry *entry = hashTable[idx]; 114 if (entry && entry->key == key) 115 { 116 entry->val = val; 117 return; 118 } 119 int lo = 0; 120 int hi = entries - 1; 121 while (lo <= hi) 122 { 123 int md = (lo + hi) / 2; 124 entry = index->fetch (md); 125 int cmp = entry->key < key ? -1 : entry->key > key ? 1 : 0; 126 if (cmp < 0) 127 lo = md + 1; 128 else if (cmp > 0) 129 hi = md - 1; 130 else 131 { 132 entry->val = val; 133 return; 134 } 135 } 136 if (entries >= nchunks * CHUNK_SIZE) 137 { 138 nchunks++; 139 // Reallocate Entry chunk array 140 Entry **new_chunks = new Entry*[nchunks]; 141 for (int i = 0; i < nchunks - 1; i++) 142 new_chunks[i] = chunks[i]; 143 delete[] chunks; 144 chunks = new_chunks; 145 146 // Allocate new chunk for entries. 147 chunks[nchunks - 1] = new Entry[CHUNK_SIZE]; 148 } 149 entry = &chunks[entries / CHUNK_SIZE][entries % CHUNK_SIZE]; 150 entry->key = key; 151 entry->val = val; 152 index->insert (lo, entry); 153 hashTable[idx] = entry; 154 entries++; 155 } 156 157 template <typename Key_t, typename Value_t> 158 Value_t 159 DefaultMap<Key_t, Value_t>::get (Key_t key) 160 { 161 unsigned idx = hash (key) % HTABLE_SIZE; 162 Entry *entry = hashTable[idx]; 163 if (entry && entry->key == key) 164 return entry->val; 165 166 int lo = 0; 167 int hi = entries - 1; 168 while (lo <= hi) 169 { 170 int md = (lo + hi) / 2; 171 entry = index->fetch (md); 172 int cmp = entry->key < key ? -1 : entry->key > key ? 1 : 0; 173 if (cmp < 0) 174 lo = md + 1; 175 else if (cmp > 0) 176 hi = md - 1; 177 else 178 { 179 hashTable[idx] = entry; 180 return entry->val; 181 } 182 } 183 return (Value_t) 0; 184 } 185 186 template <typename Key_t, typename Value_t> 187 Value_t 188 DefaultMap<Key_t, Value_t>::get (Key_t key, 189 typename Map<Key_t, Value_t>::Relation rel) 190 { 191 if (rel != Map<Key_t, Value_t>::REL_EQ) 192 return (Value_t) 0; 193 return get (key); 194 } 195 196 template <typename Key_t, typename Value_t> 197 Value_t 198 DefaultMap<Key_t, Value_t>::remove (Key_t) 199 { 200 // Not implemented 201 if (1) 202 assert (0); 203 return (Value_t) 0; 204 } 205 206 template <typename Key_t, typename Value_t> 207 Vector<Value_t> * 208 DefaultMap<Key_t, Value_t>::values () 209 { 210 Vector<Value_t> *vals = new Vector<Value_t>(entries); 211 for (int i = 0; i < entries; ++i) 212 { 213 Entry *entry = index->fetch (i); 214 vals->append (entry->val); 215 } 216 return vals; 217 } 218 219 template <typename Key_t, typename Value_t> 220 Vector<Key_t> * 221 DefaultMap<Key_t, Value_t>::keySet () 222 { 223 Vector<Key_t> *keys = new Vector<Key_t>(entries); 224 for (int i = 0; i < entries; ++i) 225 { 226 Entry *entry = index->fetch (i); 227 keys->append (entry->key); 228 } 229 return keys; 230 } 231 232 #endif 233