reactos/lib/3rdparty/freetype/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 <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
  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
  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
  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
  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*
 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
 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
 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
 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
 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
 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
 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
 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
 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*
 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*
 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*
 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 */