Skip to content

Instantly share code, notes, and snippets.

@Falconerd
Created May 21, 2020 15:14
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Falconerd/4702ba19e5413b7be522c693a00c6d11 to your computer and use it in GitHub Desktop.
/* dict.h */
#pragma once
#include <stdlib.h>
struct dict {
int *hashed_keys;
void *values;
int count;
size_t size;
};
struct dict *dict_create(size_t size);
void *dict_get(struct dict *dict, const char *key);
void dict_set(struct dict *dict, const char *key, const void *value);
void dict_del(struct dict *dict, const char *key);
/* dict.c */
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include "dict.h"
static int dict_hash(const char *key)
{
int len = strlen(key);
int g = 23;
int hash = 0;
int i = 0;
for (i = 0; i < len; ++i)
hash = g * hash + key[i];
return hash;
}
static void dict_add(struct dict *dict, const int hash, const void *value)
{
int *keys = realloc(dict->hashed_keys, sizeof(int) * (dict->count + 1));
void *values = realloc(dict->values, dict->size * (dict->count + 1));
if (NULL == keys || NULL == values)
{
puts("Error reallocating dict.");
exit(1);
}
keys[dict->count] = hash;
memcpy((char*)values+(dict->count*dict->size), value, dict->size);
dict->hashed_keys = keys;
dict->values = values;
dict->count++;
printf("Added %d to dict [%d]\n", hash, keys[dict->count-1]);
}
struct dict *dict_create(size_t size)
{
struct dict *dict = malloc(sizeof(struct dict));
dict->size = size;
return dict;
}
void *dict_get(struct dict *dict, const char *key)
{
int hash = dict_hash(key);
char *ptr = NULL;
int i;
for (i = 0; i < dict->count; ++i)
{
printf("Checking index %d: %d\n", i, dict->hashed_keys[i]);
if (hash == dict->hashed_keys[i])
{
return (void*)((char*)dict->values+(dict->size * i));
}
}
return ptr;
}
void dict_set(struct dict *dict, const char *key, const void *value)
{
int hash = dict_hash(key);
char *ptr = dict->values;
int i;
for (i = 0; i < dict->count; ++i)
{
if (hash == dict->hashed_keys[i])
{
ptr = ptr+(dict->size * i);
memcpy((void*)ptr, value, dict->size);
return;
}
}
dict_add(dict, hash, value);
}
void dict_del(struct dict *dict, const char *key)
{
int hash = dict_hash(key);
int offset = -1;
int i;
for (i = 0; i < dict->count; ++i)
{
if (hash == dict->hashed_keys[i])
{
offset = i;
goto delete;
}
}
delete:
if (dict->count == 1) {
free(dict->hashed_keys);
free(dict->values);
} else if (offset == dict->count - 1) {
int *keys = realloc(dict->hashed_keys,
sizeof(int) * (dict->count - 1));
void *values = realloc(dict->values,
dict->size * (dict->count - 1));
if (NULL == keys || NULL == values)
{
puts("Error reallocating dict during delete.");
exit(1);
}
dict->hashed_keys = keys;
dict->values = values;
} else if (offset == 0) {
int *keys = malloc(sizeof(int) * (dict->count - 1));
void *values = malloc(dict->size * (dict->count - 1));
char *ptr;
if (NULL == keys || NULL == values)
{
puts("Error mallocing dict during delete (offset 0).");
exit(1);
}
for (i = 1; i < dict->count; ++i)
keys[i-1] = dict->hashed_keys[i];
ptr = (char*)dict->values+(dict->size);
memcpy(values, (void*)ptr, dict->size * (dict->count-1));
} else {
int *keys = malloc(sizeof(int) * (dict->count - 1));
void *values = malloc(dict->size * (dict->count - 1));
char *dest_ptr;
char *src_ptr;
if (NULL == keys || NULL == values)
{
puts("Error mallocing dict during delete (offset n).");
exit(1);
}
for (i = 0; i < offset; ++i)
keys[i] = dict->hashed_keys[i];
for (i = offset + 1; i < dict->count - 1; ++i)
keys[i] = dict->hashed_keys[i];
memcpy(values, dict->values, dict->size * offset - 1);
dest_ptr = (char*)dict->values+(dict->size * (offset + 1));
src_ptr = (char*)values+(dict->size * (offset + 1));
memcpy((void*)dest_ptr, (void*)src_ptr,
dict->size * (dict->count - offset + 1));
}
dict->count--;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment