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
28struct 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.  */
46void 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.  */
74int 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.  */
108size_t dict_size(const struct dict *dict);
109
110/* Emptiness predicate.  */
111int 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.  */
116int 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.  */
128void *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.  */
160int 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.  */
182void 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.  */
210void *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.  */
229size_t dict_hash_int(const int *key);
230
231/* An equality predicate callback for integers.  */
232int dict_eq_int(const int *key1, const int *key2);
233
234/* A callback for hashing NULL-terminated strings.  */
235size_t dict_hash_string(const char **key);
236
237/* An equality predicate callback for strings.  */
238int dict_eq_string(const char **key1, const char **key2);
239
240/* A dtor which calls 'free' on keys in a table.  */
241void dict_dtor_string(const char **key, void *data);
242
243/* A cloner that calls 'strdup' on keys in a table.  */
244int dict_clone_string(const char **tgt, const char **src, void *data);
245
246#endif /* _DICT_H_ */
247