L
lolzy
Hello comp.lang.c,
This is a hash table implementation I wrote, please comment. Thanks in
advance.
# START CODE
/*
* Hash table demo.
* (C) Jori Koolstra - 19:40 11-8-2011
*/
#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 *);
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;
}
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 **) calloc(size, sizeof(hash_table *));
for (; i <= size; ++i)
{
x = (hash_table *) 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)
{
int id = hash_table_hash(s);
hash_table *q;
if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, s) != 0)
{
if (t[id]->x != NULL)
{
/* Move trough linked list */
for (q = t[id]->x; ; q = q->x)
{
if (strcmp(q->data.uid, s) == 0)
{
/* Found */
return q;
}
if (q->x == NULL)
{
break;
}
}
}
return NULL;
}
return (t[id]->data.uid == NULL ? NULL : t[id]);
}
/*
* Add 'data' to table 't' with key 'uid'.
*/
void hash_table_add_element(hash_table **t, char *uid, char *data)
{
int hash = hash_table_hash(uid);
hash_table *q = (hash_table *) calloc(1, sizeof(hash_table));
hash_table *c;
q->data.uid = strdup(uid);
q->data.d = strdup(data);
q->x = NULL;
c = t[hash];
if (c->data.uid != NULL)
{
while (c->x != NULL)
{
c = c->x;
}
c->x = q;
}
else
{
t[hash]->data.uid = strdup(uid);
t[hash]->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 id = hash_table_hash(uid);
hash_table *q;
if (t[id]->data.uid == NULL)
{
return 0;
}
if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, uid) != 0)
{
/* Move trough linked list */
for (q = t[id]; ; q = q->x)
{
if (strcmp(q->x->data.uid, uid) == 0)
{
if (q->x->x != NULL)
{
free(q->x);
q->x = q->x->x;
}
else
{
free(q->x);
q->x = NULL;
}
return 1;
}
if (q->x == NULL)
{
break;
}
}
return 0;
}
if (t[id]->x == NULL)
{
t[id]->data.uid = NULL;
}
else
{
t[id]->data.uid = t[id]->x->data.uid;
t[id]->data.d = t[id]->x->data.d;
t[id]->x = t[id]->x->x;
}
return 1;
}
/***** 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;
}
# END CODE
This is a hash table implementation I wrote, please comment. Thanks in
advance.
# START CODE
/*
* Hash table demo.
* (C) Jori Koolstra - 19:40 11-8-2011
*/
#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 *);
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;
}
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 **) calloc(size, sizeof(hash_table *));
for (; i <= size; ++i)
{
x = (hash_table *) 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)
{
int id = hash_table_hash(s);
hash_table *q;
if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, s) != 0)
{
if (t[id]->x != NULL)
{
/* Move trough linked list */
for (q = t[id]->x; ; q = q->x)
{
if (strcmp(q->data.uid, s) == 0)
{
/* Found */
return q;
}
if (q->x == NULL)
{
break;
}
}
}
return NULL;
}
return (t[id]->data.uid == NULL ? NULL : t[id]);
}
/*
* Add 'data' to table 't' with key 'uid'.
*/
void hash_table_add_element(hash_table **t, char *uid, char *data)
{
int hash = hash_table_hash(uid);
hash_table *q = (hash_table *) calloc(1, sizeof(hash_table));
hash_table *c;
q->data.uid = strdup(uid);
q->data.d = strdup(data);
q->x = NULL;
c = t[hash];
if (c->data.uid != NULL)
{
while (c->x != NULL)
{
c = c->x;
}
c->x = q;
}
else
{
t[hash]->data.uid = strdup(uid);
t[hash]->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 id = hash_table_hash(uid);
hash_table *q;
if (t[id]->data.uid == NULL)
{
return 0;
}
if (t[id]->data.uid != NULL && strcmp(t[id]->data.uid, uid) != 0)
{
/* Move trough linked list */
for (q = t[id]; ; q = q->x)
{
if (strcmp(q->x->data.uid, uid) == 0)
{
if (q->x->x != NULL)
{
free(q->x);
q->x = q->x->x;
}
else
{
free(q->x);
q->x = NULL;
}
return 1;
}
if (q->x == NULL)
{
break;
}
}
return 0;
}
if (t[id]->x == NULL)
{
t[id]->data.uid = NULL;
}
else
{
t[id]->data.uid = t[id]->x->data.uid;
t[id]->data.d = t[id]->x->data.d;
t[id]->x = t[id]->x->x;
}
return 1;
}
/***** 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;
}
# END CODE