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(void (*processor)(const char *, uint32_t, const char *, void *), size_t rechecks) {
  16     ARL_BASE *base = callocz(1, sizeof(ARL_BASE));
  17
  18     if(!processor)
  19         base->processor = arl_callback_str2ull;
  20     else
  21         base->processor = processor;
  22
  23     base->rechecks = rechecks;
  24
  25     return base;
  26 }
  27
  28 void arl_free(ARL_BASE *arl_base) {
  29     if(unlikely(!arl_base))
  30         return;
  31
  32     while(arl_base->head) {
  33         ARL_ENTRY *e = arl_base->head;
  34         arl_base->head = e->next;
  35
  36         freez(e->name);
  37 #ifdef NETDATA_INTERNAL_CHECKS
  38         memset(e, 0, sizeof(ARL_ENTRY));
  39 #endif
  40         freez(e);
  41     }
  42
  43 #ifdef NETDATA_INTERNAL_CHECKS
  44     memset(arl_base, 0, sizeof(ARL_BASE));
  45 #endif
  46
  47     freez(arl_base);
  48 }
  49
  50 void arl_begin(ARL_BASE *base) {
  51     ARL_ENTRY *e;
  52
  53     /*
  54     info("iteration %zu, expected %zu, wanted %zu, allocated %zu, relinkings %zu, found %zu, added %zu"
  55          , base->iteration
  56          , base->expected
  57          , base->wanted
  58          , base->allocated
  59          , base->relinkings
  60          , base->found
  61          , base->added
  62     );
  63     for(e = base->head; e ; e = e->next) fprintf(stderr, "%s ", e->name);
  64     fprintf(stderr, "\n");
  65      */
  66
  67     if(unlikely(base->added || base->iteration % base->rechecks) == 1) {
  68         base->added = 0;
  69         base->wanted = 0;
  70         for(e = base->head; e ; e = e->next)
  71             if(e->flags & ARL_ENTRY_FLAG_FOUND && e->flags & ARL_ENTRY_FLAG_EXPECTED)
  72                 base->wanted++;
  73     }
  74
  75     base->iteration++;
  76     base->next_keyword = base->head;
  77     base->found = 0;
  78 }
  79
  80 // register an expected keyword to the ARL
  81 // together with its destination ( i.e. the output of the processor() )
  82 ARL_ENTRY *arl_expect(ARL_BASE *base, const char *keyword, void *dst) {
  83     ARL_ENTRY *e = callocz(1, sizeof(ARL_ENTRY));
  84     e->name = strdupz(keyword);
  85     e->hash = simple_hash(e->name);
  86     e->dst = dst;
  87     e->flags = ARL_ENTRY_FLAG_EXPECTED;
  88     e->prev = NULL;
  89     e->next = base->head;
  90
  91     if(base->head) base->head->prev = e;
  92     else base->next_keyword = e;
  93
  94     base->head = e;
  95     base->expected++;
  96     base->allocated++;
  97
  98     base->wanted = base->expected;
  99
 100     return e;
 101 }
 102
 103 int arl_find_or_create_and_relink(ARL_BASE *base, const char *s, uint32_t hash, const char *value) {
 104     ARL_ENTRY *e;
 105
 106     // find if it already exists in the data
 107     for(e = base->head; e ; e = e->next)
 108         if(e->hash == hash && !strcmp(e->name, s))
 109             break;
 110
 111 #ifdef NETDATA_INTERNAL_CHECKS
 112     if(unlikely(e == base->next_keyword))
 113         fatal("Internal Error: e == base->last");
 114 #endif
 115
 116     if(e) {
 117         // found it in the keywords
 118         base->relinkings++;
 119
 120         // run the processor for it
 121         if(unlikely(e->dst)) {
 122             base->processor(e->name, hash, value, e->dst);
 123             base->found++;
 124         }
 125
 126         // unlink it - we will relink it below
 127         if(e->next) e->next->prev = e->prev;
 128         if(e->prev) e->prev->next = e->next;
 129
 130         // make sure the head is properly linked
 131         if(base->head == e)
 132             base->head = e->next;
 133     }
 134     else {
 135         // not found
 136
 137         // create it
 138         e = callocz(1, sizeof(ARL_ENTRY));
 139         e->name = strdupz(s);
 140         e->hash = hash;
 141         e->flags = ARL_ENTRY_FLAG_DYNAMIC;
 142
 143         base->allocated++;
 144         base->added++;
 145     }
 146
 147     e->flags |= ARL_ENTRY_FLAG_FOUND;
 148
 149     // link it here
 150     e->next = base->next_keyword;
 151     if(base->next_keyword) {
 152         e->prev = base->next_keyword->prev;
 153         base->next_keyword->prev = e;
 154
 155         if(base->head == base->next_keyword)
 156             base->head = e;
 157     }
 158     else
 159         e->prev = NULL;
 160
 161     if(e->prev)
 162         e->prev->next = e;
 163
 164     base->next_keyword = e->next;
 165     if(unlikely(!base->next_keyword))
 166         base->next_keyword = base->head;
 167
 168     if(unlikely(base->found == base->wanted))
 169         return 1;
 170
 171     return 0;
 172 }