Hello comp.lang.c,
This is a hash table implementation I wrote, please comment. Thanks in
advance.
Hi. Here are my 0.02€.
To start off, your code doesn't have many comments. Descriptive comments
are always nice to have, and help make the code easier to maintain.
# 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;
Your variable names could be a bit more descriptive.
};
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.
*/
A couple of things with the way you handled errors. First of all, it would
be nice that your error codes also supported the case where no error
occurred. This "everyting went ok" error code tends to be attributed to the
value 0, possibly due to the convenient way the if statement evaluates
expressions.
This makes it possible to write code such as:
<code>
int error(void)
{
(...)
if(no_error)
return 0
(...)
}
int main(void)
{
if(error)
{
// error is unequal to zero, hence this statement is executed
}
(...)
return 0;
}
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;
}
Building from the previous suggestion, it would be better if, instead of
relying on magical, undocumented numbers, you defined your error messages
through an enum, attributing to each enumerator a descriptive name. For
example:
<code>
enum hash_error
{
ERR_OK = 0,
ERR_CANNOT_DELETE_ELEMENT,
ERR_CANNOT_FIND_KEY,
ERR_UNKNOWN // in case of an unexpected error
};
void hash_table_fatal_error(int t, char *el)
{
switch (t)
{
case ERR_OK:
break;
case ERR_CANNOT_DELETE_ELEMENT:
printf("ERROR: Could not delete element '%s' from hash table.
\n",el);
break;
case ERR_CANNOT_FIND_KEY:
printf("ERROR: Could not find key '%s' in hash table.\n", el);
break;
default:
printf("ERROR: unknown error\n");
return ERR_UNKNOWN;
break;
}
}
exit(0);
}
/*
* Create a hash table with size 'size' and return a hash table array.
*/
hash_table ** hash_table_create_table(int size)
{
what about if (size < 0) ? Probably it would be a good idea to throw an
assert().
register int i = 0;
hash_table **x;
x = (hash_table **) calloc(size, sizeof(hash_table *));
It would be a good idea to test if calloc returned a null pointer, and
recover safely it it does.
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)
{
What if (t == NULL) ? And what if (*t == NULL) ? And what if (s == NULL)?
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 */
This is a bit nit-picking, but it would be nice if, instead of being forced
to run strcmp in each entry, you implemented a binary search tree for your
search terms, which would be built/updated with each call to
hash_table_add_element(). If that isn't possible then another alternative
would be to build a temporary list with all labels, test the 1st character
of each label with the 1st character of s and if it didn't matched then you
removed that entry from your list. Then, you reiterated for all subsequent
characters of the remaining entries until you were left with a complete
match. You would probably get considerable efficiency improvements with
this.
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)
{
Again, no sanity test is performed on the parameters. This is a nasty bug,
or even security problem, just waiting to happen.
int hash = hash_table_hash(uid);
hash_table *q = (hash_table *) calloc(1, sizeof(hash_table));
You need to test if calloc returned a null pointer.
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;
You've just added a new entry to your hash table without checking if it was
already present.
}
else
{
t[hash]->data.uid = strdup(uid);
t[hash]->data.d = strdup(data);
}
}
<snip/>
Hope this helps,
Rui Maciel
: