Mercurial > hg > xemacs-beta
diff src/hash.c @ 173:8eaf7971accc r20-3b13
Import from CVS: tag r20-3b13
author | cvs |
---|---|
date | Mon, 13 Aug 2007 09:49:09 +0200 |
parents | 376386a54a3c |
children | 3d6bfa290dbd |
line wrap: on
line diff
--- a/src/hash.c Mon Aug 13 09:47:55 2007 +0200 +++ b/src/hash.c Mon Aug 13 09:49:09 2007 +0200 @@ -32,17 +32,16 @@ #endif /* !emacs */ -#include <string.h> #include "hash.h" #include "elhash.h" -static CONST int +static CONST int primes []={ 13, - 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, - 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, - 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, - 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, + 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, + 761, 919, 1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, + 8419, 10103, 12143, 14591, 17519, 21023, 25229, 30293, 36353, 43627, 52361, + 62851, 75431, 90523, 108631, 130363, 156437, 187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263, 1674319, 2009191, 2411033, 2893249 }; @@ -52,7 +51,7 @@ /* from base/generic-hash.cc, and hence from Dragon book, p436 */ unsigned long string_hash (CONST void *xv) -{ +{ unsigned int h = 0; unsigned int g; unsigned CONST char *x = (unsigned CONST char *) xv; @@ -71,7 +70,7 @@ unsigned long memory_hash (CONST void *xv, int size) -{ +{ unsigned int h = 0; unsigned int g; unsigned CONST char *x = (unsigned CONST char *) xv; @@ -89,7 +88,7 @@ return h; } -static int +static int string_eq (CONST void *st1v, CONST void *st2v) { CONST char *st1 = (CONST char *)st1v; @@ -104,7 +103,7 @@ } -static unsigned int +static unsigned int prime_size (unsigned int size) { unsigned int i; @@ -125,18 +124,18 @@ hentry *harray = hash->harray; int (*test_function) (CONST void *, CONST void *) = hash->test_function; unsigned int hsize = hash->size; - unsigned int hcode_initial = + unsigned int hcode_initial = (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key); unsigned int hcode = hcode_initial % hsize; hentry *e = &harray [hcode]; CONST void *e_key = e->key; - if (!key) + if (!key) { *ret_value = hash->zero_entry; return (void *) hash->zero_set; } - + if ((e_key)? (KEYS_DIFFER_P (e_key, key, test_function)): (e->contents == NULL_ENTRY)) @@ -149,7 +148,7 @@ if (hcode >= hsize) hcode = hcode - hsize; e = &harray [hcode]; e_key = e->key; - } + } while ((e_key)? (KEYS_DIFFER_P (e_key, key, test_function)): (e->contents == NULL_ENTRY)); @@ -159,7 +158,7 @@ return e->key; } -void +void clrhash (c_hashtable hash) { memset (hash->harray, 0, sizeof (hentry) * hash->size); @@ -211,7 +210,7 @@ return res; } -c_hashtable +c_hashtable make_strings_hashtable (unsigned int hsize) { return make_general_hashtable (hsize, string_hash, string_eq); @@ -249,9 +248,9 @@ dest->size = src->size; #ifdef emacs if (!NILP (dest->elisp_table)) - dest->harray = - (hentry *) elisp_hvector_malloc - (sizeof (hentry) * dest->size, dest->elisp_table); + dest->harray = (hentry *) + elisp_hvector_malloc (sizeof (hentry) * dest->size, + dest->elisp_table); else #endif dest->harray = (hentry *) xmalloc (sizeof (hentry) * dest->size); @@ -263,7 +262,7 @@ dest->test_function = src->test_function; memcpy (dest->harray, src->harray, sizeof (hentry) * dest->size); } - + static void grow_hashtable (c_hashtable hash, unsigned int new_size) { @@ -283,8 +282,7 @@ hash->elisp_table); else #endif - new_harray = - (hentry *) xmalloc (sizeof (hentry) * new_hsize); + new_harray = (hentry *) xmalloc (sizeof (hentry) * new_hsize); hash->size = new_hsize; hash->harray = new_harray; @@ -316,7 +314,7 @@ grow_hashtable (hash, comfortable_size + 1); } -void +void puthash (CONST void *key, void *cont, c_hashtable hash) { unsigned int hsize = hash->size; @@ -325,16 +323,16 @@ hentry *harray; CONST void *e_key; hentry *e; - unsigned int hcode_initial = + unsigned int hcode_initial = (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key); unsigned int hcode; unsigned int incr = 0; unsigned int h2; CONST void *oldcontents; - if (!key) + if (!key) { - hash->zero_entry = cont; + hash->zero_entry = cont; hash->zero_set = 1; return; } @@ -350,7 +348,7 @@ h2 = hsize - 2; hcode = hcode_initial % hsize; - + e_key = harray [hcode].key; if (e_key && (KEYS_DIFFER_P (e_key, key, test_function))) { @@ -361,7 +359,7 @@ hcode = hcode + incr; if (hcode >= hsize) hcode = hcode - hsize; e_key = harray [hcode].key; - } + } while (e_key && (KEYS_DIFFER_P (e_key, key, test_function))); } oldcontents = harray [hcode].contents; @@ -409,19 +407,19 @@ } } -void +void remhash (CONST void *key, c_hashtable hash) { hentry *harray = hash->harray; int (*test_function) (CONST void*, CONST void*) = hash->test_function; unsigned int hsize = hash->size; - unsigned int hcode_initial = + unsigned int hcode_initial = (hash->hash_function)?(hash->hash_function(key)):((unsigned long) key); unsigned int hcode = hcode_initial % hsize; hentry *e = &harray [hcode]; CONST void *e_key = e->key; - if (!key) + if (!key) { hash->zero_entry = 0; hash->zero_set = 0; @@ -453,13 +451,13 @@ } } -void +void maphash (maphash_function mf, c_hashtable hash, void *arg) { hentry *e; hentry *limit; - - if (hash->zero_set) + + if (hash->zero_set) ((*mf) (0, hash->zero_entry, arg)); for (e = hash->harray, limit = e + hash->size; e < limit; e++) @@ -469,12 +467,12 @@ } } -void +void map_remhash (remhash_predicate predicate, c_hashtable hash, void *arg) { hentry *e; hentry *limit; - + if (hash->zero_set && ((*predicate) (0, hash->zero_entry, arg))) { hash->zero_set = 0;