Loading...
Searching...
No Matches
hashtable.c
Go to the documentation of this file.
#include "arc/std/hashtable.h"
#include "arc/std/errno.h"
#include <stdlib.h>
#include <stdio.h>
struct ARC_Hashtable {
uint32_t size;
ARC_HashtableNode **nodes;
ARC_Hashtable_Hash hash;
ARC_Hashtable_KeyCompare compare;
};
void CRC32(void *key, size_t *keysize, uint32_t *hashval){
*hashval = 0xffffffff;
for(size_t i = 0; i < *keysize; i++){
uint8_t value = *(((uint8_t *)key) + i);
for(uint8_t j = 0; j < 8; j++){
uint8_t flag = (uint8_t)((value ^ *hashval) & 1);
*hashval >>= 1;
if(flag){ *hashval ^= 0xEDB888320; }
value >>= 1;
}
}
*hashval = ~*hashval;
}
int8_t ARC_Default_Key_Compare(void *key1, size_t *key1size, void *key2, size_t *key2size){
return key1 == key2;
}
void ARC_HashtableNode_Create(ARC_HashtableNode **node, void *key, size_t *keysize, void *data){
*node = (ARC_HashtableNode *) malloc(sizeof(ARC_HashtableNode));
(*node)->key = key;
(*node)->keysize = *keysize;
(*node)->data = data;
(*node)->node = NULL;
}
void ARC_HashtableNode_Destroy(ARC_HashtableNode *node, ARC_HashtableNode_DestroyExternal external, void *userdata){
if(node == NULL){
return;
}
ARC_HashtableNode_Destroy(node->node, external, userdata);
if(external){
external(node, userdata);
}
free(node);
}
void ARC_Hashtable_Create(ARC_Hashtable **htable, uint32_t bucketsize, ARC_Hashtable_Hash hash, ARC_Hashtable_KeyCompare compare){
*htable = (ARC_Hashtable *) malloc(sizeof(ARC_Hashtable));
(*htable)->size = bucketsize;
(*htable)->nodes = (ARC_HashtableNode **) calloc(bucketsize, sizeof(ARC_HashtableNode *));
(*htable)->hash = (hash)? hash : CRC32;
(*htable)->compare = (compare)? compare : ARC_Default_Key_Compare;
}
void ARC_Hashtable_Destroy(ARC_Hashtable *htable, ARC_HashtableNode_DestroyExternal external, void *userdata){
for(uint32_t i = 0; i < htable->size; i++){
if(htable->nodes[i]){
ARC_HashtableNode_Destroy(htable->nodes[i], external, userdata);
}
}
free(htable->nodes);
free(htable);
}
void ARC_Hashtable_Add(ARC_Hashtable *htable, void *key, size_t keysize, void *data){
uint32_t size = 0;
htable->hash(key, &keysize, &size);
ARC_HashtableNode *bucket = htable->nodes[size % htable->size];
if(!bucket){
ARC_HashtableNode_Create(&bucket, key, &keysize, data);
htable->nodes[size % htable->size] = bucket;
return;
}
if(!htable->compare(bucket->key, &bucket->keysize, key, &keysize)){
arc_errno = ARC_ERRNO_EXISTS;
return;
}
while(bucket->node){
if(!htable->compare(bucket->node->key, &bucket->node->keysize, key, &keysize)){
arc_errno = ARC_ERRNO_EXISTS;
return;
}
bucket = bucket->node;
}
ARC_HashtableNode_Create(&(bucket->node), key, &keysize, data);
}
void ARC_Hashtable_Get(ARC_Hashtable *htable, void *key, size_t keysize, void **data){
uint32_t size = 0;
htable->hash(key, &keysize, &size);
ARC_HashtableNode *bucket = htable->nodes[size % htable->size];
if(!bucket){
*data = NULL;
arc_errno = ARC_ERRNO_NULL;
return;
}
if(!htable->compare(bucket->key, &bucket->keysize, key, &keysize)){
*data = bucket->data;
return;
}
while(bucket->node){
if(!htable->compare(bucket->node->key, &bucket->node->keysize, key, &keysize)){
*data = bucket->node->data;
return;
}
bucket = bucket->node;
}
arc_errno = ARC_ERRNO_NULL;
}
void ARC_Hashtable_Remove(ARC_Hashtable *htable, void *key, size_t keysize, ARC_HashtableNode_DestroyExternal external, void *userdata){
uint32_t size = 0;
htable->hash(key, &keysize, &size);
ARC_HashtableNode *bucket = htable->nodes[size % htable->size];
if(!bucket){
arc_errno = ARC_ERRNO_NULL;
return;
}
if(!htable->compare(bucket->key, &bucket->keysize, key, &keysize)){
ARC_HashtableNode *temp = bucket;
htable->nodes[size % htable->size] = bucket->node;
if(external){
external(temp, userdata);
}
free(temp);
return;
}
while(bucket->node){
if(!htable->compare(bucket->node->key, &bucket->node->keysize, key, &keysize)){
ARC_HashtableNode *temp = bucket->node;
bucket->node = bucket->node->node;
if(external){
external(temp, userdata);
}
free(temp);
return;
}
bucket = bucket->node;
}
arc_errno = ARC_ERRNO_NULL;
}
errno.h
arc_errno
int32_t arc_errno
Definition errno.c:5
ARC_ERRNO_EXISTS
#define ARC_ERRNO_EXISTS
Definition errno.h:9
ARC_ERRNO_NULL
#define ARC_ERRNO_NULL
Definition errno.h:6
ARC_HashtableNode_Create
void ARC_HashtableNode_Create(ARC_HashtableNode **node, void *key, size_t *keysize, void *data)
Definition hashtable.c:34
ARC_Hashtable_Destroy
void ARC_Hashtable_Destroy(ARC_Hashtable *htable, ARC_HashtableNode_DestroyExternal external, void *userdata)
destroys ARC_Hashtable type
Definition hashtable.c:64
ARC_HashtableNode_Destroy
void ARC_HashtableNode_Destroy(ARC_HashtableNode *node, ARC_HashtableNode_DestroyExternal external, void *userdata)
Definition hashtable.c:42
ARC_Hashtable_Get
void ARC_Hashtable_Get(ARC_Hashtable *htable, void *key, size_t keysize, void **data)
gets value from hashtable by key
Definition hashtable.c:103
ARC_Hashtable_Create
void ARC_Hashtable_Create(ARC_Hashtable **htable, uint32_t bucketsize, ARC_Hashtable_Hash hash, ARC_Hashtable_KeyCompare compare)
cteates ARC_Hashtable type
Definition hashtable.c:56
ARC_Hashtable_Remove
void ARC_Hashtable_Remove(ARC_Hashtable *htable, void *key, size_t keysize, ARC_HashtableNode_DestroyExternal external, void *userdata)
removes value from hashtable
Definition hashtable.c:131
ARC_Hashtable_Add
void ARC_Hashtable_Add(ARC_Hashtable *htable, void *key, size_t keysize, void *data)
adds value to hastable
Definition hashtable.c:75
ARC_Default_Key_Compare
int8_t ARC_Default_Key_Compare(void *key1, size_t *key1size, void *key2, size_t *key2size)
Definition hashtable.c:30
CRC32
void CRC32(void *key, size_t *keysize, uint32_t *hashval)
Definition hashtable.c:14
hashtable.h
ARC_Hashtable_KeyCompare
int8_t(* ARC_Hashtable_KeyCompare)(void *key1, size_t *key1size, void *key2, size_t *key2size)
key comparison function ptr
Definition hashtable.h:45
ARC_HashtableNode_DestroyExternal
void(* ARC_HashtableNode_DestroyExternal)(ARC_HashtableNode *node, void *userdata)
callback to allow memory freeing of nodes
Definition hashtable.h:53
ARC_Hashtable_Hash
void(* ARC_Hashtable_Hash)(void *key, size_t *keysize, uint32_t *hashval)
a hashing function ptr
Definition hashtable.h:35
ARC_HashtableNode
Definition hashtable.h:20
ARC_HashtableNode::key
void * key
Definition hashtable.h:21
ARC_HashtableNode::node
ARC_HashtableNode * node
Definition hashtable.h:25
ARC_HashtableNode::keysize
size_t keysize
Definition hashtable.h:22
ARC_HashtableNode::data
void * data
Definition hashtable.h:24
ARC_Hashtable
Definition hashtable.c:7
ARC_Hashtable::hash
ARC_Hashtable_Hash hash
Definition hashtable.c:10
ARC_Hashtable::nodes
ARC_HashtableNode ** nodes
Definition hashtable.c:9
ARC_Hashtable::size
uint32_t size
Definition hashtable.c:8
ARC_Hashtable::compare
ARC_Hashtable_KeyCompare compare
Definition hashtable.c:11