src/adaptive_resortable_list.h

   1 #ifndef NETDATA_ADAPTIVE_RESORTABLE_LIST_H
   2 #define NETDATA_ADAPTIVE_RESORTABLE_LIST_H
   3
   4 /*
   5  * ADAPTIVE RE-SORTABLE LIST
   6  * This structure allows netdata to read a file of NAME VALUE lines
   7  * in the fastest possible way.
   8  *
   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.
  13  *
  14  * The caller:
  15  *
  16  * 1. calls arl_create() to create a list
  17  *
  18  * 2. calls arl_expect() to register the expected keyword
  19  *
  20  * Then:
  21  *
  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.
  24  *
  25  * 4. calls arl_check() for each line read from the file.
  26  *
  27  * Finally:
  28  *
  29  * 5. calls arl_free() to destroy this and free all memory.
  30  *
  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 *.
  34  *
  35  * LIMITATIONS
  36  * DO NOT USE THIS IF THE A NAME/KEYWORD MAY APPEAR MORE THAN
  37  * ONCE IN THE SOURCE DATA SET.
  38  */
  39
  40 #include "common.h"
  41
  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
  45
  46 typedef struct arl_entry {
  47     char *name;             // the keywords
  48     uint32_t hash;          // the hash of the keyword
  49
  50     void *dst;              // the dst to pass to the processor
  51
  52     uint8_t flags;          // ARL_ENTRY_FLAG_*
  53
  54     // double linked list for fast re-linkings
  55     struct arl_entry *prev, *next;
  56 } ARL_ENTRY;
  57
  58 typedef struct arl_base {
  59     char *name;
  60
  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
  66
  67     size_t relinkings;  // the number of relinkings we have made so far
  68
  69     size_t allocated;   // the number of keywords allocated
  70     size_t fred;        // the number of keywords cleaned up
  71
  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.
  76
  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.
  80
  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
  84 #endif
  85
  86     // the processor to do the job
  87     void (*processor)(const char *name, uint32_t hash, const char *value, void *dst);
  88
  89     // the linked list of the keywords
  90     ARL_ENTRY *head;
  91
  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;
  95 } ARL_BASE;
  96
  97 // create a new ARL
  98 extern ARL_BASE *arl_create(const char *name, void (*processor)(const char *, uint32_t, const char *, void *), size_t rechecks);
  99
 100 // free an ARL
 101 extern void arl_free(ARL_BASE *arl_base);
 102
 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);
 106
 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);
 109
 110 // begin an ARL iteration
 111 extern void arl_begin(ARL_BASE *base);
 112
 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;
 120
 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);
 124 #endif
 125
 126     // it should be the first entry (pointed by base->next_keyword)
 127     if(likely(!strcmp(keyword, e->name))) {
 128         // it is
 129
 130 #ifdef NETDATA_INTERNAL_CHECKS
 131         base->fast++;
 132 #endif
 133
 134         e->flags |= ARL_ENTRY_FLAG_FOUND;
 135
 136         // execute the processor
 137         if(unlikely(e->dst)) {
 138             base->processor(e->name, e->hash, value, e->dst);
 139             base->found++;
 140         }
 141
 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;
 146
 147         // stop if we collected all the values for this iteration
 148         if(unlikely(base->found == base->wanted))
 149             return 1;
 150
 151         return 0;
 152     }
 153
 154 #ifdef NETDATA_INTERNAL_CHECKS
 155     base->slow++;
 156 #endif
 157
 158     // we read from source, a not-expected keyword
 159     return arl_find_or_create_and_relink(base, keyword, value);
 160 }
 161
 162 #endif //NETDATA_ADAPTIVE_RESORTABLE_LIST_H