/* hash - hashing table processing.
- Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
+ Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
Written by Jim Meyering, 1992.
This program is free software; you can redistribute it and/or modify
typedef enum {false = 0, true = 1} bool;
#endif
#include <stdio.h>
-#include <assert.h>
#ifndef HAVE_DECL_FREE
"this configure-time declaration test was not run"
#include "hash.h"
+struct hash_table
+ {
+ /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1,
+ for a possibility of N_BUCKETS. Among those, N_BUCKETS_USED buckets
+ are not empty, there are N_ENTRIES active entries in the table. */
+ struct hash_entry *bucket;
+ struct hash_entry *bucket_limit;
+ unsigned n_buckets;
+ unsigned n_buckets_used;
+ unsigned n_entries;
+
+ /* Tuning arguments, kept in a physicaly separate structure. */
+ const Hash_tuning *tuning;
+
+ /* Three functions are given to `hash_initialize', see the documentation
+ block for this function. In a word, HASHER randomizes a user entry
+ into a number up from 0 up to some maximum minus 1; COMPARATOR returns
+ true if two user entries compare equally; and DATA_FREER is the cleanup
+ function for a user entry. */
+ Hash_hasher hasher;
+ Hash_comparator comparator;
+ Hash_data_freer data_freer;
+
+ /* A linked list of freed struct hash_entry structs. */
+ struct hash_entry *free_entry_list;
+
+#if USE_OBSTACK
+ /* Whenever obstacks are used, it is possible to allocate all overflowed
+ entries into a single stack, so they all can be freed in a single
+ operation. It is not clear if the speedup is worth the trouble. */
+ struct obstack entry_stack;
+#endif
+ };
+
/* A hash table contains many internal entries, each holding a pointer to
some user provided data (also called a user entry). An entry indistinctly
refers to both the internal entry and its associated user entry. A user
= table->bucket + table->hasher (entry, table->n_buckets);
struct hash_entry *cursor;
- assert (bucket < table->bucket_limit);
+ if (! (bucket < table->bucket_limit))
+ abort ();
if (bucket->data == NULL)
return NULL;
if (table->n_entries == 0)
return NULL;
- for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
- if (bucket->data)
+ for (bucket = table->bucket; ; bucket++)
+ if (! (bucket < table->bucket_limit))
+ abort ();
+ else if (bucket->data)
return bucket->data;
-
- assert (0);
}
/* 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)
= table->bucket + table->hasher (entry, table->n_buckets);
struct hash_entry *cursor;
- assert (bucket < table->bucket_limit);
+ if (! (bucket < table->bucket_limit))
+ abort ();
/* Find next entry in the same bucket. */
for (cursor = bucket; cursor; cursor = cursor->next)
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;
divisor++;
}
- return candidate % divisor != 0;
+ return (candidate % divisor ? true : false);
}
/* Round a given CANDIDATE number up to the nearest prime, and return that
hash_clear (Hash_table *table)
{
struct hash_entry *bucket;
- struct hash_entry *cursor;
for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
{
if (bucket->data)
{
+ struct hash_entry *cursor;
+ struct hash_entry *next;
+
/* Free the bucket overflow. */
- for (cursor = bucket->next; cursor; cursor = cursor->next)
+ for (cursor = bucket->next; cursor; cursor = next)
{
if (table->data_freer)
(*table->data_freer) (cursor->data);
cursor->data = NULL;
+ next = cursor->next;
/* Relinking is done one entry at a time, as it is to be expected
that overflows are either rare or short. */
cursor->next = table->free_entry_list;
= table->bucket + table->hasher (entry, table->n_buckets);
struct hash_entry *cursor;
- assert (bucket < table->bucket_limit);
+ if (! (bucket < table->bucket_limit))
+ abort ();
+
*bucket_head = bucket;
/* Test for empty bucket. */
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;
= (new_table->bucket
+ new_table->hasher (data, new_table->n_buckets));
- assert (new_bucket < new_table->bucket_limit);
+ if (! (new_bucket < new_table->bucket_limit))
+ abort ();
+
next = cursor->next;
if (new_bucket->data)
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;
void *data;
struct hash_entry *bucket;
- assert (entry); /* cannot insert a NULL entry */
+ /* The caller cannot insert a NULL entry. */
+ if (! entry)
+ abort ();
/* If there's a matching entry already in the table, return that. */
if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
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--;
struct hash_entry *cursor;
if (bucket)
- printf ("%d:\n", slot);
+ printf ("%d:\n", bucket - table->bucket);
for (cursor = bucket; cursor; cursor = cursor->next)
{
char *s = (char *) cursor->data;
/* FIXME */
- printf (" %s\n", s);
+ if (s)
+ printf (" %s\n", s);
}
}
}
projects / gnulib.git / blobdiff