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