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