/*

 * Copyright 2000 Computing Research Labs, New Mexico State University

 * Copyright 2001-2015

 *   Francesco Zappa Nardelli

 *

 * Permission is hereby granted, free of charge, to any person obtaining a

 * copy of this software and associated documentation files (the "Software"),

 * to deal in the Software without restriction, including without limitation

 * the rights to use, copy, modify, merge, publish, distribute, sublicense,

 * and/or sell copies of the Software, and to permit persons to whom the

 * Software is furnished to do so, subject to the following conditions:

 *

 * The above copyright notice and this permission notice shall be included in

 * all copies or substantial portions of the Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL

 * THE COMPUTING RESEARCH LAB OR NEW MEXICO STATE UNIVERSITY BE LIABLE FOR ANY

 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT

 * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR

 * THE USE OR OTHER DEALINGS IN THE SOFTWARE.

 */

#include <ft2build.h>

#include FT_INTERNAL_HASH_H

#include FT_INTERNAL_MEMORY_H

#define INITIAL_HT_SIZE  241

  static FT_ULong

  hash_str_lookup( FT_Hashkey*  key )

  {

    const char*  kp  = key->str;

    FT_ULong     res = 0;

    /* Mocklisp hash function. */

    while ( *kp )

      res = ( res << 5 ) - res + (FT_ULong)*kp++;

    return res;

  }

  static FT_ULong

  hash_num_lookup( FT_Hashkey*  key )

  {

    FT_ULong  num = (FT_ULong)key->num;

    FT_ULong  res;

    /* Mocklisp hash function. */

    res = num & 0xFF;

    res = ( res << 5 ) - res + ( ( num >>  8 ) & 0xFF );

    res = ( res << 5 ) - res + ( ( num >> 16 ) & 0xFF );

    res = ( res << 5 ) - res + ( ( num >> 24 ) & 0xFF );

    return res;

  }

  static FT_Bool

  hash_str_compare( FT_Hashkey*  a,

                    FT_Hashkey*  b )

  {

    if ( a->str[0] == b->str[0]           &&

         ft_strcmp( a->str, b->str ) == 0 )

      return 1;

    return 0;

  }

  static FT_Bool

  hash_num_compare( FT_Hashkey*  a,

                    FT_Hashkey*  b )

  {

    if ( a->num == b->num )

      return 1;

    return 0;

  }

  static FT_Hashnode*

  hash_bucket( FT_Hashkey  key,

               FT_Hash     hash )

  {

    FT_ULong      res = 0;

    FT_Hashnode*  bp  = hash->table;

    FT_Hashnode*  ndp;

    res = (hash->lookup)( &key );

    ndp = bp + ( res % hash->size );

    while ( *ndp )

    {

      if ( (hash->compare)( &(*ndp)->key, &key ) )

        break;

      ndp--;

      if ( ndp < bp )

        ndp = bp + ( hash->size - 1 );

    }

    return ndp;

  }

  static FT_Error

  hash_rehash( FT_Hash    hash,

               FT_Memory  memory )

  {

    FT_Hashnode*  obp = hash->table;

    FT_Hashnode*  bp;

    FT_Hashnode*  nbp;

    FT_UInt   i, sz = hash->size;

    FT_Error  error = FT_Err_Ok;

    hash->size <<= 1;

    hash->limit  = hash->size / 3;

    if ( FT_NEW_ARRAY( hash->table, hash->size ) )

      goto Exit;

    for ( i = 0, bp = obp; i < sz; i++, bp++ )

    {

      if ( *bp )

      {

        nbp = hash_bucket( (*bp)->key, hash );

        *nbp = *bp;

      }

    }

    FT_FREE( obp );

  Exit:

    return error;

  }

  static FT_Error

  hash_init( FT_Hash    hash,

             FT_Bool    is_num,

             FT_Memory  memory )

  {

    FT_UInt   sz = INITIAL_HT_SIZE;

    FT_Error  error;

    hash->size  = sz;

    hash->limit = sz / 3;

    hash->used  = 0;

    if ( is_num )

    {

      hash->lookup  = hash_num_lookup;

      hash->compare = hash_num_compare;

    }

    else

    {

      hash->lookup  = hash_str_lookup;

      hash->compare = hash_str_compare;

    }

    FT_MEM_NEW_ARRAY( hash->table, sz );

    return error;

  }

  FT_Error

  ft_hash_str_init( FT_Hash    hash,

                    FT_Memory  memory )

  {

    return hash_init( hash, 0, memory );

  }

  FT_Error

  ft_hash_num_init( FT_Hash    hash,

                    FT_Memory  memory )

  {

    return hash_init( hash, 1, memory );

  }

  void

  ft_hash_str_free( FT_Hash    hash,

                    FT_Memory  memory )

  {

    if ( hash )

    {

      FT_UInt       sz = hash->size;

      FT_Hashnode*  bp = hash->table;

      FT_UInt       i;

      for ( i = 0; i < sz; i++, bp++ )

        FT_FREE( *bp );

      FT_FREE( hash->table );

    }

  }

  /* `ft_hash_num_free' is the same as `ft_hash_str_free' */

  static FT_Error

  hash_insert( FT_Hashkey  key,

               size_t      data,

               FT_Hash     hash,

               FT_Memory   memory )

  {

    FT_Hashnode   nn;

    FT_Hashnode*  bp    = hash_bucket( key, hash );

    FT_Error      error = FT_Err_Ok;

    nn = *bp;

    if ( !nn )

    {

      if ( FT_NEW( nn ) )

        goto Exit;

      *bp = nn;

      nn->key  = key;

      nn->data = data;

      if ( hash->used >= hash->limit )

      {

        error = hash_rehash( hash, memory );

        if ( error )

          goto Exit;

      }

      hash->used++;

    }

    else

      nn->data = data;

  Exit:

    return error;

  }

  FT_Error

  ft_hash_str_insert( const char*  key,

                      size_t       data,

                      FT_Hash      hash,

                      FT_Memory    memory )

  {

    FT_Hashkey  hk;

    hk.str = key;

    return hash_insert( hk, data, hash, memory );

  }

  FT_Error

  ft_hash_num_insert( FT_Int     num,

                      size_t     data,

                      FT_Hash    hash,

                      FT_Memory  memory )

  {

    FT_Hashkey  hk;

    hk.num = num;

    return hash_insert( hk, data, hash, memory );

  }

  static size_t*

  hash_lookup( FT_Hashkey  key,

               FT_Hash     hash )

  {

    FT_Hashnode*  np = hash_bucket( key, hash );

    return (*np) ? &(*np)->data

                 : NULL;

  }

  size_t*

  ft_hash_str_lookup( const char*  key,

                      FT_Hash      hash )

  {

    FT_Hashkey  hk;

    hk.str = key;

    return hash_lookup( hk, hash );

  }

  size_t*

  ft_hash_num_lookup( FT_Int   num,

                      FT_Hash  hash )

  {

    FT_Hashkey  hk;

    hk.num = num;

    return hash_lookup( hk, hash );

  }

/* END */