root/src/dd_hash_table.c

/**
 * builtin_hash_table.c -> Part of Crules Programming language
 *
 * Crules is the legal property of its developers. Please refer to the
 * COPYRIGHT file distributed with this source distribution.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 **/

#ifdef HAVE_CONFIG_H
# include "config.h"
#else
# define CMAKE 1
# include "config.h.cmake"
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <crules/crules.h>
#include <crules/opcodes.h>
#include <crules/symbols.h>
#include <crules/objects.h>
#include <crules/backend.h>
#include <crules/runtime.h>
#include <crules/garbage.h>
#include <crules/operators.h>

//threshold size alloctor to scale up faster
#define threshold_alloc(x) (((x)+16)*3/2)

static void crl_dd_hash_grow_table( crl_table_t * );

/**
 *  Hash function in use is a 32bit FNV-1
 *
 *  * http://en.wikipedia.org/wiki/Fowler-Noll-Vo_hash_function
 *  * http://isthe.com/chongo/tech/comp/fnv/#FNV-1
 *
 *  Eventualy look at using a sha1 may work better but may be too big
 *  a Digest.., but should avoid conflicts better
 **/
crl_hash_t crl_dd_hash_hash( const char *string )
{
  crl_hash_t hash = 0x811C9DC5;
  unsigned char ch = '\0';
  unsigned int idx = 0;

  for( ; idx < crl_strlen( string ); ++idx )
    {
      ch = (*string + idx);
      hash ^= ch;
      hash *= 0x1000193;
    }

  return hash;
}

crl_table_entry *
crl_dd_hash_lookup_table( crl_table_t *tbl, crl_hash_t h )
{
  crl_table_entry* retval;
  if( tbl->array )
    {
      crl_hash_t size= tbl->size, idx= (h % size);
      crl_table_entry *array= tbl->array;

      while( array[idx].symbol )
        {
          if( array[idx].hash == h )
            break;

          idx++;
          if( idx >= size )
            idx= 0;
        }
      retval= (array+idx);
    }
  else {
    retval= NULL;
  }
  return retval;
}

crl_symbol_obj**
crl_dd_hash_insert( crl_hash_t h, crl_symbol_obj* obj,
                    crl_table_t *tbl )
{
  crl_symbol_obj **retval;
  if( tbl->nr >= tbl->size )
    crl_dd_hash_grow_table( tbl );

  crl_table_entry *entry= crl_dd_hash_lookup_table( tbl, h );
  if( entry->symbol )
    retval= &( entry->symbol );
  else
    {
      entry->symbol= obj;
      entry->hash= h;
      tbl->nr++; retval= NULL;
    }
  return retval;
}

static
void crl_dd_hash_grow_table( crl_table_t * tbl )
{
  unsigned int prev_size= tbl->size, size= 0, i= 0;
  crl_table_entry *prev_array= tbl->array, *array;

  size= threshold_alloc( prev_size );
  array= (crl_table_entry*)
    crl_calloc( size, sizeof(crl_table_entry) );

  //reset nr
  tbl->nr = 0; tbl->size= size;
  tbl->array= array;

  for ( ; i<prev_size; ++i )
    {
      crl_hash_t h= prev_array[i].hash;
      crl_symbol_obj *s= prev_array[i].symbol;

      if( s )
        crl_dd_hash_insert( h, s, tbl );
    }
  if( prev_array )
    crl_free( prev_array );
}

void crl_dd_hash_init_table( crl_table_t ** tbl )
{
  if( tbl )
    {
      crl_table_t *tb= *tbl;
      tb->size= 0; tb->nr= 0;
      tb->array= NULL;
    }
  else
    {
      crl_error("null hash table!\n");
    }
}

crl_table_t * crl_dd_hash_clone_table( crl_table_t ** table )
{
  crl_table_t * retval = NULL;
  if( table )
    {
      retval = (crl_table_t*)
        crl_malloc( sizeof(crl_table_t) );
      crl_dd_hash_init_table( &retval );

      crl_table_entry* array = (crl_table_entry*)
        crl_calloc( (*table)->size, sizeof(crl_table_entry) );
      retval->size = (*table)->size;
      retval->array = array;
      retval->nr = 0;

      crl_table_entry *c_arr = (*table)->array;
      unsigned int idx = 0;
      for( ; idx<((*table)->size); ++idx )
        {
          crl_hash_t h= c_arr[idx].hash;
          crl_symbol_obj *s= c_arr[idx].symbol;

          if( s )
            {
              crl_debug("cloning this stuff <%p>!\n", (void *) s );
              crl_symbol_obj * cl = crl_runtime_obj_clone( &s, true );
              crl_dd_hash_insert( h, cl, retval );
            }
        }

      // consitancy check!
      if( (retval->nr != ((*table)->nr)) )
        {
          crl_fatal("table corruption on clone, retval->nr <%i> table->nr <%i>!\n",
                    retval->nr, (*table)->nr );
        }
    }
  return retval;
}