1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
|
// SPDX-License-Identifier: GPL-3.0-or-later
#ifndef NETDATA_DICTIONARY_H
#define NETDATA_DICTIONARY_H 1
#include "../libnetdata.h"
/*
* Netdata DICTIONARY features:
*
* CLONE or LINK
* Names and Values in the dictionary can be cloned or linked.
* In clone mode, the dictionary does all the memory management.
* The default is clone for both names and values.
* Set DICT_OPTION_NAME_LINK_DONT_CLONE to link names.
* Set DICT_OPTION_VALUE_LINK_DONT_CLONE to link names.
*
* ORDERED
* Items are ordered in the order they are added (new items are appended at the end).
* You may reverse the order by setting the flag DICT_OPTION_ADD_IN_FRONT.
*
* LOOKUP
* The dictionary uses JudyHS to maintain a very fast randomly accessible hash table.
*
* MULTI-THREADED and SINGLE-THREADED
* Each dictionary may be single threaded (no locks), or multi-threaded (multiple readers or one writer).
* The default is multi-threaded. Add the flag DICT_OPTION_SINGLE_THREADED for single-threaded.
*
* WALK-THROUGH and FOREACH traversal
* The dictionary can be traversed on read or write mode, either with a callback (walkthrough) or with
* a loop (foreach).
*
* In write mode traversal, the caller may delete only the current item, but may add as many items as needed.
*
*/
#ifdef DICTIONARY_INTERNALS
#define DICTFE_CONST
#define DICT_ITEM_CONST
#else
#define DICTFE_CONST const
#define DICT_ITEM_CONST const
#endif
typedef struct dictionary DICTIONARY;
typedef struct dictionary_item DICTIONARY_ITEM;
typedef enum dictionary_options {
DICT_OPTION_NONE = 0, // the default is the opposite of all below
DICT_OPTION_SINGLE_THREADED = (1 << 0), // don't use any locks (default: use locks)
DICT_OPTION_VALUE_LINK_DONT_CLONE = (1 << 1), // don't copy the value, just point to the one provided (default: copy)
DICT_OPTION_NAME_LINK_DONT_CLONE = (1 << 2), // don't copy the name, just point to the one provided (default: copy)
DICT_OPTION_DONT_OVERWRITE_VALUE = (1 << 3), // don't overwrite values of dictionary items (default: overwrite)
DICT_OPTION_ADD_IN_FRONT = (1 << 4), // add dictionary items at the front of the linked list (default: at the end)
} DICT_OPTIONS;
struct dictionary_stats {
const char *name; // the name of the category
struct {
size_t active; // the number of active dictionaries
size_t deleted; // the number of dictionaries queued for destruction
} dictionaries;
struct {
long entries; // active items in the dictionary
long pending_deletion; // pending deletion items in the dictionary
long referenced; // referenced items in the dictionary
} items;
struct {
size_t creations; // dictionary creations
size_t destructions; // dictionary destructions
size_t flushes; // dictionary flushes
size_t traversals; // dictionary foreach
size_t walkthroughs; // dictionary walkthrough
size_t garbage_collections; // dictionary garbage collections
size_t searches; // item searches
size_t inserts; // item inserts
size_t resets; // item resets
size_t deletes; // item deletes
} ops;
struct {
size_t inserts; // number of times the insert callback is called
size_t conflicts; // number of times the conflict callback is called
size_t reacts; // number of times the react callback is called
size_t deletes; // number of times the delete callback is called
} callbacks;
// memory
struct {
long indexed; // bytes of keys indexed (indication of the index size)
long values; // bytes of caller structures
long dict; // bytes of the structures dictionary needs
} memory;
// spin locks
struct {
size_t use; // number of times a reference to item had to spin to acquire it or ignore it
size_t search; // number of times a successful search result had to be thrown away
size_t insert; // number of times an insertion to the hash table had to be repeated
} spin_locks;
};
// Create a dictionary
#ifdef NETDATA_INTERNAL_CHECKS
#define dictionary_create(options) dictionary_create_advanced_with_trace(options, NULL, __FUNCTION__, __LINE__, __FILE__)
#define dictionary_create_advanced(options, stats) dictionary_create_advanced_with_trace(options, stats, __FUNCTION__, __LINE__, __FILE__)
extern DICTIONARY *dictionary_create_advanced_with_trace(DICT_OPTIONS options, struct dictionary_stats *stats, const char *function, size_t line, const char *file);
#else
#define dictionary_create(options) dictionary_create_advanced(options, NULL);
extern DICTIONARY *dictionary_create_advanced(DICT_OPTIONS options, struct dictionary_stats *stats);
#endif
// Create a view on a dictionary
#ifdef NETDATA_INTERNAL_CHECKS
#define dictionary_create_view(master) dictionary_create_view_with_trace(master, __FUNCTION__, __LINE__, __FILE__)
extern DICTIONARY *dictionary_create_view_with_trace(DICTIONARY *master, const char *function, size_t line, const char *file);
#else
extern DICTIONARY *dictionary_create_view(DICTIONARY *master);
#endif
// an insert callback to be called just after an item is added to the dictionary
// this callback is called while the dictionary is write locked!
extern void dictionary_register_insert_callback(DICTIONARY *dict, void (*ins_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data);
// a delete callback to be called just before an item is deleted forever
// this callback is called while the dictionary is write locked!
extern void dictionary_register_delete_callback(DICTIONARY *dict, void (*del_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data);
// a merge callback to be called when DICT_OPTION_DONT_OVERWRITE_VALUE
// and an item is already found in the dictionary - the dictionary does nothing else in this case
// the old_value will remain in the dictionary - the new_value is ignored
// The callback should return true if the value has been updated (it increases the dictionary version).
extern void dictionary_register_conflict_callback(DICTIONARY *dict, bool (*conflict_callback)(const DICTIONARY_ITEM *item, void *old_value, void *new_value, void *data), void *data);
// a reaction callback to be called after every item insertion or conflict
// after the constructors have finished and the items are fully available for use
// and the dictionary is not write locked anymore
extern void dictionary_register_react_callback(DICTIONARY *dict, void (*react_callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data);
// Destroy a dictionary
// Returns the number of bytes freed
// The returned value will not include name/key sizes
// Registered delete callbacks will be run for each item in the dictionary.
extern size_t dictionary_destroy(DICTIONARY *dict);
// Empties a dictionary
// Referenced items will survive, but are not offered anymore.
// Registered delete callbacks will be run for each item in the dictionary.
extern void dictionary_flush(DICTIONARY *dict);
extern void dictionary_version_increment(DICTIONARY *dict);
// ----------------------------------------------------------------------------
// Set an item in the dictionary
//
// - if an item with the same name does not exist, create one
// - if an item with the same name exists, then:
// a) if DICT_OPTION_DONT_OVERWRITE_VALUE is set, just return the existing value (ignore the new value)
// else b) reset the value to the new value passed at the call
//
// When DICT_OPTION_VALUE_LINK_DONT_CLONE is set, the value is linked, otherwise it is copied
// When DICT_OPTION_NAME_LINK_DONT_CLONE is set, the name is linked, otherwise it is copied
//
// When neither DICT_OPTION_VALUE_LINK_DONT_CLONE nor DICT_OPTION_NAME_LINK_DONT_CLONE are set, all the
// memory management for names and values is done by the dictionary.
//
// Passing NULL as value, the dictionary will callocz() the newly allocated value, otherwise it will copy it.
// Passing 0 as value_len, the dictionary will set the value to NULL (no allocations for value will be made).
#define dictionary_set(dict, name, value, value_len) dictionary_set_advanced(dict, name, -1, value, value_len, NULL)
extern void *dictionary_set_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, void *value, size_t value_len, void *constructor_data);
#define dictionary_set_and_acquire_item(dict, name, value, value_len) dictionary_set_and_acquire_item_advanced(dict, name, -1, value, value_len, NULL)
extern DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_set_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, void *value, size_t value_len, void *constructor_data);
// set an item in a dictionary view
#define dictionary_view_set_and_acquire_item(dict, name, master_item) dictionary_view_set_and_acquire_item_advanced(dict, name, -1, master_item)
extern DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_view_set_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, DICTIONARY_ITEM *master_item);
#define dictionary_view_set(dict, name, master_item) dictionary_view_set_advanced(dict, name, -1, master_item)
extern void *dictionary_view_set_advanced(DICTIONARY *dict, const char *name, ssize_t name_len, DICT_ITEM_CONST DICTIONARY_ITEM *master_item);
// ----------------------------------------------------------------------------
// Get an item from the dictionary
// If it returns NULL, the item is not found
#define dictionary_get(dict, name) dictionary_get_advanced(dict, name, -1)
extern void *dictionary_get_advanced(DICTIONARY *dict, const char *name, ssize_t name_len);
#define dictionary_get_and_acquire_item(dict, name) dictionary_get_and_acquire_item_advanced(dict, name, -1)
extern DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_get_and_acquire_item_advanced(DICTIONARY *dict, const char *name, ssize_t name_len);
// ----------------------------------------------------------------------------
// Delete an item from the dictionary
// returns true if the item was found and has been deleted
// returns false if the item was not found in the index
#define dictionary_del(dict, name) dictionary_del_advanced(dict, name, -1)
extern bool dictionary_del_advanced(DICTIONARY *dict, const char *name, ssize_t name_len);
// ----------------------------------------------------------------------------
// reference counters management
extern void dictionary_acquired_item_release(DICTIONARY *dict, DICT_ITEM_CONST DICTIONARY_ITEM *item);
extern DICT_ITEM_CONST DICTIONARY_ITEM *dictionary_acquired_item_dup(DICTIONARY *dict, DICT_ITEM_CONST DICTIONARY_ITEM *item);
extern const char *dictionary_acquired_item_name(DICT_ITEM_CONST DICTIONARY_ITEM *item);
extern void *dictionary_acquired_item_value(DICT_ITEM_CONST DICTIONARY_ITEM *item);
extern size_t dictionary_acquired_item_references(DICT_ITEM_CONST DICTIONARY_ITEM *item);
// ----------------------------------------------------------------------------
// Traverse (walk through) the items of the dictionary.
// The order of traversal is currently the order of insertion.
//
// The callback function may return a negative number to stop the traversal,
// in which case that negative value is returned to the caller.
//
// If all callback calls return zero or positive numbers, the sum of all of
// them is returned to the caller.
//
// You cannot alter the dictionary from inside a dictionary_walkthrough_read() - deadlock!
// You can only delete the current item from inside a dictionary_walkthrough_write() - you can add as many as you want.
//
#define dictionary_walkthrough_read(dict, callback, data) dictionary_walkthrough_rw(dict, 'r', callback, data)
#define dictionary_walkthrough_write(dict, callback, data) dictionary_walkthrough_rw(dict, 'w', callback, data)
extern int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const DICTIONARY_ITEM *item, void *value, void *data), void *data);
#define dictionary_sorted_walkthrough_read(dict, callback, data) dictionary_sorted_walkthrough_rw(dict, 'r', callback, data)
#define dictionary_sorted_walkthrough_write(dict, callback, data) dictionary_sorted_walkthrough_rw(dict, 'w', callback, data)
int dictionary_sorted_walkthrough_rw(DICTIONARY *dict, char rw, int (*callback)(const DICTIONARY_ITEM *item, void *entry, void *data), void *data);
// ----------------------------------------------------------------------------
// Traverse with foreach
//
// Use like this:
//
// DICTFE dfe = {};
// for(MY_ITEM *item = dfe_start_read(&dfe, dict); item ; item = dfe_next(&dfe)) {
// // do things with the item and its dfe.name
// }
// dfe_done(&dfe);
//
// You cannot alter the dictionary from within a dfe_read_start() - deadlock!
// You can only delete the current item from inside a dfe_start_write() - you can add as many as you want.
//
#define DICTIONARY_LOCK_READ 'r'
#define DICTIONARY_LOCK_WRITE 'w'
#define DICTIONARY_LOCK_REENTRANT 'z'
extern void dictionary_write_lock(DICTIONARY *dict);
extern void dictionary_write_unlock(DICTIONARY *dict);
typedef DICTFE_CONST struct dictionary_foreach {
DICTIONARY *dict; // the dictionary upon we work
DICTIONARY_ITEM *item;
|