libobjc/objc/hash.h

   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 <string.h>
  33 #include <objc/objc.h>
  34
  35 /*
  36  * This data structure is used to hold items
  37  *  stored in a hash table.  Each node holds
  38  *  a key/value pair.
  39  *
  40  * Items in the cache are really of type void *.
  41  */
  42 typedef struct cache_node
  43 {
  44   struct cache_node *next;      /* Pointer to next entry on the list.
  45                                    NULL indicates end of list. */
  46   const void *key;              /* Key used to locate the value.  Used
  47                                    to locate value when more than one
  48                                    key computes the same hash
  49                                    value. */
  50   void *value;                  /* Value stored for the key. */
  51 } *node_ptr;
  52
  53
  54 /*
  55  * This data type is the function that computes a hash code given a key.
  56  * Therefore, the key can be a pointer to anything and the function specific
  57  * to the key type.
  58  *
  59  * Unfortunately there is a mutual data structure reference problem with this
  60  * typedef.  Therefore, to remove compiler warnings the functions passed to
  61  * hash_new will have to be casted to this type.
  62  */
  63 typedef unsigned int (*hash_func_type) (void *, const void *);
  64
  65 /*
  66  * This data type is the function that compares two hash keys and returns an
  67  * integer greater than, equal to, or less than 0, according as the first
  68  * parameter is lexicographically greater than, equal to, or less than the
  69  * second.
  70  */
  71
  72 typedef int (*compare_func_type) (const void *, const void *);
  73
  74
  75 /*
  76  * This data structure is the cache.
  77  *
  78  * It must be passed to all of the hashing routines
  79  *   (except for new).
  80  */
  81 typedef struct cache
  82 {
  83   /* Variables used to implement the hash itself.  */
  84   node_ptr *node_table; /* Pointer to an array of hash nodes.  */
  85   /* Variables used to track the size of the hash table so to determine
  86     when to resize it.  */
  87   unsigned int size; /* Number of buckets allocated for the hash table
  88                         (number of array entries allocated for
  89                         "node_table").  Must be a power of two.  */
  90   unsigned int used; /* Current number of entries in the hash table.  */
  91   unsigned int mask; /* Precomputed mask.  */
  92
  93   /* Variables used to implement indexing through the hash table.  */
  94
  95   unsigned int last_bucket; /* Tracks which entry in the array where
  96                                the last value was returned.  */
  97   /* Function used to compute a hash code given a key.
  98      This function is specified when the hash table is created.  */
  99   hash_func_type    hash_func;
 100   /* Function used to compare two hash keys to see if they are equal.  */
 101   compare_func_type compare_func;
 102 } *cache_ptr;
 103
 104
 105 /* Two important hash tables.  */
 106 extern cache_ptr module_hash_table, class_hash_table;
 107
 108 /* Allocate and initialize a hash table.  */
 109
 110 cache_ptr hash_new (unsigned int size,
 111                     hash_func_type hash_func,
 112                     compare_func_type compare_func);
 113
 114 /* Deallocate all of the hash nodes and the cache itself.  */
 115
 116 void hash_delete (cache_ptr cache);
 117
 118 /* Add the key/value pair to the hash table.  If the
 119    hash table reaches a level of fullness then it will be resized.
 120
 121    assert if the key is already in the hash.  */
 122
 123 void hash_add (cache_ptr *cachep, const void *key, void *value);
 124
 125 /* Remove the key/value pair from the hash table.
 126    assert if the key isn't in the table.  */
 127
 128 void hash_remove (cache_ptr cache, const void *key);
 129
 130 /* Used to index through the hash table.  Start with NULL
 131    to get the first entry.
 132
 133    Successive calls pass the value returned previously.
 134    ** Don't modify the hash during this operation ***
 135
 136    Cache nodes are returned such that key or value can
 137    be extracted.  */
 138
 139 node_ptr hash_next (cache_ptr cache, node_ptr node);
 140
 141 /* Used to return a value from a hash table using a given key.  */
 142
 143 void *hash_value_for_key (cache_ptr cache, const void *key);
 144
 145 /* Used to determine if the given key exists in the hash table */
 146
 147 BOOL hash_is_key_in_hash (cache_ptr cache, const void *key);
 148
 149 /************************************************
 150
 151         Useful hashing functions.
 152
 153         Declared inline for your pleasure.
 154
 155 ************************************************/
 156
 157 /* Calculate a hash code by performing some
 158    manipulation of the key pointer.  (Use the lowest bits
 159    except for those likely to be 0 due to alignment.)  */
 160
 161 static inline unsigned int
 162 hash_ptr (cache_ptr cache, const void *key)
 163 {
 164   return ((size_t)key / sizeof (void *)) & cache->mask;
 165 }
 166
 167
 168 /* Calculate a hash code by iterating over a NULL
 169    terminate string.  */
 170 static inline unsigned int
 171 hash_string (cache_ptr cache, const void *key)
 172 {
 173   unsigned int ret = 0;
 174   unsigned int ctr = 0;
 175
 176
 177   while (*(char *) key) {
 178     ret ^= *(char *) key++ << ctr;
 179     ctr = (ctr + 1) % sizeof (void *);
 180   }
 181
 182   return ret & cache->mask;
 183 }
 184
 185
 186 /* Compare two pointers for equality.  */
 187 static inline int
 188 compare_ptrs (const void *k1, const void *k2)
 189 {
 190   return ! (k1 - k2);
 191 }
 192
 193
 194 /* Compare two strings.  */
 195 static inline int
 196 compare_strings (const void *k1, const void *k2)
 197 {
 198   if (k1 == k2)
 199     return 1;
 200   else if (k1 == 0 || k2 == 0)
 201     return 0;
 202   else
 203     return ! strcmp (k1, k2);
 204 }
 205
 206
 207 #endif /* not __hash_INCLUDE_GNU */