home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / id-utils-3.2-src.tgz / tar.out / fsf / id-utils / libidu / hash.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  7KB  |  295 lines
  1. /* hash.c -- hash table maintenance
  2.    Copyright (C) 1995 Free Software Foundation, Inc.
  3.    Written by Greg McGary <gkm@gnu.ai.mit.edu>
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 2, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  18. */
  19.  
  20. #include <config.h>
  21. #include <stdio.h>
  22. #include "xstdlib.h"
  23. #include "hash.h"
  24. #include "xnls.h"
  25. #include "xmalloc.h"
  26. #include "error.h"
  27.  
  28. static void hash_rehash __P((struct hash_table* ht));
  29. static unsigned long round_up_2 __P((unsigned long rough));
  30.  
  31. /* Implement double hashing with open addressing.  The table size is
  32.    always a power of two.  The secondary (`increment') hash function
  33.    is forced to return an odd-value, in order to be relatively prime
  34.    to the table size.  This guarantees that the increment can
  35.    potentially hit every slot in the table during collision
  36.    resolution.  */
  37.  
  38. void *hash_deleted_item = &hash_deleted_item;
  39.  
  40. /* Force the table size to be a power of two, possibly rounding up the
  41.    given size.  */
  42.  
  43. void
  44. hash_init (struct hash_table* ht, unsigned long size,
  45.        hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)
  46. {
  47.   ht->ht_size = round_up_2 (size);
  48.   if (ht->ht_size > (128 * 1024)) /* prevent size from getting out of hand */
  49.     ht->ht_size /= 2;
  50.   ht->ht_vec = (void**) CALLOC (struct token *, ht->ht_size);
  51.   if (ht->ht_vec == 0)
  52.     error (1, 0, _("can't allocate %ld bytes for hash table: memory exhausted"),
  53.        ht->ht_size * sizeof(struct token *));
  54.   ht->ht_capacity = ht->ht_size * 15 / 16; /* 93.75% loading factor */
  55.   ht->ht_fill = 0;
  56.   ht->ht_collisions = 0;
  57.   ht->ht_lookups = 0;
  58.   ht->ht_rehashes = 0;
  59.   ht->ht_hash_1 = hash_1;
  60.   ht->ht_hash_2 = hash_2;
  61.   ht->ht_compare = hash_cmp;
  62. }
  63.  
  64. /* Load an array of items into `ht'.  */
  65.  
  66. void
  67. hash_load (struct hash_table* ht, void *item_table, unsigned long cardinality, unsigned long size)
  68. {
  69.   char *items = (char *) item_table;
  70.   while (cardinality--)
  71.     {
  72.       hash_insert (ht, items);
  73.       items += size;
  74.     }
  75. }
  76.  
  77. /* Returns the address of the table slot matching `key'.  If `key' is
  78.    not found, return the address of an empty slot suitable for
  79.    inserting `key'.  The caller is responsible for incrementing
  80.    ht_fill on insertion.  */
  81.  
  82. void **
  83. hash_find_slot (struct hash_table* ht, void const *key)
  84. {
  85.   void **slot;
  86.   void **deleted_slot = 0;
  87.   unsigned int hash_2 = 0;
  88.   unsigned int hash_1 = (*ht->ht_hash_1) (key);
  89.  
  90.   ht->ht_lookups++;
  91.   for (;;)
  92.     {
  93.       hash_1 %= ht->ht_size;
  94.       slot = &ht->ht_vec[hash_1];
  95.  
  96.       if (*slot == 0)
  97.     return slot;
  98.       if (*slot == hash_deleted_item)
  99.     {
  100.       if (deleted_slot == 0)
  101.         deleted_slot = slot;
  102.     }
  103.       else
  104.     {
  105.       if (key == *slot)
  106.         return slot;
  107.       if ((*ht->ht_compare) (key, *slot) == 0)
  108.         return slot;
  109.       ht->ht_collisions++;
  110.     }
  111.       if (!hash_2)
  112.       hash_2 = (*ht->ht_hash_2) (key) | 1;
  113.       hash_1 += hash_2;
  114.     }
  115. }
  116.  
  117. void *
  118. hash_find_item (struct hash_table* ht, void const *key)
  119. {
  120.   void **slot = hash_find_slot (ht, key);
  121.   return ((HASH_VACANT (*slot)) ? 0 : *slot);
  122. }
  123.  
  124. void *
  125. hash_insert (struct hash_table* ht, void *item)
  126. {
  127.   void **slot = hash_find_slot (ht, item);
  128.   return hash_insert_at (ht, item, slot);
  129. }
  130.  
  131. void *
  132. hash_insert_at (struct hash_table* ht, void *item, void const *slot)
  133. {
  134.   void *old_item = *(void **) slot;
  135.   if (HASH_VACANT (old_item))
  136.     {
  137.       ht->ht_fill++;
  138.       old_item = item;
  139.     }
  140.   *(void const **) slot = item;
  141.   if (ht->ht_fill >= ht->ht_capacity)
  142.     hash_rehash (ht);
  143.   return old_item;
  144. }
  145.  
  146. void *
  147. hash_delete (struct hash_table* ht, void const *item)
  148. {
  149.   void **slot = hash_find_slot (ht, item);
  150.   return hash_delete_at (ht, slot);
  151. }
  152.  
  153. void *
  154. hash_delete_at (struct hash_table* ht, void const *slot)
  155. {
  156.   void *item = *(void **) slot;
  157.   if (!HASH_VACANT (item))
  158.     {
  159.       *(void const **) slot = hash_deleted_item;
  160.       ht->ht_fill--;
  161.       return item;
  162.     }
  163.   else
  164.     return 0;
  165. }
  166.  
  167. void
  168. hash_free_items (struct hash_table* ht)
  169. {
  170.   void **vec = ht->ht_vec;
  171.   void **end = &vec[ht->ht_size];
  172.   for (; vec < end; vec++)
  173.     {
  174.       void *item = *vec;
  175.       if (!HASH_VACANT (item))
  176.     free (item);
  177.       *vec = 0;
  178.     }
  179.   ht->ht_fill = 0;
  180. }
  181.  
  182. void
  183. hash_delete_items (struct hash_table* ht)
  184. {
  185.   void **vec = ht->ht_vec;
  186.   void **end = &vec[ht->ht_size];
  187.   for (; vec < end; vec++)
  188.     *vec = 0;
  189.   ht->ht_fill = 0;
  190.   ht->ht_collisions = 0;
  191.   ht->ht_lookups = 0;
  192.   ht->ht_rehashes = 0;
  193. }
  194.  
  195. void
  196. hash_free (struct hash_table* ht, int free_items)
  197. {
  198.   if (free_items)
  199.     hash_free_items (ht);
  200.   free (ht->ht_vec);
  201.   ht->ht_vec = 0;
  202.   ht->ht_fill = 0;
  203.   ht->ht_capacity = 0;
  204. }
  205.  
  206. void
  207. hash_map (struct hash_table *ht, hash_map_func_t map)
  208. {
  209.   void **slot;
  210.   void **end = &ht->ht_vec[ht->ht_size];
  211.  
  212.   for (slot = ht->ht_vec; slot < end; slot++)
  213.     {
  214.       if (!HASH_VACANT (*slot))
  215.     (*map) (*slot);
  216.     }
  217. }
  218.  
  219. /* Double the size of the hash table in the event of overflow... */
  220.  
  221. static void
  222. hash_rehash (struct hash_table* ht)
  223. {
  224.   unsigned long old_ht_size = ht->ht_size;
  225.   void **old_vec = ht->ht_vec;
  226.   void **ovp;
  227.   void **slot;
  228.  
  229.   ht->ht_size *= 2;
  230.   ht->ht_rehashes++;
  231.   ht->ht_capacity = ht->ht_size - (ht->ht_size >> 4);
  232.   ht->ht_vec = (void **) CALLOC (struct token *, ht->ht_size);
  233.  
  234.   for (ovp = old_vec; ovp < &old_vec[old_ht_size]; ovp++)
  235.     {
  236.       if (*ovp == 0)
  237.     continue;
  238.       slot = hash_find_slot (ht, *ovp);
  239.       *slot = *ovp;
  240.     }
  241.   free (old_vec);
  242. }
  243.  
  244. void
  245. hash_print_stats (struct hash_table *ht, FILE *out_FILE)
  246. {
  247.   fprintf (out_FILE, _("Load=%ld/%ld=%.0f%%, "), ht->ht_fill, ht->ht_size,
  248.        100.0 * (double) ht->ht_fill / (double) ht->ht_size);
  249.   fprintf (out_FILE, _("Rehash=%d, "), ht->ht_rehashes);
  250.   fprintf (out_FILE, _("Collisions=%ld/%ld=%.0f%%"), ht->ht_collisions, ht->ht_lookups,
  251.        (ht->ht_lookups
  252.         ? (100.0 * (double) ht->ht_collisions / (double) ht->ht_lookups)
  253.         : 0));
  254. }
  255.  
  256. /* Dump all items into a NULL-terminated vector.  Use the
  257.    user-supplied vector, or malloc one.  */
  258.  
  259. void**
  260. hash_dump (struct hash_table *ht, void **vector_0, qsort_cmp_t compare)
  261. {
  262.   void **vector;
  263.   void **slot;
  264.   void **end = &ht->ht_vec[ht->ht_size];
  265.  
  266.   if (vector_0 == 0)
  267.     vector_0 = MALLOC (void *, ht->ht_fill + 1);
  268.   vector = vector_0;
  269.  
  270.   for (slot = ht->ht_vec; slot < end; slot++)
  271.     if (!HASH_VACANT (*slot))
  272.       *vector++ = *slot;
  273.   *vector = 0;
  274.  
  275.   if (compare)
  276.     qsort (vector_0, ht->ht_fill, sizeof (void *), compare);
  277.   return vector_0;
  278. }
  279.  
  280. /* Round a given number up to the nearest power of 2. */
  281.  
  282. static unsigned long
  283. round_up_2 (unsigned long rough)
  284. {
  285.   int round;
  286.  
  287.   round = 1;
  288.   while (rough)
  289.     {
  290.       round <<= 1;
  291.       rough >>= 1;
  292.     }
  293.   return round;
  294. }
  295.