hash implementation

06 Apr 2010 some hash

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

#define HSH_EMPTY "__EMPTY__"
#define HSH_MAX_SIZE 3 
#define HSH_FOUND 0
#define HSH_FOUND_FIRST 1
#define HSH_NOT_FOUND -1
#define HSH_NOT_INIT -2

typedef struct hash_node {
 struct hash_node *n;
 char *k;
 char *v;
} hash_type;

extern void     hash_delete  (hash_type **, char *); 
extern char    *hash_get   (hash_type **, char *);
extern void     hash_pairs     (hash_type **, void (*func)(hash_type *));
extern void     hash_set   (hash_type **, char *, char *);
















void
print_pair (hash_type *p)
{
 printf ("%s -> %s\n", p->k, p->v);
}

hash_type *me[HSH_MAX_SIZE];

int
main (void)
{ 
 hash_set (me, "nome", "Daniel");
 hash_set (me, "sobrenome", "Hilst");
 hash_delete (me, "nome");
 printf ("%s %s\n", hash_get (me, "nome"), hash_get (me, "sobrenome"));
 return 0;
}


















struct hash_found {
 signed int s;
 hash_type *p;
};

static hash_type   *hash_alloc  (void);
static unsigned    hash_index  (char *);
static struct hash_found  hash_lookup (hash_type **, char *, unsigned); 

void
hash_delete (hash_type *h[], char *k)
{ 
 unsigned i = hash_index (k);
 struct hash_found f = hash_lookup (h, k, i);
 hash_type *p, *prev;
 if (f.s == HSH_FOUND) {
  prev = f.p;
  p = f.p->n;
  prev->n = prev->n->n;
  free (p->k);
  free (p->v);
  free (p);
 }
 else if (f.s == HSH_FOUND_FIRST) {
   p = h[i];
  h[i] = h[i]->n;
  free (p->k);
  free (p->v);
  free (p);
 }  
}

char *
hash_get (hash_type *h[], char *k)
{ 
 unsigned i = hash_index (k);
 struct hash_found f = hash_lookup (h, k, i);
 if (f.s == HSH_FOUND) {
  return f.p->n->v;
 }
 else if (f.s == HSH_FOUND_FIRST) { 
  return f.p->v;
 }
 return HSH_EMPTY;
}

void
hash_pairs (hash_type *h[], void (*func)(hash_type *))
{ 
 unsigned i = 0;
 hash_type *p = h[i];
 for (; i < HSH_MAX_SIZE;) {
  for(; p != NULL; p = p->n)
   func (p);
  p = h[++i];
 }
}

void
hash_set (hash_type *h[], char *k, char *v)
{ 
 unsigned i = hash_index (k);
 struct hash_found f = hash_lookup (h, k, i);
 hash_type *p, *prev;
 
 if (f.s == HSH_FOUND) {
  p = f.p->n;
  free (p->v);
  p->v = strdup (v); 
 }
 else if (f.s == HSH_FOUND_FIRST) {
  p = f.p;
  free (p->v);
  p->v = strdup (v);
 }
 else if (f.s == HSH_NOT_INIT) {
  p = h[ i ] = hash_alloc ();
  p->k = strdup (k);
  p->v = strdup (v);
  p->n = NULL;
 }
 else { // if (f.s == HSH_NOT_FOUND) {
  prev = f.p;
  p = prev->n = hash_alloc ();
  p->k = strdup (k);
  p->v = strdup (v); 
 }
}









static hash_type *
hash_alloc (void)
{
 hash_type *new = (hash_type *) malloc (sizeof (hash_type));
 if (new == NULL) {
  fprintf (stderr, "malloc error\n");
  exit (EXIT_FAILURE);
 }
 return new;
}

static unsigned
hash_index (char *k)
{ 
 unsigned i;
 for (i = 0; *k != '\0'; k++)
  i += *k;  
 return i % HSH_MAX_SIZE;
}

static struct hash_found 
hash_lookup (hash_type **h, char *k, unsigned i) /* hash, key, index */ 
{ 
 hash_type *p, *prev;
 p = h[ i ];
 if (p == NULL) 
  return (struct hash_found) {HSH_NOT_INIT, NULL};
 else if (strcmp (p->k, k) == 0)
  return (struct hash_found) {HSH_FOUND_FIRST, p};

 prev = p;
 p = p->n;
 for (; p != NULL; p = p->n) {
  if (strcmp (p->k, k) == 0)
   return (struct hash_found) {HSH_FOUND, prev};
  prev = p;
 } 
 return (struct hash_found) {HSH_NOT_FOUND, prev};
}

use:
hash_type *MONHASH[HSH_MAX_SIZE]; // the HSH_MAX_SIZE is mandatory here, if this ins't global
you need to initializate every element of it to NULL;

hash_set (MONHASH, "KEY", "VALUE"); // install a key or change it
hash_get (MONHASH, "KEY"); // returns "VALUE" or "__EMPTY__" if doesn't found it
hash_delete (MONHASH, "KEY"); // delete the pair "KEY" "VALUE" and free its memory
hash_pairs (MONHASH, FUNC); for each pair in hash execute the function FUNC passing the pair to it via MONHASH, entry; (e.g) void f (hash_type *h) { puts (h->k) };. Then hash_pairs (MONHASH, f);



What else... math makes me fell sad..