libobjc/objc-private/hash.h

   1 /* Hash tables for Objective C method dispatch.
   2    Copyright (C) 1993, 1995, 1996, 2004, 2009 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC 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 3, or (at your option)
   9 any later version.
  10
  11 GCC 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 Under Section 7 of GPL version 3, you are granted additional
  17 permissions described in the GCC Runtime Library Exception, version
  18 3.1, as published by the Free Software Foundation.
  19
  20 You should have received a copy of the GNU General Public License and
  21 a copy of the GCC Runtime Library Exception along with this program;
  22 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 <http://www.gnu.org/licenses/>.  */
  24
  25 /* You need to include this file after including objc.h  */
  26
  27 #ifndef __hash_INCLUDE_GNU
  28 #define __hash_INCLUDE_GNU
  29
  30 #include <stddef.h>
  31 #include <string.h>
  32
  33 #ifdef __cplusplus
  34 extern "C" {
  35 #endif /* __cplusplus */
  36
  37 /*
  38  * This data structure is used to hold items
  39  *  stored in a hash table.  Each node holds
  40  *  a key/value pair.
  41  *
  42  * Items in the cache are really of type void *.
  43  */
  44 typedef struct cache_node
  45 {
  46   struct cache_node *next;      /* Pointer to next entry on the list.
  47                                    NULL indicates end of list. */
  48   const void *key;              /* Key used to locate the value.  Used
  49                                    to locate value when more than one
  50                                    key computes the same hash
  51                                    value. */
  52   void *value;                  /* Value stored for the key. */
  53 } *node_ptr;
  54
  55
  56 /*
  57  * This data type is the function that computes a hash code given a key.
  58  * Therefore, the key can be a pointer to anything and the function specific
  59  * to the key type.
  60  *
  61  * Unfortunately there is a mutual data structure reference problem with this
  62  * typedef.  Therefore, to remove compiler warnings the functions passed to
  63  * objc_hash_new will have to be casted to this type.
  64  */
  65 typedef unsigned int (*hash_func_type) (void *, const void *);
  66
  67 /*
  68  * This data type is the function that compares two hash keys and returns an
  69  * integer greater than, equal to, or less than 0, according as the first
  70  * parameter is lexicographically greater than, equal to, or less than the
  71  * second.
  72  */
  73
  74 typedef int (*compare_func_type) (const void *, const void *);
  75
  76
  77 /*
  78  * This data structure is the cache.
  79  *
  80  * It must be passed to all of the hashing routines
  81  *   (except for new).
  82  */
  83 typedef struct cache
  84 {
  85   /* Variables used to implement the hash itself.  */
  86   node_ptr *node_table; /* Pointer to an array of hash nodes.  */
  87   /* Variables used to track the size of the hash table so to determine
  88     when to resize it.  */
  89   unsigned int size; /* Number of buckets allocated for the hash table
  90                         (number of array entries allocated for
  91                         "node_table").  Must be a power of two.  */
  92   unsigned int used; /* Current number of entries in the hash table.  */
  93   unsigned int mask; /* Precomputed mask.  */
  94
  95   /* Variables used to implement indexing through the hash table.  */
  96
  97   unsigned int last_bucket; /* Tracks which entry in the array where
  98                                the last value was returned.  */
  99   /* Function used to compute a hash code given a key.
 100      This function is specified when the hash table is created.  */
 101   hash_func_type    hash_func;
 102   /* Function used to compare two hash keys to see if they are equal.  */
 103   compare_func_type compare_func;
 104 } *cache_ptr;
 105
 106
 107 /* Two important hash tables.  */
 108 extern cache_ptr module_hash_table, class_hash_table;
 109
 110 /* Allocate and initialize a hash table.  */
 111
 112 cache_ptr objc_hash_new (unsigned int size,
 113                          hash_func_type hash_func,
 114                          compare_func_type compare_func);
 115
 116 /* Deallocate all of the hash nodes and the cache itself.  */
 117
 118 void objc_hash_delete (cache_ptr cache);
 119
 120 /* Add the key/value pair to the hash table.  If the
 121    hash table reaches a level of fullness then it will be resized.
 122
 123    assert if the key is already in the hash.  */
 124
 125 void objc_hash_add (cache_ptr *cachep, const void *key, void *value);
 126
 127 /* Remove the key/value pair from the hash table.
 128    assert if the key isn't in the table.  */
 129
 130 void objc_hash_remove (cache_ptr cache, const void *key);
 131
 132 /* Used to index through the hash table.  Start with NULL
 133    to get the first entry.
 134
 135    Successive calls pass the value returned previously.
 136    ** Don't modify the hash during this operation ***
 137
 138    Cache nodes are returned such that key or value can
 139    be extracted.  */
 140
 141 node_ptr objc_hash_next (cache_ptr cache, node_ptr node);
 142
 143 /* Used to return a value from a hash table using a given key.  */
 144
 145 void *objc_hash_value_for_key (cache_ptr cache, const void *key);
 146
 147 /* Used to determine if the given key exists in the hash table */
 148
 149 BOOL objc_hash_is_key_in_hash (cache_ptr cache, const void *key);
 150
 151 /************************************************
 152
 153         Useful hashing functions.
 154
 155         Declared inline for your pleasure.
 156
 157 ************************************************/
 158
 159 /* Calculate a hash code by performing some
 160    manipulation of the key pointer.  (Use the lowest bits
 161    except for those likely to be 0 due to alignment.)  */
 162
 163 static inline unsigned int
 164 objc_hash_ptr (cache_ptr cache, const void *key)
 165 {
 166   return ((size_t)key / sizeof (void *)) & cache->mask;
 167 }
 168
 169
 170 /* Calculate a hash code by iterating over a NULL
 171    terminate string.  */
 172 static inline unsigned int
 173 objc_hash_string (cache_ptr cache, const void *key)
 174 {
 175   unsigned int ret = 0;
 176   unsigned int ctr = 0;
 177   const char *ckey = (const char *) key;
 178
 179   while (*ckey) {
 180     ret ^= *ckey++ << ctr;
 181     ctr = (ctr + 1) % sizeof (void *);
 182   }
 183
 184   return ret & cache->mask;
 185 }
 186
 187
 188 /* Compare two pointers for equality.  */
 189 static inline int
 190 objc_compare_ptrs (const void *k1, const void *k2)
 191 {
 192   return (k1 == k2);
 193 }
 194
 195
 196 /* Compare two strings.  */
 197 static inline int
 198 objc_compare_strings (const void *k1, const void *k2)
 199 {
 200   if (k1 == k2)
 201     return 1;
 202   else if (k1 == 0 || k2 == 0)
 203     return 0;
 204   else
 205     return ! strcmp ((const char *) k1, (const char *) k2);
 206 }
 207
 208
 209 #ifdef __cplusplus
 210 }
 211 #endif /* __cplusplus */
 212
 213
 214 #endif /* not __hash_INCLUDE_GNU */