diff options
author | Lennart Weller <lhw@ring0.de> | 2017-01-24 15:21:09 +0000 |
---|---|---|
committer | Lennart Weller <lhw@ring0.de> | 2017-01-24 15:21:09 +0000 |
commit | 3ed3b02ed96ddab1c084811f3579b3a2aec83e04 (patch) | |
tree | 7a61ab288ae47800c4f11be5677d6ad8288dcd98 /src/adaptive_resortable_list.h | |
parent | New upstream version 1.4.0+dfsg (diff) | |
download | netdata-846b62730cc46cdb088594ab8a1548209cdc1b57.tar.xz netdata-846b62730cc46cdb088594ab8a1548209cdc1b57.zip |
New upstream version 1.5.0+dfsgupstream/1.5.0+dfsg
Diffstat (limited to 'src/adaptive_resortable_list.h')
-rw-r--r-- | src/adaptive_resortable_list.h | 162 |
1 files changed, 162 insertions, 0 deletions
diff --git a/src/adaptive_resortable_list.h b/src/adaptive_resortable_list.h new file mode 100644 index 000000000..609cd0c43 --- /dev/null +++ b/src/adaptive_resortable_list.h @@ -0,0 +1,162 @@ +#ifndef NETDATA_ADAPTIVE_RESORTABLE_LIST_H +#define NETDATA_ADAPTIVE_RESORTABLE_LIST_H + +/* + * ADAPTIVE RE-SORTABLE LIST + * This structure allows netdata to read a file of NAME VALUE lines + * in the fastest possible way. + * + * It maintains a linked list of all NAME (keywords), sorted in the + * same order as found in the source data file. + * The linked list is kept sorted at all times - the source file + * may change at any time, the list will adapt. + * + * The caller: + * + * 1. calls arl_create() to create a list + * + * 2. calls arl_expect() to register the expected keyword + * + * Then: + * + * 3. calls arl_begin() to initiate a data collection iteration. + * This is to be called just ONCE every time the source is re-scanned. + * + * 4. calls arl_check() for each line read from the file. + * + * Finally: + * + * 5. calls arl_free() to destroy this and free all memory. + * + * The program will call the processor() function, given to + * arl_create(), for each expected keyword found. + * The default processor() expects dst to be an unsigned long long *. + * + * LIMITATIONS + * DO NOT USE THIS IF THE A NAME/KEYWORD MAY APPEAR MORE THAN + * ONCE IN THE SOURCE DATA SET. + */ + +#include "common.h" + +#define ARL_ENTRY_FLAG_FOUND 0x01 // the entry has been found in the source data +#define ARL_ENTRY_FLAG_EXPECTED 0x02 // the entry is expected by the program +#define ARL_ENTRY_FLAG_DYNAMIC 0x04 // the entry was dynamically allocated, from source data + +typedef struct arl_entry { + char *name; // the keywords + uint32_t hash; // the hash of the keyword + + void *dst; // the dst to pass to the processor + + uint8_t flags; // ARL_ENTRY_FLAG_* + + // double linked list for fast re-linkings + struct arl_entry *prev, *next; +} ARL_ENTRY; + +typedef struct arl_base { + char *name; + + size_t iteration; // incremented on each iteration (arl_begin()) + size_t found; // the number of expected keywords found in this iteration + size_t expected; // the number of expected keywords + size_t wanted; // the number of wanted keywords + // i.e. the number of keywords found and expected + + size_t relinkings; // the number of relinkings we have made so far + + size_t allocated; // the number of keywords allocated + size_t fred; // the number of keywords cleaned up + + size_t rechecks; // the number of iterations between re-checks of the + // wanted number of keywords + // this is only needed in cases where the source + // is having less lines over time. + + size_t added; // it is non-zero if new keywords have been added + // this is only needed to detect new lines have + // been added to the file, over time. + +#ifdef NETDATA_INTERNAL_CHECKS + size_t fast; // the number of times we have taken the fast path + size_t slow; // the number of times we have taken the slow path +#endif + + // the processor to do the job + void (*processor)(const char *name, uint32_t hash, const char *value, void *dst); + + // the linked list of the keywords + ARL_ENTRY *head; + + // since we keep the list of keywords sorted (as found in the source data) + // this is next keyword that we expect to find in the source data. + ARL_ENTRY *next_keyword; +} ARL_BASE; + +// create a new ARL +extern ARL_BASE *arl_create(const char *name, void (*processor)(const char *, uint32_t, const char *, void *), size_t rechecks); + +// free an ARL +extern void arl_free(ARL_BASE *arl_base); + +// register an expected keyword to the ARL +// together with its destination ( i.e. the output of the processor() ) +extern ARL_ENTRY *arl_expect(ARL_BASE *base, const char *keyword, void *dst); + +// an internal call to complete the check() call +extern int arl_find_or_create_and_relink(ARL_BASE *base, const char *s, const char *value); + +// begin an ARL iteration +extern void arl_begin(ARL_BASE *base); + +// check a keyword against the ARL +// this is to be called for each keyword read from source data +// s = the keyword, as collected +// src = the src data to be passed to the processor +// it is defined in the header file in order to be inlined +static inline int arl_check(ARL_BASE *base, const char *keyword, const char *value) { + ARL_ENTRY *e = base->next_keyword; + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely((base->fast + base->slow) % (base->expected + base->allocated) == 0 && (base->fast + base->slow) > (base->expected + base->allocated) * base->iteration)) + info("ARL '%s': Did you forget to call arl_begin()?", base->name); +#endif + + // it should be the first entry (pointed by base->next_keyword) + if(likely(!strcmp(keyword, e->name))) { + // it is + +#ifdef NETDATA_INTERNAL_CHECKS + base->fast++; +#endif + + e->flags |= ARL_ENTRY_FLAG_FOUND; + + // execute the processor + if(unlikely(e->dst)) { + base->processor(e->name, e->hash, value, e->dst); + base->found++; + } + + // be prepared for the next iteration + base->next_keyword = e->next; + if(unlikely(!base->next_keyword)) + base->next_keyword = base->head; + + // stop if we collected all the values for this iteration + if(unlikely(base->found == base->wanted)) + return 1; + + return 0; + } + +#ifdef NETDATA_INTERNAL_CHECKS + base->slow++; +#endif + + // we read from source, a not-expected keyword + return arl_find_or_create_and_relink(base, keyword, value); +} + +#endif //NETDATA_ADAPTIVE_RESORTABLE_LIST_H |