gnulib/lib/hash.c

1 /* hash - hashing table processing.
21 /* A generic hash table package.  */
53        are not empty, there are N_ENTRIES active entries in the table.  */
83 /* A hash table contains many internal entries, each holding a pointer to
88    and the current table size.  At each slot position in the hash table,
94    entries divided by the table size.  Finding the slot for a data is usually
97    larger hash table size (that is, a larger number of buckets) is prone to
100    Long buckets slow down the lookup algorithm.  One might use big hash table
102    become inordinate, as unused slots in the hash table take some space.  The
104    that those are not that easy to write! :-), and to use a table size
107 /* If an insertion makes the ratio of nonempty buckets to table size larger
109    the table size by multiplying by the growth factor (a number greater than
111    defaults to 1.414, meaning that the table will have doubled its size
117    table size to become smaller than the shrink threshold (a number between
118    0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a
120    threshold and factor default to 0.0 and 1.0, meaning that the table never
139    table organization: the number of entries, number of buckets and maximum
142 /* Return the number of buckets in the hash table.  The table size, the total
147 hash_get_n_buckets (const Hash_table *table)
149   return table->n_buckets;
155 hash_get_n_buckets_used (const Hash_table *table)
157   return table->n_buckets_used;
163 hash_get_n_entries (const Hash_table *table)
165   return table->n_entries;
171 hash_get_max_bucket_length (const Hash_table *table)
176   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
194 /* Do a mild validation of a hash table, by traversing it and checking two
198 hash_table_ok (const Hash_table *table)
204   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
220   if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)
227 hash_print_statistics (const Hash_table *table, FILE *stream)
229   size_t n_entries = hash_get_n_entries (table);
230   size_t n_buckets = hash_get_n_buckets (table);
231   size_t n_buckets_used = hash_get_n_buckets_used (table);
232   size_t max_bucket_length = hash_get_max_bucket_length (table);
243 /* If ENTRY matches an entry already in the hash table, return the
244    entry from the table.  Otherwise, return NULL.  */
247 hash_lookup (const Hash_table *table, const void *entry)
250     = table->bucket + table->hasher (entry, table->n_buckets);
253   if (! (bucket < table->bucket_limit))
260     if (table->comparator (entry, cursor->data))
268 /* The functions in this page traverse the hash table and process the
269    contained entries.  For the traversal to work properly, the hash table
273 /* Return the first data in the table, or NULL if the table is empty.  */
276 hash_get_first (const Hash_table *table)
280   if (table->n_entries == 0)
283   for (bucket = table->bucket; ; bucket++)
284     if (! (bucket < table->bucket_limit))
295 hash_get_next (const Hash_table *table, const void *entry)
298     = table->bucket + table->hasher (entry, table->n_buckets);
301   if (! (bucket < table->bucket_limit))
310   while (++bucket < table->bucket_limit)
318 /* Fill BUFFER with pointers to active user entries in the hash table, then
323 hash_get_entries (const Hash_table *table, void **buffer,
330   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
346 /* Call a PROCESSOR function for each entry of a hash table, and return the
355 hash_do_for_each (const Hash_table *table, Hash_processor processor,
362   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
477    in the hash table (that is, the user loses the right of further modifying
481 check_tuning (Hash_table *table)
483   const Hash_tuning *tuning = table->tuning;
501   table->tuning = &default_tuning;
505 /* Allocate and return a new hash table, or NULL upon failure.  The initial
508    the hash table size occurs.  So, if have a reasonably tight a-priori upper
509    bound on the number of entries you intend to insert in the hash table, you
510    may save some table memory and insertion time, by specifying it here.  If
541   Hash_table *table;
546   table = malloc (sizeof *table);
547   if (table == NULL)
552   table->tuning = tuning;
553   if (!check_tuning (table))
556 	 when the user gets some feedback about it.  Once the table is created,
571   if (xalloc_oversized (candidate, sizeof *table->bucket))
573   table->n_buckets = next_prime (candidate);
574   if (xalloc_oversized (table->n_buckets, sizeof *table->bucket))
577   table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
578   if (table->bucket == NULL)
580   table->bucket_limit = table->bucket + table->n_buckets;
581   table->n_buckets_used = 0;
582   table->n_entries = 0;
584   table->hasher = hasher;
585   table->comparator = comparator;
586   table->data_freer = data_freer;
588   table->free_entry_list = NULL;
590   obstack_init (&table->entry_stack);
592   return table;
595   free (table);
604 hash_clear (Hash_table *table)
608   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
618 	      if (table->data_freer)
619 		(*table->data_freer) (cursor->data);
625 	      cursor->next = table->free_entry_list;
626 	      table->free_entry_list = cursor;
630 	  if (table->data_freer)
631 	    (*table->data_freer) (bucket->data);
637   table->n_buckets_used = 0;
638   table->n_entries = 0;
641 /* Reclaim all storage associated with a hash table.  If a data_freer
642    function has been supplied by the user when the hash table was created,
647 hash_free (Hash_table *table)
654   if (table->data_freer && table->n_entries)
656       for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
662 		  (*table->data_freer) (cursor->data);
670   obstack_free (&table->entry_stack, NULL);
675   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
685   for (cursor = table->free_entry_list; cursor; cursor = next)
693   /* Free the remainder of the hash table structure.  */
694   free (table->bucket);
695   free (table);
704 allocate_entry (Hash_table *table)
708   if (table->free_entry_list)
710       new = table->free_entry_list;
711       table->free_entry_list = new->next;
716       new = obstack_alloc (&table->entry_stack, sizeof *new);
729 free_entry (Hash_table *table, struct hash_entry *entry)
732   entry->next = table->free_entry_list;
733   table->free_entry_list = entry;
737    ENTRY matches an entry in the table, return a pointer to the corresponding
740    the table, unlink the matching entry.  */
743 hash_find_entry (Hash_table *table, const void *entry,
747     = table->bucket + table->hasher (entry, table->n_buckets);
750   if (! (bucket < table->bucket_limit))
760   if ((*table->comparator) (entry, bucket->data))
773 	      free_entry (table, next);
787       if ((*table->comparator) (entry, cursor->next->data))
798 	      free_entry (table, next);
809 /* For an already existing hash table, change the number of buckets through
810    specifying CANDIDATE.  The contents of the hash table are preserved.  The
812    the table may receive at least CANDIDATE different user entries, including
813    those already in the table, before any other growth of the hash table size
818 hash_rehash (Hash_table *table, size_t candidate)
825   new_table = hash_initialize (candidate, table->tuning, table->hasher,
826 			       table->comparator, table->data_freer);
830   /* Merely reuse the extra old space into the new table.  */
833   new_table->entry_stack = table->entry_stack;
835   new_table->free_entry_list = table->free_entry_list;
837   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
887   free (table->bucket);
888   table->bucket = new_table->bucket;
889   table->bucket_limit = new_table->bucket_limit;
890   table->n_buckets = new_table->n_buckets;
891   table->n_buckets_used = new_table->n_buckets_used;
892   table->free_entry_list = new_table->free_entry_list;
893   /* table->n_entries already holds its value.  */
895   table->entry_stack = new_table->entry_stack;
902 /* If ENTRY matches an entry already in the hash table, return the pointer
903    to the entry from the table.  Otherwise, insert ENTRY and return ENTRY.
907 hash_insert (Hash_table *table, const void *entry)
916   /* If there's a matching entry already in the table, return that.  */
917   if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
924       struct hash_entry *new_entry = allocate_entry (table);
934       table->n_entries++;
941   table->n_entries++;
942   table->n_buckets_used++;
945      the table size and rehash.  There's no point in checking the number of
949   if (table->n_buckets_used
950       > table->tuning->growth_threshold * table->n_buckets)
954       check_tuning (table);
955       if (table->n_buckets_used
956 	  > table->tuning->growth_threshold * table->n_buckets)
958 	  const Hash_tuning *tuning = table->tuning;
961 	     ? (table->n_buckets * tuning->growth_factor)
962 	     : (table->n_buckets * tuning->growth_factor
969 	  if (!hash_rehash (table, candidate))
977 /* If ENTRY is already in the table, remove it and return the just-deleted
979    table, don't modify the table and return NULL.  */
982 hash_delete (Hash_table *table, const void *entry)
987   data = hash_find_entry (table, entry, &bucket, true);
991   table->n_entries--;
994       table->n_buckets_used--;
997 	 rehash into a smaller table.  */
999       if (table->n_buckets_used
1000 	  < table->tuning->shrink_threshold * table->n_buckets)
1004 	  check_tuning (table);
1005 	  if (table->n_buckets_used
1006 	      < table->tuning->shrink_threshold * table->n_buckets)
1008 	      const Hash_tuning *tuning = table->tuning;
1011 		 ? table->n_buckets * tuning->shrink_factor
1012 		 : (table->n_buckets * tuning->shrink_factor
1015 	      hash_rehash (table, candidate);
1028 hash_print (const Hash_table *table)
1032   for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1037 	printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));