Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@cirocosta
Last active January 31, 2024 14:02
Show Gist options
  • Star 4 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cirocosta/e61e52cc6afe2633500b to your computer and use it in GitHub Desktop.
Save cirocosta/e61e52cc6afe2633500b to your computer and use it in GitHub Desktop.
glibc hash table example
/**
* Compile with -D_GNU_SOURCE
* Note: we're using static keys here and we don't plan to add
* new items to the table. In such case using a perfect
* hash generator (e.g, gperf) would clearly outperform
* this simple example w/ the cost of first running gperf
* (and other tradeoff that must be considered)
*
* Note: it's up to you to manage those resources contained in
* the hash table. Also, hsearch does NOT provide a
* REMOVE action, only ENTER and FIND. If you with to
* improve it with remove semantics you'll probably need
* to deal with it in the data-management side,
* remembering that the table will keep only growing in
* space (there's no UPDATE action as well)
*/
#include <search.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
static char* keys[] = { "ciro", "hue", "br", "haha", "Lol" };
static char* values[] = { "cccc", "hhhh", "bbbb", "aaa", "oooo" };
typedef struct table_t {
struct hsearch_data htab;
size_t size;
} table_t;
#define TABLE_T_INITIALIZER \
(table_t) \
{ \
.htab = (struct hsearch_data){ 0 }, .size = 0 \
}
table_t* table_create(size_t size)
{
table_t* table = malloc(sizeof(*table));
*table = TABLE_T_INITIALIZER;
hcreate_r(size, &table->htab);
return table;
}
void table_destroy(table_t* table)
{
hdestroy_r(&table->htab);
free(table);
table = NULL;
}
int table_add(table_t* table, char* key, void* data)
{
unsigned n = 0;
ENTRY e, *ep;
e.key = key;
e.data = data;
n = hsearch_r(e, ENTER, &ep, &table->htab);
return n;
}
void* table_get(table_t* table, char* key)
{
unsigned n = 0;
ENTRY e, *ep;
e.key = key;
n = hsearch_r(e, FIND, &ep, &table->htab);
if (!n)
return NULL;
return ep->data;
}
int main(int argc, char* argv[])
{
unsigned i = 0;
table_t* table = table_create(10);
void* d = NULL;
if (argc < 2) {
fprintf(stderr, "%s\n", "Usage: ./hash-tables <name>\n");
exit(EXIT_FAILURE);
}
for (; i < table->size; i++)
table_add(table, keys[i], values[i]);
if ((d = table_get(table, argv[1])) != NULL)
fprintf(stdout, "%s\n", (char*)d);
else
fprintf(stdout, "%s\n", "Not found :(");
table_destroy(table);
return 0;
}
@novaua
Copy link

novaua commented Nov 23, 2017

Reworked code is here https://github.com/novaua/ExpC/blob/master/glibc_hash_tbl/main.c
This includes the mentioned above fixes and improved memory management.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment