1 /* hash.h -- decls for hash table 2 Copyright (C) 1995, 1999, 2002, 2010 Free Software Foundation, Inc. 3 Written by Greg McGary <gkm@gnu.org> <greg@mcgary.org> 4 5 GNU Make is free software; you can redistribute it and/or modify it under the 6 terms of the GNU General Public License as published by the Free Software 7 Foundation; either version 3 of the License, or (at your option) any later 8 version. 9 10 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY 11 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR 12 A PARTICULAR PURPOSE. See the GNU General Public License for more details. 13 14 You should have received a copy of the GNU General Public License along with 15 this program. If not, see <http://www.gnu.org/licenses/>. */ 16 17 #ifndef _hash_h_ 18 #define _hash_h_ 19 20 #include <stdio.h> 21 #include <ctype.h> 22 23 #if defined __cplusplus || (defined __STDC__ && __STDC__) || defined WINDOWS32 24 # if !defined __GLIBC__ || !defined __P 25 # undef __P 26 # define __P(protos) protos 27 # endif 28 #else /* Not C++ or ANSI C. */ 29 # undef __P 30 # define __P(protos) () 31 /* We can get away without defining `const' here only because in this file 32 it is used only inside the prototype for `fnmatch', which is elided in 33 non-ANSI C where `const' is problematical. */ 34 #endif /* C++ or ANSI C. */ 35 36 typedef unsigned long (*hash_func_t) __P((void const *key)); 37 typedef int (*hash_cmp_func_t) __P((void const *x, void const *y)); 38 typedef void (*hash_map_func_t) __P((void const *item)); 39 typedef void (*hash_map_arg_func_t) __P((void const *item, void *arg)); 40 41 struct hash_table 42 { 43 void **ht_vec; 44 unsigned long ht_size; /* total number of slots (power of 2) */ 45 unsigned long ht_capacity; /* usable slots, limited by loading-factor */ 46 unsigned long ht_fill; /* items in table */ 47 unsigned long ht_empty_slots; /* empty slots not including deleted slots */ 48 unsigned long ht_collisions; /* # of failed calls to comparison function */ 49 unsigned long ht_lookups; /* # of queries */ 50 unsigned int ht_rehashes; /* # of times we've expanded table */ 51 hash_func_t ht_hash_1; /* primary hash function */ 52 hash_func_t ht_hash_2; /* secondary hash function */ 53 hash_cmp_func_t ht_compare; /* comparison function */ 54 #ifdef CONFIG_WITH_STRCACHE2 55 struct strcache2 *ht_strcache; /* the string cache pointer. */ 56 unsigned int ht_off_string; /* offsetof (struct key, string) */ 57 #endif 58 }; 59 60 typedef int (*qsort_cmp_t) __P((void const *, void const *)); 61 62 void hash_init __P((struct hash_table *ht, unsigned long size, 63 hash_func_t hash_1, hash_func_t hash_2, hash_cmp_func_t hash_cmp)); 64 void hash_load __P((struct hash_table *ht, void *item_table, 65 unsigned long cardinality, unsigned long size)); 66 void **hash_find_slot __P((struct hash_table *ht, void const *key)); 67 void *hash_find_item __P((struct hash_table *ht, void const *key)); 68 void *hash_insert __P((struct hash_table *ht, const void *item)); 69 void *hash_insert_at __P((struct hash_table *ht, const void *item, void const *slot)); 70 void *hash_delete __P((struct hash_table *ht, void const *item)); 71 void *hash_delete_at __P((struct hash_table *ht, void const *slot)); 72 void hash_delete_items __P((struct hash_table *ht)); 73 void hash_free_items __P((struct hash_table *ht)); 74 void hash_free __P((struct hash_table *ht, int free_items)); 75 #ifdef CONFIG_WITH_ALLOC_CACHES 76 void hash_free_items_cached __P((struct hash_table *ht, struct alloccache *cache)); 77 void hash_free_cached __P((struct hash_table *ht, int free_items, struct alloccache *cache)); 78 #endif 79 void hash_map __P((struct hash_table *ht, hash_map_func_t map)); 80 void hash_map_arg __P((struct hash_table *ht, hash_map_arg_func_t map, void *arg)); 81 void hash_print_stats __P((struct hash_table *ht, FILE *out_FILE)); 82 void **hash_dump __P((struct hash_table *ht, void **vector_0, qsort_cmp_t compare)); 83 84 #ifdef CONFIG_WITH_STRCACHE2 85 void hash_init_strcached __P((struct hash_table *ht, unsigned long size, 86 struct strcache2 *strcache, unsigned int off_strptr)); 87 void **hash_find_slot_strcached __P((struct hash_table *ht, const void *key)); 88 void *hash_find_item_strcached __P((struct hash_table *ht, void const *key)); 89 void *hash_insert_strcached __P((struct hash_table *ht, const void *item)); 90 void *hash_delete_strcached __P((struct hash_table *ht, void const *item)); 91 #endif /* CONFIG_WITH_STRCACHE2 */ 92 93 extern void *hash_deleted_item; 94 #define HASH_VACANT(item) ((item) == 0 || (void *) (item) == hash_deleted_item) 95 96 97 /* hash and comparison macros for case-sensitive string keys. */ 98 99 /* Due to the strcache, it's not uncommon for the string pointers to 100 be identical. Take advantage of that to short-circuit string compares. */ 101 102 #define STRING_HASH_1(KEY, RESULT) do { \ 103 unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ 104 while (*++_key_) \ 105 (RESULT) += (*_key_ << (_key_[1] & 0xf)); \ 106 } while (0) 107 #define return_STRING_HASH_1(KEY) do { \ 108 unsigned long _result_ = 0; \ 109 STRING_HASH_1 ((KEY), _result_); \ 110 return _result_; \ 111 } while (0) 112 113 #define STRING_HASH_2(KEY, RESULT) do { \ 114 unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ 115 while (*++_key_) \ 116 (RESULT) += (*_key_ << (_key_[1] & 0x7)); \ 117 } while (0) 118 #define return_STRING_HASH_2(KEY) do { \ 119 unsigned long _result_ = 0; \ 120 STRING_HASH_2 ((KEY), _result_); \ 121 return _result_; \ 122 } while (0) 123 124 #define STRING_COMPARE(X, Y, RESULT) do { \ 125 RESULT = (X) == (Y) ? 0 : strcmp ((X), (Y)); \ 126 } while (0) 127 #define return_STRING_COMPARE(X, Y) do { \ 128 return (X) == (Y) ? 0 : strcmp ((X), (Y)); \ 129 } while (0) 130 131 132 #define STRING_N_HASH_1(KEY, N, RESULT) do { \ 133 unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ 134 int _n_ = (N); \ 135 if (_n_) \ 136 while (--_n_ && *++_key_) \ 137 (RESULT) += (*_key_ << (_key_[1] & 0xf)); \ 138 (RESULT) += *++_key_; \ 139 } while (0) 140 #define return_STRING_N_HASH_1(KEY, N) do { \ 141 unsigned long _result_ = 0; \ 142 STRING_N_HASH_1 ((KEY), (N), _result_); \ 143 return _result_; \ 144 } while (0) 145 146 #define STRING_N_HASH_2(KEY, N, RESULT) do { \ 147 unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ 148 int _n_ = (N); \ 149 if (_n_) \ 150 while (--_n_ && *++_key_) \ 151 (RESULT) += (*_key_ << (_key_[1] & 0x7)); \ 152 (RESULT) += *++_key_; \ 153 } while (0) 154 #define return_STRING_N_HASH_2(KEY, N) do { \ 155 unsigned long _result_ = 0; \ 156 STRING_N_HASH_2 ((KEY), (N), _result_); \ 157 return _result_; \ 158 } while (0) 159 160 #define STRING_N_COMPARE(X, Y, N, RESULT) do { \ 161 RESULT = (X) == (Y) ? 0 : strncmp ((X), (Y), (N)); \ 162 } while (0) 163 #define return_STRING_N_COMPARE(X, Y, N) do { \ 164 return (X) == (Y) ? 0 : strncmp ((X), (Y), (N)); \ 165 } while (0) 166 167 #ifdef HAVE_CASE_INSENSITIVE_FS 168 169 /* hash and comparison macros for case-insensitive string _key_s. */ 170 171 #define ISTRING_HASH_1(KEY, RESULT) do { \ 172 unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ 173 while (*++_key_) \ 174 (RESULT) += ((isupper (*_key_) ? tolower (*_key_) : *_key_) << (_key_[1] & 0xf)); \ 175 } while (0) 176 #define return_ISTRING_HASH_1(KEY) do { \ 177 unsigned long _result_ = 0; \ 178 ISTRING_HASH_1 ((KEY), _result_); \ 179 return _result_; \ 180 } while (0) 181 182 #define ISTRING_HASH_2(KEY, RESULT) do { \ 183 unsigned char const *_key_ = (unsigned char const *) (KEY) - 1; \ 184 while (*++_key_) \ 185 (RESULT) += ((isupper (*_key_) ? tolower (*_key_) : *_key_) << (_key_[1] & 0x7)); \ 186 } while (0) 187 #define return_ISTRING_HASH_2(KEY) do { \ 188 unsigned long _result_ = 0; \ 189 ISTRING_HASH_2 ((KEY), _result_); \ 190 return _result_; \ 191 } while (0) 192 193 #define ISTRING_COMPARE(X, Y, RESULT) do { \ 194 RESULT = (X) == (Y) ? 0 : strcasecmp ((X), (Y)); \ 195 } while (0) 196 #define return_ISTRING_COMPARE(X, Y) do { \ 197 return (X) == (Y) ? 0 : strcasecmp ((X), (Y)); \ 198 } while (0) 199 200 #else 201 202 #define ISTRING_HASH_1(KEY, RESULT) STRING_HASH_1 ((KEY), (RESULT)) 203 #define return_ISTRING_HASH_1(KEY) return_STRING_HASH_1 (KEY) 204 205 #define ISTRING_HASH_2(KEY, RESULT) STRING_HASH_2 ((KEY), (RESULT)) 206 #define return_ISTRING_HASH_2(KEY) return_STRING_HASH_2 (KEY) 207 208 #define ISTRING_COMPARE(X, Y, RESULT) STRING_COMPARE ((X), (Y), (RESULT)) 209 #define return_ISTRING_COMPARE(X, Y) return_STRING_COMPARE ((X), (Y)) 210 211 #endif 212 213 /* hash and comparison macros for integer _key_s. */ 214 215 #define INTEGER_HASH_1(KEY, RESULT) do { \ 216 (RESULT) += ((unsigned long)(KEY)); \ 217 } while (0) 218 #define return_INTEGER_HASH_1(KEY) do { \ 219 unsigned long _result_ = 0; \ 220 INTEGER_HASH_1 ((KEY), _result_); \ 221 return _result_; \ 222 } while (0) 223 224 #define INTEGER_HASH_2(KEY, RESULT) do { \ 225 (RESULT) += ~((unsigned long)(KEY)); \ 226 } while (0) 227 #define return_INTEGER_HASH_2(KEY) do { \ 228 unsigned long _result_ = 0; \ 229 INTEGER_HASH_2 ((KEY), _result_); \ 230 return _result_; \ 231 } while (0) 232 233 #define INTEGER_COMPARE(X, Y, RESULT) do { \ 234 (RESULT) = X - Y; \ 235 } while (0) 236 #define return_INTEGER_COMPARE(X, Y) do { \ 237 int _result_; \ 238 INTEGER_COMPARE (X, Y, _result_); \ 239 return _result_; \ 240 } while (0) 241 242 /* hash and comparison macros for address keys. */ 243 244 #define ADDRESS_HASH_1(KEY, RESULT) INTEGER_HASH_1 (((unsigned long)(KEY)) >> 3, (RESULT)) 245 #define ADDRESS_HASH_2(KEY, RESULT) INTEGER_HASH_2 (((unsigned long)(KEY)) >> 3, (RESULT)) 246 #define ADDRESS_COMPARE(X, Y, RESULT) INTEGER_COMPARE ((X), (Y), (RESULT)) 247 #define return_ADDRESS_HASH_1(KEY) return_INTEGER_HASH_1 (((unsigned long)(KEY)) >> 3) 248 #define return_ADDRESS_HASH_2(KEY) return_INTEGER_HASH_2 (((unsigned long)(KEY)) >> 3) 249 #define return_ADDRESS_COMPARE(X, Y) return_INTEGER_COMPARE ((X), (Y)) 250 251 #endif /* not _hash_h_ */ 252