1/* Hash tables for Objective C method dispatch. 2 Copyright (C) 1993-2022 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC 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 3, or (at your option) 9any later version. 10 11GCC 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 16Under Section 7 of GPL version 3, you are granted additional 17permissions described in the GCC Runtime Library Exception, version 183.1, as published by the Free Software Foundation. 19 20You should have received a copy of the GNU General Public License and 21a copy of the GCC Runtime Library Exception along with this program; 22see 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 */ 40typedef 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 */ 61typedef 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 70typedef 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 */ 79typedef 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 105cache_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 111void 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 118void 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 123void 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 134node_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 138void *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 142BOOL 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 156static inline unsigned int 157objc_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. */ 165static inline unsigned int 166objc_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. */ 182static inline int 183objc_compare_ptrs (const void *k1, const void *k2) 184{ 185 return (k1 == k2); 186} 187 188 189/* Compare two strings. */ 190static inline int 191objc_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