-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathhashmap.h
187 lines (169 loc) · 19.4 KB
/
hashmap.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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#ifndef HASHMAP_H
#define HASHMAP_H
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define INITIAL_SIZE 1024
#define RANDOM_MULTIPLIER 0.69
#define defineMap(_key_type, _value_type) \
typedef struct _Element_##_key_type##_value_type { \
_key_type key; \
_value_type value; \
struct _Element_##_key_type##_value_type *_next; \
} Element_##_key_type##_value_type; \
\
typedef struct _Map_##_key_type##_value_type { \
\
Element_##_key_type##_value_type *_data; \
Element_##_key_type##_value_type *_head; \
Element_##_key_type##_value_type *_tail; \
int _entities; \
\
bool (*insert)(struct _Map_##_key_type##_value_type *map, _key_type key, _value_type value); \
bool (*erase)(struct _Map_##_key_type##_value_type *map, _key_type key); \
void (*swap)(struct _Map_##_key_type##_value_type *map, struct _Map_##_key_type##_value_type *nextMap); \
bool (*clear)(struct _Map_##_key_type##_value_type *map); \
\
_value_type* (*find)(struct _Map_##_key_type##_value_type *map, _key_type key); \
int (*count)(struct _Map_##_key_type##_value_type *map); \
\
size_t (*size)(struct _Map_##_key_type##_value_type *map); \
bool (*isEmpty)(struct _Map_##_key_type##_value_type *map); \
\
} Map_##_key_type##_value_type; \
\
uint32_t _map_##_key_type##_value_type##_hash(_key_type key) \
{ \
/*@todo:pointer */ \
/* when having pointer we should know the real size of the array or the exact pointer and so it is not */ \
/* possible at this instance but can be made in further version. */ \
\
size_t keySize = sizeof(key); \
uint32_t hashval = 0; \
for(size_t i = 0; i < keySize; i++){ \
hashval += *( ((uint8_t *) &key)+i ) + (i*RANDOM_MULTIPLIER); \
} \
hashval = hashval % INITIAL_SIZE; \
return hashval; \
} \
\
bool _map_##_key_type##_value_type##_insert(Map_##_key_type##_value_type *map, _key_type key, _value_type value) \
{ \
uint32_t hashval = _map_##_key_type##_value_type##_hash(key); \
\
Element_##_key_type##_value_type* element = (Element_##_key_type##_value_type*) malloc(sizeof(Element_##_key_type##_value_type));\
element->key = key;element->value = value;element->_next = NULL; \
Element_##_key_type##_value_type* itr = &(map->_data[hashval]); \
\
while(itr->_next != NULL){itr = itr->_next;} \
itr->_next = element; \
\
map->_entities++; \
return true; \
} \
\
bool _map_##_key_type##_value_type##_erase(Map_##_key_type##_value_type *map, _key_type key) \
{ \
uint32_t hashval = _map_##_key_type##_value_type##_hash(key); \
\
Element_##_key_type##_value_type* itr = &(map->_data[hashval]); \
Element_##_key_type##_value_type* prev = NULL; \
\
while(itr != NULL){ \
if(itr->key == key){ \
Element_##_key_type##_value_type* tmp = itr; \
if(prev == NULL){ \
map->_data[hashval] = *itr->_next; \
}else{ \
prev->_next = itr->_next; \
} \
free(tmp); \
map->_entities--; \
return true; \
} \
prev = itr; \
itr = itr->_next; \
} \
return false; \
} \
\
void _map_##_key_type##_value_type##_swap(Map_##_key_type##_value_type *map, Map_##_key_type##_value_type *nextMap) \
{ \
Map_##_key_type##_value_type tmp = *map; \
*map = *nextMap; \
*nextMap = tmp; \
} \
\
bool _map_##_key_type##_value_type##_clear(Map_##_key_type##_value_type *map) \
{ \
free(map->_data); \
map->_entities = 0; \
return true; \
} \
\
_value_type* _map_##_key_type##_value_type##_find(Map_##_key_type##_value_type *map, _key_type key) \
{ \
uint32_t hashval = _map_##_key_type##_value_type##_hash(key); \
Element_##_key_type##_value_type* itr = &(map->_data[hashval]); \
while(itr != NULL){ \
if(itr->key == key) return &(itr->value); \
itr = itr->_next; \
} \
return NULL; \
} \
\
int _map_##_key_type##_value_type##_count(Map_##_key_type##_value_type *map) \
{ \
return map->_entities; \
} \
\
size_t _map_##_key_type##_value_type##_size(Map_##_key_type##_value_type *map) \
{ \
return (size_t) sizeof(Element_##_key_type##_value_type)*map->_entities; \
} \
\
bool _map_##_key_type##_value_type##_isEmpty(Map_##_key_type##_value_type *map) \
{ \
return map->_entities==0; \
} \
\
Map_##_key_type##_value_type _map_create_##_key_type##_value_type() \
{ \
Map_##_key_type##_value_type _map; \
_map._entities = 0; \
_map._head = NULL; \
_map._data = (Element_##_key_type##_value_type*) calloc(INITIAL_SIZE, sizeof(Element_##_key_type##_value_type));\
_map.insert = _map_##_key_type##_value_type##_insert; \
_map.erase = _map_##_key_type##_value_type##_erase; \
_map.swap = _map_##_key_type##_value_type##_swap; \
_map.clear = _map_##_key_type##_value_type##_clear; \
_map.find = _map_##_key_type##_value_type##_find; \
_map.count = _map_##_key_type##_value_type##_count; \
_map.size = _map_##_key_type##_value_type##_size; \
_map.isEmpty = _map_##_key_type##_value_type##_isEmpty; \
\
return _map; \
} \
#define Map(_key_type, _value_type) \
Map_##_key_type##_value_type \
#define new_map(_key_type, _value_type) \
_map_create_##_key_type##_value_type() \
#define map_create(_key_type, _value_type) \
_map_create_##_key_type##_value_type() \
#define map_insert(_map, _key, _value) \
_map.insert(&_map, _key, _value) \
#define map_erase(_map, _key) \
_map.erase(&_map, _key) \
#define map_swap(_map, _nextMap) \
_map.swap(&_map, &_nextMap) \
#define map_clear(_map) \
_map.clear(&_map) \
#define map_find(_map, _key) \
_map.find(&_map, _key) \
#define map_count(_map) \
_map.count(&_map) \
#define map_size(_map) \
_map.size(&_map) \
#define map_empty(_map) \
_map.isEmpty(&_map) \
#endif /* HASHMAP_H */