Mercurial > hg > xemacs-beta
annotate src/hash.c @ 5518:3cc7470ea71c
gnuclient: if TMPDIR was set and connect failed, try again with /tmp
2011-06-03 Aidan Kehoe <kehoea@parhasard.net>
* gnuslib.c (connect_to_unix_server):
Retry with /tmp as a directory in which to search for Unix sockets
if an attempt to connect with some other directory failed (which
may be because gnuclient and gnuserv don't share an environment
value for TMPDIR, or because gnuserv was compiled with USE_TMPDIR
turned off).
| author | Aidan Kehoe <kehoea@parhasard.net> |
|---|---|
| date | Fri, 03 Jun 2011 18:40:57 +0100 |
| 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 } |