dict.h

   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 <stdint.h>
  26 #include <assert.h>
  27 #include "vect.h"
  28
  29 struct dict {
  30         /* The invariant is that KEYS, VALUES and STATUS are of the
  31          * same size.  */
  32         struct vect keys;
  33         struct vect values;
  34         struct vect status;
  35         size_t size;
  36
  37         size_t (*hash1)(const void *);
  38         int (*eq)(const void *, const void *);
  39         size_t (*hash2)(size_t);
  40 };
  41
  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));
  52
  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)        \
  57         ({                                                              \
  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, \
  64                           HASH2);                                       \
  65         })
  66
  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),
  80                void *data);
  81
  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.  */      \
  87         ({                                                              \
  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,    \
 105                            (DATA));                                     \
 106         })
 107
 108 /* Return number of key-value pairs stored in DICT.  */
 109 size_t dict_size(const struct dict *dict);
 110
 111 /* Emptiness predicate.  */
 112 int dict_empty(const struct dict *dict);
 113
 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);
 118
 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
 121  * the right size.  */
 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)))
 126
 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);
 130
 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)
 136
 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
 139  * not found.  */
 140 #define DICT_FIND_REF(DICTP, KEYP, VALUE_TYPE)                  \
 141         (assert((DICTP)->keys.elt_size == sizeof(*(KEYP))),     \
 142          (VALUE_TYPE *)dict_find((DICTP), (KEYP)))
 143
 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)                                 \
 148         ({                                                              \
 149                 assert((DICTP)->keys.elt_size == sizeof(*(KEYP)));      \
 150                 assert((DICTP)->values.elt_size == sizeof((VAR)));      \
 151                 void *_ptr = dict_find((DICTP), (KEYP));                \
 152                 if (_ptr != NULL)                                       \
 153                         memcpy((VAR), _ptr, (DICTP)->values.elt_size);  \
 154                 _ptr != NULL ? 0 : -1;                                  \
 155         })
 156
 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
 160  * value.  */
 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),
 164                void *data);
 165
 166 /* Erase from DICTP a value of type VALUE_TYPE corresponding to
 167  * KEYP.  */
 168 #define DICT_ERASE(DICTP, KEYP, VALUE_TYPE, DTOR_KEY, DTOR_VALUE, DATA) \
 169         ({                                                              \
 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,    \
 177                            (DATA));                                     \
 178         })
 179
 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),
 186                   void *data);
 187
 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) \
 191         do {                                                            \
 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,  \
 200                              (DATA));                                   \
 201         } while (0)
 202
 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
 210  * stopped.  */
 211 void *dict_each(struct dict *dict, void *start_after,
 212                 enum callback_status (*cb)(void *, void *, void *), void *data);
 213
 214 #define DICT_EACH(DICTP, KEY_TYPE, VALUE_TYPE, START_AFTER, CB, DATA)   \
 215         /* xxx GCC-ism necessary to get in the safety latches.  */      \
 216         ({                                                              \
 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 *,   \
 221                                             void *) = CB;               \
 222                 KEY_TYPE *_start_after = (START_AFTER);                 \
 223                 (KEY_TYPE *)dict_each((DICTP), _start_after,            \
 224                                       (enum callback_status             \
 225                                        (*)(void *, void *, void *))_cb, \
 226                                       (DATA));                          \
 227         })
 228
 229 /* A callback for hashing integers.  */
 230 size_t dict_hash_int(const int *key);
 231
 232 /* An equality predicate callback for integers.  */
 233 int dict_eq_int(const int *key1, const int *key2);
 234
 235 /* A callback for hashing uint64_t.  */
 236 size_t dict_hash_uint64(const uint64_t *key);
 237
 238 /* An equality predicate callback for uint64_t.  */
 239 int dict_eq_uint64(const uint64_t *key1, const uint64_t *key2);
 240
 241 /* A callback for hashing NULL-terminated strings.  */
 242 size_t dict_hash_string(const char **key);
 243
 244 /* An equality predicate callback for strings.  */
 245 int dict_eq_string(const char **key1, const char **key2);
 246
 247 /* A dtor which calls 'free' on keys in a table.  */
 248 void dict_dtor_string(const char **key, void *data);
 249
 250 /* A cloner that calls 'strdup' on keys in a table.  */
 251 int dict_clone_string(const char **tgt, const char **src, void *data);
 252
 253 #endif /* DICT_H */