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
  56 #ifdef NETDATA_INTERNAL_CHECKS
  57     if(likely(base->iteration > 10)) {
  58         // do these checks after the ARL has been sorted
  59
  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);
  63
  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);
  67
  68         if(unlikely(base->iteration % 60 == 0)) {
  69             info("ARL '%s' statistics: iteration %zu, expected %zu, wanted %zu, allocated %zu, fred %zu, relinkings %zu, found %zu, added %zu, fast %zu, slow %zu"
  70                  , base->name
  71                  , base->iteration
  72                  , base->expected
  73                  , base->wanted
  74                  , base->allocated
  75                  , base->fred
  76                  , base->relinkings
  77                  , base->found
  78                  , base->added
  79                  , base->fast
  80                  , base->slow
  81             );
  82             // for(e = base->head; e; e = e->next) fprintf(stderr, "%s ", e->name);
  83             // fprintf(stderr, "\n");
  84         }
  85     }
  86 #endif
  87
  88     if(unlikely(base->added || base->iteration % base->rechecks) == 1) {
  89         base->added = 0;
  90         base->wanted = 0;
  91         ARL_ENTRY *e = base->head;
  92         while(e) {
  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             }
 103             else if(e->flags & ARL_ENTRY_FLAG_DYNAMIC && !(base->head == e && !e->next)) { // not last entry
 104                 // we can remove this entry
 105                 // it is not found, and it was created because
 106                 // it was found in the source file
 107
 108                 // remember the next one
 109                 ARL_ENTRY *t = e->next;
 110
 111                 // remove it from the list
 112                 if(e->next) e->next->prev = e->prev;
 113                 if(e->prev) e->prev->next = e->next;
 114                 if(base->head == e) base->head = e->next;
 115
 116                 // free it
 117                 freez(e->name);
 118                 freez(e);
 119
 120                 // count it
 121                 base->fred++;
 122
 123                 // continue
 124                 e = t;
 125                 continue;
 126             }
 127
 128             e = e->next;
 129         }
 130     }
 131
 132     if(unlikely(!base->head)) {
 133         // hm... no nodes at all in the list #1700
 134         // add a fake one to prevent a crash
 135         // this is better than checking for the existence of nodes all the time
 136         arl_expect(base, "a-really-not-existing-source-keyword", NULL);
 137     }
 138
 139     base->iteration++;
 140     base->next_keyword = base->head;
 141     base->found = 0;
 142
 143 }
 144
 145 // register an expected keyword to the ARL
 146 // together with its destination ( i.e. the output of the processor() )
 147 ARL_ENTRY *arl_expect(ARL_BASE *base, const char *keyword, void *dst) {
 148     ARL_ENTRY *e = callocz(1, sizeof(ARL_ENTRY));
 149     e->name = strdupz(keyword);
 150     e->hash = simple_hash(e->name);
 151     e->dst = dst;
 152     e->flags = ARL_ENTRY_FLAG_EXPECTED;
 153     e->prev = NULL;
 154     e->next = base->head;
 155
 156     if(base->head) base->head->prev = e;
 157     else base->next_keyword = e;
 158
 159     base->head = e;
 160     base->expected++;
 161     base->allocated++;
 162
 163     base->wanted = base->expected;
 164
 165     return e;
 166 }
 167
 168 int arl_find_or_create_and_relink(ARL_BASE *base, const char *s, const char *value) {
 169     ARL_ENTRY *e;
 170
 171     uint32_t hash = simple_hash(s);
 172
 173     // find if it already exists in the data
 174     for(e = base->head; e ; e = e->next)
 175         if(e->hash == hash && !strcmp(e->name, s))
 176             break;
 177
 178 #ifdef NETDATA_INTERNAL_CHECKS
 179     if(unlikely(base->next_keyword && e == base->next_keyword))
 180         fatal("Internal Error: e == base->last");
 181 #endif
 182
 183     if(e) {
 184         // found it in the keywords
 185
 186         base->relinkings++;
 187
 188         // run the processor for it
 189         if(unlikely(e->dst)) {
 190             base->processor(e->name, hash, value, e->dst);
 191             base->found++;
 192         }
 193
 194         // unlink it - we will relink it below
 195         if(e->next) e->next->prev = e->prev;
 196         if(e->prev) e->prev->next = e->next;
 197
 198         // make sure the head is properly linked
 199         if(base->head == e)
 200             base->head = e->next;
 201     }
 202     else {
 203         // not found
 204
 205         // create it
 206         e = callocz(1, sizeof(ARL_ENTRY));
 207         e->name = strdupz(s);
 208         e->hash = hash;
 209         e->flags = ARL_ENTRY_FLAG_DYNAMIC;
 210
 211         base->allocated++;
 212         base->added++;
 213     }
 214
 215 #ifdef NETDATA_INTERNAL_CHECKS
 216     if(unlikely(base->iteration % 60 == 0 && e->flags & ARL_ENTRY_FLAG_FOUND))
 217         info("ARL '%s': entry '%s' is already found. Did you forget to call arl_begin()?", base->name, s);
 218 #endif
 219
 220     e->flags |= ARL_ENTRY_FLAG_FOUND;
 221
 222     // link it here
 223     e->next = base->next_keyword;
 224     if(base->next_keyword) {
 225         e->prev = base->next_keyword->prev;
 226         base->next_keyword->prev = e;
 227
 228         if(e->prev)
 229             e->prev->next = e;
 230
 231         if(base->head == base->next_keyword)
 232             base->head = e;
 233     }
 234     else
 235         e->prev = NULL;
 236
 237     base->next_keyword = e->next;
 238     if(unlikely(!base->next_keyword))
 239         base->next_keyword = base->head;
 240
 241     if(unlikely(base->found == base->wanted))
 242         return 1;
 243
 244     return 0;
 245 }