Loading...
Searching...
No Matches
hashtable.c File Reference
`#include "arc/std/hashtable.h"`
`#include "arc/std/errno.h"`
`#include <stdlib.h>`
`#include <stdio.h>`

Go to the source code of this file.

## Data Structures

struct | ARC_Hashtable

## Functions

void | CRC32 (void *key, size_t *keysize, uint32_t *hashval)
int8_t | ARC_Default_Key_Compare (void *key1, size_t *key1size, void *key2, size_t *key2size)
void | ARC_HashtableNode_Create (ARC_HashtableNode **node, void *key, size_t *keysize, void *data)
void | ARC_HashtableNode_Destroy (ARC_HashtableNode *node, ARC_HashtableNode_DestroyExternal external, void *userdata)
void | ARC_Hashtable_Create (ARC_Hashtable **htable, uint32_t bucketsize, ARC_Hashtable_Hash hash, ARC_Hashtable_KeyCompare compare)
| cteates ARC_Hashtable type
void | ARC_Hashtable_Destroy (ARC_Hashtable *htable, ARC_HashtableNode_DestroyExternal external, void *userdata)
| destroys ARC_Hashtable type
void | ARC_Hashtable_Add (ARC_Hashtable *htable, void *key, size_t keysize, void *data)
| adds value to hastable
void | ARC_Hashtable_Get (ARC_Hashtable *htable, void *key, size_t keysize, void **data)
| gets value from hashtable by key
void | ARC_Hashtable_Remove (ARC_Hashtable *htable, void *key, size_t keysize, ARC_HashtableNode_DestroyExternal external, void *userdata)
| removes value from hashtable

## Function Documentation

## ARC_Default_Key_Compare()

int8_t ARC_Default_Key_Compare | ( | void * | key1,
|  | size_t * | key1size,
|  | void * | key2,
|  | size_t * | key2size )

Definition at line 30 of file hashtable.c.

{
return key1 == key2;
}

Referenced by ARC_Hashtable_Create().

## ARC_Hashtable_Add()

void ARC_Hashtable_Add | ( | ARC_Hashtable * | htable,
|  | void * | key,
|  | size_t | keysize,
|  | void * | data )

adds value to hastable

Parameters

  htable | ARC_Hashtable to add to
  key | key for node that is being added
  keysize | sizeof key before it is passed into a void *
  data | data for node that is being added

Definition at line 75 of file hashtable.c.

{
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);
}
arc_errno
int32_t arc_errno
Definition errno.c:5
ARC_ERRNO_EXISTS
#define ARC_ERRNO_EXISTS
Definition errno.h:9
ARC_HashtableNode_Create
void ARC_HashtableNode_Create(ARC_HashtableNode **node, void *key, size_t *keysize, void *data)
Definition hashtable.c:34
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_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

References arc_errno, ARC_ERRNO_EXISTS, ARC_HashtableNode_Create(), ARC_Hashtable::compare, ARC_Hashtable::hash, ARC_HashtableNode::key, ARC_HashtableNode::keysize, ARC_HashtableNode::node, ARC_Hashtable::nodes, and ARC_Hashtable::size.

Referenced by ARC_Config_AddKey(), ARC_Config_AddKeyCString(), ARC_Config_CreateGroup(), and ARC_Config_LoadFromKey().

## 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

Parameters

  htable | where to store data
  bucketsize | num of nodes to create in inital table
  hash | hashing function to be used, if set to NULL, CRC32 will be used
  compare | comparison functon for checking keys, if set to NULL, addresses will be compared

Definition at line 56 of file hashtable.c.

{
*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;
}
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
ARC_Hashtable
Definition hashtable.c:7

References ARC_Default_Key_Compare(), CRC32(), and ARC_Hashtable::size.

Referenced by ARC_Config_Create(), and ARC_Config_CreateGroup().

## ARC_Hashtable_Destroy()

void ARC_Hashtable_Destroy | ( | ARC_Hashtable * | htable,
|  | ARC_HashtableNode_DestroyExternal | external,
|  | void * | userdata )

destroys ARC_Hashtable type

Parameters

  htable | htable that will be destroyed
  external | function to allow external freeing of nodes, can be NULL
  userdata | any data the user wants access to in the callback

Definition at line 64 of file hashtable.c.

{
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);
}
ARC_HashtableNode_Destroy
void ARC_HashtableNode_Destroy(ARC_HashtableNode *node, ARC_HashtableNode_DestroyExternal external, void *userdata)
Definition hashtable.c:42

References ARC_HashtableNode_Destroy(), ARC_Hashtable::nodes, and ARC_Hashtable::size.

Referenced by ARC_Config_Destroy(), and ARC_Config_DestroyGroup().

## ARC_Hashtable_Get()

void ARC_Hashtable_Get | ( | ARC_Hashtable * | htable,
|  | void * | key,
|  | size_t | keysize,
|  | void ** | data )

gets value from hashtable by key

Parameters

  htable | table to get value from
  key | key to get value from table
  keysize | sizeof key before it is passed into a void *
  data | data retrieved from table

Definition at line 103 of file hashtable.c.

{
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;
}
ARC_ERRNO_NULL
#define ARC_ERRNO_NULL
Definition errno.h:6
ARC_HashtableNode::data
void * data
Definition hashtable.h:24

References arc_errno, ARC_ERRNO_NULL, ARC_Hashtable::compare, ARC_HashtableNode::data, ARC_Hashtable::hash, ARC_HashtableNode::key, ARC_HashtableNode::keysize, ARC_HashtableNode::node, ARC_Hashtable::nodes, and ARC_Hashtable::size.

Referenced by ARC_Config_Get(), ARC_Config_LoadFromKey(), and ARC_Config_SetGroup().

## 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

Parameters

  htable | ARC_Hashtable to remove from
  key | key of data to remove from hash table
  keysize | sizeof key before it is passed into a void *
  external | function to allow external freeing of data, can be NULL
  userdata | any data the user wants access to in the callback

Definition at line 131 of file hashtable.c.

{
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;
}

References arc_errno, ARC_ERRNO_NULL, ARC_Hashtable::compare, ARC_Hashtable::hash, ARC_HashtableNode::key, ARC_HashtableNode::keysize, ARC_HashtableNode::node, ARC_Hashtable::nodes, and ARC_Hashtable::size.

Referenced by ARC_Config_UnloadFromKey().

## ARC_HashtableNode_Create()

void ARC_HashtableNode_Create | ( | ARC_HashtableNode ** | node,
|  | void * | key,
|  | size_t * | keysize,
|  | void * | data )

Definition at line 34 of file hashtable.c.

{
*node = (ARC_HashtableNode *) malloc(sizeof(ARC_HashtableNode));
(*node)->key = key;
(*node)->keysize = *keysize;
(*node)->data = data;
(*node)->node = NULL;
}

References ARC_HashtableNode::key.

Referenced by ARC_Hashtable_Add().

## ARC_HashtableNode_Destroy()

void ARC_HashtableNode_Destroy | ( | ARC_HashtableNode * | node,
|  | ARC_HashtableNode_DestroyExternal | external,
|  | void * | userdata )

Definition at line 42 of file hashtable.c.

{
if(node == NULL){
return;
}
ARC_HashtableNode_Destroy(node->node, external, userdata);
if(external){
external(node, userdata);
}
free(node);
}

References ARC_HashtableNode_Destroy(), and ARC_HashtableNode::node.

Referenced by ARC_Hashtable_Destroy(), and ARC_HashtableNode_Destroy().

## CRC32()

void CRC32 | ( | void * | key,
|  | size_t * | keysize,
|  | uint32_t * | hashval )

Definition at line 14 of file hashtable.c.

{
*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;
}

Referenced by ARC_Hashtable_Create().