2 * This file is part of ltrace.
3 * Copyright (C) 2012, 2013 Petr Machata, Red Hat Inc.
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation; either version 2 of the
8 * License, or (at your option) any later version.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
30 /* The invariant is that KEYS, VALUES and STATUS are of the
37 size_t (*hash1)(const void *);
38 int (*eq)(const void *, const void *);
39 size_t (*hash2)(size_t);
42 /* Initialize a dictionary DICT. The dictionary will hold keys of the
43 * size KEY_SIZE and values of the size VALUE_SIZE. HASH1 and HASH2
44 * are, respectively, primary and secondary hashing functions. The
45 * latter may be NULL, in which case a default internal hash is used.
46 * EQ is a callback for comparing two keys. */
47 void dict_init(struct dict *dict,
48 size_t key_size, size_t value_size,
49 size_t (*hash1)(const void *),
50 int (*eq)(const void *, const void *),
51 size_t (*hash2)(size_t));
53 /* Wrapper around dict_init. Initializes a dictionary DITCP which
54 * will hold keys of type KEY_TYPE and values of type VALUE_TYPE.
55 * Other arguments as above. */
56 #define DICT_INIT(DICTP, KEY_TYPE, VALUE_TYPE, HASH1, EQ, HASH2) \
58 /* Check that callbacks are typed properly. */ \
59 size_t (*_hash1_callback)(const KEY_TYPE *) = HASH1; \
60 int (*_eq_callback)(const KEY_TYPE *, const KEY_TYPE *) = EQ; \
61 dict_init(DICTP, sizeof(KEY_TYPE), sizeof(VALUE_TYPE), \
62 (size_t (*)(const void *))_hash1_callback, \
63 (int (*)(const void *, const void *))_eq_callback, \
67 /* Clone SOURCE to TARGET. For cloning slots, CLONE_KEY and
68 * CLONE_VALUE are called. These callbacks return 0 on success or a
69 * negative value on failure. If any of the callbacks is NULL, the
70 * default action is simple memmove. Returns 0 on success. If the
71 * cloning fails for any reason, already-cloned keys and values are
72 * destroyed again by DTOR_KEY and DTOR_VALUE callbacks (if non-NULL),
73 * and the function returns a negative value. DATA is passed to all
74 * callbacks verbatim. */
75 int dict_clone(struct dict *target, const struct dict *source,
76 int (*clone_key)(void *tgt, const void *src, void *data),
77 void (*dtor_key)(void *tgt, void *data),
78 int (*clone_value)(void *tgt, const void *src, void *data),
79 void (*dtor_value)(void *tgt, void *data),
82 /* Clone SRC_DICTP, which holds KEY_TYPE-VALUE_TYPE pairs, into
83 * TGT_DICTP. Other arguments and return codes as above. */
84 #define DICT_CLONE(TGT_DICTP, SRC_DICTP, KEY_TYPE, VALUE_TYPE, \
85 CLONE_KEY, DTOR_KEY, CLONE_VALUE, DTOR_VALUE, DATA) \
86 /* xxx GCC-ism necessary to get in the safety latches. */ \
88 const struct dict *_source_d = (SRC_DICTP); \
89 assert(_source_d->keys.elt_size == sizeof(KEY_TYPE)); \
90 assert(_source_d->values.elt_size == sizeof(VALUE_TYPE)); \
91 /* Check that callbacks are typed properly. */ \
92 void (*_key_dtor_cb)(KEY_TYPE *, void *) = DTOR_KEY; \
93 int (*_key_clone_cb)(KEY_TYPE *, const KEY_TYPE *, \
94 void *) = CLONE_KEY; \
95 void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
96 int (*_value_clone_cb)(VALUE_TYPE *, const VALUE_TYPE *, \
97 void *) = CLONE_VALUE; \
98 dict_clone((TGT_DICTP), _source_d, \
99 (int (*)(void *, const void *, \
100 void *))_key_clone_cb, \
101 (void (*)(void *, void *))_key_dtor_cb, \
102 (int (*)(void *, const void *, \
103 void *))_value_clone_cb, \
104 (void (*)(void *, void *))_value_dtor_cb, \
108 /* Return number of key-value pairs stored in DICT. */
109 size_t dict_size(const struct dict *dict);
111 /* Emptiness predicate. */
112 int dict_empty(const struct dict *dict);
114 /* Insert into DICT a pair of KEY and VALUE. Returns 0 if insertion
115 * was successful, a negative value on error, or a positive value if
116 * this key is already present in the table. */
117 int dict_insert(struct dict *dict, void *key, void *value);
119 /* Insert into DICT a pair of KEY and VALUE. See dict_insert for
120 * details. In addition, make a check whether DICTP holds elements of
122 #define DICT_INSERT(DICTP, KEYP, VALUEP) \
123 (assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
124 assert((DICTP)->values.elt_size == sizeof(*(VALUEP))), \
125 dict_insert((DICTP), (KEYP), (VALUEP)))
127 /* Find in DICT a value corresponding to KEY and return a pointer to
128 * it. Returns NULL if the key was not found. */
129 void *dict_find(struct dict *dict, const void *key);
131 /* Look into DICTP for a key *KEYP. Return a boolean indicating
132 * whether the key was found. */
133 #define DICT_HAS_KEY(DICTP, KEYP) \
134 (assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
135 dict_find((DICTP), (KEYP)) != NULL)
137 /* Find in DICTP a value of type VALUE_TYPE corresponding to KEYP and
138 * return a pointer (VALUE_TYPE *) to it. Returns NULL if the key was
140 #define DICT_FIND_REF(DICTP, KEYP, VALUE_TYPE) \
141 (assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
142 (VALUE_TYPE *)dict_find((DICTP), (KEYP)))
144 /* Find in DICTP a value of type VALUE_TYPE corresponding to KEYP and
145 * copy it to the memory pointed-to by VAR. Returns 0 on success, or
146 * a negative value if the key was not found. */
147 #define DICT_FIND_VAL(DICTP, KEYP, VAR) \
149 assert((DICTP)->keys.elt_size == sizeof(*(KEYP))); \
150 assert((DICTP)->values.elt_size == sizeof((VAR))); \
151 void *_ptr = dict_find((DICTP), (KEYP)); \
153 memcpy((VAR), _ptr, (DICTP)->values.elt_size); \
154 _ptr != NULL ? 0 : -1; \
157 /* Erase from DICT the entry corresponding to KEY. Returns a negative
158 * value if the key was not found, or 0 on success. DTOR_KEY and
159 * DTOR_VALUE, if non-NULL, are called to destroy the erased
161 int dict_erase(struct dict *dict, const void *key,
162 void (*dtor_key)(void *tgt, void *data),
163 void (*dtor_value)(void *tgt, void *data),
166 /* Erase from DICTP a value of type VALUE_TYPE corresponding to
168 #define DICT_ERASE(DICTP, KEYP, VALUE_TYPE, DTOR_KEY, DTOR_VALUE, DATA) \
170 struct dict *_d = (DICTP); \
171 assert(_d->keys.elt_size == sizeof(*KEYP)); \
172 assert(_d->values.elt_size == sizeof(VALUE_TYPE)); \
173 /* Check that callbacks are typed properly. */ \
174 void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
175 dict_erase(_d, (KEYP), (DTOR_KEY), \
176 (void (*)(void *, void *))_value_dtor_cb, \
180 /* Destroy DICT. If KEY_DTOR is non-NULL, then it's called on each
181 * key stored in DICT. Similarly for VALUE_DTOR. DATA is passed to
182 * DTOR's verbatim. The memory pointed-to by DICT is not freed. */
183 void dict_destroy(struct dict *dict,
184 void (*dtor_key)(void *tgt, void *data),
185 void (*dtor_value)(void *tgt, void *data),
188 /* Destroy DICTP, which holds keys of type KEY_TYPE and values of type
189 * VALUE_TYPE, using DTOR. */
190 #define DICT_DESTROY(DICTP, KEY_TYPE, VALUE_TYPE, DTOR_KEY, DTOR_VALUE, DATA) \
192 struct dict *_d = (DICTP); \
193 assert(_d->keys.elt_size == sizeof(KEY_TYPE)); \
194 assert(_d->values.elt_size == sizeof(VALUE_TYPE)); \
195 /* Check that callbacks are typed properly. */ \
196 void (*_key_dtor_cb)(KEY_TYPE *, void *) = DTOR_KEY; \
197 void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
198 dict_destroy(_d, (void (*)(void *, void *))_key_dtor_cb, \
199 (void (*)(void *, void *))_value_dtor_cb, \
203 /* Iterate through DICT. See callback.h for notes on iteration
204 * interfaces. Callback arguments are key, value, DATA. Note that
205 * the iteration over DICT is more expensive than in other containers:
206 * while CB is only called for items present in the table, and is
207 * therefore O(number of elements), the iterator needs to go through
208 * all the table, which is proportional to O(size of table).
209 * START_AFTER and the returned iterator are key where the iteration
211 void *dict_each(struct dict *dict, void *start_after,
212 enum callback_status (*cb)(void *, void *, void *), void *data);
214 #define DICT_EACH(DICTP, KEY_TYPE, VALUE_TYPE, START_AFTER, CB, DATA) \
215 /* xxx GCC-ism necessary to get in the safety latches. */ \
217 assert((DICTP)->keys.elt_size == sizeof(KEY_TYPE)); \
218 assert((DICTP)->values.elt_size == sizeof(VALUE_TYPE)); \
219 /* Check that CB is typed properly. */ \
220 enum callback_status (*_cb)(KEY_TYPE *, VALUE_TYPE *, \
222 KEY_TYPE *_start_after = (START_AFTER); \
223 (KEY_TYPE *)dict_each((DICTP), _start_after, \
224 (enum callback_status \
225 (*)(void *, void *, void *))_cb, \
229 /* A callback for hashing integers. */
230 size_t dict_hash_int(const int *key);
232 /* An equality predicate callback for integers. */
233 int dict_eq_int(const int *key1, const int *key2);
235 /* A callback for hashing uint64_t. */
236 size_t dict_hash_uint64(const uint64_t *key);
238 /* An equality predicate callback for uint64_t. */
239 int dict_eq_uint64(const uint64_t *key1, const uint64_t *key2);
241 /* A callback for hashing NULL-terminated strings. */
242 size_t dict_hash_string(const char **key);
244 /* An equality predicate callback for strings. */
245 int dict_eq_string(const char **key1, const char **key2);
247 /* A dtor which calls 'free' on keys in a table. */
248 void dict_dtor_string(const char **key, void *data);
250 /* A cloner that calls 'strdup' on keys in a table. */
251 int dict_clone_string(const char **tgt, const char **src, void *data);