home *** CD-ROM | disk | FTP | other *** search
/ PC World 2000 April / PCWorld_2000-04_cd.bin / Software / Servis / Devc / _SETUP.6 / Group7 / hash.h < prev    next >
C/C++ Source or Header  |  1999-11-07  |  6KB  |  207 lines
  1. /* Hash tables for Objective C method dispatch.
  2.    Copyright (C) 1993, 1995, 1996 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU CC.
  5.  
  6. GNU CC is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 2, or (at your option)
  9. any later version.
  10.  
  11. GNU CC is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GNU CC; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 59 Temple Place - Suite 330,
  19. Boston, MA 02111-1307, USA.  */
  20.  
  21. /* As a special exception, if you link this library with files
  22.    compiled with GCC to produce an executable, this does not cause
  23.    the resulting executable to be covered by the GNU General Public License.
  24.    This exception does not however invalidate any other reasons why
  25.    the executable file might be covered by the GNU General Public License.  */
  26.  
  27.  
  28. #ifndef __hash_INCLUDE_GNU
  29. #define __hash_INCLUDE_GNU
  30.  
  31. #include <stddef.h>
  32. #include <objc/objc.h>
  33.  
  34. /*
  35.  * This data structure is used to hold items
  36.  *  stored in a hash table.  Each node holds 
  37.  *  a key/value pair.
  38.  *
  39.  * Items in the cache are really of type void *.
  40.  */
  41. typedef struct cache_node
  42. {
  43.   struct cache_node *next;    /* Pointer to next entry on the list.
  44.                    NULL indicates end of list. */
  45.   const void *key;        /* Key used to locate the value.  Used
  46.                    to locate value when more than one
  47.                    key computes the same hash
  48.                    value. */
  49.   void *value;            /* Value stored for the key. */
  50. } *node_ptr;
  51.  
  52.  
  53. /*
  54.  * This data type is the function that computes a hash code given a key.
  55.  * Therefore, the key can be a pointer to anything and the function specific
  56.  * to the key type. 
  57.  *
  58.  * Unfortunately there is a mutual data structure reference problem with this
  59.  * typedef.  Therefore, to remove compiler warnings the functions passed to
  60.  * hash_new will have to be casted to this type. 
  61.  */
  62. typedef unsigned int (*hash_func_type)(void *, const void *);
  63.  
  64. /*
  65.  * This data type is the function that compares two hash keys and returns an
  66.  * integer greater than, equal to, or less than 0, according as the first
  67.  * parameter is lexicographically greater than, equal to, or less than the
  68.  * second. 
  69.  */
  70.  
  71. typedef int (*compare_func_type)(const void *, const void *);
  72.  
  73.  
  74. /*
  75.  * This data structure is the cache.
  76.  *
  77.  * It must be passed to all of the hashing routines
  78.  *   (except for new).
  79.  */
  80. typedef struct cache
  81. {
  82.   /* Variables used to implement the hash itself.  */
  83.   node_ptr *node_table; /* Pointer to an array of hash nodes.  */
  84.   /* Variables used to track the size of the hash table so to determine
  85.     when to resize it.  */
  86.   unsigned int size; /* Number of buckets allocated for the hash table
  87.             (number of array entries allocated for
  88.             "node_table").  Must be a power of two.  */
  89.   unsigned int used; /* Current number of entries in the hash table.  */
  90.   unsigned int mask; /* Precomputed mask.  */
  91.  
  92.   /* Variables used to implement indexing through the hash table.  */
  93.  
  94.   unsigned int last_bucket; /* Tracks which entry in the array where
  95.                    the last value was returned.  */
  96.   /* Function used to compute a hash code given a key. 
  97.      This function is specified when the hash table is created.  */
  98.   hash_func_type    hash_func;
  99.   /* Function used to compare two hash keys to see if they are equal.  */
  100.   compare_func_type compare_func;
  101. } *cache_ptr;
  102.  
  103.  
  104. /* Two important hash tables.  */
  105. extern cache_ptr module_hash_table, class_hash_table;
  106.  
  107. /* Allocate and initialize a hash table.  */ 
  108.  
  109. cache_ptr hash_new (unsigned int size,
  110.             hash_func_type hash_func,
  111.             compare_func_type compare_func);
  112.                        
  113. /* Deallocate all of the hash nodes and the cache itself.  */
  114.  
  115. void hash_delete (cache_ptr cache);
  116.  
  117. /* Add the key/value pair to the hash table.  If the
  118.    hash table reaches a level of fullness then it will be resized. 
  119.                                                    
  120.    assert if the key is already in the hash.  */
  121.  
  122. void hash_add (cache_ptr *cachep, const void *key, void *value);
  123.      
  124. /* Remove the key/value pair from the hash table.  
  125.    assert if the key isn't in the table.  */
  126.  
  127. void hash_remove (cache_ptr cache, const void *key);
  128.  
  129. /* Used to index through the hash table.  Start with NULL
  130.    to get the first entry.
  131.                                                   
  132.    Successive calls pass the value returned previously.
  133.    ** Don't modify the hash during this operation *** 
  134.                                                   
  135.    Cache nodes are returned such that key or value can
  136.    be extracted.  */
  137.  
  138. node_ptr hash_next (cache_ptr cache, node_ptr node);
  139.  
  140. /* Used to return a value from a hash table using a given key.  */
  141.  
  142. void *hash_value_for_key (cache_ptr cache, const void *key);
  143.  
  144. /* Used to determine if the given key exists in the hash table */
  145.  
  146. BOOL hash_is_key_in_hash (cache_ptr cache, const void *key);
  147.  
  148. /************************************************
  149.  
  150.         Useful hashing functions.  
  151.         
  152.         Declared inline for your pleasure.
  153.         
  154. ************************************************/
  155.  
  156. /* Calculate a hash code by performing some 
  157.    manipulation of the key pointer.  (Use the lowest bits
  158.    except for those likely to be 0 due to alignment.)  */
  159.  
  160. static inline unsigned int
  161. hash_ptr (cache_ptr cache, const void *key)
  162. {
  163.   return ((size_t)key / sizeof (void *)) & cache->mask;
  164. }
  165.  
  166.  
  167. /* Calculate a hash code by iterating over a NULL 
  168.    terminate string.  */
  169. static inline unsigned int 
  170. hash_string (cache_ptr cache, const void *key)
  171. {
  172.   unsigned int ret = 0;
  173.   unsigned int ctr = 0;
  174.         
  175.         
  176.   while (*(char*)key) {
  177.     ret ^= *(char*)key++ << ctr;
  178.     ctr = (ctr + 1) % sizeof (void *);
  179.   }
  180.  
  181.   return ret & cache->mask;
  182. }
  183.  
  184.  
  185. /* Compare two pointers for equality.  */
  186. static inline int 
  187. compare_ptrs (const void *k1, const void *k2)
  188. {
  189.   return !(k1 - k2);
  190. }
  191.  
  192.  
  193. /* Compare two strings.  */
  194. static inline int 
  195. compare_strings (const void *k1, const void *k2)
  196. {
  197.   if (k1 == k2)
  198.     return 1;
  199.   else if (k1 == 0 || k2 == 0)
  200.     return 0;
  201.   else
  202.     return !strcmp (k1, k2);
  203. }
  204.  
  205.  
  206. #endif /* not __hash_INCLUDE_GNU */
  207.