238 lines
8.3 KiB
C
238 lines
8.3 KiB
C
#ifndef VESSEL_HMAP_H_
|
|
#define VESSEL_HMAP_H_
|
|
|
|
#include "conf.h"
|
|
|
|
#include "def.h"
|
|
#include "thread.h"
|
|
|
|
/* SipHash */
|
|
#ifndef VS_HMAP_SIPHASH_C_ROUNDS
|
|
# define VS_HMAP_SIPHASH_C_ROUNDS 2
|
|
#endif /* VS_HMAP_SIPHASH_C_ROUNDS */
|
|
|
|
#ifndef VS_HMAP_SIPHASH_D_ROUNDS
|
|
# define VS_HMAP_SIPHASH_D_ROUNDS 4
|
|
#endif /* VS_HMAP_SIPHASH_D_ROUNDS */
|
|
/* End SipHash */
|
|
|
|
#define VS_HMAP_INITIAL_CAP 7 /* Initial capacity (should satisfy isprime(4k+3), where p=4k+3) */
|
|
#define VS_HMAP_LOAD_FACTOR 0.85 /* Load factor: size over capacity */
|
|
|
|
#define VS_HMAP_OCCPIED_MULTIPLIER 1.15 /* >1 */
|
|
#define VS_HMAP_MULTIPLIER 1.33 /* >1 */
|
|
#define VS_HMAP_MULTIPLIER_COLLISION 1.1 /* >1 */
|
|
|
|
typedef struct {
|
|
void *key;
|
|
size_t key_length;
|
|
void *value;
|
|
size_t hash;
|
|
size_t id; /* Immutable entry ID (unique ID for each insert) */
|
|
|
|
bool _occupied;
|
|
size_t _occupied_ents_idx; /* Element order in occupied_els, unique but dyanamic (index into
|
|
occupied_els[]) */
|
|
} vs_HMapEntry;
|
|
|
|
typedef struct {
|
|
vs_HMapEntry *entries;
|
|
size_t size;
|
|
|
|
/* TODO: Reduce memory overhead. */
|
|
vs_HMapEntry **occupied_ents; /* Occupied elements so you wouldn't need
|
|
to inefficiently loop over all the occupied
|
|
entries. An array of size `vs_HMap->size` elements.
|
|
Linked list implementation is a lot slower (trust
|
|
I tried) */
|
|
|
|
size_t _cap;
|
|
size_t _occupied_ents_cap;
|
|
uint64_t _siphash64_seed[2]; /* SipHash seeds for the index function */
|
|
bool _is_hset; /* If this hashmap is a hashset (keys only) */
|
|
size_t _id; /* A unique ID for every entry */
|
|
|
|
vs_Lock _lock;
|
|
} vs_HMap;
|
|
|
|
typedef struct {
|
|
size_t _hash;
|
|
size_t _id;
|
|
} vs_HMapID;
|
|
|
|
bool vs_HMapID_is_valid(vs_HMapID hid);
|
|
vs_HMapID vs_HMapID_get(const vs_HMapEntry *entry);
|
|
|
|
#define VS_HMAP_ID_FMTS "%zx%zx"
|
|
#define VS_HMAP_ID_FMT(hid) (hid)._hash, (hid)._id
|
|
|
|
bool vs_HMap_init(vs_HMap *hmap); /* Initialize an vs_HMap */
|
|
bool vs_HMap_init_set(vs_HMap *hmap); /* Initialize an vs_HMap */
|
|
|
|
bool vs_HMap_init_unsafe(vs_HMap *hmap); /* Initialize an vs_HMap (no thread safety) */
|
|
bool vs_HMap_init_set_unsafe(vs_HMap *hmap); /* Initialize an vs_HMap (no thread safety) */
|
|
|
|
size_t vs_HMap_hash(const void *key, size_t key_length, const uint64_t seed[2])
|
|
__attribute__((const));
|
|
#define VS_HMAP_HASH_CAP(cap, ...) (vs_HMap_hash(__VA_ARGS__) & ((cap) - 1))
|
|
|
|
size_t vs_HMap_probe(size_t index, size_t probe, size_t cap)
|
|
__attribute__((pure)); /* Probe a hashmap */
|
|
size_t vs_HMap_probe0(size_t hash, size_t cap) __attribute__((pure));
|
|
|
|
bool vs_HMap_rehash(vs_HMap *hmap, bool force); /* Rehash an vs_HMap if needed
|
|
(respects VS_HMAP_LOAD_FACTOR) or forced */
|
|
|
|
vs_HMapID vs_HMap_insertn(vs_HMap *hmap, const void *key, size_t len, void *value);
|
|
|
|
/* The choice of 0 being an error is to be consistent with other vs_HMap_*
|
|
* functions - you can simply negate it to check for error. */
|
|
vs_HMapID
|
|
vs_HMap_insert(vs_HMap *hmap, const char *key, void *value); /* Insert a value into an vs_HMap
|
|
(returns a special ID, or 0 on error) */
|
|
|
|
#define VS_HMAP_INSERT_KEY(hmap, key) vs_HMap_insert((hmap), (key), NULL)
|
|
|
|
bool vs_HMap_deleten(vs_HMap *hmap, const void *key, size_t len);
|
|
|
|
bool vs_HMap_delete(vs_HMap *hmap, const char *key); /* Delete a value from an vs_HMap */
|
|
|
|
bool vs_HMap_delete_id(vs_HMap *hmap, vs_HMapID hid); /* Delete a value from an vs_HMap */
|
|
|
|
vs_HMapEntry *vs_HMap_findn(vs_HMap *hmap, const void *key, size_t len);
|
|
|
|
vs_HMapEntry *vs_HMap_find(vs_HMap *hmap, const char *key); /* Find the entry associated with the
|
|
key - returns NULL on not found */
|
|
|
|
vs_HMapEntry *vs_HMap_find_id(vs_HMap *hmap, vs_HMapID hid);
|
|
|
|
const vs_HMapEntry *vs_HMap_findn_unsafe(const vs_HMap *hmap, const void *key, size_t len);
|
|
|
|
const vs_HMapEntry *vs_HMap_find_unsafe(const vs_HMap *hmap, const char *key);
|
|
|
|
const vs_HMapEntry *vs_HMap_find_id_unsafe(const vs_HMap *hmap, vs_HMapID hid);
|
|
|
|
vs_HMapEntry *
|
|
vs_HMap_find_val(vs_HMap *hmap, const void *val, size_t *counter); /* Find a entry by value.
|
|
Counter must be initialised with the n-th value to be found
|
|
(or NULL for the first value). Returns NULL on not found. */
|
|
|
|
const vs_HMapEntry *vs_HMap_find_val_unsafe(const vs_HMap *hmap, const void *val, size_t *counter);
|
|
|
|
bool vs_HMap_clear(vs_HMap *hmap); /* Clear all data of an vs_HMap */
|
|
bool vs_HMap_clear_free(
|
|
vs_HMap *hmap); /* Clear all data of an vs_HMap, including freeing the values. */
|
|
|
|
bool vs_HMap_destroy(vs_HMap *hmap); /* Destroy an vs_HMap */
|
|
bool vs_HMap_destroy_free(vs_HMap *hmap); /* Destroy an vs_HMap and free() its values */
|
|
|
|
/* Debugging functions */
|
|
|
|
void vs_HMap_print_as_str(const vs_HMap *hmap); /* Print an vs_HMap assuming values are strings. */
|
|
void vs_HMap_print_as_wstr(
|
|
const vs_HMap *hmap); /* Print an vs_HMap assuming values are wide strings. */
|
|
void vs_HMap_print_as_ptr(const vs_HMap *hmap); /* Print an vs_HMap assuming values are pointers. */
|
|
|
|
#if 0
|
|
/* --------------------------- STACK-BASED HASHMAP --------------------------- */
|
|
|
|
# ifndef VS_SHMAP_CAP
|
|
# define VS_SHMAP_CAP ((size_t)32)
|
|
# endif
|
|
|
|
# ifndef VS_SHMAP_KEY_SIZE
|
|
# define VS_SHMAP_KEY_SIZE ((size_t)32)
|
|
# endif
|
|
|
|
/* SipHash */
|
|
# ifndef VS_SHMAP_SIPHASH_C_ROUNDS
|
|
# define VS_SHMAP_SIPHASH_C_ROUNDS 2
|
|
# endif /* VS_SHMAP_SIPHASH_C_ROUNDS */
|
|
|
|
# ifndef VS_SHMAP_SIPHASH_D_ROUNDS
|
|
# define VS_SHMAP_SIPHASH_D_ROUNDS 4
|
|
# endif /* VS_SHMAP_SIPHASH_D_ROUNDS */
|
|
/* End SipHash */
|
|
|
|
typedef struct vs_SHMapEntry {
|
|
char key[VS_SHMAP_KEY_SIZE + 1];
|
|
uint8_t key_length;
|
|
void *value;
|
|
size_t hash;
|
|
|
|
struct vs_SHMapEntry *prev;
|
|
struct vs_SHMapEntry *next;
|
|
|
|
bool _occupied;
|
|
} vs_SHMapEntry;
|
|
|
|
typedef struct {
|
|
vs_SHMapEntry entries[VS_SHMAP_CAP];
|
|
uint16_t size;
|
|
|
|
struct vs_SHMapEntry *head;
|
|
struct vs_SHMapEntry *tail;
|
|
|
|
bool _is_hset;
|
|
uint64_t _siphash64_seed[2];
|
|
Lock _lock;
|
|
} vs_SHMap;
|
|
|
|
typedef struct {
|
|
size_t _idx;
|
|
size_t _hash;
|
|
bool _error;
|
|
} vs_SHMapID;
|
|
|
|
# define VS_SHMAP_ID_FMTS "%p%zx"
|
|
# define VS_SHMAP_ID_FMT(hid) (hid)._ptr, (hid)._hash
|
|
|
|
bool vs_SHMapID_is_valid(vs_SHMapID hid);
|
|
/* vs_SHMapID vs_SHMapID_get(const vs_SHMapEntry *entry); */
|
|
|
|
bool vs_SHMap_init(vs_SHMap *shmap);
|
|
bool vs_SHMap_init_set(vs_SHMap *shmap);
|
|
|
|
bool vs_SHMap_init_unsafe(vs_SHMap *shmap);
|
|
bool vs_SHMap_init_set_unsafe(vs_SHMap *shmap);
|
|
|
|
size_t vs_SHMap_hash(const char *key, size_t key_length, const uint64_t seed[2])
|
|
__attribute__((const));
|
|
# define VS_SHMAP_HASH_CAP(cap, ...) (vs_SHMap_hash(__VA_ARGS__) & ((cap) - 1))
|
|
|
|
size_t vs_SHMap_probe(size_t index, size_t probe) __attribute__((const));
|
|
|
|
vs_SHMapID vs_SHMap_insertn(vs_SHMap *shmap, const char *key, uint8_t len, void *value);
|
|
vs_SHMapID vs_SHMap_insert(vs_SHMap *shmap, const char *key, void *value);
|
|
|
|
# define VS_SHMAP_INSERT_KEY(SHMap, key) vs_SHMap_insert((SHMap), (key), NULL)
|
|
|
|
bool vs_SHMap_deleten(vs_SHMap *shmap, const char *key, size_t len);
|
|
bool vs_SHMap_delete(vs_SHMap *shmap, const char *key);
|
|
bool vs_SHMap_delete_id(vs_SHMap *shmap, vs_SHMapID hid);
|
|
|
|
vs_SHMapEntry *vs_SHMap_findn(vs_SHMap *shmap, const char *key, size_t len);
|
|
vs_SHMapEntry *vs_SHMap_find(vs_SHMap *shmap, const char *key);
|
|
vs_SHMapEntry *vs_SHMap_find_id(vs_SHMap *shmap, vs_SHMapID hid);
|
|
|
|
const vs_SHMapEntry *vs_SHMap_findn_unsafe(const vs_SHMap *shmap, const char *key, size_t len);
|
|
const vs_SHMapEntry *vs_SHMap_find_unsafe(const vs_SHMap *shmap, const char *key);
|
|
const vs_SHMapEntry *vs_SHMap_find_id_unsafe(const vs_SHMap *shmap, vs_SHMapID hid);
|
|
|
|
vs_SHMapEntry *vs_SHMap_find_val(vs_SHMap *shmap, const void *val, size_t *counter);
|
|
|
|
const vs_SHMapEntry *
|
|
vs_SHMap_find_val_unsafe(const vs_SHMap *shmap, const void *val, size_t *counter);
|
|
|
|
bool vs_SHMap_clear(vs_SHMap *shmap);
|
|
bool vs_SHMap_clear_free(vs_SHMap *shmap);
|
|
|
|
bool vs_SHMap_destroy(vs_SHMap *shmap);
|
|
bool vs_SHMap_destroy_free(vs_SHMap *shmap);
|
|
|
|
void vs_SHMap_print_as_str(const vs_SHMap *shmap);
|
|
void vs_SHMap_print_as_wstr(const vs_SHMap *shmap);
|
|
void vs_SHMap_print_as_ptr(const vs_SHMap *shmap);
|
|
#endif
|
|
|
|
#endif /* VESSEL_HMAP_H_ */
|