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, fred %zu, relinkings %zu, found %zu, added %zu, fast %zu, slow %zu"
  55          , base->iteration
  56          , base->expected
  57          , base->wanted
  58          , base->allocated
  59          , base->fred
  60          , base->relinkings
  61          , base->found
  62          , base->added
  63          , base->fast
  64          , base->slow
  65     );
  66     for(e = base->head; e ; e = e->next) fprintf(stderr, "%s ", e->name);
  67     fprintf(stderr, "\n");
  68      */
  69
  70     if(unlikely(base->added || base->iteration % base->rechecks) == 1) {
  71         base->added = 0;
  72         base->wanted = 0;
  73         for(e = base->head; e ; e = e->next) {
  74             if(e->flags & ARL_ENTRY_FLAG_FOUND) {
  75
  76                 // remove the found flag
  77                 e->flags &= ~ARL_ENTRY_FLAG_FOUND;
  78
  79                 // count it in wanted
  80                 if(e->flags & ARL_ENTRY_FLAG_EXPECTED)
  81                     base->wanted++;
  82             }
  83             else if(e->flags & ARL_ENTRY_FLAG_DYNAMIC) {
  84                 // we can remove this entry
  85                 // it is not found, and it was created because
  86                 // it was found in the source file
  87                 if(e->next) e->next->prev = e->prev;
  88                 if(e->prev) e->prev->next = e->next;
  89                 if(base->head == e) base->head = e->next;
  90                 freez(e->name);
  91                 freez(e);
  92
  93                 base->fred++;
  94             }
  95         }
  96     }
  97
  98     base->iteration++;
  99     base->next_keyword = base->head;
 100     base->found = 0;
 101 }
 102
 103 // register an expected keyword to the ARL
 104 // together with its destination ( i.e. the output of the processor() )
 105 ARL_ENTRY *arl_expect(ARL_BASE *base, const char *keyword, void *dst) {
 106     ARL_ENTRY *e = callocz(1, sizeof(ARL_ENTRY));
 107     e->name = strdupz(keyword);
 108     e->hash = simple_hash(e->name);
 109     e->dst = dst;
 110     e->flags = ARL_ENTRY_FLAG_EXPECTED;
 111     e->prev = NULL;
 112     e->next = base->head;
 113
 114     if(base->head) base->head->prev = e;
 115     else base->next_keyword = e;
 116
 117     base->head = e;
 118     base->expected++;
 119     base->allocated++;
 120
 121     base->wanted = base->expected;
 122
 123     return e;
 124 }
 125
 126 int arl_find_or_create_and_relink(ARL_BASE *base, const char *s, const char *value) {
 127     ARL_ENTRY *e;
 128
 129     uint32_t hash = simple_hash(s);
 130
 131     // find if it already exists in the data
 132     for(e = base->head; e ; e = e->next)
 133         if(e->hash == hash && !strsame(e->name, s))
 134             break;
 135
 136 #ifdef NETDATA_INTERNAL_CHECKS
 137     if(unlikely(e == base->next_keyword))
 138         fatal("Internal Error: e == base->last");
 139 #endif
 140
 141     if(e) {
 142         // found it in the keywords
 143         base->relinkings++;
 144
 145         // run the processor for it
 146         if(unlikely(e->dst)) {
 147             base->processor(e->name, hash, value, e->dst);
 148             base->found++;
 149         }
 150
 151         // unlink it - we will relink it below
 152         if(e->next) e->next->prev = e->prev;
 153         if(e->prev) e->prev->next = e->next;
 154
 155         // make sure the head is properly linked
 156         if(base->head == e)
 157             base->head = e->next;
 158     }
 159     else {
 160         // not found
 161
 162         // create it
 163         e = callocz(1, sizeof(ARL_ENTRY));
 164         e->name = strdupz(s);
 165         e->hash = hash;
 166         e->flags = ARL_ENTRY_FLAG_DYNAMIC;
 167
 168         base->allocated++;
 169         base->added++;
 170     }
 171
 172     e->flags |= ARL_ENTRY_FLAG_FOUND;
 173
 174     // link it here
 175     e->next = base->next_keyword;
 176     if(base->next_keyword) {
 177         e->prev = base->next_keyword->prev;
 178         base->next_keyword->prev = e;
 179
 180         if(e->prev)
 181             e->prev->next = e;
 182
 183         if(base->head == base->next_keyword)
 184             base->head = e;
 185     }
 186     else
 187         e->prev = NULL;
 188
 189     base->next_keyword = e->next;
 190     if(unlikely(!base->next_keyword))
 191         base->next_keyword = base->head;
 192
 193     if(unlikely(base->found == base->wanted))
 194         return 1;
 195
 196     return 0;
 197 }