@cryptotaxi247 / netdata
Code Commits Issues Pulls Sessions CI/CD
master
master
c 293 lines 8.52 KB
Raw
1 // SPDX-License-Identifier: GPL-3.0-or-later
2
3 #include "dictionary-internals.h"
4
5
6 // ----------------------------------------------------------------------------
7 // traversal with loop
8
9 void *dictionary_foreach_start_rw(DICTFE *dfe) {
10 if(unlikely(!dfe || !dfe->dict)) return NULL;
11
12 DICTIONARY_STATS_TRAVERSALS_PLUS1(dfe->dict);
13
14 if(unlikely(is_dictionary_destroyed(dfe->dict))) {
15 internal_error(true, "DICTIONARY: attempted to dictionary_foreach_start_rw() on a destroyed dictionary");
16 dfe->dict = NULL;
17 dfe->item = NULL;
18 dfe->name = NULL;
19 dfe->value = NULL;
20 dfe->counter = 0;
21 return NULL;
22 }
23
24 dfe->counter = 0;
25 dfe->locked = true;
26 ll_recursive_lock(dfe->dict, dfe->rw);
27
28 // Re-check under the lock — dictionary_destroy() sets the flag while
29 // holding this lock, so this is the synchronized check.
30 if(unlikely(is_dictionary_destroyed(dfe->dict))) {
31 ll_recursive_unlock(dfe->dict, dfe->rw);
32 dfe->locked = false;
33 dfe->dict = NULL;
34 dfe->item = NULL;
35 dfe->name = NULL;
36 dfe->value = NULL;
37 dfe->counter = 0;
38 return NULL;
39 }
40
41 // get the first item from the list
42 DICTIONARY_ITEM *item = dfe->dict->items.list;
43
44 // skip all the deleted items
45 while(item && !item_check_and_acquire(dfe->dict, item))
46 item = item->next;
47
48 if(likely(item)) {
49 dfe->item = item;
50 dfe->name = (char *)item_get_name(item);
51 dfe->value = item->shared->value;
52 }
53 else {
54 dfe->item = NULL;
55 dfe->name = NULL;
56 dfe->value = NULL;
57 }
58
59 if(unlikely(dfe->rw == DICTIONARY_LOCK_REENTRANT)) {
60 ll_recursive_unlock(dfe->dict, dfe->rw);
61 dfe->locked = false;
62 }
63
64 return dfe->value;
65 }
66
67 ALWAYS_INLINE void *dictionary_foreach_next(DICTFE *dfe) {
68 if(unlikely(!dfe || !dfe->dict)) return NULL;
69
70 if(unlikely(is_dictionary_destroyed(dfe->dict))) {
71 internal_error(true, "DICTIONARY: attempted to dictionary_foreach_next() on a destroyed dictionary");
72 dictionary_foreach_done(dfe);
73 return NULL;
74 }
75
76 if(unlikely(dfe->rw == DICTIONARY_LOCK_REENTRANT) || !dfe->locked) {
77 ll_recursive_lock(dfe->dict, dfe->rw);
78 dfe->locked = true;
79
80 if(unlikely(is_dictionary_destroyed(dfe->dict))) {
81 // Unlock before foreach_done — in reentrant mode, foreach_done
82 // does not release the lock (it assumes the caller manages it).
83 ll_recursive_unlock(dfe->dict, dfe->rw);
84 dfe->locked = false;
85 dictionary_foreach_done(dfe);
86 return NULL;
87 }
88 }
89
90 // the item we just did
91 DICTIONARY_ITEM *item = dfe->item;
92
93 // get the next item from the list
94 DICTIONARY_ITEM *item_next = (item) ? item->next : NULL;
95
96 // skip all the deleted items until one that can be acquired is found
97 while(item_next && !item_check_and_acquire(dfe->dict, item_next))
98 item_next = item_next->next;
99
100 if(likely(item)) {
101 dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dfe->dict, item, dfe->rw);
102 // item_release(dfe->dict, item);
103 }
104
105 item = item_next;
106 if(likely(item)) {
107 dfe->item = item;
108 dfe->name = (char *)item_get_name(item);
109 dfe->value = item->shared->value;
110 dfe->counter++;
111 }
112 else {
113 dfe->item = NULL;
114 dfe->name = NULL;
115 dfe->value = NULL;
116 }
117
118 if(unlikely(dfe->rw == DICTIONARY_LOCK_REENTRANT)) {
119 ll_recursive_unlock(dfe->dict, dfe->rw);
120 dfe->locked = false;
121 }
122
123 return dfe->value;
124 }
125
126 void dictionary_foreach_unlock(DICTFE *dfe) {
127 if(dfe->locked) {
128 ll_recursive_unlock(dfe->dict, dfe->rw);
129 dfe->locked = false;
130 }
131 }
132
133 void dictionary_foreach_done(DICTFE *dfe) {
134 if(unlikely(!dfe || !dfe->dict)) return;
135
136 // the item we just did
137 DICTIONARY_ITEM *item = dfe->item;
138
139 // release it, so that it can possibly be deleted
140 if(likely(item)) {
141 dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dfe->dict, item, dfe->rw);
142 // item_release(dfe->dict, item);
143 }
144
145 if(likely(dfe->rw != DICTIONARY_LOCK_REENTRANT) && dfe->locked) {
146 ll_recursive_unlock(dfe->dict, dfe->rw);
147 dfe->locked = false;
148 }
149
150 dfe->dict = NULL;
151 dfe->item = NULL;
152 dfe->name = NULL;
153 dfe->value = NULL;
154 dfe->counter = 0;
155 }
156
157 // ----------------------------------------------------------------------------
158 // API - walk through the dictionary.
159 // The dictionary is locked for reading while this happens
160 // do not use other dictionary calls while walking the dictionary - deadlock!
161
162 int dictionary_walkthrough_rw(DICTIONARY *dict, char rw, dict_walkthrough_callback_t walkthrough_callback, void *data) {
163 if(unlikely(!dict || !walkthrough_callback)) return 0;
164
165 if(unlikely(is_dictionary_destroyed(dict))) {
166 internal_error(true, "DICTIONARY: attempted to dictionary_walkthrough_rw() on a destroyed dictionary");
167 return 0;
168 }
169
170 ll_recursive_lock(dict, rw);
171
172 if(unlikely(is_dictionary_destroyed(dict))) {
173 ll_recursive_unlock(dict, rw);
174 return 0;
175 }
176
177 DICTIONARY_STATS_WALKTHROUGHS_PLUS1(dict);
178
179 // written in such a way, that the callback can delete the active element
180
181 int ret = 0;
182 DICTIONARY_ITEM *item = dict->items.list, *item_next;
183 while(item) {
184
185 // skip the deleted items
186 if(unlikely(!item_check_and_acquire(dict, item))) {
187 item = item->next;
188 continue;
189 }
190
191 if(unlikely(rw == DICTIONARY_LOCK_REENTRANT))
192 ll_recursive_unlock(dict, rw);
193
194 int r = walkthrough_callback(item, item->shared->value, data);
195
196 if(unlikely(rw == DICTIONARY_LOCK_REENTRANT))
197 ll_recursive_lock(dict, rw);
198
199 // since we have a reference counter, this item cannot be deleted
200 // until we release the reference counter, so the pointers are there
201 item_next = item->next;
202
203 dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dict, item, rw);
204 // item_release(dict, item);
205
206 if(unlikely(r < 0)) {
207 ret = r;
208 break;
209 }
210
211 ret += r;
212
213 item = item_next;
214 }
215
216 ll_recursive_unlock(dict, rw);
217
218 return ret;
219 }
220
221 // ----------------------------------------------------------------------------
222 // sorted walkthrough
223
224 typedef int (*qsort_compar)(const void *item1, const void *item2);
225
226 static int dictionary_sort_compar(const void *item1, const void *item2) {
227 return strcmp(item_get_name((*(DICTIONARY_ITEM **)item1)), item_get_name((*(DICTIONARY_ITEM **)item2)));
228 }
229
230 int dictionary_sorted_walkthrough_rw(DICTIONARY *dict, char rw, dict_walkthrough_callback_t walkthrough_callback, void *data, dict_item_comparator_t item_comparator) {
231 if(unlikely(!dict || !walkthrough_callback)) return 0;
232
233 if(unlikely(is_dictionary_destroyed(dict))) {
234 internal_error(true, "DICTIONARY: attempted to dictionary_sorted_walkthrough_rw() on a destroyed dictionary");
235 return 0;
236 }
237
238 ll_recursive_lock(dict, rw);
239
240 if(unlikely(is_dictionary_destroyed(dict))) {
241 ll_recursive_unlock(dict, rw);
242 return 0;
243 }
244
245 DICTIONARY_STATS_WALKTHROUGHS_PLUS1(dict);
246
247 size_t entries = __atomic_load_n(&dict->entries, __ATOMIC_RELAXED);
248 DICTIONARY_ITEM **array = mallocz(sizeof(DICTIONARY_ITEM *) * entries);
249
250 size_t i;
251 DICTIONARY_ITEM *item;
252 for(item = dict->items.list, i = 0; item && i < entries; item = item->next) {
253 if(likely(item_check_and_acquire(dict, item)))
254 array[i++] = item;
255 }
256 ll_recursive_unlock(dict, rw);
257
258 if(unlikely(i != entries))
259 entries = i;
260
261 if(item_comparator)
262 qsort(array, entries, sizeof(DICTIONARY_ITEM *), (qsort_compar) item_comparator);
263 else
264 qsort(array, entries, sizeof(DICTIONARY_ITEM *), dictionary_sort_compar);
265
266 bool callit = true;
267 int ret = 0, r;
268 for(i = 0; i < entries ;i++) {
269 item = array[i];
270
271 if(callit)
272 r = walkthrough_callback(item, item->shared->value, data);
273
274 dict_item_release_and_check_if_it_is_deleted_and_can_be_removed_under_this_lock_mode(dict, item, rw);
275 // item_release(dict, item);
276
277 if(r < 0) {
278 ret = r;
279 r = 0;
280
281 // stop calling the callback,
282 // but we have to continue, to release all the reference counters
283 callit = false;
284 }
285 else
286 ret += r;
287 }
288
289 freez(array);
290
291 return ret;
292 }
293