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 <ft2build.h> 43 #include FT_INTERNAL_HASH_H 44 #include FT_INTERNAL_MEMORY_H 45 46 47 #define INITIAL_HT_SIZE 241 48 49 50 static FT_ULong hash_str_lookup(FT_Hashkey * key)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 hash_num_lookup(FT_Hashkey * key)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 hash_str_compare(FT_Hashkey * a,FT_Hashkey * b)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 hash_num_compare(FT_Hashkey * a,FT_Hashkey * b)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* hash_bucket(FT_Hashkey key,FT_Hash hash)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 hash_rehash(FT_Hash hash,FT_Memory memory)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 hash_init(FT_Hash hash,FT_Bool is_num,FT_Memory memory)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 ft_hash_str_init(FT_Hash hash,FT_Memory memory)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 ft_hash_num_init(FT_Hash hash,FT_Memory memory)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 ft_hash_str_free(FT_Hash hash,FT_Memory memory)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 hash_insert(FT_Hashkey key,size_t data,FT_Hash hash,FT_Memory memory)234 hash_insert( FT_Hashkey key, 235 size_t data, 236 FT_Hash hash, 237 FT_Memory memory ) 238 { 239 FT_Hashnode nn; 240 FT_Hashnode* bp = hash_bucket( key, hash ); 241 FT_Error error = FT_Err_Ok; 242 243 244 nn = *bp; 245 if ( !nn ) 246 { 247 if ( FT_NEW( nn ) ) 248 goto Exit; 249 *bp = nn; 250 251 nn->key = key; 252 nn->data = data; 253 254 if ( hash->used >= hash->limit ) 255 { 256 error = hash_rehash( hash, memory ); 257 if ( error ) 258 goto Exit; 259 } 260 261 hash->used++; 262 } 263 else 264 nn->data = data; 265 266 Exit: 267 return error; 268 } 269 270 271 FT_Error ft_hash_str_insert(const char * key,size_t data,FT_Hash hash,FT_Memory memory)272 ft_hash_str_insert( const char* key, 273 size_t data, 274 FT_Hash hash, 275 FT_Memory memory ) 276 { 277 FT_Hashkey hk; 278 279 280 hk.str = key; 281 282 return hash_insert( hk, data, hash, memory ); 283 } 284 285 286 FT_Error ft_hash_num_insert(FT_Int num,size_t data,FT_Hash hash,FT_Memory memory)287 ft_hash_num_insert( FT_Int num, 288 size_t data, 289 FT_Hash hash, 290 FT_Memory memory ) 291 { 292 FT_Hashkey hk; 293 294 295 hk.num = num; 296 297 return hash_insert( hk, data, hash, memory ); 298 } 299 300 301 static size_t* hash_lookup(FT_Hashkey key,FT_Hash hash)302 hash_lookup( FT_Hashkey key, 303 FT_Hash hash ) 304 { 305 FT_Hashnode* np = hash_bucket( key, hash ); 306 307 308 return (*np) ? &(*np)->data 309 : NULL; 310 } 311 312 313 size_t* ft_hash_str_lookup(const char * key,FT_Hash hash)314 ft_hash_str_lookup( const char* key, 315 FT_Hash hash ) 316 { 317 FT_Hashkey hk; 318 319 320 hk.str = key; 321 322 return hash_lookup( hk, hash ); 323 } 324 325 326 size_t* ft_hash_num_lookup(FT_Int num,FT_Hash hash)327 ft_hash_num_lookup( FT_Int num, 328 FT_Hash hash ) 329 { 330 FT_Hashkey hk; 331 332 333 hk.num = num; 334 335 return hash_lookup( hk, hash ); 336 } 337 338 339 /* END */ 340