fthash.c (8406B)
1 /**************************************************************************** 2 * 3 * fthash.c 4 * 5 * Hashing functions (body). 6 * 7 */ 8 9 /* 10 * Copyright 2000 Computing Research Labs, New Mexico State University 11 * Copyright 2001-2015 12 * Francesco Zappa Nardelli 13 * 14 * Permission is hereby granted, free of charge, to any person obtaining a 15 * copy of this software and associated documentation files (the "Software"), 16 * to deal in the Software without restriction, including without limitation 17 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 18 * and/or sell copies of the Software, and to permit persons to whom the 19 * Software is furnished to do so, subject to the following conditions: 20 * 21 * The above copyright notice and this permission notice shall be included in 22 * all copies or substantial portions of the Software. 23 * 24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 25 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 26 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 27 * THE COMPUTING RESEARCH LAB OR NEW MEXICO STATE UNIVERSITY BE LIABLE FOR ANY 28 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT 29 * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR 30 * THE USE OR OTHER DEALINGS IN THE SOFTWARE. 31 */ 32 33 /************************************************************************** 34 * 35 * This file is based on code from bdf.c,v 1.22 2000/03/16 20:08:50 36 * 37 * taken from Mark Leisher's xmbdfed package 38 * 39 */ 40 41 42 #include <freetype/internal/fthash.h> 43 #include <freetype/internal/ftmemory.h> 44 #include <freetype/internal/ftobjs.h> 45 46 47 #define INITIAL_HT_SIZE 241 48 49 50 static FT_ULong 51 hash_str_lookup( FT_Hashkey* key ) 52 { 53 const char* kp = key->str; 54 FT_ULong res = 0; 55 56 57 /* Mocklisp hash function. */ 58 while ( *kp ) 59 res = ( res << 5 ) - res + (FT_ULong)*kp++; 60 61 return res; 62 } 63 64 65 static FT_ULong 66 hash_num_lookup( FT_Hashkey* key ) 67 { 68 FT_ULong num = (FT_ULong)key->num; 69 FT_ULong res; 70 71 72 /* Mocklisp hash function. */ 73 res = num & 0xFF; 74 res = ( res << 5 ) - res + ( ( num >> 8 ) & 0xFF ); 75 res = ( res << 5 ) - res + ( ( num >> 16 ) & 0xFF ); 76 res = ( res << 5 ) - res + ( ( num >> 24 ) & 0xFF ); 77 78 return res; 79 } 80 81 82 static FT_Bool 83 hash_str_compare( FT_Hashkey* a, 84 FT_Hashkey* b ) 85 { 86 if ( a->str[0] == b->str[0] && 87 ft_strcmp( a->str, b->str ) == 0 ) 88 return 1; 89 90 return 0; 91 } 92 93 94 static FT_Bool 95 hash_num_compare( FT_Hashkey* a, 96 FT_Hashkey* b ) 97 { 98 if ( a->num == b->num ) 99 return 1; 100 101 return 0; 102 } 103 104 105 static FT_Hashnode* 106 hash_bucket( FT_Hashkey key, 107 FT_Hash hash ) 108 { 109 FT_ULong res = 0; 110 FT_Hashnode* bp = hash->table; 111 FT_Hashnode* ndp; 112 113 114 res = (hash->lookup)( &key ); 115 116 ndp = bp + ( res % hash->size ); 117 while ( *ndp ) 118 { 119 if ( (hash->compare)( &(*ndp)->key, &key ) ) 120 break; 121 122 ndp--; 123 if ( ndp < bp ) 124 ndp = bp + ( hash->size - 1 ); 125 } 126 127 return ndp; 128 } 129 130 131 static FT_Error 132 hash_rehash( FT_Hash hash, 133 FT_Memory memory ) 134 { 135 FT_Hashnode* obp = hash->table; 136 FT_Hashnode* bp; 137 FT_Hashnode* nbp; 138 139 FT_UInt i, sz = hash->size; 140 FT_Error error = FT_Err_Ok; 141 142 143 hash->size <<= 1; 144 hash->limit = hash->size / 3; 145 146 if ( FT_NEW_ARRAY( hash->table, hash->size ) ) 147 goto Exit; 148 149 for ( i = 0, bp = obp; i < sz; i++, bp++ ) 150 { 151 if ( *bp ) 152 { 153 nbp = hash_bucket( (*bp)->key, hash ); 154 *nbp = *bp; 155 } 156 } 157 158 FT_FREE( obp ); 159 160 Exit: 161 return error; 162 } 163 164 165 static FT_Error 166 hash_init( FT_Hash hash, 167 FT_Bool is_num, 168 FT_Memory memory ) 169 { 170 FT_UInt sz = INITIAL_HT_SIZE; 171 FT_Error error; 172 173 174 hash->size = sz; 175 hash->limit = sz / 3; 176 hash->used = 0; 177 178 if ( is_num ) 179 { 180 hash->lookup = hash_num_lookup; 181 hash->compare = hash_num_compare; 182 } 183 else 184 { 185 hash->lookup = hash_str_lookup; 186 hash->compare = hash_str_compare; 187 } 188 189 FT_MEM_NEW_ARRAY( hash->table, sz ); 190 191 return error; 192 } 193 194 195 FT_Error 196 ft_hash_str_init( FT_Hash hash, 197 FT_Memory memory ) 198 { 199 return hash_init( hash, 0, memory ); 200 } 201 202 203 FT_Error 204 ft_hash_num_init( FT_Hash hash, 205 FT_Memory memory ) 206 { 207 return hash_init( hash, 1, memory ); 208 } 209 210 211 void 212 ft_hash_str_free( FT_Hash hash, 213 FT_Memory memory ) 214 { 215 if ( hash ) 216 { 217 FT_UInt sz = hash->size; 218 FT_Hashnode* bp = hash->table; 219 FT_UInt i; 220 221 222 for ( i = 0; i < sz; i++, bp++ ) 223 FT_FREE( *bp ); 224 225 FT_FREE( hash->table ); 226 } 227 } 228 229 230 /* `ft_hash_num_free' is the same as `ft_hash_str_free' */ 231 232 233 static FT_Error 234 hash_insert( FT_Hashkey key, 235 size_t data, 236 FT_Hash hash, 237 FT_Memory memory, 238 FT_Bool overwrite ) 239 { 240 FT_Hashnode nn; 241 FT_Hashnode* bp = hash_bucket( key, hash ); 242 FT_Error error = FT_Err_Ok; 243 244 245 nn = *bp; 246 if ( !nn ) 247 { 248 if ( FT_QNEW( nn ) ) 249 goto Exit; 250 *bp = nn; 251 252 nn->key = key; 253 nn->data = data; 254 255 if ( hash->used >= hash->limit ) 256 { 257 error = hash_rehash( hash, memory ); 258 if ( error ) 259 goto Exit; 260 } 261 262 hash->used++; 263 } 264 else if ( overwrite ) 265 nn->data = data; 266 267 Exit: 268 return error; 269 } 270 271 272 FT_Error 273 ft_hash_str_insert( const char* key, 274 size_t data, 275 FT_Hash hash, 276 FT_Memory memory ) 277 { 278 FT_Hashkey hk; 279 280 281 hk.str = key; 282 283 return hash_insert( hk, data, hash, memory, TRUE ); 284 } 285 286 287 FT_Error 288 ft_hash_num_insert( FT_Int num, 289 size_t data, 290 FT_Hash hash, 291 FT_Memory memory ) 292 { 293 FT_Hashkey hk; 294 295 296 hk.num = num; 297 298 return hash_insert( hk, data, hash, memory, TRUE ); 299 } 300 301 302 FT_Error 303 ft_hash_str_insert_no_overwrite( const char* key, 304 size_t data, 305 FT_Hash hash, 306 FT_Memory memory ) 307 { 308 FT_Hashkey hk; 309 310 311 hk.str = key; 312 313 return hash_insert( hk, data, hash, memory, FALSE ); 314 } 315 316 317 FT_Error 318 ft_hash_num_insert_no_overwrite( FT_Int num, 319 size_t data, 320 FT_Hash hash, 321 FT_Memory memory ) 322 { 323 FT_Hashkey hk; 324 325 326 hk.num = num; 327 328 return hash_insert( hk, data, hash, memory, FALSE ); 329 } 330 331 332 static size_t* 333 hash_lookup( FT_Hashkey key, 334 FT_Hash hash ) 335 { 336 FT_Hashnode* np = hash_bucket( key, hash ); 337 338 339 return (*np) ? &(*np)->data 340 : NULL; 341 } 342 343 344 size_t* 345 ft_hash_str_lookup( const char* key, 346 FT_Hash hash ) 347 { 348 FT_Hashkey hk; 349 350 351 hk.str = key; 352 353 return hash_lookup( hk, hash ); 354 } 355 356 357 size_t* 358 ft_hash_num_lookup( FT_Int num, 359 FT_Hash hash ) 360 { 361 FT_Hashkey hk; 362 363 364 hk.num = num; 365 366 return hash_lookup( hk, hash ); 367 } 368 369 370 FT_Bool 371 ft_hash_num_iterator( FT_UInt *idx, 372 FT_Int *key, 373 size_t *value, 374 FT_Hash hash ) 375 { 376 FT_Hashnode nn = NULL; 377 378 379 while ( 1 ) 380 { 381 if ( *idx >= hash->size ) 382 return 0; 383 384 nn = hash->table[*idx]; 385 if ( nn ) 386 break; 387 388 (*idx)++; 389 } 390 391 if ( key ) 392 *key = nn->key.num; 393 if ( value ) 394 *value = nn->data; 395 396 (*idx)++; 397 398 return 1; 399 } 400 401 402 FT_Bool 403 ft_hash_str_iterator( FT_UInt *idx, 404 const char* *key, 405 size_t *value, 406 FT_Hash hash ) 407 { 408 FT_Hashnode nn = NULL; 409 410 411 while ( 1 ) 412 { 413 if ( *idx >= hash->size ) 414 return 0; 415 416 nn = hash->table[*idx]; 417 if ( nn ) 418 break; 419 420 (*idx)++; 421 } 422 423 if ( key ) 424 *key = nn->key.str; 425 if ( value ) 426 *value = nn->data; 427 428 (*idx)++; 429 430 return 1; 431 } 432 433 434 /* END */