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 {
59 size_t iteration; // incremented on each iteration (arl_begin())
60 size_t found; // the number of expected keywords found in this iteration
61 size_t expected; // the number of expected keywords
62 size_t wanted; // the number of wanted keywords
63 // i.e. the number of keywords found and expected
65 size_t relinkings; // the number of relinkings we have made so far
67 size_t allocated; // the number of keywords allocated
68 size_t fred; // the number of keywords cleaned up
70 size_t rechecks; // the number of iterations between re-checks of the
71 // wanted number of keywords
72 // this is only needed in cases where the source
73 // is having less lines over time.
75 size_t added; // it is non-zero if new keywords have been added
76 // this is only needed to detect new lines have
77 // been added to the file, over time.
79 #ifdef NETDATA_INTERNAL_CHECKS
80 size_t fast; // the number of times we have taken the fast path
81 size_t slow; // the number of times we have taken the slow path
84 // the processor to do the job
85 void (*processor)(const char *name, uint32_t hash, const char *value, void *dst);
87 // the linked list of the keywords
90 // since we keep the list of keywords sorted (as found in the source data)
91 // this is next keyword that we expect to find in the source data.
92 ARL_ENTRY *next_keyword;
96 extern ARL_BASE *arl_create(void (*processor)(const char *, uint32_t, const char *, void *), size_t rechecks);
99 extern void arl_free(ARL_BASE *arl_base);
101 // register an expected keyword to the ARL
102 // together with its destination ( i.e. the output of the processor() )
103 extern ARL_ENTRY *arl_expect(ARL_BASE *base, const char *keyword, void *dst);
105 // an internal call to complete the check() call
106 extern int arl_find_or_create_and_relink(ARL_BASE *base, const char *s, const char *value);
108 // begin an ARL iteration
109 extern void arl_begin(ARL_BASE *base);
111 // check a keyword against the ARL
112 // this is to be called for each keyword read from source data
113 // s = the keyword, as collected
114 // src = the src data to be passed to the processor
115 // it is defined in the header file in order to be inlined
116 static inline int arl_check(ARL_BASE *base, const char *keyword, const char *value) {
117 ARL_ENTRY *e = base->next_keyword;
119 // it should be the first entry (pointed by base->next_keyword)
120 if(likely(!strcmp(keyword, e->name))) {
123 #ifdef NETDATA_INTERNAL_CHECKS
127 e->flags |= ARL_ENTRY_FLAG_FOUND;
129 // execute the processor
130 if(unlikely(e->dst)) {
131 base->processor(e->name, e->hash, value, e->dst);
135 // be prepared for the next iteration
136 base->next_keyword = e->next;
137 if(unlikely(!base->next_keyword))
138 base->next_keyword = base->head;
140 // stop if we collected all the values for this iteration
141 if(unlikely(base->found == base->wanted))
147 #ifdef NETDATA_INTERNAL_CHECKS
151 // we read from source, a not-expected keyword
152 return arl_find_or_create_and_relink(base, keyword, value);
155 #endif //NETDATA_ADAPTIVE_RESORTABLE_LIST_H