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 45 46 #define INITIAL_HT_SIZE 241 47 48 49 static FT_ULong hash_str_lookup(FT_Hashkey * key)50 hash_str_lookup( FT_Hashkey* key ) 51 { 52 const char* kp = key->str; 53 FT_ULong res = 0; 54 55 56 /* Mocklisp hash function. */ 57 while ( *kp ) 58 res = ( res << 5 ) - res + (FT_ULong)*kp++; 59 60 return res; 61 } 62 63 64 static FT_ULong hash_num_lookup(FT_Hashkey * key)65 hash_num_lookup( FT_Hashkey* key ) 66 { 67 FT_ULong num = (FT_ULong)key->num; 68 FT_ULong res; 69 70 71 /* Mocklisp hash function. */ 72 res = num & 0xFF; 73 res = ( res << 5 ) - res + ( ( num >> 8 ) & 0xFF ); 74 res = ( res << 5 ) - res + ( ( num >> 16 ) & 0xFF ); 75 res = ( res << 5 ) - res + ( ( num >> 24 ) & 0xFF ); 76 77 return res; 78 } 79 80 81 static FT_Bool hash_str_compare(FT_Hashkey * a,FT_Hashkey * b)82 hash_str_compare( FT_Hashkey* a, 83 FT_Hashkey* b ) 84 { 85 if ( a->str[0] == b->str[0] && 86 ft_strcmp( a->str, b->str ) == 0 ) 87 return 1; 88 89 return 0; 90 } 91 92 93 static FT_Bool hash_num_compare(FT_Hashkey * a,FT_Hashkey * b)94 hash_num_compare( FT_Hashkey* a, 95 FT_Hashkey* b ) 96 { 97 if ( a->num == b->num ) 98 return 1; 99 100 return 0; 101 } 102 103 104 static FT_Hashnode* hash_bucket(FT_Hashkey key,FT_Hash hash)105 hash_bucket( FT_Hashkey key, 106 FT_Hash hash ) 107 { 108 FT_ULong res = 0; 109 FT_Hashnode* bp = hash->table; 110 FT_Hashnode* ndp; 111 112 113 res = (hash->lookup)( &key ); 114 115 ndp = bp + ( res % hash->size ); 116 while ( *ndp ) 117 { 118 if ( (hash->compare)( &(*ndp)->key, &key ) ) 119 break; 120 121 ndp--; 122 if ( ndp < bp ) 123 ndp = bp + ( hash->size - 1 ); 124 } 125 126 return ndp; 127 } 128 129 130 static FT_Error hash_rehash(FT_Hash hash,FT_Memory memory)131 hash_rehash( FT_Hash hash, 132 FT_Memory memory ) 133 { 134 FT_Hashnode* obp = hash->table; 135 FT_Hashnode* bp; 136 FT_Hashnode* nbp; 137 138 FT_UInt i, sz = hash->size; 139 FT_Error error = FT_Err_Ok; 140 141 142 hash->size <<= 1; 143 hash->limit = hash->size / 3; 144 145 if ( FT_NEW_ARRAY( hash->table, hash->size ) ) 146 goto Exit; 147 148 for ( i = 0, bp = obp; i < sz; i++, bp++ ) 149 { 150 if ( *bp ) 151 { 152 nbp = hash_bucket( (*bp)->key, hash ); 153 *nbp = *bp; 154 } 155 } 156 157 FT_FREE( obp ); 158 159 Exit: 160 return error; 161 } 162 163 164 static FT_Error hash_init(FT_Hash hash,FT_Bool is_num,FT_Memory memory)165 hash_init( FT_Hash hash, 166 FT_Bool is_num, 167 FT_Memory memory ) 168 { 169 FT_UInt sz = INITIAL_HT_SIZE; 170 FT_Error error; 171 172 173 hash->size = sz; 174 hash->limit = sz / 3; 175 hash->used = 0; 176 177 if ( is_num ) 178 { 179 hash->lookup = hash_num_lookup; 180 hash->compare = hash_num_compare; 181 } 182 else 183 { 184 hash->lookup = hash_str_lookup; 185 hash->compare = hash_str_compare; 186 } 187 188 FT_MEM_NEW_ARRAY( hash->table, sz ); 189 190 return error; 191 } 192 193 194 FT_Error ft_hash_str_init(FT_Hash hash,FT_Memory memory)195 ft_hash_str_init( FT_Hash hash, 196 FT_Memory memory ) 197 { 198 return hash_init( hash, 0, memory ); 199 } 200 201 202 FT_Error ft_hash_num_init(FT_Hash hash,FT_Memory memory)203 ft_hash_num_init( FT_Hash hash, 204 FT_Memory memory ) 205 { 206 return hash_init( hash, 1, memory ); 207 } 208 209 210 void ft_hash_str_free(FT_Hash hash,FT_Memory memory)211 ft_hash_str_free( FT_Hash hash, 212 FT_Memory memory ) 213 { 214 if ( hash ) 215 { 216 FT_UInt sz = hash->size; 217 FT_Hashnode* bp = hash->table; 218 FT_UInt i; 219 220 221 for ( i = 0; i < sz; i++, bp++ ) 222 FT_FREE( *bp ); 223 224 FT_FREE( hash->table ); 225 } 226 } 227 228 229 /* `ft_hash_num_free' is the same as `ft_hash_str_free' */ 230 231 232 static FT_Error hash_insert(FT_Hashkey key,size_t data,FT_Hash hash,FT_Memory memory)233 hash_insert( FT_Hashkey key, 234 size_t data, 235 FT_Hash hash, 236 FT_Memory memory ) 237 { 238 FT_Hashnode nn; 239 FT_Hashnode* bp = hash_bucket( key, hash ); 240 FT_Error error = FT_Err_Ok; 241 242 243 nn = *bp; 244 if ( !nn ) 245 { 246 if ( FT_NEW( nn ) ) 247 goto Exit; 248 *bp = nn; 249 250 nn->key = key; 251 nn->data = data; 252 253 if ( hash->used >= hash->limit ) 254 { 255 error = hash_rehash( hash, memory ); 256 if ( error ) 257 goto Exit; 258 } 259 260 hash->used++; 261 } 262 else 263 nn->data = data; 264 265 Exit: 266 return error; 267 } 268 269 270 FT_Error ft_hash_str_insert(const char * key,size_t data,FT_Hash hash,FT_Memory memory)271 ft_hash_str_insert( const char* key, 272 size_t data, 273 FT_Hash hash, 274 FT_Memory memory ) 275 { 276 FT_Hashkey hk; 277 278 279 hk.str = key; 280 281 return hash_insert( hk, data, hash, memory ); 282 } 283 284 285 FT_Error ft_hash_num_insert(FT_Int num,size_t data,FT_Hash hash,FT_Memory memory)286 ft_hash_num_insert( FT_Int num, 287 size_t data, 288 FT_Hash hash, 289 FT_Memory memory ) 290 { 291 FT_Hashkey hk; 292 293 294 hk.num = num; 295 296 return hash_insert( hk, data, hash, memory ); 297 } 298 299 300 static size_t* hash_lookup(FT_Hashkey key,FT_Hash hash)301 hash_lookup( FT_Hashkey key, 302 FT_Hash hash ) 303 { 304 FT_Hashnode* np = hash_bucket( key, hash ); 305 306 307 return (*np) ? &(*np)->data 308 : NULL; 309 } 310 311 312 size_t* ft_hash_str_lookup(const char * key,FT_Hash hash)313 ft_hash_str_lookup( const char* key, 314 FT_Hash hash ) 315 { 316 FT_Hashkey hk; 317 318 319 hk.str = key; 320 321 return hash_lookup( hk, hash ); 322 } 323 324 325 size_t* ft_hash_num_lookup(FT_Int num,FT_Hash hash)326 ft_hash_num_lookup( FT_Int num, 327 FT_Hash hash ) 328 { 329 FT_Hashkey hk; 330 331 332 hk.num = num; 333 334 return hash_lookup( hk, hash ); 335 } 336 337 338 /* END */ 339