src/adaptive_resortable_list.c

   1 #include "adaptive_resortable_list.h"
   2
   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) {
   6     (void)name;
   7     (void)hash;
   8
   9     register unsigned long long *d = dst;
  10     *d = str2ull(value);
  11     // fprintf(stderr, "name '%s' with hash %u and value '%s' is %llu\n", name, hash, value, *d);
  12 }
  13
  14 // create a new ARL
  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));
  17
  18     base->name = strdupz(name);
  19
  20     if(!processor)
  21         base->processor = arl_callback_str2ull;
  22     else
  23         base->processor = processor;
  24
  25     base->rechecks = rechecks;
  26
  27     return base;
  28 }
  29
  30 void arl_free(ARL_BASE *arl_base) {
  31     if(unlikely(!arl_base))
  32         return;
  33
  34     while(arl_base->head) {
  35         ARL_ENTRY *e = arl_base->head;
  36         arl_base->head = e->next;
  37
  38         freez(e->name);
  39 #ifdef NETDATA_INTERNAL_CHECKS
  40         memset(e, 0, sizeof(ARL_ENTRY));
  41 #endif
  42         freez(e);
  43     }
  44
  45     freez(arl_base->name);
  46
  47 #ifdef NETDATA_INTERNAL_CHECKS
  48     memset(arl_base, 0, sizeof(ARL_BASE));
  49 #endif
  50
  51     freez(arl_base);
  52 }
  53
  54 void arl_begin(ARL_BASE *base) {
  55     ARL_ENTRY *e;
  56
  57 #ifdef NETDATA_INTERNAL_CHECKS
  58     if(likely(base->iteration > 10)) {
  59         // do these checks after the ARL has been sorted
  60
  61         if(unlikely(base->relinkings > (base->expected + base->allocated)))
  62             info("ARL '%s' has %zu relinkings with %zu expected and %zu allocated entries. Is the source changing so fast?"
  63                  , base->name, base->relinkings, base->expected, base->allocated);
  64
  65         if(unlikely(base->slow > base->fast))
  66             info("ARL '%s' has %zu fast searches and %zu slow searches. Is the source really changing so fast?"
  67                  , base->name, base->fast, base->slow);
  68
  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"
  71                  , base->name
  72                  , base->iteration
  73                  , base->expected
  74                  , base->wanted
  75                  , base->allocated
  76                  , base->fred
  77                  , base->relinkings
  78                  , base->found
  79                  , base->added
  80                  , base->fast
  81                  , base->slow
  82             );
  83             // for(e = base->head; e; e = e->next) fprintf(stderr, "%s ", e->name);
  84             // fprintf(stderr, "\n");
  85         }
  86     }
  87 #endif
  88
  89     if(unlikely(base->added || base->iteration % base->rechecks) == 1) {
  90         base->added = 0;
  91         base->wanted = 0;
  92         for(e = base->head; e ; e = e->next) {
  93             if(e->flags & ARL_ENTRY_FLAG_FOUND) {
  94
  95                 // remove the found flag
  96                 e->flags &= ~ARL_ENTRY_FLAG_FOUND;
  97
  98                 // count it in wanted
  99                 if(e->flags & ARL_ENTRY_FLAG_EXPECTED)
 100                     base->wanted++;
 101             }
 102             else if(e->flags & ARL_ENTRY_FLAG_DYNAMIC) {
 103                 // we can remove this entry
 104                 // it is not found, and it was created because
 105                 // it was found in the source file
 106                 if(e->next) e->next->prev = e->prev;
 107                 if(e->prev) e->prev->next = e->next;
 108                 if(base->head == e) base->head = e->next;
 109                 freez(e->name);
 110                 freez(e);
 111
 112                 base->fred++;
 113             }
 114         }
 115     }
 116
 117     base->iteration++;
 118     base->next_keyword = base->head;
 119     base->found = 0;
 120 }
 121
 122 // register an expected keyword to the ARL
 123 // together with its destination ( i.e. the output of the processor() )
 124 ARL_ENTRY *arl_expect(ARL_BASE *base, const char *keyword, void *dst) {
 125     ARL_ENTRY *e = callocz(1, sizeof(ARL_ENTRY));
 126     e->name = strdupz(keyword);
 127     e->hash = simple_hash(e->name);
 128     e->dst = dst;
 129     e->flags = ARL_ENTRY_FLAG_EXPECTED;
 130     e->prev = NULL;
 131     e->next = base->head;
 132
 133     if(base->head) base->head->prev = e;
 134     else base->next_keyword = e;
 135
 136     base->head = e;
 137     base->expected++;
 138     base->allocated++;
 139
 140     base->wanted = base->expected;
 141
 142     return e;
 143 }
 144
 145 int arl_find_or_create_and_relink(ARL_BASE *base, const char *s, const char *value) {
 146     ARL_ENTRY *e;
 147
 148     uint32_t hash = simple_hash(s);
 149
 150     // find if it already exists in the data
 151     for(e = base->head; e ; e = e->next)
 152         if(e->hash == hash && !strcmp(e->name, s))
 153             break;
 154
 155 #ifdef NETDATA_INTERNAL_CHECKS
 156     if(unlikely(e == base->next_keyword))
 157         fatal("Internal Error: e == base->last");
 158 #endif
 159
 160     if(e) {
 161         // found it in the keywords
 162
 163         base->relinkings++;
 164
 165         // run the processor for it
 166         if(unlikely(e->dst)) {
 167             base->processor(e->name, hash, value, e->dst);
 168             base->found++;
 169         }
 170
 171         // unlink it - we will relink it below
 172         if(e->next) e->next->prev = e->prev;
 173         if(e->prev) e->prev->next = e->next;
 174
 175         // make sure the head is properly linked
 176         if(base->head == e)
 177             base->head = e->next;
 178     }
 179     else {
 180         // not found
 181
 182         // create it
 183         e = callocz(1, sizeof(ARL_ENTRY));
 184         e->name = strdupz(s);
 185         e->hash = hash;
 186         e->flags = ARL_ENTRY_FLAG_DYNAMIC;
 187
 188         base->allocated++;
 189         base->added++;
 190     }
 191
 192 #ifdef NETDATA_INTERNAL_CHECKS
 193     if(unlikely(base->iteration % 60 == 0 && e->flags & ARL_ENTRY_FLAG_FOUND))
 194         info("ARL '%s': entry '%s' is already found. Did you forget to call arl_begin()?", base->name, s);
 195 #endif
 196
 197     e->flags |= ARL_ENTRY_FLAG_FOUND;
 198
 199     // link it here
 200     e->next = base->next_keyword;
 201     if(base->next_keyword) {
 202         e->prev = base->next_keyword->prev;
 203         base->next_keyword->prev = e;
 204
 205         if(e->prev)
 206             e->prev->next = e;
 207
 208         if(base->head == base->next_keyword)
 209             base->head = e;
 210     }
 211     else
 212         e->prev = NULL;
 213
 214     base->next_keyword = e->next;
 215     if(unlikely(!base->next_keyword))
 216         base->next_keyword = base->head;
 217
 218     if(unlikely(base->found == base->wanted))
 219         return 1;
 220
 221     return 0;
 222 }