141 lines
3.1 KiB
C
Executable File
141 lines
3.1 KiB
C
Executable File
/*
|
|
* hashtable.c
|
|
* really simple hash table implementation
|
|
*
|
|
* Copyright (c) 2011-2016 Nikias Bassen, All Rights Reserved.
|
|
*
|
|
* This library is free software; you can redistribute it and/or
|
|
* modify it under the terms of the GNU Lesser General Public
|
|
* License as published by the Free Software Foundation; either
|
|
* version 2.1 of the License, or (at your option) any later version.
|
|
*
|
|
* This library is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
* Lesser General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU Lesser General Public
|
|
* License along with this library; if not, write to the Free Software
|
|
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
|
|
*/
|
|
#include "hashtable.h"
|
|
|
|
hashtable_t* hash_table_new(hash_func_t hash_func, compare_func_t compare_func, free_func_t free_func)
|
|
{
|
|
hashtable_t* ht = (hashtable_t*)malloc(sizeof(hashtable_t));
|
|
int i;
|
|
for (i = 0; i < 4096; i++) {
|
|
ht->entries[i] = NULL;
|
|
}
|
|
ht->count = 0;
|
|
ht->hash_func = hash_func;
|
|
ht->compare_func = compare_func;
|
|
ht->free_func = free_func;
|
|
return ht;
|
|
}
|
|
|
|
void hash_table_destroy(hashtable_t *ht)
|
|
{
|
|
if (!ht) return;
|
|
|
|
int i = 0;
|
|
for (i = 0; i < 4096; i++) {
|
|
if (ht->entries[i]) {
|
|
hashentry_t* e = ht->entries[i];
|
|
while (e) {
|
|
if (ht->free_func) {
|
|
ht->free_func(e->value);
|
|
}
|
|
hashentry_t* old = e;
|
|
e = e->next;
|
|
free(old);
|
|
}
|
|
}
|
|
}
|
|
free(ht);
|
|
}
|
|
|
|
void hash_table_insert(hashtable_t* ht, void *key, void *value)
|
|
{
|
|
if (!ht || !key) return;
|
|
|
|
unsigned int hash = ht->hash_func(key);
|
|
|
|
int idx0 = hash & 0xFFF;
|
|
|
|
// get the idx0 list
|
|
hashentry_t* e = ht->entries[idx0];
|
|
while (e) {
|
|
if (ht->compare_func(e->key, key)) {
|
|
// element already present. replace value.
|
|
e->value = value;
|
|
return;
|
|
}
|
|
e = e->next;
|
|
}
|
|
|
|
// if we get here, the element is not yet in the list.
|
|
|
|
// make a new entry.
|
|
hashentry_t* entry = (hashentry_t*)malloc(sizeof(hashentry_t));
|
|
entry->key = key;
|
|
entry->value = value;
|
|
if (!ht->entries[idx0]) {
|
|
// first entry
|
|
entry->next = NULL;
|
|
} else {
|
|
// add to list
|
|
entry->next = ht->entries[idx0];
|
|
}
|
|
ht->entries[idx0] = entry;
|
|
ht->count++;
|
|
}
|
|
|
|
void* hash_table_lookup(hashtable_t* ht, void *key)
|
|
{
|
|
if (!ht || !key) return NULL;
|
|
unsigned int hash = ht->hash_func(key);
|
|
|
|
int idx0 = hash & 0xFFF;
|
|
|
|
hashentry_t* e = ht->entries[idx0];
|
|
while (e) {
|
|
if (ht->compare_func(e->key, key)) {
|
|
return e->value;
|
|
}
|
|
e = e->next;
|
|
}
|
|
return NULL;
|
|
}
|
|
|
|
void hash_table_remove(hashtable_t* ht, void *key)
|
|
{
|
|
if (!ht || !key) return;
|
|
|
|
unsigned int hash = ht->hash_func(key);
|
|
|
|
int idx0 = hash & 0xFFF;
|
|
|
|
// get the idx0 list
|
|
hashentry_t* e = ht->entries[idx0];
|
|
hashentry_t* last = e;
|
|
while (e) {
|
|
if (ht->compare_func(e->key, key)) {
|
|
// found element, remove it from the list
|
|
hashentry_t* old = e;
|
|
if (e == ht->entries[idx0]) {
|
|
ht->entries[idx0] = e->next;
|
|
} else {
|
|
last->next = e->next;
|
|
}
|
|
if (ht->free_func) {
|
|
ht->free_func(old->value);
|
|
}
|
|
free(old);
|
|
return;
|
|
}
|
|
last = e;
|
|
e = e->next;
|
|
}
|
|
}
|