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
29 /* The invariant is that KEYS, VALUES and STATUS are of the
36 size_t (*hash1)(const void *);
37 int (*eq)(const void *, const void *);
38 size_t (*hash2)(size_t);
41 /* Initialize a dictionary DICT. The dictionary will hold keys of the
42 * size KEY_SIZE and values of the size VALUE_SIZE. HASH1 and HASH2
43 * are, respectively, primary and secondary hashing functions. The
44 * latter may be NULL, in which case a default internal hash is used.
45 * EQ is a callback for comparing two keys. */
46 void dict_init(struct dict *dict,
47 size_t key_size, size_t value_size,
48 size_t (*hash1)(const void *),
49 int (*eq)(const void *, const void *),
50 size_t (*hash2)(size_t));
52 /* Wrapper around dict_init. Initializes a dictionary DITCP which
53 * will hold keys of type KEY_TYPE and values of type VALUE_TYPE.
54 * Other arguments as above. */
55 #define DICT_INIT(DICTP, KEY_TYPE, VALUE_TYPE, HASH1, EQ, HASH2) \
57 /* Check that callbacks are typed properly. */ \
58 size_t (*_hash1_callback)(const KEY_TYPE *) = HASH1; \
59 int (*_eq_callback)(const KEY_TYPE *, const KEY_TYPE *) = EQ; \
60 dict_init(DICTP, sizeof(KEY_TYPE), sizeof(VALUE_TYPE), \
61 (size_t (*)(const void *))_hash1_callback, \
62 (int (*)(const void *, const void *))_eq_callback, \
66 /* Clone SOURCE to TARGET. For cloning slots, CLONE_KEY and
67 * CLONE_VALUE are called. These callbacks return 0 on success or a
68 * negative value on failure. If any of the callbacks is NULL, the
69 * default action is simple memmove. Returns 0 on success. If the
70 * cloning fails for any reason, already-cloned keys and values are
71 * destroyed again by DTOR_KEY and DTOR_VALUE callbacks (if non-NULL),
72 * and the function returns a negative value. DATA is passed to all
73 * callbacks verbatim. */
74 int dict_clone(struct dict *target, const struct dict *source,
75 int (*clone_key)(void *tgt, const void *src, void *data),
76 void (*dtor_key)(void *tgt, void *data),
77 int (*clone_value)(void *tgt, const void *src, void *data),
78 void (*dtor_value)(void *tgt, void *data),
81 /* Clone SRC_DICTP, which holds KEY_TYPE-VALUE_TYPE pairs, into
82 * TGT_DICTP. Other arguments and return codes as above. */
83 #define DICT_CLONE(TGT_DICTP, SRC_DICTP, KEY_TYPE, VALUE_TYPE, \
84 CLONE_KEY, DTOR_KEY, CLONE_VALUE, DTOR_VALUE, DATA) \
85 /* xxx GCC-ism necessary to get in the safety latches. */ \
87 const struct dict *_source_d = (SRC_DICTP); \
88 assert(_source_d->keys.elt_size == sizeof(KEY_TYPE)); \
89 assert(_source_d->values.elt_size == sizeof(VALUE_TYPE)); \
90 /* Check that callbacks are typed properly. */ \
91 void (*_key_dtor_cb)(KEY_TYPE *, void *) = DTOR_KEY; \
92 int (*_key_clone_cb)(KEY_TYPE *, const KEY_TYPE *, \
93 void *) = CLONE_KEY; \
94 void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
95 int (*_value_clone_cb)(VALUE_TYPE *, const VALUE_TYPE *, \
96 void *) = CLONE_VALUE; \
97 dict_clone((TGT_DICTP), _source_d, \
98 (int (*)(void *, const void *, \
99 void *))_key_clone_cb, \
100 (void (*)(void *, void *))_key_dtor_cb, \
101 (int (*)(void *, const void *, \
102 void *))_value_clone_cb, \
103 (void (*)(void *, void *))_value_dtor_cb, \
107 /* Return number of key-value pairs stored in DICT. */
108 size_t dict_size(const struct dict *dict);
110 /* Emptiness predicate. */
111 int dict_empty(const struct dict *dict);
113 /* Insert into DICT a pair of KEY and VALUE. Returns 0 if insertion
114 * was successful, a negative value on error, or a positive value if
115 * this key is already present in the table. */
116 int dict_insert(struct dict *dict, void *key, void *value);
118 /* Insert into DICT a pair of KEY and VALUE. See dict_insert for
119 * details. In addition, make a check whether DICTP holds elements of
121 #define DICT_INSERT(DICTP, KEYP, VALUEP) \
122 (assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
123 assert((DICTP)->values.elt_size == sizeof(*(VALUEP))), \
124 dict_insert((DICTP), (KEYP), (VALUEP)))
126 /* Find in DICT a value corresponding to KEY and return a pointer to
127 * it. Returns NULL if the key was not found. */
128 void *dict_find(struct dict *dict, const void *key);
130 /* Look into DICTP for a key *KEYP. Return a boolean indicating
131 * whether the key was found. */
132 #define DICT_HAS_KEY(DICTP, KEYP) \
133 (assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
134 dict_find((DICTP), (KEYP)) != NULL)
136 /* Find in DICTP a value of type VALUE_TYPE corresponding to KEYP and
137 * return a pointer (VALUE_TYPE *) to it. Returns NULL if the key was
139 #define DICT_FIND_REF(DICTP, KEYP, VALUE_TYPE) \
140 (assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
141 (VALUE_TYPE *)dict_find((DICTP), (KEYP)))
143 /* Find in DICTP a value of type VALUE_TYPE corresponding to KEYP and
144 * copy it to the memory pointed-to by VAR. Returns 0 on success, or
145 * a negative value if the key was not found. */
146 #define DICT_FIND_VAL(DICTP, KEYP, VAR) \
148 assert((DICTP)->keys.elt_size == sizeof(*(KEYP))); \
149 assert((DICTP)->values.elt_size == sizeof((VAR))); \
150 void *_ptr = dict_find((DICTP), (KEYP)); \
152 memcpy((VAR), _ptr, (DICTP)->values.elt_size); \
153 _ptr != NULL ? 0 : -1; \
156 /* Erase from DICT the entry corresponding to KEY. Returns a negative
157 * value if the key was not found, or 0 on success. DTOR_KEY and
158 * DTOR_VALUE, if non-NULL, are called to destroy the erased
160 int dict_erase(struct dict *dict, const void *key,
161 void (*dtor_key)(void *tgt, void *data),
162 void (*dtor_value)(void *tgt, void *data),
165 /* Erase from DICTP a value of type VALUE_TYPE corresponding to
167 #define DICT_ERASE(DICTP, KEYP, VALUE_TYPE, DTOR_KEY, DTOR_VALUE, DATA) \
169 struct dict *_d = (DICTP); \
170 assert(_d->keys.elt_size == sizeof(*KEYP)); \
171 assert(_d->values.elt_size == sizeof(VALUE_TYPE)); \
172 /* Check that callbacks are typed properly. */ \
173 void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
174 dict_erase(_d, (KEYP), (DTOR_KEY), \
175 (void (*)(void *, void *))_value_dtor_cb, \
179 /* Destroy DICT. If KEY_DTOR is non-NULL, then it's called on each
180 * key stored in DICT. Similarly for VALUE_DTOR. DATA is passed to
181 * DTOR's verbatim. The memory pointed-to by DICT is not freed. */
182 void dict_destroy(struct dict *dict,
183 void (*dtor_key)(void *tgt, void *data),
184 void (*dtor_value)(void *tgt, void *data),
187 /* Destroy DICTP, which holds keys of type KEY_TYPE and values of type
188 * VALUE_TYPE, using DTOR. */
189 #define DICT_DESTROY(DICTP, KEY_TYPE, VALUE_TYPE, DTOR_KEY, DTOR_VALUE, DATA) \
191 struct dict *_d = (DICTP); \
192 assert(_d->keys.elt_size == sizeof(KEY_TYPE)); \
193 assert(_d->values.elt_size == sizeof(VALUE_TYPE)); \
194 /* Check that callbacks are typed properly. */ \
195 void (*_key_dtor_cb)(KEY_TYPE *, void *) = DTOR_KEY; \
196 void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
197 dict_destroy(_d, (void (*)(void *, void *))_key_dtor_cb, \
198 (void (*)(void *, void *))_value_dtor_cb, \
202 /* Iterate through DICT. See callback.h for notes on iteration
203 * interfaces. Callback arguments are key, value, DATA. Note that
204 * the iteration over DICT is more expensive than in other containers:
205 * while CB is only called for items present in the table, and is
206 * therefore O(number of elements), the iterator needs to go through
207 * all the table, which is proportional to O(size of table).
208 * START_AFTER and the returned iterator are key where the iteration
210 void *dict_each(struct dict *dict, void *start_after,
211 enum callback_status (*cb)(void *, void *, void *), void *data);
213 #define DICT_EACH(DICTP, KEY_TYPE, VALUE_TYPE, START_AFTER, CB, DATA) \
214 /* xxx GCC-ism necessary to get in the safety latches. */ \
216 assert((DICTP)->keys.elt_size == sizeof(KEY_TYPE)); \
217 assert((DICTP)->values.elt_size == sizeof(VALUE_TYPE)); \
218 /* Check that CB is typed properly. */ \
219 enum callback_status (*_cb)(KEY_TYPE *, VALUE_TYPE *, \
221 KEY_TYPE *_start_after = (START_AFTER); \
222 (KEY_TYPE *)dict_each((DICTP), _start_after, \
223 (enum callback_status \
224 (*)(void *, void *, void *))_cb, \
228 /* A callback for hashing integers. */
229 size_t dict_hash_int(const int *key);
231 /* An equality predicate callback for integers. */
232 int dict_eq_int(const int *key1, const int *key2);
234 /* A callback for hashing NULL-terminated strings. */
235 size_t dict_hash_string(const char **key);
237 /* An equality predicate callback for strings. */
238 int dict_eq_string(const char **key1, const char **key2);
240 /* A dtor which calls 'free' on keys in a table. */
241 void dict_dtor_string(const char **key, void *data);
243 /* A cloner that calls 'strdup' on keys in a table. */
244 int dict_clone_string(const char **tgt, const char **src, void *data);
246 #endif /* _DICT_H_ */