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
|
// 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 DICTIONARY_FLAG_NAME_LINK_DONT_CLONE to link names.
* Set DICTIONARY_FLAG_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 DICTIONARY_FLAG_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 DICTIONARY_FLAG_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.
*
*/
#ifndef DICTIONARY_INTERNALS
typedef void DICTIONARY;
#endif
typedef enum dictionary_flags {
DICTIONARY_FLAG_NONE = 0, // the default is the opposite of all below
DICTIONARY_FLAG_SINGLE_THREADED = (1 << 0), // don't use any locks (default: use locks)
DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE = (1 << 1), // don't copy the value, just point to the one provided (default: copy)
DICTIONARY_FLAG_NAME_LINK_DONT_CLONE = (1 << 2), // don't copy the name, just point to the one provided (default: copy)
DICTIONARY_FLAG_WITH_STATISTICS = (1 << 3), // maintain statistics about dictionary operations (default: disabled)
DICTIONARY_FLAG_DONT_OVERWRITE_VALUE = (1 << 4), // don't overwrite values of dictionary items (default: overwrite)
DICTIONARY_FLAG_ADD_IN_FRONT = (1 << 5), // add dictionary items at the front of the linked list (default: at the end)
DICTIONARY_FLAG_RESERVED1 = (1 << 6), // this is reserved for DICTIONARY_FLAG_REFERENCE_COUNTERS
} DICTIONARY_FLAGS;
// Create a dictionary
extern DICTIONARY *dictionary_create(DICTIONARY_FLAGS flags);
// 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 char *name, 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 char *name, void *value, void *data), void *data);
// a merge callback to be called when DICTIONARY_FLAG_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
extern void dictionary_register_conflict_callback(DICTIONARY *dict, void (*conflict_callback)(const char *name, void *old_value, void *new_value, void *data), void *data);
// Destroy a dictionary
// returns the number of bytes freed
// the returned value will not include name and value sizes if DICTIONARY_FLAG_WITH_STATISTICS is not set
extern size_t dictionary_destroy(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 DICTIONARY_FLAG_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 DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE is set, the value is linked, otherwise it is copied
// When DICTIONARY_FLAG_NAME_LINK_DONT_CLONE is set, the name is linked, otherwise it is copied
//
// When neither DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE nor DICTIONARY_FLAG_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).
extern void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len) NEVERNULL;
// Get an item from the dictionary
// If it returns NULL, the item is not found
extern void *dictionary_get(DICTIONARY *dict, const char *name);
// Delete an item from the dictionary
// returns 0 if the item was found and has been deleted
// returns -1 if the item was not found in the index
extern int dictionary_del(DICTIONARY *dict, const char *name);
// UNSAFE functions, without locks
// to be used when the user is traversing with the right lock type
// Read lock is acquired by dictionary_walktrhough_read() and dfe_start_read()
// Write lock is acquired by dictionary_walktrhough_write() and dfe_start_write()
// For code readability, please use these macros:
#define dictionary_get_having_read_lock(dict, name) dictionary_get_unsafe(dict, name)
#define dictionary_get_having_write_lock(dict, name) dictionary_get_unsafe(dict, name)
#define dictionary_set_having_write_lock(dict, name, value, value_len) dictionary_set_unsafe(dict, name, value, value_len)
#define dictionary_del_having_write_lock(dict, name) dictionary_del_unsafe(dict, name)
extern void *dictionary_get_unsafe(DICTIONARY *dict, const char *name);
extern void *dictionary_set_unsafe(DICTIONARY *dict, const char *name, void *value, size_t value_len);
extern int dictionary_del_unsafe(DICTIONARY *dict, const char *name);
// 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 char *name, void *value, 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.
//
#ifdef DICTIONARY_INTERNALS
#define DICTFE_CONST
#else
#define DICTFE_CONST const
#endif
typedef DICTFE_CONST struct dictionary_foreach {
DICTFE_CONST char *name; // the dictionary name of the last item used
void *value; // the dictionary value of the last item used
// same as the return value of dictfe_start() and dictfe_next()
// the following are for internal use only - to keep track of the point we are
usec_t started_ut; // the time the caller started iterating (now_realtime_usec())
DICTIONARY *dict; // the dictionary upon we work
void *last_position_index; // the internal position index, to remember the position we are at
void *next_position_index; // the internal position index, of the next item
} DICTFE;
#define dfe_start_read(dict, value) dfe_start_rw(dict, value, 'r')
#define dfe_start_write(dict, value) dfe_start_rw(dict, value, 'w')
#define dfe_start_rw(dict, value, mode) \
do { \
DICTFE value ## _dfe = {}; \
const char *value ## _name; (void)(value ## _name); \
for((value) = dictionary_foreach_start_rw(&value ## _dfe, (dict), (mode)), ( value ## _name ) = value ## _dfe.name; \
(value) ;\
(value) = dictionary_foreach_next(&value ## _dfe), ( value ## _name ) = value ## _dfe.name)
#define dfe_done(value) \
dictionary_foreach_done(&value ## _dfe); \
} while(0)
extern void * dictionary_foreach_start_rw(DICTFE *dfe, DICTIONARY *dict, char rw);
extern void * dictionary_foreach_next(DICTFE *dfe);
extern usec_t dictionary_foreach_done(DICTFE *dfe);
// Get statistics about the dictionary
// If DICTIONARY_FLAG_WITH_STATISTICS is not set, these return zero
extern size_t dictionary_stats_allocated_memory(DICTIONARY *dict);
extern size_t dictionary_stats_entries(DICTIONARY *dict);
extern size_t dictionary_stats_inserts(DICTIONARY *dict);
extern size_t dictionary_stats_searches(DICTIONARY *dict);
extern size_t dictionary_stats_deletes(DICTIONARY *dict);
extern size_t dictionary_stats_resets(DICTIONARY *dict);
extern int dictionary_unittest(size_t entries);
#endif /* NETDATA_DICTIONARY_H */
|
