src/base/fthash.c

   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
  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
  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
  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
  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*
 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
 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
 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
 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
 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
 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
 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
 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
 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*
 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*
 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*
 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 */