1 /* 2 * This file is part of ltrace. 3 * Copyright (C) 2012, 2013 Petr Machata, Red Hat Inc. 4 * 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. 9 * 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. 14 * 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 18 * 02110-1301 USA 19 */ 20 21 #ifndef _DICT_H_ 22 #define _DICT_H_ 23 24 #include <stddef.h> 25 #include <assert.h> 26 #include "vect.h" 27 28 struct dict { 29 /* The invariant is that KEYS, VALUES and STATUS are of the 30 * same size. */ 31 struct vect keys; 32 struct vect values; 33 struct vect status; 34 size_t size; 35 36 size_t (*hash1)(const void *); 37 int (*eq)(const void *, const void *); 38 size_t (*hash2)(size_t); 39 }; 40 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)); 51 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) \ 56 ({ \ 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, \ 63 HASH2); \ 64 }) 65 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), 79 void *data); 80 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. */ \ 86 ({ \ 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, \ 104 (DATA)); \ 105 }) 106 107 /* Return number of key-value pairs stored in DICT. */ 108 size_t dict_size(const struct dict *dict); 109 110 /* Emptiness predicate. */ 111 int dict_empty(const struct dict *dict); 112 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); 117 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 120 * the right size. */ 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))) 125 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); 129 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) 135 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 138 * not found. */ 139 #define DICT_FIND_REF(DICTP, KEYP, VALUE_TYPE) \ 140 (assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \ 141 (VALUE_TYPE *)dict_find((DICTP), (KEYP))) 142 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) \ 147 ({ \ 148 assert((DICTP)->keys.elt_size == sizeof(*(KEYP))); \ 149 assert((DICTP)->values.elt_size == sizeof((VAR))); \ 150 void *_ptr = dict_find((DICTP), (KEYP)); \ 151 if (_ptr != NULL) \ 152 memcpy((VAR), _ptr, (DICTP)->values.elt_size); \ 153 _ptr != NULL ? 0 : -1; \ 154 }) 155 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 159 * value. */ 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), 163 void *data); 164 165 /* Erase from DICTP a value of type VALUE_TYPE corresponding to 166 * KEYP. */ 167 #define DICT_ERASE(DICTP, KEYP, VALUE_TYPE, DTOR_KEY, DTOR_VALUE, DATA) \ 168 ({ \ 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, \ 176 (DATA)); \ 177 }) 178 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), 185 void *data); 186 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) \ 190 do { \ 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, \ 199 (DATA)); \ 200 } while (0) 201 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 209 * stopped. */ 210 void *dict_each(struct dict *dict, void *start_after, 211 enum callback_status (*cb)(void *, void *, void *), void *data); 212 213 #define DICT_EACH(DICTP, KEY_TYPE, VALUE_TYPE, START_AFTER, CB, DATA) \ 214 /* xxx GCC-ism necessary to get in the safety latches. */ \ 215 ({ \ 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 *, \ 220 void *) = CB; \ 221 KEY_TYPE *_start_after = (START_AFTER); \ 222 (KEY_TYPE *)dict_each((DICTP), _start_after, \ 223 (enum callback_status \ 224 (*)(void *, void *, void *))_cb, \ 225 (DATA)); \ 226 }) 227 228 /* A callback for hashing integers. */ 229 size_t dict_hash_int(const int *key); 230 231 /* An equality predicate callback for integers. */ 232 int dict_eq_int(const int *key1, const int *key2); 233 234 /* A callback for hashing NULL-terminated strings. */ 235 size_t dict_hash_string(const char **key); 236 237 /* An equality predicate callback for strings. */ 238 int dict_eq_string(const char **key1, const char **key2); 239 240 /* A dtor which calls 'free' on keys in a table. */ 241 void dict_dtor_string(const char **key, void *data); 242 243 /* A cloner that calls 'strdup' on keys in a table. */ 244 int dict_clone_string(const char **tgt, const char **src, void *data); 245 246 #endif /* _DICT_H_ */ 247