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#ifndef _DBE_DEFAULTMAP_H 22#define _DBE_DEFAULTMAP_H 23 24#include <assert.h> 25#include <vec.h> 26#include <Map.h> 27 28template <typename Key_t, typename Value_t> 29class DefaultMap : public Map<Key_t, Value_t> 30{ 31public: 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 43private: 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 62template <typename Key_t, typename Value_t> 63const int DefaultMap<Key_t, Value_t>::CHUNK_SIZE = 16384; 64template <typename Key_t, typename Value_t> 65const int DefaultMap<Key_t, Value_t>::HTABLE_SIZE = 1024; 66 67template <typename Key_t, typename Value_t> 68DefaultMap<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 79template <typename Key_t, typename Value_t> 80DefaultMap<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 89template <typename Key_t, typename Value_t> 90void 91DefaultMap<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 99template <typename Key_t> 100inline unsigned 101hash (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 108template <typename Key_t, typename Value_t> 109void 110DefaultMap<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 157template <typename Key_t, typename Value_t> 158Value_t 159DefaultMap<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 186template <typename Key_t, typename Value_t> 187Value_t 188DefaultMap<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 196template <typename Key_t, typename Value_t> 197Value_t 198DefaultMap<Key_t, Value_t>::remove (Key_t) 199{ 200 // Not implemented 201 if (1) 202 assert (0); 203 return (Value_t) 0; 204} 205 206template <typename Key_t, typename Value_t> 207Vector<Value_t> * 208DefaultMap<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 219template <typename Key_t, typename Value_t> 220Vector<Key_t> * 221DefaultMap<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