ReactOS 0.4.15-dev-8109-gd7be748
fthash.c
Go to the documentation of this file.
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
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
67 {
68 FT_ULong num = (FT_ULong)key->num;
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
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
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*
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
134 {
135 FT_Hashnode* obp = hash->table;
136 FT_Hashnode* bp;
137 FT_Hashnode* nbp;
138
139 FT_UInt i, sz = hash->size;
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
169 {
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
198 {
199 return hash_init( hash, 0, memory );
200 }
201
202
206 {
207 return hash_init( hash, 1, memory );
208 }
209
210
211 void
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
235 size_t data,
238 {
239 FT_Hashnode nn;
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 {
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
273 size_t data,
276 {
277 FT_Hashkey hk;
278
279
280 hk.str = key;
281
282 return hash_insert( hk, data, hash, memory );
283 }
284
285
288 size_t data,
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*
303 FT_Hash hash )
304 {
306
307
308 return (*np) ? &(*np)->data
309 : NULL;
310 }
311
312
313 size_t*
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*
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 */
#define NULL
Definition: types.h:112
static BOOL is_num(WCHAR val)
Definition: uri.c:267
return FT_Err_Ok
Definition: ftbbox.c:511
size_t * ft_hash_num_lookup(FT_Int num, FT_Hash hash)
Definition: fthash.c:327
#define INITIAL_HT_SIZE
Definition: fthash.c:47
static FT_Error hash_insert(FT_Hashkey key, size_t data, FT_Hash hash, FT_Memory memory)
Definition: fthash.c:234
void ft_hash_str_free(FT_Hash hash, FT_Memory memory)
Definition: fthash.c:212
static FT_ULong hash_num_lookup(FT_Hashkey *key)
Definition: fthash.c:66
static FT_Error hash_rehash(FT_Hash hash, FT_Memory memory)
Definition: fthash.c:132
FT_Error ft_hash_num_init(FT_Hash hash, FT_Memory memory)
Definition: fthash.c:204
static FT_Error hash_init(FT_Hash hash, FT_Bool is_num, FT_Memory memory)
Definition: fthash.c:166
size_t * ft_hash_str_lookup(const char *key, FT_Hash hash)
Definition: fthash.c:314
static size_t * hash_lookup(FT_Hashkey key, FT_Hash hash)
Definition: fthash.c:302
FT_Error ft_hash_num_insert(FT_Int num, size_t data, FT_Hash hash, FT_Memory memory)
Definition: fthash.c:287
static FT_Bool hash_str_compare(FT_Hashkey *a, FT_Hashkey *b)
Definition: fthash.c:83
static FT_Bool hash_num_compare(FT_Hashkey *a, FT_Hashkey *b)
Definition: fthash.c:95
static FT_ULong hash_str_lookup(FT_Hashkey *key)
Definition: fthash.c:51
FT_Error ft_hash_str_init(FT_Hash hash, FT_Memory memory)
Definition: fthash.c:196
FT_Error ft_hash_str_insert(const char *key, size_t data, FT_Hash hash, FT_Memory memory)
Definition: fthash.c:272
FT_BEGIN_HEADER union FT_Hashkey_ FT_Hashkey
#define FT_NEW_ARRAY(ptr, count)
Definition: ftmemory.h:333
#define FT_NEW(ptr)
Definition: ftmemory.h:331
#define FT_MEM_NEW_ARRAY(ptr, count)
Definition: ftmemory.h:271
#define FT_FREE(ptr)
Definition: ftmemory.h:329
#define ft_strcmp
Definition: ftstdlib.h:86
typedefFT_BEGIN_HEADER struct FT_MemoryRec_ * FT_Memory
Definition: ftsystem.h:66
FT_BEGIN_HEADER typedef unsigned char FT_Bool
Definition: fttypes.h:108
unsigned long FT_ULong
Definition: fttypes.h:253
int FT_Error
Definition: fttypes.h:300
unsigned int FT_UInt
Definition: fttypes.h:231
signed int FT_Int
Definition: fttypes.h:220
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
GLuint res
Definition: glext.h:9613
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLuint GLuint num
Definition: glext.h:9618
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define error(str)
Definition: mkdosfs.c:1605
static char memory[1024 *256]
Definition: process.c:116
static void Exit(void)
Definition: sock.c:1330
size_t data
Definition: fthash.h:64
FT_Hashkey key
Definition: fthash.h:63
Definition: _hash_fun.h:40
Definition: copy.c:22