• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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