#ifndef HASHSET_H
#define HASHSET_H
#include <string.h>
#include <stdlib.h>
#include <assert.h>
struct hash_entry {
const char *key;
struct hash_entry *next;
};
typedef struct hashset {
int size, num_entries;
struct hash_entry *first;
struct hash_entry **table;
} hashset;
static inline unsigned long hash_function(const char *strinput) {
unsigned long hash = 5381;
const unsigned char *str = (const unsigned char *)strinput;
int c;
while ((c = *str++)) hash = hash * 33 ^ c;
return hash;
}
static struct hash_entry * lookup_in_hash(hashset *hash, const char *str) {
if (!str) return NULL;
unsigned long h = hash_function(str) % hash->size;
struct hash_entry *e = hash->table[h];
while (e) {
if (strcmp(e->key, str) == 0) return e;
if (!e->next || hash_function(e->next->key) % hash->size != h) return NULL;
e = e->next;
}
return NULL;
}
static inline void insert_hashset(hashset *hash, const char *key) {
if (!key) return;
if (lookup_in_hash(hash, key)) return;
struct hash_entry *e = malloc(sizeof(struct hash_entry)+strlen(key)+1);
e->key = ((char *)e) + sizeof(struct hash_entry);
strcpy((char *)e->key, key);
e->next = NULL;
hash->num_entries++;
unsigned long h = hash_function(e->key) % hash->size;
struct hash_entry *enext = hash->table[h];
if (enext) {
e->next = enext->next;
enext->next = e;
} else {
e->next = hash->first;
hash->first = e;
hash->table[h] = e;
}
}
static inline void delete_from_hashset(hashset *hash, const char *key) {
if (!key) return;
struct hash_entry *e = lookup_in_hash(hash, key);
if (e) {
struct hash_entry *x = hash->first;
if (x == e) {
hash->first = e->next;
} else {
while (x) {
if (x->next == e) {
x->next = e->next;
}
x = x->next;
}
}
unsigned long h = hash_function(e->key) % hash->size;
if (hash->table[h] == e) {
if (e->next && hash_function(e->next->key) % hash->size == h) {
hash->table[h] = e->next;
} else {
hash->table[h] = NULL;
}
}
hash->num_entries -= 1;
free(e);
}
}
static inline char **hashset_to_array(hashset *hs) {
int numentries = 0;
long total_size = 0;
for (struct hash_entry *e = (struct hash_entry *)hs->first;
e; e = (struct hash_entry *)e->next) {
numentries++;
total_size += strlen(e->key) + 1;
}
char **array = malloc((numentries + 1)*sizeof(char *) + total_size);
char *strings = (char *)(array + numentries + 1);
int i = 0;
for (struct hash_entry *e = (struct hash_entry *)hs->first;
e; e = (struct hash_entry *)e->next) {
array[i] = strings;
const char *from = e->key;
while (*from) {
*strings++ = *from++; }
*strings++ = 0; i++;
}
array[numentries] = NULL; return array;
}
static inline void free_hashset(hashset *h) {
free(h->table);
struct hash_entry *todelete = NULL;
for (struct hash_entry *e = h->first; e; e = e->next) {
free(todelete);
todelete = e;
}
free(todelete);
}
static inline void init_hashset(hashset *h, int size) {
h->size = size;
h->num_entries = 0;
h->first = NULL;
h->table = calloc(sizeof(struct hash_entry *), size);
}
#endif