ReactOS  0.4.14-dev-98-gb0d4763
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;
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
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
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;
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
167  FT_Bool is_num,
168  FT_Memory memory )
169  {
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
197  FT_Memory memory )
198  {
199  return hash_init( hash, 0, memory );
200  }
201 
202 
203  FT_Error
205  FT_Memory memory )
206  {
207  return hash_init( hash, 1, memory );
208  }
209 
210 
211  void
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
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 );
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 
271  FT_Error
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
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*
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*
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*
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 */
int FT_Error
Definition: fttypes.h:300
FT_Error ft_hash_str_init(FT_Hash hash, FT_Memory memory)
Definition: fthash.c:196
unsigned long FT_ULong
Definition: fttypes.h:253
#define error(str)
Definition: mkdosfs.c:1605
static FT_Bool hash_str_compare(FT_Hashkey *a, FT_Hashkey *b)
Definition: fthash.c:83
signed int FT_Int
Definition: fttypes.h:220
FT_Error ft_hash_num_init(FT_Hash hash, FT_Memory memory)
Definition: fthash.c:204
#define FT_MEM_NEW_ARRAY(ptr, count)
Definition: ftmemory.h:271
return FT_Err_Ok
Definition: ftbbox.c:511
static char memory[1024 *256]
Definition: process.c:116
FT_Error ft_hash_str_insert(const char *key, size_t data, FT_Hash hash, FT_Memory memory)
Definition: fthash.c:272
static size_t * hash_lookup(FT_Hashkey key, FT_Hash hash)
Definition: fthash.c:302
FT_BEGIN_HEADER typedef unsigned char FT_Bool
Definition: fttypes.h:108
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
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_ULong hash_str_lookup(FT_Hashkey *key)
Definition: fthash.c:51
#define INITIAL_HT_SIZE
Definition: fthash.c:47
smooth NULL
Definition: ftsmooth.c:416
#define FT_FREE(ptr)
Definition: ftmemory.h:329
static FT_Error hash_rehash(FT_Hash hash, FT_Memory memory)
Definition: fthash.c:132
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
static void Exit(void)
Definition: sock.c:1331
GLuint GLuint num
Definition: glext.h:9618
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
size_t * ft_hash_str_lookup(const char *key, FT_Hash hash)
Definition: fthash.c:314
static FT_Bool hash_num_compare(FT_Hashkey *a, FT_Hashkey *b)
Definition: fthash.c:95
HKEY key
Definition: reg.c:42
typedefFT_BEGIN_HEADER struct FT_MemoryRec_ * FT_Memory
Definition: ftsystem.h:66
#define FT_NEW_ARRAY(ptr, count)
Definition: ftmemory.h:333
size_t data
Definition: fthash.h:64
static BOOL is_num(WCHAR val)
Definition: uri.c:266
unsigned int FT_UInt
Definition: fttypes.h:231
FT_Hashkey key
Definition: fthash.h:63
FT_BEGIN_HEADER union FT_Hashkey_ FT_Hashkey
static FT_Error hash_insert(FT_Hashkey key, size_t data, FT_Hash hash, FT_Memory memory)
Definition: fthash.c:234
GLuint res
Definition: glext.h:9613
static FT_Hashnode * hash_bucket(FT_Hashkey key, FT_Hash hash)
Definition: fthash.c:106
#define FT_NEW(ptr)
Definition: ftmemory.h:331
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
Definition: _hash_fun.h:40
static FT_Error hash_init(FT_Hash hash, FT_Bool is_num, FT_Memory memory)
Definition: fthash.c:166
FT_Error ft_hash_num_insert(FT_Int num, size_t data, FT_Hash hash, FT_Memory memory)
Definition: fthash.c:287
#define ft_strcmp
Definition: ftstdlib.h:86
Definition: path.c:42
size_t * ft_hash_num_lookup(FT_Int num, FT_Hash hash)
Definition: fthash.c:327