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