1 #include "adaptive_resortable_list.h"
3 // the default processor() of the ARL
4 // can be overwritten at arl_create()
5 static inline void arl_callback_str2ull(const char *name, uint32_t hash, const char *value, void *dst) {
9 register unsigned long long *d = dst;
11 // fprintf(stderr, "name '%s' with hash %u and value '%s' is %llu\n", name, hash, value, *d);
15 ARL_BASE *arl_create(const char *name, void (*processor)(const char *, uint32_t, const char *, void *), size_t rechecks) {
16 ARL_BASE *base = callocz(1, sizeof(ARL_BASE));
18 base->name = strdupz(name);
21 base->processor = arl_callback_str2ull;
23 base->processor = processor;
25 base->rechecks = rechecks;
30 void arl_free(ARL_BASE *arl_base) {
31 if(unlikely(!arl_base))
34 while(arl_base->head) {
35 ARL_ENTRY *e = arl_base->head;
36 arl_base->head = e->next;
39 #ifdef NETDATA_INTERNAL_CHECKS
40 memset(e, 0, sizeof(ARL_ENTRY));
45 freez(arl_base->name);
47 #ifdef NETDATA_INTERNAL_CHECKS
48 memset(arl_base, 0, sizeof(ARL_BASE));
54 void arl_begin(ARL_BASE *base) {
56 #ifdef NETDATA_INTERNAL_CHECKS
57 if(likely(base->iteration > 10)) {
58 // do these checks after the ARL has been sorted
60 if(unlikely(base->relinkings > (base->expected + base->allocated)))
61 info("ARL '%s' has %zu relinkings with %zu expected and %zu allocated entries. Is the source changing so fast?"
62 , base->name, base->relinkings, base->expected, base->allocated);
64 if(unlikely(base->slow > base->fast))
65 info("ARL '%s' has %zu fast searches and %zu slow searches. Is the source really changing so fast?"
66 , base->name, base->fast, base->slow);
69 if(unlikely(base->iteration % 60 == 0)) {
70 info("ARL '%s' statistics: iteration %zu, expected %zu, wanted %zu, allocated %zu, fred %zu, relinkings %zu, found %zu, added %zu, fast %zu, slow %zu"
83 // for(e = base->head; e; e = e->next) fprintf(stderr, "%s ", e->name);
84 // fprintf(stderr, "\n");
90 if(unlikely(base->added || base->iteration % base->rechecks) == 1) {
93 ARL_ENTRY *e = base->head;
95 if(e->flags & ARL_ENTRY_FLAG_FOUND) {
97 // remove the found flag
98 e->flags &= ~ARL_ENTRY_FLAG_FOUND;
100 // count it in wanted
101 if(e->flags & ARL_ENTRY_FLAG_EXPECTED)
105 else if(e->flags & ARL_ENTRY_FLAG_DYNAMIC && !(base->head == e && !e->next)) { // not last entry
106 // we can remove this entry
107 // it is not found, and it was created because
108 // it was found in the source file
110 // remember the next one
111 ARL_ENTRY *t = e->next;
113 // remove it from the list
114 if(e->next) e->next->prev = e->prev;
115 if(e->prev) e->prev->next = e->next;
116 if(base->head == e) base->head = e->next;
134 if(unlikely(!base->head)) {
135 // hm... no nodes at all in the list #1700
136 // add a fake one to prevent a crash
137 // this is better than checking for the existence of nodes all the time
138 arl_expect(base, "a-really-not-existing-source-keyword", NULL);
142 base->next_keyword = base->head;
147 // register an expected keyword to the ARL
148 // together with its destination ( i.e. the output of the processor() )
149 ARL_ENTRY *arl_expect(ARL_BASE *base, const char *keyword, void *dst) {
150 ARL_ENTRY *e = callocz(1, sizeof(ARL_ENTRY));
151 e->name = strdupz(keyword);
152 e->hash = simple_hash(e->name);
154 e->flags = ARL_ENTRY_FLAG_EXPECTED;
156 e->next = base->head;
158 if(base->head) base->head->prev = e;
159 else base->next_keyword = e;
165 base->wanted = base->expected;
170 int arl_find_or_create_and_relink(ARL_BASE *base, const char *s, const char *value) {
173 uint32_t hash = simple_hash(s);
175 // find if it already exists in the data
176 for(e = base->head; e ; e = e->next)
177 if(e->hash == hash && !strcmp(e->name, s))
180 #ifdef NETDATA_INTERNAL_CHECKS
181 if(unlikely(base->next_keyword && e == base->next_keyword))
182 fatal("Internal Error: e == base->last");
186 // found it in the keywords
190 // run the processor for it
191 if(unlikely(e->dst)) {
192 base->processor(e->name, hash, value, e->dst);
196 // unlink it - we will relink it below
197 if(e->next) e->next->prev = e->prev;
198 if(e->prev) e->prev->next = e->next;
200 // make sure the head is properly linked
202 base->head = e->next;
208 e = callocz(1, sizeof(ARL_ENTRY));
209 e->name = strdupz(s);
211 e->flags = ARL_ENTRY_FLAG_DYNAMIC;
217 #ifdef NETDATA_INTERNAL_CHECKS
218 if(unlikely(base->iteration % 60 == 0 && e->flags & ARL_ENTRY_FLAG_FOUND))
219 info("ARL '%s': entry '%s' is already found. Did you forget to call arl_begin()?", base->name, s);
222 e->flags |= ARL_ENTRY_FLAG_FOUND;
225 e->next = base->next_keyword;
226 if(base->next_keyword) {
227 e->prev = base->next_keyword->prev;
228 base->next_keyword->prev = e;
233 if(base->head == base->next_keyword)
239 base->next_keyword = e->next;
240 if(unlikely(!base->next_keyword))
241 base->next_keyword = base->head;
243 if(unlikely(base->found == base->wanted))