hashing demo

hash.c

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

#define HASH_TABLE_SIZE 100

#define HASH_TABLE_DELETE_ELEMENT_CHECK_FOR_ERRORS(t, n) 
if (hash_table_delete_element(t, n) == 0) 
hash_table_fatal_error(0, n)

#define HASH_TABLE_GET_STRING_FROM_TABLE_CHECK_FOR_ERRORS(t,n, z) 
if ((z = 
hash_table_get_string_from_table(t, n)) == NULL) 
hash_table_fatal_error(1, n)


struct table_data { char *uid; char *d;

};

typedef struct table_data table_data;

struct hash_table { table_data data; struct hash_table *x;

};

typedef struct hash_table hash_table;

hash_table ** hash_table_create_table(int); hash_table * hash_table_get_string_from_table(hash_table **, char *); 
int hash_table_hash(char *); void hash_table_add_element(hash_table **, char *, char *); 
int hash_table_delete_element(hash_table **, char *); 
void hash_table_fatal_error(int, char *); 
void * hash_table_safe_calloc(size_t, size_t);

int main(void) 
{ 
hash_table **table; 
hash_table *y;

table = hash_table_create_table(HASH_TABLE_SIZE);

hash_table_add_element(table, "John", "Hello John!"); hash_table_add_element(table, "Kim", "Hello Kim!"); hash_table_add_element(table, "Jori", "Hello Jori!"); hash_table_add_element(table, "Jack", "Hello Jack!");

HASH_TABLE_DELETE_ELEMENT_CHECK_FOR_ERRORS(table, "Kim");

HASH_TABLE_GET_STRING_FROM_TABLE_CHECK_FOR_ERRORS(table, "Jack", y);

printf("%s\n", y->data.d);

return 0;

}

/* * Print error and quit. */void hash_table_fatal_error(int t, char *el) { switch (t) { case 0: printf("ERROR: Could not delete element '%s' from hash table.\n", el); break; case 1: printf("ERROR: Could not find key '%s' in hash table.\n", el); break; case 2: printf("ERROR: Could not allocate memory.\n"); break; }

exit(0);

}

/* * Create a hash table with size 'size' and return a hash table array. */hash_table ** hash_table_create_table(int size) { register int i = 0; hash_table **x;

x = (hash_table **) hash_table_safe_calloc(size, sizeof(hash_table *));

for (; i < size; ++i) { x[i] = (hash_table *) hash_table_safe_calloc(1, sizeof(hash_table)); }

return x;

}

/* * Returns a specified hash table element from table't'with key's', * or NULL on failure. */hash_table * hash_table_get_string_from_table(hash_table **t, char *s) { hash_table *q;

for (q = t[hash_table_hash(s)]; q; q = q->x) { if (q->data.uid && 0 == strcmp(q->data.uid, s)) { return q; } }

return NULL;

}

/* * Add 'data' to table 't' with key 'uid'. */void hash_table_add_element(hash_table **t, char *uid, char *data) { int h = hash_table_hash(uid); hash_table *q, *c = t[h];

if (c->data.uid != NULL) { q = (hash_table *) hash_table_safe_calloc(1, sizeof(hash_table)); q->data.uid = strdup(uid); q->data.d = strdup(data);

for (; c->x != NULL; c = c->x)

c->x = q; } else { t[h]->data.uid = strdup(uid); t[h]->data.d = strdup(data); }

}

/* * Delete element identified by 'uid' from hash table't'. * Returns: 1 on success, 0 on failure. */int hash_table_delete_element(hash_table **t, char *uid) { int h = hash_table_hash(uid); hash_table *q;

if (t[h]->data.uid != NULL && strcmp(t[h]->data.uid, uid) != 0) { /* Move trough linked list */for (q = t[h]; q; q = q->x) { if (strcmp(q->x->data.uid, uid) == 0) { free(q->x); q->x = q->x->x;

return 1; } }

return 0; }

if (t[h]->x == NULL) { if (t[h]->data.uid == NULL) { return 0; } else { t[h]->data.uid = NULL; } } else { t[h]->data.uid = t[h]->x->data.uid; t[h]->data.d = t[h]->x->data.d; t[h]->x = t[h]->x->x; }

return 1;

}

/* * Allocate space with error checking. */void * hash_table_safe_calloc(size_t num, size_t size) { void *p;

if ((p = calloc(num, size)) == NULL) { hash_table_fatal_error(2, ""); }

return p;

}

/***** NOT UNDER MY COPYRIGHT *****//* * UNIX ELF hash. * Published hash algorithm used in the UNIX ELF format for object files. */int hash_table_hash(char *data) { int h = 0, g;

while (*data) { h = (h << 4) + *data++;

if (g = h & 0xF0000000) { h ^= g >> 24; }

h &= ~g; }

return h % HASH_TABLE_SIZE;