Created
December 10, 2012 17:34
-
-
Save int3/4252033 to your computer and use it in GitHub Desktop.
Simple open-addressed hashtable
This file contains hidden or 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> | |
#include <stdbool.h> | |
#include <string.h> | |
#include <assert.h> | |
// no actual pointer should have this value, due to alignment | |
static void* DELETED = (void*)1; | |
static int TABLE_SIZE = 701; | |
static int hash(int key) { | |
return key % TABLE_SIZE; | |
} | |
static int hash2(int key) { | |
return 1 + key % (TABLE_SIZE - 1); | |
} | |
typedef struct { | |
int key; | |
void* value; | |
} entry; | |
entry** ht_create() { | |
entry** table = malloc(sizeof(entry*) * TABLE_SIZE); | |
memset(table, 0, sizeof(entry*) * TABLE_SIZE); | |
return table; | |
} | |
bool ht_put(entry** table, int key, void* value) { | |
int start = hash(key); | |
int idx = start; | |
int second_hash = hash2(key); | |
int i = 0; | |
do { | |
if (table[idx] == NULL) { | |
table[idx] = malloc(sizeof(entry)); | |
table[idx]->key = key; | |
table[idx]->value = value; | |
return true; | |
} | |
else if (table[idx] != DELETED && table[idx]->key == key) { | |
table[idx]->value = value; | |
return true; | |
} | |
} | |
while((idx = (start + second_hash * ++i) % TABLE_SIZE) != start); | |
return false; | |
} | |
bool ht_get(entry** table, int key, void** value) { | |
int start = hash(key); | |
int idx = start; | |
int second_hash = hash2(key); | |
int i = 0; | |
do { | |
if (table[idx] == NULL) { | |
return false; | |
} | |
else if (table[idx] != DELETED && table[idx]->key == key) { | |
*value = table[idx]->value; | |
return true; | |
} | |
} | |
while((idx = (start + second_hash * ++i) % TABLE_SIZE) != start); | |
return false; | |
} | |
bool ht_del(entry** table, int key) { | |
int start = hash(key); | |
int idx = start; | |
int second_hash = hash2(key); | |
int i = 0; | |
do { | |
if (table[idx]->key == key) { | |
free(table[idx]); | |
table[idx] = DELETED; | |
return true; | |
} | |
} | |
while((idx = (start + second_hash * ++i) % TABLE_SIZE) != start); | |
return false; | |
} | |
int main() { | |
entry** table = ht_create(); | |
assert(ht_put(table, 1234, (void*)5)); | |
assert(ht_put(table, 1234, (void*)5)); | |
assert(ht_put(table, 1234 + 701, (void*)6)); | |
long result; | |
assert(ht_get(table, 1234, (void*)&result)); | |
assert(result == 5); | |
assert(ht_get(table, 1234 + 701, (void*)&result)); | |
assert(result == 6); | |
assert(ht_del(table, 1234)); | |
assert(ht_get(table, 1234, (void*)&result) != true); | |
assert(ht_get(table, 1234 + 701, (void*)&result)); | |
assert(result == 6); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment