1/* Copyright (C) 2000-2010 Red Hat, Inc. 2 This file is part of elfutils. 3 Written by Ulrich Drepper <drepper@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 46static size_t 47lookup (htab, hval, val) 48 NAME *htab; 49 HASHTYPE hval; 50 TYPE val __attribute__ ((unused)); 51{ 52 /* First hash function: simply take the modul but prevent zero. Small values 53 can skip the division, which helps performance when this is common. */ 54 size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size); 55 56 if (htab->table[idx].hashval != 0) 57 { 58 HASHTYPE hash; 59 60 if (htab->table[idx].hashval == hval 61 && COMPARE (htab->table[idx].data, val) == 0) 62 return idx; 63 64 /* Second hash function as suggested in [Knuth]. */ 65 hash = 1 + hval % (htab->size - 2); 66 67 do 68 { 69 if (idx <= hash) 70 idx = htab->size + idx - hash; 71 else 72 idx -= hash; 73 74 /* If entry is found use it. */ 75 if (htab->table[idx].hashval == hval 76 && COMPARE (htab->table[idx].data, val) == 0) 77 return idx; 78 } 79 while (htab->table[idx].hashval); 80 } 81 return idx; 82} 83 84 85static void 86insert_entry_2 (NAME *htab, HASHTYPE hval, size_t idx, TYPE data) 87{ 88#ifdef ITERATE 89 if (htab->table[idx].hashval == 0) 90 { 91# ifdef REVERSE 92 htab->table[idx].next = htab->first; 93 htab->first = &htab->table[idx]; 94# else 95 /* Add the new value to the list. */ 96 if (htab->first == NULL) 97 htab->first = htab->table[idx].next = &htab->table[idx]; 98 else 99 { 100 htab->table[idx].next = htab->first->next; 101 htab->first = htab->first->next = &htab->table[idx]; 102 } 103# endif 104 } 105#endif 106 107 htab->table[idx].hashval = hval; 108 htab->table[idx].data = data; 109 110 ++htab->filled; 111 if (100 * htab->filled > 90 * htab->size) 112 { 113 /* Table is filled more than 90%. Resize the table. */ 114#ifdef ITERATE 115 __typeof__ (htab->first) first; 116# ifndef REVERSE 117 __typeof__ (htab->first) runp; 118# endif 119#else 120 size_t old_size = htab->size; 121#endif 122#define _TABLE(name) \ 123 name##_ent *table = htab->table 124#define TABLE(name) _TABLE (name) 125 TABLE(NAME); 126 127 htab->size = next_prime (htab->size * 2); 128 htab->filled = 0; 129#ifdef ITERATE 130 first = htab->first; 131 htab->first = NULL; 132#endif 133 htab->table = calloc ((1 + htab->size), sizeof (htab->table[0])); 134 if (htab->table == NULL) 135 { 136 /* We cannot enlarge the table. Live with what we got. This 137 might lead to an infinite loop at some point, though. */ 138 htab->table = table; 139 return; 140 } 141 142 /* Add the old entries to the new table. When iteration is 143 supported we maintain the order. */ 144#ifdef ITERATE 145# ifdef REVERSE 146 while (first != NULL) 147 { 148 insert_entry_2 (htab, first->hashval, 149 lookup (htab, first->hashval, first->data), 150 first->data); 151 152 first = first->next; 153 } 154# else 155 assert (first != NULL); 156 runp = first = first->next; 157 do 158 insert_entry_2 (htab, runp->hashval, 159 lookup (htab, runp->hashval, runp->data), runp->data); 160 while ((runp = runp->next) != first); 161# endif 162#else 163 for (idx = 1; idx <= old_size; ++idx) 164 if (table[idx].hashval != 0) 165 insert_entry_2 (htab, table[idx].hashval, 166 lookup (htab, table[idx].hashval, table[idx].data), 167 table[idx].data); 168#endif 169 170 free (table); 171 } 172} 173 174 175int 176#define INIT(name) _INIT (name) 177#define _INIT(name) \ 178 name##_init 179INIT(NAME) (htab, init_size) 180 NAME *htab; 181 size_t init_size; 182{ 183 /* We need the size to be a prime. */ 184 init_size = next_prime (init_size); 185 186 /* Initialize the data structure. */ 187 htab->size = init_size; 188 htab->filled = 0; 189#ifdef ITERATE 190 htab->first = NULL; 191#endif 192 htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0])); 193 if (htab->table == NULL) 194 return -1; 195 196 return 0; 197} 198 199 200int 201#define FREE(name) _FREE (name) 202#define _FREE(name) \ 203 name##_free 204FREE(NAME) (htab) 205 NAME *htab; 206{ 207 free (htab->table); 208 return 0; 209} 210 211 212int 213#define INSERT(name) _INSERT (name) 214#define _INSERT(name) \ 215 name##_insert 216INSERT(NAME) (htab, hval, data) 217 NAME *htab; 218 HASHTYPE hval; 219 TYPE data; 220{ 221 size_t idx; 222 223 /* Make the hash value nonzero. */ 224 hval = hval ?: 1; 225 226 idx = lookup (htab, hval, data); 227 228 if (htab->table[idx].hashval != 0) 229 /* We don't want to overwrite the old value. */ 230 return -1; 231 232 /* An empty bucket has been found. */ 233 insert_entry_2 (htab, hval, idx, data); 234 return 0; 235} 236 237 238#ifdef OVERWRITE 239int 240#define INSERT(name) _INSERT (name) 241#define _INSERT(name) \ 242 name##_overwrite 243INSERT(NAME) (htab, hval, data) 244 NAME *htab; 245 HASHTYPE hval; 246 TYPE data; 247{ 248 size_t idx; 249 250 /* Make the hash value nonzero. */ 251 hval = hval ?: 1; 252 253 idx = lookup (htab, hval, data); 254 255 /* The correct bucket has been found. */ 256 insert_entry_2 (htab, hval, idx, data); 257 return 0; 258} 259#endif 260 261 262TYPE 263#define FIND(name) _FIND (name) 264#define _FIND(name) \ 265 name##_find 266FIND(NAME) (htab, hval, val) 267 NAME *htab; 268 HASHTYPE hval; 269 TYPE val; 270{ 271 size_t idx; 272 273 /* Make the hash value nonzero. */ 274 hval = hval ?: 1; 275 276 idx = lookup (htab, hval, val); 277 278 if (htab->table[idx].hashval == 0) 279 return NULL; 280 281 return htab->table[idx].data; 282} 283 284 285#ifdef ITERATE 286# define ITERATEFCT(name) _ITERATEFCT (name) 287# define _ITERATEFCT(name) \ 288 name##_iterate 289TYPE 290ITERATEFCT(NAME) (htab, ptr) 291 NAME *htab; 292 void **ptr; 293{ 294 void *p = *ptr; 295 296# define TYPENAME(name) _TYPENAME (name) 297# define _TYPENAME(name) name##_ent 298 299# ifdef REVERSE 300 if (p == NULL) 301 p = htab->first; 302 else 303 p = ((TYPENAME(NAME) *) p)->next; 304 305 if (p == NULL) 306 { 307 *ptr = NULL; 308 return NULL; 309 } 310# else 311 if (p == NULL) 312 { 313 if (htab->first == NULL) 314 return NULL; 315 p = htab->first->next; 316 } 317 else 318 { 319 if (p == htab->first) 320 return NULL; 321 322 p = ((TYPENAME(NAME) *) p)->next; 323 } 324# endif 325 326 /* Prepare the next element. If possible this will pull the data 327 into the cache, for reading. */ 328 __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2); 329 330 return ((TYPENAME(NAME) *) (*ptr = p))->data; 331} 332#endif 333