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