Mercurial > hg > xemacs-beta
annotate src/hash.c @ 5697:40fbceabaafd
menubar-items.el (default-menubar): Reorganize.
Add PROBLEMS to toplevel.
New "More about XEmacs" submenu for NEWS, licensing, etc.
New "Recent History" menu for messages, lossage, etc.
Get rid of ugly and unexpressive ellipses.
| author | Stephen J. Turnbull <stephen@xemacs.org> |
|---|---|
| date | Mon, 24 Dec 2012 03:08:33 +0900 |
| parents | 308d34e9f07d |
| children | e2fae7783046 |
| rev | line source |
|---|---|
| 428 | 1 /* Hash tables. |
| 2 Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc. | |
|
5146
88bd4f3ef8e4
make lrecord UID's have a separate UID space for each object, resurrect debug SOE code in extents.c
Ben Wing <ben@xemacs.org>
parents:
4976
diff
changeset
|
3 Copyright (C) 2003, 2004, 2010 Ben Wing. |
| 428 | 4 |
| 5 This file is part of XEmacs. | |
| 6 | |
|
5402
308d34e9f07d
Changed bulk of GPLv2 or later files identified by script
Mats Lidell <matsl@xemacs.org>
parents:
5146
diff
changeset
|
7 XEmacs is free software: you can redistribute it and/or modify it |
| 428 | 8 under the terms of the GNU General Public License as published by the |
|
5402
308d34e9f07d
Changed bulk of GPLv2 or later files identified by script
Mats Lidell <matsl@xemacs.org>
parents:
5146
diff
changeset
|
9 Free Software Foundation, either version 3 of the License, or (at your |
|
308d34e9f07d
Changed bulk of GPLv2 or later files identified by script
Mats Lidell <matsl@xemacs.org>
parents:
5146
diff
changeset
|
10 option) any later version. |
| 428 | 11 |
| 12 XEmacs is distributed in the hope that it will be useful, but WITHOUT | |
| 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 15 for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
|
5402
308d34e9f07d
Changed bulk of GPLv2 or later files identified by script
Mats Lidell <matsl@xemacs.org>
parents:
5146
diff
changeset
|
18 along with XEmacs. If not, see <http://www.gnu.org/licenses/>. */ |
| 428 | 19 |
| 20 /* Synched up with: Not in FSF. */ | |
| 21 | |
| 1292 | 22 /* Author: Lost in the mists of history. At least back to Lucid 19.3, |
| 23 circa Sep 1992. */ | |
| 24 | |
| 428 | 25 #include <config.h> |
| 26 #include "lisp.h" | |
| 27 #include "hash.h" | |
| 28 | |
|
5146
88bd4f3ef8e4
make lrecord UID's have a separate UID space for each object, resurrect debug SOE code in extents.c
Ben Wing <ben@xemacs.org>
parents:
4976
diff
changeset
|
29 #define NULL_ENTRY ((void *) 0xDEADBEEF) /* -559038737 base 10 */ |
| 428 | 30 |
| 31 #define COMFORTABLE_SIZE(size) (21 * (size) / 16) | |
| 32 | |
| 3025 | 33 #define KEYS_DIFFER_P(old, new_, testfun) \ |
| 34 (((old) != (new_)) && (!(testfun) || !(testfun) ((old),(new_)))) | |
| 428 | 35 |
| 665 | 36 static void rehash (hentry *harray, struct hash_table *ht, Elemcount size); |
| 428 | 37 |
| 665 | 38 Hashcode |
| 39 memory_hash (const void *xv, Bytecount size) | |
| 428 | 40 { |
| 665 | 41 Hashcode h = 0; |
| 442 | 42 unsigned const char *x = (unsigned const char *) xv; |
| 428 | 43 |
| 44 if (!x) return 0; | |
| 45 | |
| 46 while (size--) | |
| 47 { | |
| 665 | 48 Hashcode g; |
| 428 | 49 h = (h << 4) + *x++; |
| 50 if ((g = h & 0xf0000000) != 0) | |
| 51 h = (h ^ (g >> 24)) ^ g; | |
| 52 } | |
| 53 | |
| 54 return h; | |
| 55 } | |
| 56 | |
| 2515 | 57 static int |
| 58 string_equal (const void *st1, const void *st2) | |
| 59 { | |
| 60 if (!st1) | |
| 61 return st2 ? 0 : 1; | |
| 62 else if (!st2) | |
| 63 return 0; | |
| 64 else | |
| 65 return !strcmp ((const char *) st1, (const char *) st2); | |
| 66 } | |
| 67 | |
| 68 static Hashcode | |
| 69 string_hash (const void *xv) | |
| 442 | 70 { |
| 665 | 71 Hashcode h = 0; |
| 442 | 72 unsigned const char *x = (unsigned const char *) xv; |
| 73 | |
| 74 if (!x) return 0; | |
| 75 | |
| 76 while (*x) | |
| 77 { | |
| 665 | 78 Hashcode g; |
| 442 | 79 h = (h << 4) + *x++; |
| 80 if ((g = h & 0xf0000000) != 0) | |
| 81 h = (h ^ (g >> 24)) ^ g; | |
| 82 } | |
| 83 | |
| 84 return h; | |
| 85 } | |
| 86 | |
| 428 | 87 /* Return a suitable size for a hash table, with at least SIZE slots. */ |
| 665 | 88 static Elemcount |
| 89 hash_table_size (Elemcount requested_size) | |
| 428 | 90 { |
| 91 /* Return some prime near, but greater than or equal to, SIZE. | |
| 92 Decades from the time of writing, someone will have a system large | |
| 93 enough that the list below will be too short... */ | |
| 665 | 94 static const Elemcount primes [] = |
| 428 | 95 { |
| 96 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031, | |
| 97 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, | |
| 98 19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941, | |
| 99 204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519, | |
| 100 1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301, | |
| 101 10445899, 13579681, 17653589, 22949669, 29834603, 38784989, | |
| 102 50420551, 65546729, 85210757, 110774011, 144006217, 187208107, | |
| 103 243370577, 316381771, 411296309, 534685237, 695090819, 903618083, | |
| 647 | 104 1174703521, 1527114613, 1985248999 /* , 2580823717UL, 3355070839UL */ |
| 428 | 105 }; |
| 106 /* We've heard of binary search. */ | |
| 107 int low, high; | |
| 108 for (low = 0, high = countof (primes) - 1; high - low > 1;) | |
| 109 { | |
| 110 /* Loop Invariant: size < primes [high] */ | |
| 111 int mid = (low + high) / 2; | |
| 112 if (primes [mid] < requested_size) | |
| 113 low = mid; | |
| 114 else | |
| 115 high = mid; | |
| 116 } | |
| 117 return primes [high]; | |
| 118 } | |
| 119 | |
| 442 | 120 const void * |
| 121 gethash (const void *key, struct hash_table *hash_table, const void **ret_value) | |
| 428 | 122 { |
| 123 if (!key) | |
| 124 { | |
| 125 *ret_value = hash_table->zero_entry; | |
| 126 return (void *) hash_table->zero_set; | |
| 127 } | |
| 128 else | |
| 129 { | |
| 130 hentry *harray = hash_table->harray; | |
| 131 hash_table_test_function test_function = hash_table->test_function; | |
| 665 | 132 Elemcount size = hash_table->size; |
| 133 Hashcode hcode_initial = | |
| 428 | 134 hash_table->hash_function ? |
| 135 hash_table->hash_function (key) : | |
| 665 | 136 (Hashcode) key; |
| 137 Elemcount hcode = (Elemcount) (hcode_initial % size); | |
| 428 | 138 hentry *e = &harray [hcode]; |
| 442 | 139 const void *e_key = e->key; |
| 428 | 140 |
| 141 if (e_key ? | |
| 142 KEYS_DIFFER_P (e_key, key, test_function) : | |
| 143 e->contents == NULL_ENTRY) | |
| 144 { | |
| 665 | 145 Elemcount h2 = size - 2; |
| 146 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2)); | |
| 428 | 147 do |
| 148 { | |
| 149 hcode += incr; if (hcode >= size) hcode -= size; | |
| 150 e = &harray [hcode]; | |
| 151 e_key = e->key; | |
| 152 } | |
| 153 while (e_key ? | |
| 154 KEYS_DIFFER_P (e_key, key, test_function) : | |
| 155 e->contents == NULL_ENTRY); | |
| 156 } | |
| 157 | |
| 158 *ret_value = e->contents; | |
| 159 return e->key; | |
| 160 } | |
| 161 } | |
| 162 | |
| 163 void | |
| 164 clrhash (struct hash_table *hash_table) | |
| 165 { | |
| 166 memset (hash_table->harray, 0, sizeof (hentry) * hash_table->size); | |
| 167 hash_table->zero_entry = 0; | |
| 168 hash_table->zero_set = 0; | |
| 169 hash_table->fullness = 0; | |
| 170 } | |
| 171 | |
| 172 void | |
| 173 free_hash_table (struct hash_table *hash_table) | |
| 174 { | |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
3025
diff
changeset
|
175 xfree (hash_table->harray); |
|
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
3025
diff
changeset
|
176 xfree (hash_table); |
| 428 | 177 } |
| 178 | |
| 2515 | 179 struct hash_table * |
| 665 | 180 make_hash_table (Elemcount size) |
| 428 | 181 { |
| 182 struct hash_table *hash_table = xnew_and_zero (struct hash_table); | |
| 183 hash_table->size = hash_table_size (COMFORTABLE_SIZE (size)); | |
| 184 hash_table->harray = xnew_array (hentry, hash_table->size); | |
| 185 clrhash (hash_table); | |
| 186 return hash_table; | |
| 187 } | |
| 188 | |
| 189 struct hash_table * | |
| 2515 | 190 make_string_hash_table (Elemcount size) |
| 191 { | |
| 192 return make_general_hash_table (size, string_hash, string_equal); | |
| 193 } | |
| 194 | |
| 195 struct hash_table * | |
| 665 | 196 make_general_hash_table (Elemcount size, |
| 428 | 197 hash_table_hash_function hash_function, |
| 198 hash_table_test_function test_function) | |
| 199 { | |
| 200 struct hash_table* hash_table = make_hash_table (size); | |
| 201 hash_table->hash_function = hash_function; | |
| 202 hash_table->test_function = test_function; | |
| 203 return hash_table; | |
| 204 } | |
| 205 | |
| 206 static void | |
| 665 | 207 grow_hash_table (struct hash_table *hash_table, Elemcount new_size) |
| 428 | 208 { |
| 665 | 209 Elemcount old_size = hash_table->size; |
| 428 | 210 hentry *old_harray = hash_table->harray; |
| 211 | |
| 212 hash_table->size = hash_table_size (new_size); | |
| 213 hash_table->harray = xnew_array (hentry, hash_table->size); | |
| 214 | |
| 215 /* do the rehash on the "grown" table */ | |
| 216 { | |
| 217 long old_zero_set = hash_table->zero_set; | |
| 218 void *old_zero_entry = hash_table->zero_entry; | |
| 219 clrhash (hash_table); | |
| 220 hash_table->zero_set = old_zero_set; | |
| 221 hash_table->zero_entry = old_zero_entry; | |
| 222 rehash (old_harray, hash_table, old_size); | |
| 223 } | |
| 224 | |
|
4976
16112448d484
Rename xfree(FOO, TYPE) -> xfree(FOO)
Ben Wing <ben@xemacs.org>
parents:
3025
diff
changeset
|
225 xfree (old_harray); |
| 428 | 226 } |
| 227 | |
| 228 void | |
| 1292 | 229 pregrow_hash_table_if_necessary (struct hash_table *hash_table, |
| 230 Elemcount breathing_room) | |
| 231 { | |
| 232 Elemcount comfortable_size = COMFORTABLE_SIZE (hash_table->fullness); | |
| 233 if (hash_table->size < comfortable_size - breathing_room) | |
| 234 grow_hash_table (hash_table, comfortable_size + 1); | |
| 235 } | |
| 236 | |
| 237 void | |
| 442 | 238 puthash (const void *key, void *contents, struct hash_table *hash_table) |
| 428 | 239 { |
| 240 if (!key) | |
| 241 { | |
| 242 hash_table->zero_entry = contents; | |
| 243 hash_table->zero_set = 1; | |
| 244 } | |
| 245 else | |
| 246 { | |
| 247 hash_table_test_function test_function = hash_table->test_function; | |
| 665 | 248 Elemcount size = hash_table->size; |
| 428 | 249 hentry *harray = hash_table->harray; |
| 665 | 250 Hashcode hcode_initial = |
| 428 | 251 hash_table->hash_function ? |
| 252 hash_table->hash_function (key) : | |
| 665 | 253 (Hashcode) key; |
| 254 Elemcount hcode = (Elemcount) (hcode_initial % size); | |
| 255 Elemcount h2 = size - 2; | |
| 256 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2)); | |
| 442 | 257 const void *e_key = harray [hcode].key; |
| 258 const void *oldcontents; | |
| 428 | 259 |
| 260 if (e_key && KEYS_DIFFER_P (e_key, key, test_function)) | |
| 261 { | |
| 262 do | |
| 263 { | |
| 264 hcode += incr; if (hcode >= size) hcode -= size; | |
| 265 e_key = harray [hcode].key; | |
| 266 } | |
| 267 while (e_key && KEYS_DIFFER_P (e_key, key, test_function)); | |
| 268 } | |
| 269 oldcontents = harray [hcode].contents; | |
| 270 harray [hcode].key = key; | |
| 271 harray [hcode].contents = contents; | |
| 272 /* If the entry that we used was a deleted entry, | |
| 273 check for a non deleted entry of the same key, | |
| 274 then delete it. */ | |
| 275 if (!e_key && oldcontents == NULL_ENTRY) | |
| 276 { | |
| 277 hentry *e; | |
| 278 | |
| 279 do | |
| 280 { | |
| 281 hcode += incr; if (hcode >= size) hcode -= size; | |
| 282 e = &harray [hcode]; | |
| 283 e_key = e->key; | |
| 284 } | |
| 285 while (e_key ? | |
| 286 KEYS_DIFFER_P (e_key, key, test_function): | |
| 287 e->contents == NULL_ENTRY); | |
| 288 | |
| 289 if (e_key) | |
| 290 { | |
| 291 e->key = 0; | |
| 292 e->contents = NULL_ENTRY; | |
| 293 } | |
| 294 } | |
| 295 | |
| 296 /* only increment the fullness when we used up a new hentry */ | |
| 297 if (!e_key || KEYS_DIFFER_P (e_key, key, test_function)) | |
| 298 { | |
| 665 | 299 Elemcount comfortable_size = COMFORTABLE_SIZE (++(hash_table->fullness)); |
| 428 | 300 if (hash_table->size < comfortable_size) |
| 301 grow_hash_table (hash_table, comfortable_size + 1); | |
| 302 } | |
| 303 } | |
| 304 } | |
| 305 | |
| 306 static void | |
| 665 | 307 rehash (hentry *harray, struct hash_table *hash_table, Elemcount size) |
| 428 | 308 { |
| 309 hentry *limit = harray + size; | |
| 310 hentry *e; | |
| 311 for (e = harray; e < limit; e++) | |
| 312 { | |
| 313 if (e->key) | |
| 314 puthash (e->key, e->contents, hash_table); | |
| 315 } | |
| 316 } | |
| 317 | |
| 318 void | |
| 442 | 319 remhash (const void *key, struct hash_table *hash_table) |
| 428 | 320 { |
| 321 if (!key) | |
| 322 { | |
| 323 hash_table->zero_entry = 0; | |
| 324 hash_table->zero_set = 0; | |
| 325 } | |
| 326 else | |
| 327 { | |
| 328 hentry *harray = hash_table->harray; | |
| 329 hash_table_test_function test_function = hash_table->test_function; | |
| 665 | 330 Elemcount size = hash_table->size; |
| 331 Hashcode hcode_initial = | |
| 428 | 332 (hash_table->hash_function) ? |
| 333 (hash_table->hash_function (key)) : | |
| 665 | 334 ((Hashcode) key); |
| 335 Elemcount hcode = (Elemcount) (hcode_initial % size); | |
| 428 | 336 hentry *e = &harray [hcode]; |
| 442 | 337 const void *e_key = e->key; |
| 428 | 338 |
| 339 if (e_key ? | |
| 340 KEYS_DIFFER_P (e_key, key, test_function) : | |
| 341 e->contents == NULL_ENTRY) | |
| 342 { | |
| 665 | 343 Elemcount h2 = size - 2; |
| 344 Elemcount incr = (Elemcount) (1 + (hcode_initial % h2)); | |
| 428 | 345 do |
| 346 { | |
| 347 hcode += incr; if (hcode >= size) hcode -= size; | |
| 348 e = &harray [hcode]; | |
| 349 e_key = e->key; | |
| 350 } | |
| 351 while (e_key? | |
| 352 KEYS_DIFFER_P (e_key, key, test_function): | |
| 353 e->contents == NULL_ENTRY); | |
| 354 } | |
| 355 if (e_key) | |
| 356 { | |
| 357 e->key = 0; | |
| 358 e->contents = NULL_ENTRY; | |
| 359 /* Note: you can't do fullness-- here, it breaks the world. */ | |
| 360 } | |
| 361 } | |
| 362 } | |
| 363 | |
| 364 void | |
| 365 maphash (maphash_function mf, struct hash_table *hash_table, void *arg) | |
| 366 { | |
| 367 hentry *e; | |
| 368 hentry *limit; | |
| 369 | |
| 370 if (hash_table->zero_set) | |
| 371 { | |
| 372 if (mf (0, hash_table->zero_entry, arg)) | |
| 373 return; | |
| 374 } | |
| 375 | |
| 376 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++) | |
| 377 { | |
| 378 if (e->key && mf (e->key, e->contents, arg)) | |
| 379 return; | |
| 380 } | |
| 381 } | |
| 382 | |
| 383 void | |
| 384 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg) | |
| 385 { | |
| 386 hentry *e; | |
| 387 hentry *limit; | |
| 388 | |
| 389 if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg)) | |
| 390 { | |
| 391 hash_table->zero_set = 0; | |
| 392 hash_table->zero_entry = 0; | |
| 393 } | |
| 394 | |
| 395 for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++) | |
| 396 if (predicate (e->key, e->contents, arg)) | |
| 397 { | |
| 398 e->key = 0; | |
| 399 e->contents = NULL_ENTRY; | |
| 400 } | |
| 401 } |