forked from OpenIPC/ipctool
-
Notifications
You must be signed in to change notification settings - Fork 0
/
hashtable.h
116 lines (81 loc) · 3.08 KB
/
hashtable.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <stdbool.h>
#include <stddef.h>
/****************** DEFINTIIONS ******************/
#define HT_MINIMUM_CAPACITY 8
#define HT_LOAD_FACTOR 5
#define HT_MINIMUM_THRESHOLD (HT_MINIMUM_CAPACITY) * (HT_LOAD_FACTOR)
#define HT_GROWTH_FACTOR 2
#define HT_SHRINK_THRESHOLD (1 / 4)
#define HT_ERROR -1
#define HT_SUCCESS 0
#define HT_UPDATED 1
#define HT_INSERTED 0
#define HT_NOT_FOUND 0
#define HT_FOUND 01
#define HT_INITIALIZER {0, 0, 0, 0, 0, NULL, NULL, NULL};
typedef int (*comparison_t)(const void *, const void *, size_t);
typedef size_t (*hash_t)(const void *, size_t);
/****************** STRUCTURES ******************/
typedef struct HTNode {
struct HTNode *next;
void *key;
void *value;
} HTNode;
typedef struct HashTable {
size_t size;
size_t threshold;
size_t capacity;
size_t key_size;
size_t value_size;
comparison_t compare;
hash_t hash;
HTNode **nodes;
} HashTable;
/****************** INTERFACE ******************/
/* Setup */
int ht_setup(
HashTable *table, size_t key_size, size_t value_size, size_t capacity);
int ht_copy(HashTable *first, HashTable *second);
int ht_move(HashTable *first, HashTable *second);
int ht_swap(HashTable *first, HashTable *second);
/* Destructor */
int ht_destroy(HashTable *table);
int ht_insert(HashTable *table, const void *key, void *value);
int ht_contains(HashTable *table, const void *key);
void *ht_lookup(HashTable *table, const void *key);
const void *ht_const_lookup(const HashTable *table, void *key);
#define HT_LOOKUP_AS(type, table_pointer, key_pointer) \
(*(type *)ht_lookup((table_pointer), (key_pointer)))
int ht_erase(HashTable *table, void *key);
int ht_clear(HashTable *table);
int ht_is_empty(HashTable *table);
bool ht_is_initialized(HashTable *table);
int ht_reserve(HashTable *table, size_t minimum_capacity);
void ht_iterate(
HashTable *ht, void *user,
void (*callback)(void *key, void *value, void *user));
void ht_iterate_n_erase(
HashTable *ht, void *user,
bool (*callback)(void *key, void *value, void *user));
/****************** PRIVATE ******************/
void _ht_int_swap(size_t *first, size_t *second);
void _ht_pointer_swap(void **first, void **second);
size_t _ht_default_hash(const void *key, size_t key_size);
int _ht_default_compare(
const void *first_key, const void *second_key, size_t key_size);
size_t _ht_hash(const HashTable *table, const void *key);
bool _ht_equal(const HashTable *table, const void *first_key, void *second_key);
bool _ht_should_grow(HashTable *table);
bool _ht_should_shrink(HashTable *table);
HTNode *
_ht_create_node(HashTable *table, const void *key, void *value, HTNode *next);
int _ht_push_front(
HashTable *table, size_t index, const void *key, void *value);
void _ht_destroy_node(HTNode *node);
int _ht_adjust_capacity(HashTable *table);
int _ht_allocate(HashTable *table, size_t capacity);
int _ht_resize(HashTable *table, size_t new_capacity);
void _ht_rehash(HashTable *table, HTNode **old, size_t old_capacity);
#endif /* HASHTABLE_H */