Created
April 15, 2013 16:54
-
-
Save phil303/5389534 to your computer and use it in GitHub Desktop.
Simple hashtable in c
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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