1 /****************************************************************** 2 * 3 * fthash.h - fast dynamic hash tables 4 * 5 * Copyright 2002 by 6 * David Turner, Robert Wilhelm, and Werner Lemberg 7 * 8 * This file is part of the FreeType project, and may only be used, 9 * modified, and distributed under the terms of the FreeType project 10 * license, LICENSE.TXT. By continuing to use, modify, or distribute 11 * this file you indicate that you have read the license and 12 * understand and accept it fully. 13 * 14 * 15 * This header is used to define dynamic hash tables as described 16 * by the article "Main-Memory Linear Hashing - Some Enhancements 17 * of Larson's Algorithm" by Mikael Petterson. 18 * 19 * Basically, linear hashing prevents big "stalls" during 20 * resizes of the buckets array by only splitting one bucket 21 * at a time. This ensures excellent response time even when 22 * the table is frequently resized.. 23 * 24 * 25 * Note that the use of the FT_Hash type is rather unusual in order 26 * to be as generic and efficient as possible. See the comments in the 27 * following definitions for more details. 28 */ 29 30 #ifndef __FT_HASH_H__ 31 #define __FT_HASH_H__ 32 33 #include <ft2build.h> 34 #include FT_TYPES_H 35 36 FT_BEGIN_HEADER 37 38 /*********************************************************** 39 * 40 * @type: FT_Hash 41 * 42 * @description: 43 * handle to a @FT_HashRec structure used to model a 44 * dynamic hash table 45 */ 46 typedef struct FT_HashRec_* FT_Hash; 47 48 49 /*********************************************************** 50 * 51 * @type: FT_HashNode 52 * 53 * @description: 54 * handle to a @FT_HashNodeRec structure used to model a 55 * single node of a hash table 56 */ 57 typedef struct FT_HashNodeRec_* FT_HashNode; 58 59 60 /*********************************************************** 61 * 62 * @type: FT_HashLookup 63 * 64 * @description: 65 * handle to a @FT_HashNode pointer. This is returned by 66 * the @ft_hash_lookup function and can later be used by 67 * @ft_hash_add or @ft_hash_remove 68 */ 69 typedef FT_HashNode* FT_HashLookup; 70 71 72 /*********************************************************** 73 * 74 * @type: FT_Hash_EqualFunc 75 * 76 * @description: 77 * a function used to compare two nodes of the hash table 78 * 79 * @input: 80 * node1 :: handle to first node 81 * node2 :: handle to second node 82 * 83 * @return: 84 * 1 iff the 'keys' in 'node1' and 'node2' are identical. 85 * 0 otherwise. 86 */ 87 typedef FT_Int (*FT_Hash_EqualFunc)( FT_HashNode node1, 88 FT_HashNode node2 ); 89 90 91 /*********************************************************** 92 * 93 * @struct: FT_HashRec 94 * 95 * @description: 96 * a structure used to model a dynamic hash table. 97 * 98 * @fields: 99 * memory :: memory manager used to allocate 100 * the buckets array and the hash nodes 101 * 102 * buckets :: array of hash buckets 103 * 104 * node_size :: size of node in bytes 105 * node_compare :: a function used to compare two nodes 106 * node_hash :: a function used to compute the hash 107 * value of a given node 108 * p :: 109 * mask :: 110 * slack :: 111 * 112 * @note: 113 * 'p', 'mask' and 'slack' are control values managed by 114 * the hash table. Do not try to interpret them directly. 115 * 116 * You can grab the hash table size by calling 117 * '@ft_hash_get_size'. 118 */ 119 typedef struct FT_HashRec_ 120 { 121 FT_HashNode* buckets; 122 FT_UInt p; 123 FT_UInt mask; /* really maxp-1 */ 124 FT_Long slack; 125 FT_Hash_EqualFunc node_equal; 126 FT_Memory memory; 127 128 } FT_HashRec; 129 130 131 /*********************************************************** 132 * 133 * @struct: FT_HashNodeRec 134 * 135 * @description: 136 * a structure used to model the root fields of a dynamic 137 * hash table node. 138 * 139 * it's up to client applications to "sub-class" this 140 * structure to add relevant (key,value) definitions 141 * 142 * @fields: 143 * link :: pointer to next node in bucket's collision list 144 * hash :: 32-bit hash value for this node 145 * 146 * @note: 147 * it's up to client applications to "sub-class" this structure 148 * to add relevant (key,value) type definitions. For example, 149 * if we want to build a "string -> int" mapping, we could use 150 * something like: 151 * 152 * { 153 * typedef struct MyNodeRec_ 154 * { 155 * FT_HashNodeRec hnode; 156 * const char* key; 157 * int value; 158 * 159 * } MyNodeRec, *MyNode; 160 * } 161 * 162 */ 163 typedef struct FT_HashNodeRec_ 164 { 165 FT_HashNode link; 166 FT_UInt32 hash; 167 168 } FT_HashNodeRec; 169 170 171 /**************************************************************** 172 * 173 * @function: ft_hash_init 174 * 175 * @description: 176 * initialize a dynamic hash table 177 * 178 * @input: 179 * table :: handle to target hash table structure 180 * node_equal :: node comparison function 181 * memory :: memory manager handle used to allocate the 182 * buckets array within the hash table 183 * 184 * @return: 185 * error code. 0 means success 186 * 187 * @note: 188 * the node comparison function should only compare node _keys_ 189 * and ignore values !! with good hashing computation (which the 190 * user must perform itself), the comparison function should be 191 * pretty seldom called. 192 * 193 * here is a simple example: 194 * 195 * { 196 * static int my_equal( MyNode node1, 197 * MyNode node2 ) 198 * { 199 * // compare keys of 'node1' and 'node2' 200 * return (strcmp( node1->key, node2->key ) == 0); 201 * } 202 * 203 * .... 204 * 205 * ft_hash_init( &hash, (FT_Hash_EqualFunc) my_compare, memory ); 206 * .... 207 * } 208 */ 209 FT_BASE( FT_Error ) 210 ft_hash_init( FT_Hash table, 211 FT_Hash_EqualFunc compare, 212 FT_Memory memory ); 213 214 215 /**************************************************************** 216 * 217 * @function: ft_hash_lookup 218 * 219 * @description: 220 * search a hash table to find a node corresponding to a given 221 * key. 222 * 223 * @input: 224 * table :: handle to target hash table structure 225 * keynode :: handle to a reference hash node that will be 226 * only used for key comparisons with the table's 227 * elements 228 * 229 * @return: 230 * a pointer-to-hash-node value, which must be used as followed: 231 * 232 * - if '*result' is NULL, the key wasn't found in the hash 233 * table. The value of 'result' can be used to add new elements 234 * through @ft_hash_add however.. 235 * 236 * - if '*result' is not NULL, it's a handle to the first table 237 * node that corresponds to the search key. The value of 'result' 238 * can be used to remove this element through @ft_hash_remove 239 * 240 * @note: 241 * here is an example: 242 * 243 * { 244 * // maps a string to an integer with a hash table 245 * // returns -1 in case of failure 246 * // 247 * int my_lookup( FT_Hash table, 248 * const char* key ) 249 * { 250 * MyNode* pnode; 251 * MyNodeRec noderec; 252 * 253 * // set-up key node. It's 'hash' and 'key' fields must 254 * // be set correctly.. we ignore 'link' and 'value' 255 * // 256 * noderec.hnode.hash = strhash( key ); 257 * noderec.key = key; 258 * 259 * // perform search - return value 260 * // 261 * pnode = (MyNode) ft_hash_lookup( table, &noderec ); 262 * if ( *pnode ) 263 * { 264 * // we found it 265 * return (*pnode)->value; 266 * } 267 * return -1; 268 * } 269 * } 270 */ 271 FT_BASE_DEF( FT_HashLookup ) 272 ft_hash_lookup( FT_Hash table, 273 FT_HashNode keynode ); 274 275 276 /**************************************************************** 277 * 278 * @function: ft_hash_add 279 * 280 * @description: 281 * add a new node to a dynamic hash table. the user must 282 * call @ft_hash_lookup and allocate a new node before calling 283 * this function. 284 * 285 * @input: 286 * table :: hash table handle 287 * lookup :: pointer-to-hash-node value returned by @ft_hash_lookup 288 * new_node :: handle to new hash node. All its fields must be correctly 289 * set, including 'hash'. 290 * 291 * @return: 292 * error code. 0 means success 293 * 294 * @note: 295 * this function should always be used _after_ a call to @ft_hash_lookup 296 * that returns a pointer to a NULL handle. Here's an example: 297 * 298 * { 299 * // sets the value corresponding to a given string key 300 * // 301 * void my_set( FT_Hash table, 302 * const char* key, 303 * int value ) 304 * { 305 * MyNode* pnode; 306 * MyNodeRec noderec; 307 * MyNode node; 308 * 309 * // set-up key node. It's 'hash' and 'key' fields must 310 * // be set correctly.. 311 * noderec.hnode.hash = strhash( key ); 312 * noderec.key = key; 313 * 314 * // perform search - return value 315 * pnode = (MyNode) ft_hash_lookup( table, &noderec ); 316 * if ( *pnode ) 317 * { 318 * // we found it, simply replace the value in the node 319 * (*pnode)->value = value; 320 * return; 321 * } 322 * 323 * // allocate a new node - and set it up 324 * node = (MyNode) malloc( sizeof(*node) ); 325 * if ( node == NULL ) ..... 326 * 327 * node->hnode.hash = noderec.hnode.hash; 328 * node->key = key; 329 * node->value = value; 330 * 331 * // add it to the hash table 332 * error = ft_hash_add( table, pnode, node ); 333 * if (error) .... 334 * } 335 */ 336 FT_BASE( FT_Error ) 337 ft_hash_add( FT_Hash table, 338 FT_HashLookup lookup, 339 FT_HashNode new_node ); 340 341 342 /**************************************************************** 343 * 344 * @function: ft_hash_remove 345 * 346 * @description: 347 * try to remove the node corresponding to a given key from 348 * a hash table. This must be called after @ft_hash_lookup 349 * 350 * @input: 351 * table :: hash table handle 352 * lookup :: pointer-to-hash-node value returned by @ft_hash_lookup 353 * 354 * @note: 355 * this function doesn't free the node itself !! Here's an example: 356 * 357 * { 358 * // sets the value corresponding to a given string key 359 * // 360 * void my_remove( FT_Hash table, 361 * const char* key ) 362 * { 363 * MyNodeRec noderec; 364 * MyNode node; 365 * 366 * noderec.hnode.hash = strhash(key); 367 * noderec.key = key; 368 * node = &noderec; 369 * 370 * pnode = ft_hash_lookup( table, &noderec ); 371 * node = *pnode; 372 * if ( node != NULL ) 373 * { 374 * error = ft_hash_remove( table, pnode ); 375 * if ( !error ) 376 * free( node ); 377 * } 378 * } 379 * } 380 */ 381 FT_BASE( FT_Error ) 382 ft_hash_remove( FT_Hash table, 383 FT_HashLookup lookup ); 384 385 386 387 /**************************************************************** 388 * 389 * @function: ft_hash_get_size 390 * 391 * @description: 392 * return the number of elements in a given hash table 393 * 394 * @input: 395 * table :: handle to target hash table structure 396 * 397 * @return: 398 * number of elements. 0 if empty 399 */ 400 FT_BASE( FT_UInt ) 401 ft_hash_get_size( FT_Hash table ); 402 403 404 405 /**************************************************************** 406 * 407 * @functype: FT_Hash_ForeachFunc 408 * 409 * @description: 410 * a function used to iterate over all elements of a given 411 * hash table 412 * 413 * @input: 414 * node :: handle to target @FT_HashNodeRec node structure 415 * data :: optional argument to iteration routine 416 * 417 * @also: @ft_hash_foreach 418 */ 419 typedef void (*FT_Hash_ForeachFunc)( const FT_HashNode node, 420 const FT_Pointer data ); 421 422 423 /**************************************************************** 424 * 425 * @function: ft_hash_foreach 426 * 427 * @description: 428 * parse over all elements in a hash table 429 * 430 * @input: 431 * table :: handle to target hash table structure 432 * foreach_func :: iteration routine called for each element 433 * foreach_data :: optional argument to the iteration routine 434 * 435 * @note: 436 * this function is often used to release all elements from a 437 * hash table. See the example given for @ft_hash_done 438 */ 439 FT_BASE( void ) 440 ft_hash_foreach( FT_Hash table, 441 FT_Hash_ForeachFunc foreach_func, 442 const FT_Pointer foreach_data ); 443 444 445 446 /**************************************************************** 447 * 448 * @function: ft_hash_done 449 * 450 * @description: 451 * finalize a given hash table 452 * 453 * @input: 454 * table :: handle to target hash table structure 455 * node_func :: optional iteration function pointer. this 456 * can be used to destroy all nodes explicitely 457 * node_data :: optional argument to the node iterator 458 * 459 * @note: 460 * this function simply frees the hash table's buckets. 461 * you probably will need to call @ft_hash_foreach to 462 * destroy all its elements before @ft_hash_done, as in 463 * the following example: 464 * 465 * { 466 * static void my_node_clear( const MyNode node ) 467 * { 468 * free( node ); 469 * } 470 * 471 * static void my_done( FT_Hash table ) 472 * { 473 * ft_hash_done( table, (FT_Hash_ForeachFunc) my_node_clear, NULL ); 474 * } 475 * } 476 */ 477 FT_BASE( void ) 478 ft_hash_done( FT_Hash table, 479 FT_Hash_ForeachFunc item_func, 480 const FT_Pointer item_data ); 481 482 /* */ 483 484 /* compute bucket index from hash value in a dynamic hash table */ 485 /* this is only used to break encapsulation to speed lookups in */ 486 /* the FreeType cache manager !! */ 487 /* */ 488 489 #define FT_HASH_COMPUTE_INDEX(_table,_hash,_index) \ 490 { \ 491 FT_UInt _mask = (_table)->mask; \ 492 FT_UInt _hash0 = (_hash); \ 493 \ 494 (_index) = (FT_UInt)( (_hash0) & _mask ) ); \ 495 if ( (_index) < (_table)->p ) \ 496 (_index) = (FT_uInt)( (_hash0) & ( 2*_mask+1 ) ); \ 497 } 498 499 500 FT_END_HEADER 501 502 #endif /* __FT_HASH_H__ */ 503