hash.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"hash.h"
#include"util.h"

cell *cell_new(char *key, int val, cell *next)
{
  cell *c = (cell *)memalloc(sizeof(cell));
  c->val = val;
  c->key = key;
  c->next = next;
  return c;
}

void cell_free(cell *c)
{
  if(c == NULL) return;
  cell_free(c->next);
  free(c->key);
  free(c);
}


hash *hash_new(int size)
{
  int i;
  hash *h = (hash *)memalloc(sizeof(hash));
  h->size = size;
  h->nbelem = 0;
  h->array = (cell **)memalloc(size * sizeof(cell *));
  for(i=0; i < size; i++)
    h->array[i] = NULL;
  return h;
}

void hash_free(hash *h)
{
  int i;
  for(i=0; i < h->size; i++)
    cell_free(h->array[i]);
  free(h->array);
  free(h);
}

int hash_func(char *key, int size)
{
  int i;
  int l = strlen(key);
  int val = key[0];
  for(i=1; i < l; i++)
    val = val + i *i * abs(key[i]);
  return val % size;
}

cell *hash_lookup(hash *h, char *key)
{
  int index = hash_func(key, h->size);
  cell *c;
  for(c=h->array[index]; c; c = c->next)
    if(!strcmp(key, c->key))
      return c;
  return NULL;
}

int hash_get_val(hash *h, char *key)
{
  int index = hash_func(key, h->size);
  cell *c;
  for(c=h->array[index]; c; c = c->next)
    if(!strcmp(key, c->key))
      return c->val;
  return HASH_INVALID_VAL;
}

cell *hash_add(hash *h, char *key, int val)
{
  int index;
  cell *c = hash_lookup(h, key);
  if(c != NULL) return c;
  index = hash_func(key, h->size);
  c = cell_new(strdup(key), val, h->array[index]);
  h->array[index] = c;
  h->nbelem++;
  return c;
}

int cell_nb(cell *c)
{
  if(c == NULL) return 0;
  return 1 + cell_nb(c->next);
}

void hash_inc_val(hash *h, char *key, int inc)
{
  cell *c = hash_lookup(h, key);
  if(c == NULL)
    hash_add(h, key, 0);
  else
    c->val += inc;
}

void hash_stats(hash *h)
{
  int max = 0;
  int i,l;
  int *table;
  int nb;

  for(i=0; i < h->size; i++)
    if((l = cell_nb(h->array[i])) > max)
    max = l;
  nb = max + 1;
  table = (int *)memalloc(nb * sizeof(int));
  for(i=0; i < nb; i++)
    table[i] = 0;
  for(i=0; i < h->size; i++)
    table[cell_nb(h->array[i])]++;
  
  for(i=0; i < nb; i++)
    printf("%d %d\n", i, table[i]);
}