1/* Hash tables for Objective C method dispatch. 2 Copyright (C) 1993, 1995, 1996 Free Software Foundation, Inc. 3 4This file is part of GNU CC. 5 6GNU CC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 2, or (at your option) 9any later version. 10 11GNU CC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GNU CC; see the file COPYING. If not, write to 18the Free Software Foundation, 59 Temple Place - Suite 330, 19Boston, 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 */ 41typedef 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 */ 62typedef 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 71typedef 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 */ 80typedef 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. */ 105extern cache_ptr module_hash_table, class_hash_table; 106 107/* Allocate and initialize a hash table. */ 108 109cache_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 115void 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 122void 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 127void 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 138node_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 142void *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 146BOOL 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 160static inline unsigned int 161hash_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. */ 169static inline unsigned int 170hash_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. */ 186static inline int 187compare_ptrs (const void *k1, const void *k2) 188{ 189 return !(k1 - k2); 190} 191 192 193/* Compare two strings. */ 194static inline int 195compare_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