1 /* Copyright (C) 2000-2010 Red Hat, Inc. 2 This file is part of elfutils. 3 Written by Ulrich Drepper <drepper (at) redhat.com>, 2000. 4 5 This file is free software; you can redistribute it and/or modify 6 it under the terms of either 7 8 * the GNU Lesser General Public License as published by the Free 9 Software Foundation; either version 3 of the License, or (at 10 your option) any later version 11 12 or 13 14 * the GNU General Public License as published by the Free 15 Software Foundation; either version 2 of the License, or (at 16 your option) any later version 17 18 or both in parallel, as here. 19 20 elfutils is distributed in the hope that it will be useful, but 21 WITHOUT ANY WARRANTY; without even the implied warranty of 22 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 23 General Public License for more details. 24 25 You should have received copies of the GNU General Public License and 26 the GNU Lesser General Public License along with this program. If 27 not, see <http://www.gnu.org/licenses/>. */ 28 29 #include <assert.h> 30 #include <stdlib.h> 31 #include <system.h> 32 33 /* Before including this file the following macros must be defined: 34 35 NAME name of the hash table structure. 36 TYPE data type of the hash table entries 37 COMPARE comparison function taking two pointers to TYPE objects 38 39 The following macros if present select features: 40 41 ITERATE iterating over the table entries is possible 42 REVERSE iterate in reverse order of insert 43 */ 44 45 46 static size_t 47 lookup (NAME *htab, HASHTYPE hval, TYPE val __attribute__ ((unused))) 48 { 49 /* First hash function: simply take the modul but prevent zero. Small values 50 can skip the division, which helps performance when this is common. */ 51 size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size); 52 53 if (htab->table[idx].hashval != 0) 54 { 55 HASHTYPE hash; 56 57 if (htab->table[idx].hashval == hval 58 && COMPARE (htab->table[idx].data, val) == 0) 59 return idx; 60 61 /* Second hash function as suggested in [Knuth]. */ 62 hash = 1 + hval % (htab->size - 2); 63 64 do 65 { 66 if (idx <= hash) 67 idx = htab->size + idx - hash; 68 else 69 idx -= hash; 70 71 /* If entry is found use it. */ 72 if (htab->table[idx].hashval == hval 73 && COMPARE (htab->table[idx].data, val) == 0) 74 return idx; 75 } 76 while (htab->table[idx].hashval); 77 } 78 return idx; 79 } 80 81 82 static void 83 insert_entry_2 (NAME *htab, HASHTYPE hval, size_t idx, TYPE data) 84 { 85 #ifdef ITERATE 86 if (htab->table[idx].hashval == 0) 87 { 88 # ifdef REVERSE 89 htab->table[idx].next = htab->first; 90 htab->first = &htab->table[idx]; 91 # else 92 /* Add the new value to the list. */ 93 if (htab->first == NULL) 94 htab->first = htab->table[idx].next = &htab->table[idx]; 95 else 96 { 97 htab->table[idx].next = htab->first->next; 98 htab->first = htab->first->next = &htab->table[idx]; 99 } 100 # endif 101 } 102 #endif 103 104 htab->table[idx].hashval = hval; 105 htab->table[idx].data = data; 106 107 ++htab->filled; 108 if (100 * htab->filled > 90 * htab->size) 109 { 110 /* Table is filled more than 90%. Resize the table. */ 111 #ifdef ITERATE 112 __typeof__ (htab->first) first; 113 # ifndef REVERSE 114 __typeof__ (htab->first) runp; 115 # endif 116 #else 117 size_t old_size = htab->size; 118 #endif 119 #define _TABLE(name) \ 120 name##_ent *table = htab->table 121 #define TABLE(name) _TABLE (name) 122 TABLE(NAME); 123 124 htab->size = next_prime (htab->size * 2); 125 htab->filled = 0; 126 #ifdef ITERATE 127 first = htab->first; 128 htab->first = NULL; 129 #endif 130 htab->table = calloc ((1 + htab->size), sizeof (htab->table[0])); 131 if (htab->table == NULL) 132 { 133 /* We cannot enlarge the table. Live with what we got. This 134 might lead to an infinite loop at some point, though. */ 135 htab->table = table; 136 return; 137 } 138 139 /* Add the old entries to the new table. When iteration is 140 supported we maintain the order. */ 141 #ifdef ITERATE 142 # ifdef REVERSE 143 while (first != NULL) 144 { 145 insert_entry_2 (htab, first->hashval, 146 lookup (htab, first->hashval, first->data), 147 first->data); 148 149 first = first->next; 150 } 151 # else 152 assert (first != NULL); 153 runp = first = first->next; 154 do 155 insert_entry_2 (htab, runp->hashval, 156 lookup (htab, runp->hashval, runp->data), runp->data); 157 while ((runp = runp->next) != first); 158 # endif 159 #else 160 for (idx = 1; idx <= old_size; ++idx) 161 if (table[idx].hashval != 0) 162 insert_entry_2 (htab, table[idx].hashval, 163 lookup (htab, table[idx].hashval, table[idx].data), 164 table[idx].data); 165 #endif 166 167 free (table); 168 } 169 } 170 171 172 int 173 #define INIT(name) _INIT (name) 174 #define _INIT(name) \ 175 name##_init 176 INIT(NAME) (NAME *htab, size_t init_size) 177 { 178 /* We need the size to be a prime. */ 179 init_size = next_prime (init_size); 180 181 /* Initialize the data structure. */ 182 htab->size = init_size; 183 htab->filled = 0; 184 #ifdef ITERATE 185 htab->first = NULL; 186 #endif 187 htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0])); 188 if (htab->table == NULL) 189 return -1; 190 191 return 0; 192 } 193 194 195 int 196 #define FREE(name) _FREE (name) 197 #define _FREE(name) \ 198 name##_free 199 FREE(NAME) (NAME *htab) 200 { 201 free (htab->table); 202 return 0; 203 } 204 205 206 int 207 #define INSERT(name) _INSERT (name) 208 #define _INSERT(name) \ 209 name##_insert 210 INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data) 211 { 212 size_t idx; 213 214 /* Make the hash value nonzero. */ 215 hval = hval ?: 1; 216 217 idx = lookup (htab, hval, data); 218 219 if (htab->table[idx].hashval != 0) 220 /* We don't want to overwrite the old value. */ 221 return -1; 222 223 /* An empty bucket has been found. */ 224 insert_entry_2 (htab, hval, idx, data); 225 return 0; 226 } 227 228 229 #ifdef OVERWRITE 230 int 231 #define INSERT(name) _INSERT (name) 232 #define _INSERT(name) \ 233 name##_overwrite 234 INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data) 235 { 236 size_t idx; 237 238 /* Make the hash value nonzero. */ 239 hval = hval ?: 1; 240 241 idx = lookup (htab, hval, data); 242 243 /* The correct bucket has been found. */ 244 insert_entry_2 (htab, hval, idx, data); 245 return 0; 246 } 247 #endif 248 249 250 TYPE 251 #define FIND(name) _FIND (name) 252 #define _FIND(name) \ 253 name##_find 254 FIND(NAME) (NAME *htab, HASHTYPE hval, TYPE val) 255 { 256 size_t idx; 257 258 /* Make the hash value nonzero. */ 259 hval = hval ?: 1; 260 261 idx = lookup (htab, hval, val); 262 263 if (htab->table[idx].hashval == 0) 264 return NULL; 265 266 return htab->table[idx].data; 267 } 268 269 270 #ifdef ITERATE 271 # define ITERATEFCT(name) _ITERATEFCT (name) 272 # define _ITERATEFCT(name) \ 273 name##_iterate 274 TYPE 275 ITERATEFCT(NAME) (NAME *htab, void **ptr) 276 { 277 void *p = *ptr; 278 279 # define TYPENAME(name) _TYPENAME (name) 280 # define _TYPENAME(name) name##_ent 281 282 # ifdef REVERSE 283 if (p == NULL) 284 p = htab->first; 285 else 286 p = ((TYPENAME(NAME) *) p)->next; 287 288 if (p == NULL) 289 { 290 *ptr = NULL; 291 return NULL; 292 } 293 # else 294 if (p == NULL) 295 { 296 if (htab->first == NULL) 297 return NULL; 298 p = htab->first->next; 299 } 300 else 301 { 302 if (p == htab->first) 303 return NULL; 304 305 p = ((TYPENAME(NAME) *) p)->next; 306 } 307 # endif 308 309 /* Prepare the next element. If possible this will pull the data 310 into the cache, for reading. */ 311 __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2); 312 313 return ((TYPENAME(NAME) *) (*ptr = p))->data; 314 } 315 #endif 316
