-
Notifications
You must be signed in to change notification settings - Fork 17
/
dict.h
253 lines (222 loc) · 10.1 KB
/
dict.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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
/*
* This file is part of ltrace.
* Copyright (C) 2012, 2013 Petr Machata, Red Hat Inc.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
* published by the Free Software Foundation; either version 2 of the
* License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
* 02110-1301 USA
*/
#ifndef DICT_H
#define DICT_H
#include <stddef.h>
#include <stdint.h>
#include <assert.h>
#include "vect.h"
struct dict {
/* The invariant is that KEYS, VALUES and STATUS are of the
* same size. */
struct vect keys;
struct vect values;
struct vect status;
size_t size;
size_t (*hash1)(const void *);
int (*eq)(const void *, const void *);
size_t (*hash2)(size_t);
};
/* Initialize a dictionary DICT. The dictionary will hold keys of the
* size KEY_SIZE and values of the size VALUE_SIZE. HASH1 and HASH2
* are, respectively, primary and secondary hashing functions. The
* latter may be NULL, in which case a default internal hash is used.
* EQ is a callback for comparing two keys. */
void dict_init(struct dict *dict,
size_t key_size, size_t value_size,
size_t (*hash1)(const void *),
int (*eq)(const void *, const void *),
size_t (*hash2)(size_t));
/* Wrapper around dict_init. Initializes a dictionary DITCP which
* will hold keys of type KEY_TYPE and values of type VALUE_TYPE.
* Other arguments as above. */
#define DICT_INIT(DICTP, KEY_TYPE, VALUE_TYPE, HASH1, EQ, HASH2) \
({ \
/* Check that callbacks are typed properly. */ \
size_t (*_hash1_callback)(const KEY_TYPE *) = HASH1; \
int (*_eq_callback)(const KEY_TYPE *, const KEY_TYPE *) = EQ; \
dict_init(DICTP, sizeof(KEY_TYPE), sizeof(VALUE_TYPE), \
(size_t (*)(const void *))_hash1_callback, \
(int (*)(const void *, const void *))_eq_callback, \
HASH2); \
})
/* Clone SOURCE to TARGET. For cloning slots, CLONE_KEY and
* CLONE_VALUE are called. These callbacks return 0 on success or a
* negative value on failure. If any of the callbacks is NULL, the
* default action is simple memmove. Returns 0 on success. If the
* cloning fails for any reason, already-cloned keys and values are
* destroyed again by DTOR_KEY and DTOR_VALUE callbacks (if non-NULL),
* and the function returns a negative value. DATA is passed to all
* callbacks verbatim. */
int dict_clone(struct dict *target, const struct dict *source,
int (*clone_key)(void *tgt, const void *src, void *data),
void (*dtor_key)(void *tgt, void *data),
int (*clone_value)(void *tgt, const void *src, void *data),
void (*dtor_value)(void *tgt, void *data),
void *data);
/* Clone SRC_DICTP, which holds KEY_TYPE-VALUE_TYPE pairs, into
* TGT_DICTP. Other arguments and return codes as above. */
#define DICT_CLONE(TGT_DICTP, SRC_DICTP, KEY_TYPE, VALUE_TYPE, \
CLONE_KEY, DTOR_KEY, CLONE_VALUE, DTOR_VALUE, DATA) \
/* xxx GCC-ism necessary to get in the safety latches. */ \
({ \
const struct dict *_source_d = (SRC_DICTP); \
assert(_source_d->keys.elt_size == sizeof(KEY_TYPE)); \
assert(_source_d->values.elt_size == sizeof(VALUE_TYPE)); \
/* Check that callbacks are typed properly. */ \
void (*_key_dtor_cb)(KEY_TYPE *, void *) = DTOR_KEY; \
int (*_key_clone_cb)(KEY_TYPE *, const KEY_TYPE *, \
void *) = CLONE_KEY; \
void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
int (*_value_clone_cb)(VALUE_TYPE *, const VALUE_TYPE *, \
void *) = CLONE_VALUE; \
dict_clone((TGT_DICTP), _source_d, \
(int (*)(void *, const void *, \
void *))_key_clone_cb, \
(void (*)(void *, void *))_key_dtor_cb, \
(int (*)(void *, const void *, \
void *))_value_clone_cb, \
(void (*)(void *, void *))_value_dtor_cb, \
(DATA)); \
})
/* Return number of key-value pairs stored in DICT. */
size_t dict_size(const struct dict *dict);
/* Emptiness predicate. */
int dict_empty(const struct dict *dict);
/* Insert into DICT a pair of KEY and VALUE. Returns 0 if insertion
* was successful, a negative value on error, or a positive value if
* this key is already present in the table. */
int dict_insert(struct dict *dict, void *key, void *value);
/* Insert into DICT a pair of KEY and VALUE. See dict_insert for
* details. In addition, make a check whether DICTP holds elements of
* the right size. */
#define DICT_INSERT(DICTP, KEYP, VALUEP) \
(assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
assert((DICTP)->values.elt_size == sizeof(*(VALUEP))), \
dict_insert((DICTP), (KEYP), (VALUEP)))
/* Find in DICT a value corresponding to KEY and return a pointer to
* it. Returns NULL if the key was not found. */
void *dict_find(struct dict *dict, const void *key);
/* Look into DICTP for a key *KEYP. Return a boolean indicating
* whether the key was found. */
#define DICT_HAS_KEY(DICTP, KEYP) \
(assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
dict_find((DICTP), (KEYP)) != NULL)
/* Find in DICTP a value of type VALUE_TYPE corresponding to KEYP and
* return a pointer (VALUE_TYPE *) to it. Returns NULL if the key was
* not found. */
#define DICT_FIND_REF(DICTP, KEYP, VALUE_TYPE) \
(assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
(VALUE_TYPE *)dict_find((DICTP), (KEYP)))
/* Find in DICTP a value of type VALUE_TYPE corresponding to KEYP and
* copy it to the memory pointed-to by VAR. Returns 0 on success, or
* a negative value if the key was not found. */
#define DICT_FIND_VAL(DICTP, KEYP, VAR) \
({ \
assert((DICTP)->keys.elt_size == sizeof(*(KEYP))); \
assert((DICTP)->values.elt_size == sizeof((VAR))); \
void *_ptr = dict_find((DICTP), (KEYP)); \
if (_ptr != NULL) \
memcpy((VAR), _ptr, (DICTP)->values.elt_size); \
_ptr != NULL ? 0 : -1; \
})
/* Erase from DICT the entry corresponding to KEY. Returns a negative
* value if the key was not found, or 0 on success. DTOR_KEY and
* DTOR_VALUE, if non-NULL, are called to destroy the erased
* value. */
int dict_erase(struct dict *dict, const void *key,
void (*dtor_key)(void *tgt, void *data),
void (*dtor_value)(void *tgt, void *data),
void *data);
/* Erase from DICTP a value of type VALUE_TYPE corresponding to
* KEYP. */
#define DICT_ERASE(DICTP, KEYP, VALUE_TYPE, DTOR_KEY, DTOR_VALUE, DATA) \
({ \
struct dict *_d = (DICTP); \
assert(_d->keys.elt_size == sizeof(*KEYP)); \
assert(_d->values.elt_size == sizeof(VALUE_TYPE)); \
/* Check that callbacks are typed properly. */ \
void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
dict_erase(_d, (KEYP), (DTOR_KEY), \
(void (*)(void *, void *))_value_dtor_cb, \
(DATA)); \
})
/* Destroy DICT. If KEY_DTOR is non-NULL, then it's called on each
* key stored in DICT. Similarly for VALUE_DTOR. DATA is passed to
* DTOR's verbatim. The memory pointed-to by DICT is not freed. */
void dict_destroy(struct dict *dict,
void (*dtor_key)(void *tgt, void *data),
void (*dtor_value)(void *tgt, void *data),
void *data);
/* Destroy DICTP, which holds keys of type KEY_TYPE and values of type
* VALUE_TYPE, using DTOR. */
#define DICT_DESTROY(DICTP, KEY_TYPE, VALUE_TYPE, DTOR_KEY, DTOR_VALUE, DATA) \
do { \
struct dict *_d = (DICTP); \
assert(_d->keys.elt_size == sizeof(KEY_TYPE)); \
assert(_d->values.elt_size == sizeof(VALUE_TYPE)); \
/* Check that callbacks are typed properly. */ \
void (*_key_dtor_cb)(KEY_TYPE *, void *) = DTOR_KEY; \
void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
dict_destroy(_d, (void (*)(void *, void *))_key_dtor_cb, \
(void (*)(void *, void *))_value_dtor_cb, \
(DATA)); \
} while (0)
/* Iterate through DICT. See callback.h for notes on iteration
* interfaces. Callback arguments are key, value, DATA. Note that
* the iteration over DICT is more expensive than in other containers:
* while CB is only called for items present in the table, and is
* therefore O(number of elements), the iterator needs to go through
* all the table, which is proportional to O(size of table).
* START_AFTER and the returned iterator are key where the iteration
* stopped. */
void *dict_each(struct dict *dict, void *start_after,
enum callback_status (*cb)(void *, void *, void *), void *data);
#define DICT_EACH(DICTP, KEY_TYPE, VALUE_TYPE, START_AFTER, CB, DATA) \
/* xxx GCC-ism necessary to get in the safety latches. */ \
({ \
assert((DICTP)->keys.elt_size == sizeof(KEY_TYPE)); \
assert((DICTP)->values.elt_size == sizeof(VALUE_TYPE)); \
/* Check that CB is typed properly. */ \
enum callback_status (*_cb)(KEY_TYPE *, VALUE_TYPE *, \
void *) = CB; \
KEY_TYPE *_start_after = (START_AFTER); \
(KEY_TYPE *)dict_each((DICTP), _start_after, \
(enum callback_status \
(*)(void *, void *, void *))_cb, \
(DATA)); \
})
/* A callback for hashing integers. */
size_t dict_hash_int(const int *key);
/* An equality predicate callback for integers. */
int dict_eq_int(const int *key1, const int *key2);
/* A callback for hashing uint64_t. */
size_t dict_hash_uint64(const uint64_t *key);
/* An equality predicate callback for uint64_t. */
int dict_eq_uint64(const uint64_t *key1, const uint64_t *key2);
/* A callback for hashing NULL-terminated strings. */
size_t dict_hash_string(const char **key);
/* An equality predicate callback for strings. */
int dict_eq_string(const char **key1, const char **key2);
/* A dtor which calls 'free' on keys in a table. */
void dict_dtor_string(const char **key, void *data);
/* A cloner that calls 'strdup' on keys in a table. */
int dict_clone_string(const char **tgt, const char **src, void *data);
#endif /* DICT_H */