code example
/* Hash table example
* ref: https://gist.github.com/tonious/1377667
*/
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
typedef struct entry_s {
char *key;
char *value;
struct entry_s *next;
} entry_t;
typedef struct hashtable_s {
int size;
struct entry_s **table;
} hashtable_t;
/* create hashtable */
hashtable_t *
ht_create(int size)
{
hashtable_t *hashtable = NULL;
int i;
if (size < 1 ) return NULL;
/* allocate hashtable */
if ( (hashtable = malloc(sizeof(hashtable_t))) == NULL ) {
return NULL;
}
/* hashtable_t
* +-------------------------------+
* | size = n |
* +-------------------------------+
* | entry_t table[0] |
* +-------------------------------+
* | entry_t table[1] |
* +-------------------------------+
* | ... |
* | |
* +-------------------------------+
* | entry_t table[n-1] |
* +-------------------------------+
*/
/* allocate pointers to the head nodes */
if( (hashtable->table = malloc(sizeof(entry_t *) * size)) == NULL ) {
return NULL;
}
for ( i = 0; i < size; i++ ) {
hashtable->table[i] = NULL;
}
hashtable->size = size;
return hashtable;
}
/* hash a string for a particular hash table */
int ht_hash( hashtable_t *hashtable, char *key)
{
unsigned long int hashval=0;
int i = 0;
/* hash_func(key) = hashval */
while (hashval < ULONG_MAX && i < strlen(key) ) {
hashval = hashval << 8;
hashval += key[i];
i++;
}
return hashval % hashtable->size;
}
/* create a key-value pair */
entry_t *ht_newpair( char *key, char *value)
{
entry_t *newpair;
/* create entry_t */
if ( (newpair = malloc(sizeof(entry_t))) == NULL ) {
return NULL;
}
/* assign key */
if ( (newpair->key = strdup(key)) == NULL ) {
return NULL;
}
/* assign value */
if ( (newpair->value = strdup(value)) == NULL ) {
return NULL;
}
newpair->next = NULL;
return newpair;
}
/* insert a key-value pair into a hash table */
void ht_set( hashtable_t *hashtable, char *key, char *value)
{
int bin = 0;
entry_t *newpair = NULL;
entry_t *next = NULL;
entry_t *last = NULL;
bin = ht_hash(hashtable, key);
next = hashtable->table[bin];
while (next != NULL && next->key != NULL && strcmp(key,next->key) > 0 ) {
last = next;
next = next->next;
}
/* There is a already a pair, let's replace that string */
if (next != NULL && next->key != NULL && strcmp(key, next->key) == 0 ) {
free(next->value);
next->value = strdup(value);
} else {
/* Nope, couldn't find it, time to grow a pair */
newpair = ht_newpair(key, value);
/* start entry */
if ( next == hashtable->table[bin] ) {
newpair->next = next;
hashtable->table[bin] = newpair;
} else if ( next == NULL ) {
last->next = newpair;
} else {
newpair->next = next;
last->next = newpair;
}
}
}
/* retrieve a key-value pair from a hash table */
char *
ht_get( hashtable_t *hashtable, char *key)
{
int bin = 0;
entry_t *pair;
bin = ht_hash(hashtable, key);
pair = hashtable->table[bin];
while( pair != NULL && pair->key != NULL && strcmp(key, pair->key) > 0 ) {
pair = pair->next;
}
if ( pair == NULL || pair->key == NULL || strcmp(key, pair->key ) != 0 ) {
return NULL;
} else {
return pair->value;
}
}
int main(int argc, char **argv) {
hashtable_t *hashtable = ht_create(65536);
ht_set(hashtable, "key1", "ink");
ht_set(hashtable, "key2", "pinky");
ht_set(hashtable, "key3", "blinky");
printf("key1: %s\n", ht_get(hashtable, "key1"));
printf("key2: %s\n", ht_get(hashtable, "key2"));
printf("Push key1->red\n");
ht_set(hashtable, "key1", "red");
printf("key1: %s\n", ht_get(hashtable, "key1"));
return 0;
}