Mercurial > hg > xemacs-beta

comparison src/hash.c @ 272:c5d627a313b1 r21-0b34

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r21-0b34
author cvs
date Mon, 13 Aug 2007 10:28:48 +0200
parents 966663fcf606
children 8626e4521993
comparison
equal deleted inserted replaced
271:c7b7086b0a39 272:c5d627a313b1
33 #endif /* !emacs */ 33 #endif /* !emacs */
34 34
35 #include "hash.h" 35 #include "hash.h"
36 #include "elhash.h" 36 #include "elhash.h"
37 37
38 static CONST int 38 static CONST unsigned int
39 primes []={ 39 primes []={
40 13, 40 13,
41 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 41 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631,
42 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 42 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013,
43 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, 43 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361,
51 /* from base/generic-hash.cc, and hence from Dragon book, p436 */ 51 /* from base/generic-hash.cc, and hence from Dragon book, p436 */
52 unsigned long 52 unsigned long
53 string_hash (CONST void *xv) 53 string_hash (CONST void *xv)
54 { 54 {
55 unsigned int h = 0; 55 unsigned int h = 0;
56 unsigned int g;
57 unsigned CONST char *x = (unsigned CONST char *) xv; 56 unsigned CONST char *x = (unsigned CONST char *) xv;
58 57
59 if (!x) return 0; 58 if (!x) return 0;
60 59
61 while (*x != 0) 60 while (*x != 0)
62 { 61 {
62 unsigned int g;
63 h = (h << 4) + *x++; 63 h = (h << 4) + *x++;
64 if ((g = h & 0xf0000000) != 0) 64 if ((g = h & 0xf0000000) != 0)
65 h = (h ^ (g >> 24)) ^ g; 65 h = (h ^ (g >> 24)) ^ g;
66 } 66 }
67 67
68 return h; 68 return h;
69 } 69 }
70 70
71 unsigned long 71 unsigned long
72 memory_hash (CONST void *xv, int size) 72 memory_hash (CONST void *xv, size_t size)
73 { 73 {
74 unsigned int h = 0; 74 unsigned int h = 0;
75 unsigned int g;
76 unsigned CONST char *x = (unsigned CONST char *) xv; 75 unsigned CONST char *x = (unsigned CONST char *) xv;
77 76
78 if (!x) return 0; 77 if (!x) return 0;
79 78
80 while (size > 0) 79 while (size > 0)
81 { 80 {
81 unsigned int g;
82 h = (h << 4) + *x++; 82 h = (h << 4) + *x++;
83 if ((g = h & 0xf0000000) != 0) 83 if ((g = h & 0xf0000000) != 0)
84 h = (h ^ (g >> 24)) ^ g; 84 h = (h ^ (g >> 24)) ^ g;
85 size--; 85 size--;
86 } 86 }
98 else 98 else
99 return !strcmp ( (CONST char *) st1, (CONST char *) st2); 99 return !strcmp ( (CONST char *) st1, (CONST char *) st2);
100 } 100 }
101 101
102 102
103 /* ### Ever heard of binary search? */
103 static unsigned int 104 static unsigned int
104 prime_size (unsigned int size) 105 prime_size (unsigned int size)
105 { 106 {
106 unsigned int i; 107 int i;
107 CONST int lim = countof (primes); 108 for (i = 0; i < countof (primes); i++)
108 for (i = 0; i < lim; i++) 109 if (size <= primes [i])
109 if (size <= primes [i]) return primes [i]; 110 return primes [i];
110 return primes [lim - 1]; 111 return primes [countof (primes) - 1];
111 } 112 }
112 113
113 static void rehash (hentry *harray, c_hashtable ht, unsigned int size); 114 static void rehash (hentry *harray, c_hashtable ht, unsigned int size);
114 115
115 #define KEYS_DIFFER_P(old, new, testfun) \ 116 #define KEYS_DIFFER_P(old, new, testfun) \
305 } 306 }
306 307
307 void 308 void
308 expand_hashtable (c_hashtable hash, unsigned int needed_size) 309 expand_hashtable (c_hashtable hash, unsigned int needed_size)
309 { 310 {
310 unsigned int hsize = hash->size; 311 size_t hsize = hash->size;
311 int comfortable_size = (13 * needed_size) / 10; 312 size_t comfortable_size = (13 * needed_size) / 10;
312 if (hsize < comfortable_size) 313 if (hsize < comfortable_size)
313 grow_hashtable (hash, comfortable_size + 1); 314 grow_hashtable (hash, comfortable_size + 1);
314 } 315 }
315 316
316 void 317 void