Skip to content

Instantly share code, notes, and snippets.

@phil303
Created April 15, 2013 16:54
Show Gist options
  • Save phil303/5389534 to your computer and use it in GitHub Desktop.
Save phil303/5389534 to your computer and use it in GitHub Desktop.
Simple hashtable in c
#include <stdlib.h>
#include <stdio.h>
int HASH_SIZE = 10;
struct Node {
char *key;
char *value;
struct Node *next;
};
char *search_list(struct Node *node, char *key)
{
struct Node *prev = NULL;
while (node) {
if (node->key = key) {
return node->value;
}
prev = node;
node = node->next;
}
}
int needs_replace(struct Node *node, struct Node *new_node, struct Node *prev, char *key)
{
if (node->key == key) {
// if not a head node, replace the severed connection
if (prev) {
prev->next = new_node;
}
new_node->next = node->next;
free(node);
return 1;
}
}
struct Node *append(struct Node *head_node, char *key, char *value)
{
// allocate some memory for node
struct Node *new_node = malloc(sizeof(struct Node *));
// set attributes on node
new_node->key = key;
new_node->value = value;
new_node->next = NULL;
// append to end of list
struct Node *node = head_node;
struct Node *prev = NULL;
if (head_node) {
while (node->next) {
if (needs_replace(node, new_node, prev, key)) {
return head_node;
}
prev = node;
node = node->next;
}
/*link the last node to the new node*/
/*will be head ptr if never entered loop above*/
if (prev) {
prev->next = new_node;
} else {
if (needs_replace(head_node, new_node, prev, key)) {
return new_node;
}
head_node->next = new_node;
}
return head_node;
} else {
return new_node;
}
}
int hash(char *key)
{
int inter = 0;
int i;
for (i = 0; i < 10; i++) {
int b = key[i];
if (b == 0) {
return inter;
}
inter += b;
}
}
struct Node **ptr_array;
void insert(char *key, char *val)
{
int h = hash(key);
int bucket = h % HASH_SIZE;
ptr_array[bucket] = append(ptr_array[bucket], key, val);
}
char *get(char *key)
{
int h = hash(key);
int bucket = h % HASH_SIZE;
struct Node *node = ptr_array[bucket];
return search_list(node, key);
}
void initialize_buckets()
{
ptr_array = malloc(sizeof(struct Node *) * HASH_SIZE);
int i;
for (i = 0; i < HASH_SIZE; i++) {
ptr_array[i] = NULL;
}
}
int main()
{
initialize_buckets();
insert("foo\0", "bar\0");
insert("newb\0", "baz\0");
insert("nub\0", "bob\0");
printf("%s\n", get("foo\0"));
printf("%s\n", get("foo\0"));
printf("%s\n", get("nub\0"));
// test replace
insert("key\0", "foo\0");
insert("key\0", "fooz\0");
insert("key\0", "fab\0");
printf("%s\n", get("key\0"));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment