1 #ifndef NETDATA_ADAPTIVE_RESORTABLE_LIST_H
2 #define NETDATA_ADAPTIVE_RESORTABLE_LIST_H
5 * ADAPTIVE RE-SORTABLE LIST
6 * This structure allows netdata to read a file of NAME VALUE lines
7 * in the fastest possible way.
9 * It maintains a linked list of all NAME (keywords), sorted in the
10 * same order as found in the source data file.
11 * The linked list is kept sorted at all times - the source file
12 * may change at any time, the list will adapt.
16 * 1. calls arl_create() to create a list
18 * 2. calls arl_expect() to register the expected keyword
22 * 3. calls arl_begin() to initiate a data collection iteration.
23 * This is to be called just ONCE every time the source is re-scanned.
25 * 4. calls arl_check() for each line read from the file.
29 * 5. calls arl_free() to destroy this and free all memory.
31 * The program will call the processor() function, given to
32 * arl_create(), for each expected keyword found.
33 * The default processor() expects dst to be an unsigned long long *.
36 * DO NOT USE THIS IF THE A NAME/KEYWORD MAY APPEAR MORE THAN
37 * ONCE IN THE SOURCE DATA SET.
42 #define ARL_ENTRY_FLAG_FOUND 0x01 // the entry has been found in the source data
43 #define ARL_ENTRY_FLAG_EXPECTED 0x02 // the entry is expected by the program
44 #define ARL_ENTRY_FLAG_DYNAMIC 0x04 // the entry was dynamically allocated, from source data
46 typedef struct arl_entry {
47 char *name; // the keywords
48 uint32_t hash; // the hash of the keyword
50 void *dst; // the dst to pass to the processor
52 uint8_t flags; // ARL_ENTRY_FLAG_*
54 // double linked list for fast re-linkings
55 struct arl_entry *prev, *next;
58 typedef struct arl_base {
61 size_t iteration; // incremented on each iteration (arl_begin())
62 size_t found; // the number of expected keywords found in this iteration
63 size_t expected; // the number of expected keywords
64 size_t wanted; // the number of wanted keywords
65 // i.e. the number of keywords found and expected
67 size_t relinkings; // the number of relinkings we have made so far
69 size_t allocated; // the number of keywords allocated
70 size_t fred; // the number of keywords cleaned up
72 size_t rechecks; // the number of iterations between re-checks of the
73 // wanted number of keywords
74 // this is only needed in cases where the source
75 // is having less lines over time.
77 size_t added; // it is non-zero if new keywords have been added
78 // this is only needed to detect new lines have
79 // been added to the file, over time.
81 #ifdef NETDATA_INTERNAL_CHECKS
82 size_t fast; // the number of times we have taken the fast path
83 size_t slow; // the number of times we have taken the slow path
86 // the processor to do the job
87 void (*processor)(const char *name, uint32_t hash, const char *value, void *dst);
89 // the linked list of the keywords
92 // since we keep the list of keywords sorted (as found in the source data)
93 // this is next keyword that we expect to find in the source data.
94 ARL_ENTRY *next_keyword;
98 extern ARL_BASE *arl_create(const char *name, void (*processor)(const char *, uint32_t, const char *, void *), size_t rechecks);
101 extern void arl_free(ARL_BASE *arl_base);
103 // register an expected keyword to the ARL
104 // together with its destination ( i.e. the output of the processor() )
105 extern ARL_ENTRY *arl_expect(ARL_BASE *base, const char *keyword, void *dst);
107 // an internal call to complete the check() call
108 extern int arl_find_or_create_and_relink(ARL_BASE *base, const char *s, const char *value);
110 // begin an ARL iteration
111 extern void arl_begin(ARL_BASE *base);
113 // check a keyword against the ARL
114 // this is to be called for each keyword read from source data
115 // s = the keyword, as collected
116 // src = the src data to be passed to the processor
117 // it is defined in the header file in order to be inlined
118 static inline int arl_check(ARL_BASE *base, const char *keyword, const char *value) {
119 ARL_ENTRY *e = base->next_keyword;
121 #ifdef NETDATA_INTERNAL_CHECKS
122 if(unlikely((base->fast + base->slow) % (base->expected + base->allocated) == 0 && (base->fast + base->slow) > (base->expected + base->allocated) * base->iteration))
123 info("ARL '%s': Did you forget to call arl_begin()?", base->name);
126 // it should be the first entry (pointed by base->next_keyword)
127 if(likely(!strcmp(keyword, e->name))) {
130 #ifdef NETDATA_INTERNAL_CHECKS
134 e->flags |= ARL_ENTRY_FLAG_FOUND;
136 // execute the processor
137 if(unlikely(e->dst)) {
138 base->processor(e->name, e->hash, value, e->dst);
142 // be prepared for the next iteration
143 base->next_keyword = e->next;
144 if(unlikely(!base->next_keyword))
145 base->next_keyword = base->head;
147 // stop if we collected all the values for this iteration
148 if(unlikely(base->found == base->wanted))
154 #ifdef NETDATA_INTERNAL_CHECKS
158 // we read from source, a not-expected keyword
159 return arl_find_or_create_and_relink(base, keyword, value);
162 #endif //NETDATA_ADAPTIVE_RESORTABLE_LIST_H