X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;ds=sidebyside;f=lib%2Fhash.c;h=802a34ed4c803bf8d7095e5d76489e3a2501bea5;hb=702f288a1c0d2053385edfe9a47ed0e184a9f1fe;hp=70ec0094ecace5c6f18d951735042673144f48ff;hpb=9166d49ff02e2622e63f0f8a7b00227e82d40dff;p=gnulib.git diff --git a/lib/hash.c b/lib/hash.c index 70ec0094e..802a34ed4 100644 --- a/lib/hash.c +++ b/lib/hash.c @@ -1,5 +1,5 @@ /* hash - hashing table processing. - Copyright (C) 1998, 1999 Free Software Foundation, Inc. + Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. Written by Jim Meyering, 1992. This program is free software; you can redistribute it and/or modify @@ -35,9 +35,16 @@ typedef enum {false = 0, true = 1} bool; #include #include +#ifndef HAVE_DECL_FREE +"this configure-time declaration test was not run" +#endif #if !HAVE_DECL_FREE void free (); #endif + +#ifndef HAVE_DECL_MALLOC +"this configure-time declaration test was not run" +#endif #if !HAVE_DECL_MALLOC char *malloc (); #endif @@ -256,11 +263,12 @@ hash_get_first (const Hash_table *table) return bucket->data; assert (0); + return NULL; } /* Return the user data for the entry following ENTRY, where ENTRY has been returned by a previous call to either `hash_get_first' or `hash_get_next'. - Return NULL if there is no more entries. */ + Return NULL if there are no more entries. */ void * hash_get_next (const Hash_table *table, const void *entry) @@ -277,7 +285,7 @@ hash_get_next (const Hash_table *table, const void *entry) return cursor->next->data; /* Find first entry in any subsequent bucket. */ - for (; bucket < table->bucket_limit; bucket++) + while (++bucket < table->bucket_limit) if (bucket->data) return bucket->data; @@ -402,7 +410,7 @@ hash_string (const char *string, unsigned n_buckets) /* Return true if CANDIDATE is a prime number. CANDIDATE should be an odd number at least equal to 11. */ -static int +static bool is_prime (unsigned long candidate) { unsigned long divisor = 3; @@ -415,7 +423,7 @@ is_prime (unsigned long candidate) divisor++; } - return candidate % divisor != 0; + return (candidate % divisor ? true : false); } /* Round a given CANDIDATE number up to the nearest prime, and return that @@ -445,8 +453,8 @@ hash_reset_tuning (Hash_tuning *tuning) /* For the given hash TABLE, check the user supplied tuning structure for reasonable values, and return true if there is no gross error with it. - Otherwise, definitvely reset the TUNING field to some acceptable default in - the hash table (that is, the user loses the right of further modifying + Otherwise, definitively reset the TUNING field to some acceptable default + in the hash table (that is, the user loses the right of further modifying tuning arguments), and return false. */ static bool @@ -468,15 +476,14 @@ check_tuning (Hash_table *table) return false; } -/* Allocate and return a new hash table, or NULL upon failure. The - initial number of buckets is automatically selected so as to _guarantee_ that - you may insert at least CANDIDATE different user entries before any growth - of the hash table size occurs. So, if have a reasonably tight a-priori - upper bound on the - number of entries you intend to insert in the hash table, you may save some - table memory and insertion time, by specifying it here. If the - IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE argument - has its meaning changed to the wanted number of buckets. +/* Allocate and return a new hash table, or NULL upon failure. The initial + number of buckets is automatically selected so as to _guarantee_ that you + may insert at least CANDIDATE different user entries before any growth of + the hash table size occurs. So, if have a reasonably tight a-priori upper + bound on the number of entries you intend to insert in the hash table, you + may save some table memory and insertion time, by specifying it here. If + the IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE + argument has its meaning changed to the wanted number of buckets. TUNING points to a structure of user-supplied values, in case some fine tuning is wanted over the default behavior of the hasher. If TUNING is @@ -717,7 +724,7 @@ hash_find_entry (Hash_table *table, const void *entry, if (bucket->data == NULL) return NULL; - /* Check if then entry is found as the bucket head. */ + /* See if the entry is the first in the bucket. */ if ((*table->comparator) (entry, bucket->data)) { void *data = bucket->data; @@ -769,8 +776,8 @@ hash_find_entry (Hash_table *table, const void *entry, /* For an already existing hash table, change the number of buckets through specifying CANDIDATE. The contents of the hash table are preserved. The - new number of buckets is automatically selected so as to _guarantee_ that the - table may receive at least CANDIDATE different user entries, including + new number of buckets is automatically selected so as to _guarantee_ that + the table may receive at least CANDIDATE different user entries, including those already in the table, before any other growth of the hash table size occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the exact number of buckets desired. */ @@ -848,6 +855,7 @@ hash_rehash (Hash_table *table, unsigned candidate) table->bucket_limit = new_table->bucket_limit; table->n_buckets = new_table->n_buckets; table->n_buckets_used = new_table->n_buckets_used; + table->free_entry_list = new_table->free_entry_list; /* table->n_entries already holds its value. */ #if USE_OBSTACK table->entry_stack = new_table->entry_stack; @@ -937,7 +945,8 @@ hash_delete (Hash_table *table, const void *entry) void *data; struct hash_entry *bucket; - if (data = hash_find_entry (table, entry, &bucket, true), !data) + data = hash_find_entry (table, entry, &bucket, true); + if (!data) return NULL; table->n_entries--;