diff options
Diffstat (limited to 'libnetdata/july/july.c')
| -rw-r--r-- | libnetdata/july/july.c | 453 |
1 files changed, 0 insertions, 453 deletions
diff --git a/libnetdata/july/july.c b/libnetdata/july/july.c deleted file mode 100644 index 56b8494b3..000000000 --- a/libnetdata/july/july.c +++ /dev/null @@ -1,453 +0,0 @@ -// SPDX-License-Identifier: GPL-3.0-or-later - -#include "july.h" - -#define JULYL_MIN_ENTRIES 10 - -struct JulyL_item { - Word_t index; - void *value; -}; - -struct JulyL { - size_t entries; - size_t used; - - // statistics - size_t bytes; - size_t bytes_moved; - size_t reallocs; - - struct { - struct JulyL *prev; - struct JulyL *next; - } cache; - - struct JulyL_item array[]; -}; - -// ---------------------------------------------------------------------------- -// JulyL cache - -static struct { - struct { - SPINLOCK spinlock; - struct JulyL *available_items; - size_t available; - } protected; - - struct { - size_t bytes; - size_t allocated; - size_t bytes_moved; - size_t reallocs; - } atomics; -} julyl_globals = { - .protected = { - .spinlock = NETDATA_SPINLOCK_INITIALIZER, - .available_items = NULL, - .available = 0, - }, - .atomics = { - .bytes = 0, - .allocated = 0, - .bytes_moved = 0, - .reallocs = 0, - }, -}; - -void julyl_cleanup1(void) { - struct JulyL *item = NULL; - - if(!spinlock_trylock(&julyl_globals.protected.spinlock)) - return; - - if(julyl_globals.protected.available_items && julyl_globals.protected.available > 10) { - item = julyl_globals.protected.available_items; - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(julyl_globals.protected.available_items, item, cache.prev, cache.next); - julyl_globals.protected.available--; - } - - spinlock_unlock(&julyl_globals.protected.spinlock); - - if(item) { - size_t bytes = item->bytes; - freez(item); - __atomic_sub_fetch(&julyl_globals.atomics.bytes, bytes, __ATOMIC_RELAXED); - __atomic_sub_fetch(&julyl_globals.atomics.allocated, 1, __ATOMIC_RELAXED); - } -} - -struct JulyL *julyl_get(void) { - struct JulyL *j; - - spinlock_lock(&julyl_globals.protected.spinlock); - - j = julyl_globals.protected.available_items; - if(likely(j)) { - DOUBLE_LINKED_LIST_REMOVE_ITEM_UNSAFE(julyl_globals.protected.available_items, j, cache.prev, cache.next); - julyl_globals.protected.available--; - } - - spinlock_unlock(&julyl_globals.protected.spinlock); - - if(unlikely(!j)) { - size_t bytes = sizeof(struct JulyL) + JULYL_MIN_ENTRIES * sizeof(struct JulyL_item); - j = mallocz(bytes); - j->bytes = bytes; - j->entries = JULYL_MIN_ENTRIES; - __atomic_add_fetch(&julyl_globals.atomics.bytes, bytes, __ATOMIC_RELAXED); - __atomic_add_fetch(&julyl_globals.atomics.allocated, 1, __ATOMIC_RELAXED); - } - - j->used = 0; - j->bytes_moved = 0; - j->reallocs = 0; - j->cache.next = j->cache.prev = NULL; - return j; -} - -static void julyl_release(struct JulyL *j) { - if(unlikely(!j)) return; - - __atomic_add_fetch(&julyl_globals.atomics.bytes_moved, j->bytes_moved, __ATOMIC_RELAXED); - __atomic_add_fetch(&julyl_globals.atomics.reallocs, j->reallocs, __ATOMIC_RELAXED); - - spinlock_lock(&julyl_globals.protected.spinlock); - DOUBLE_LINKED_LIST_APPEND_ITEM_UNSAFE(julyl_globals.protected.available_items, j, cache.prev, cache.next); - julyl_globals.protected.available++; - spinlock_unlock(&julyl_globals.protected.spinlock); -} - -size_t julyl_cache_size(void) { - return __atomic_load_n(&julyl_globals.atomics.bytes, __ATOMIC_RELAXED); -} - -size_t julyl_bytes_moved(void) { - return __atomic_load_n(&julyl_globals.atomics.bytes_moved, __ATOMIC_RELAXED); -} - -// ---------------------------------------------------------------------------- -// JulyL - -size_t JulyLGet_binary_search_position_of_index(const struct JulyL *July, Word_t Index) { - // return the position of the first item >= Index - - size_t left = 0; - size_t right = July->used; - while(left < right) { - size_t middle = (left + right) >> 1; - - if(July->array[middle].index > Index) - right = middle; - - else - left = middle + 1; - } - - internal_fatal(left > July->used, "JULY: invalid position returned"); - - if(left > 0 && July->array[left - 1].index == Index) - return left - 1; - - internal_fatal( (left < July->used && July->array[left].index < Index) || - (left > 0 && July->array[left - 1].index >= Index) - , "JULY: wrong item returned"); - - return left; -} - -PPvoid_t JulyLGet(Pcvoid_t PArray, Word_t Index, PJError_t PJError __maybe_unused) { - const struct JulyL *July = PArray; - if(!July) - return NULL; - - size_t pos = JulyLGet_binary_search_position_of_index(July, Index); - - if(unlikely(pos >= July->used || July->array[pos].index != Index)) - return NULL; - - return (PPvoid_t)&July->array[pos].value; -} - -PPvoid_t JulyLIns(PPvoid_t PPArray, Word_t Index, PJError_t PJError __maybe_unused) { - struct JulyL *July = *PPArray; - if(unlikely(!July)) { - July = julyl_get(); - July->used = 0; - *PPArray = July; - } - - size_t pos = JulyLGet_binary_search_position_of_index(July, Index); - - if((pos == July->used || July->array[pos].index != Index)) { - // we have to add this entry - - if (unlikely(July->used == July->entries)) { - // we have to expand the array - size_t bytes = sizeof(struct JulyL) + July->entries * 2 * sizeof(struct JulyL_item); - __atomic_add_fetch(&julyl_globals.atomics.bytes, bytes - July->bytes, __ATOMIC_RELAXED); - July = reallocz(July, bytes); - July->bytes = bytes; - July->entries *= 2; - July->reallocs++; - *PPArray = July; - } - - if (unlikely(pos != July->used)) { - // we have to shift some members to make room - size_t size = (July->used - pos) * sizeof(struct JulyL_item); - memmove(&July->array[pos + 1], &July->array[pos], size); - July->bytes_moved += size; - } - - July->used++; - July->array[pos].value = NULL; - July->array[pos].index = Index; - } - - return &July->array[pos].value; -} - -PPvoid_t JulyLFirst(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) { - const struct JulyL *July = PArray; - if(!July) - return NULL; - - size_t pos = JulyLGet_binary_search_position_of_index(July, *Index); - // pos is >= Index - - if(unlikely(pos == July->used)) - return NULL; - - *Index = July->array[pos].index; - return (PPvoid_t)&July->array[pos].value; -} - -PPvoid_t JulyLNext(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) { - const struct JulyL *July = PArray; - if(!July) - return NULL; - - size_t pos = JulyLGet_binary_search_position_of_index(July, *Index); - // pos is >= Index - - if(unlikely(pos == July->used)) - return NULL; - - if(July->array[pos].index == *Index) { - pos++; - - if(unlikely(pos == July->used)) - return NULL; - } - - *Index = July->array[pos].index; - return (PPvoid_t)&July->array[pos].value; -} - -PPvoid_t JulyLLast(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) { - const struct JulyL *July = PArray; - if(!July) - return NULL; - - size_t pos = JulyLGet_binary_search_position_of_index(July, *Index); - // pos is >= Index - - if(pos > 0 && (pos == July->used || July->array[pos].index > *Index)) - pos--; - - if(unlikely(pos == 0 && July->array[0].index > *Index)) - return NULL; - - *Index = July->array[pos].index; - return (PPvoid_t)&July->array[pos].value; -} - -PPvoid_t JulyLPrev(Pcvoid_t PArray, Word_t *Index, PJError_t PJError __maybe_unused) { - const struct JulyL *July = PArray; - if(!July) - return NULL; - - size_t pos = JulyLGet_binary_search_position_of_index(July, *Index); - // pos is >= Index - - if(unlikely(pos == 0 || July->used == 0)) - return NULL; - - // get the previous one - pos--; - - *Index = July->array[pos].index; - return (PPvoid_t)&July->array[pos].value; -} - -Word_t JulyLFreeArray(PPvoid_t PPArray, PJError_t PJError __maybe_unused) { - struct JulyL *July = *PPArray; - if(unlikely(!July)) - return 0; - - size_t bytes = July->bytes; - julyl_release(July); - *PPArray = NULL; - return bytes; -} - -// ---------------------------------------------------------------------------- -// unittest - -#define item_index(i) (((i) * 2) + 100) - -int julytest(void) { - Word_t entries = 10000; - Pvoid_t array = NULL; - - // test additions - for(Word_t i = 0; i < entries ;i++) { - Pvoid_t *PValue = JulyLIns(&array, item_index(i), PJE0); - if(!PValue) - fatal("JULY: cannot insert item %lu", item_index(i)); - - *PValue = (void *)(item_index(i)); - } - - // test successful finds - for(Word_t i = 0; i < entries ;i++) { - Pvoid_t *PValue = JulyLGet(array, item_index(i), PJE0); - if(!PValue) - fatal("JULY: cannot find item %lu", item_index(i)); - - if(*PValue != (void *)(item_index(i))) - fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue)); - } - - // test finding the first item - for(Word_t i = 0; i < entries ;i++) { - Word_t index = item_index(i); - Pvoid_t *PValue = JulyLFirst(array, &index, PJE0); - if(!PValue) - fatal("JULY: cannot find first item %lu", item_index(i)); - - if(*PValue != (void *)(item_index(i))) - fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue)); - - if(index != item_index(i)) - fatal("JULY: item %lu has index %lu", item_index(i), index); - } - - // test finding the next item - for(Word_t i = 0; i < entries - 1 ;i++) { - Word_t index = item_index(i); - Pvoid_t *PValue = JulyLNext(array, &index, PJE0); - if(!PValue) - fatal("JULY: cannot find next item %lu", item_index(i)); - - if(*PValue != (void *)(item_index(i + 1))) - fatal("JULY: item %lu next has the value %lu", item_index(i), (unsigned long)(*PValue)); - - if(index != item_index(i + 1)) - fatal("JULY: item %lu next has index %lu", item_index(i), index); - } - - // test finding the last item - for(Word_t i = 0; i < entries ;i++) { - Word_t index = item_index(i); - Pvoid_t *PValue = JulyLLast(array, &index, PJE0); - if(!PValue) - fatal("JULY: cannot find last item %lu", item_index(i)); - - if(*PValue != (void *)(item_index(i))) - fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue)); - - if(index != item_index(i)) - fatal("JULY: item %lu has index %lu", item_index(i), index); - } - - // test finding the prev item - for(Word_t i = 1; i < entries ;i++) { - Word_t index = item_index(i); - Pvoid_t *PValue = JulyLPrev(array, &index, PJE0); - if(!PValue) - fatal("JULY: cannot find prev item %lu", item_index(i)); - - if(*PValue != (void *)(item_index(i - 1))) - fatal("JULY: item %lu prev has the value %lu", item_index(i), (unsigned long)(*PValue)); - - if(index != item_index(i - 1)) - fatal("JULY: item %lu prev has index %lu", item_index(i), index); - } - - // test full traversal forward - { - Word_t i = 0; - Word_t index = 0; - bool first = true; - Pvoid_t *PValue; - while((PValue = JulyLFirstThenNext(array, &index, &first))) { - if(*PValue != (void *)(item_index(i))) - fatal("JULY: item %lu traversal has the value %lu", item_index(i), (unsigned long)(*PValue)); - - if(index != item_index(i)) - fatal("JULY: item %lu traversal has index %lu", item_index(i), index); - - i++; - } - - if(i != entries) - fatal("JULY: expected to forward traverse %lu entries, but traversed %lu", entries, i); - } - - // test full traversal backward - { - Word_t i = 0; - Word_t index = (Word_t)(-1); - bool first = true; - Pvoid_t *PValue; - while((PValue = JulyLLastThenPrev(array, &index, &first))) { - if(*PValue != (void *)(item_index(entries - i - 1))) - fatal("JULY: item %lu traversal has the value %lu", item_index(i), (unsigned long)(*PValue)); - - if(index != item_index(entries - i - 1)) - fatal("JULY: item %lu traversal has index %lu", item_index(i), index); - - i++; - } - - if(i != entries) - fatal("JULY: expected to back traverse %lu entries, but traversed %lu", entries, i); - } - - // test finding non-existing first item - for(Word_t i = 0; i < entries ;i++) { - Word_t index = item_index(i) - 1; - Pvoid_t *PValue = JulyLFirst(array, &index, PJE0); - if(!PValue) - fatal("JULY: cannot find first item %lu", item_index(i) - 1); - - if(*PValue != (void *)(item_index(i))) - fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue)); - - if(index != item_index(i)) - fatal("JULY: item %lu has index %lu", item_index(i), index); - } - - // test finding non-existing last item - for(Word_t i = 0; i < entries ;i++) { - Word_t index = item_index(i) + 1; - Pvoid_t *PValue = JulyLLast(array, &index, PJE0); - if(!PValue) - fatal("JULY: cannot find last item %lu", item_index(i) + 1); - - if(*PValue != (void *)(item_index(i))) - fatal("JULY: item %lu has the value %lu", item_index(i), (unsigned long)(*PValue)); - - if(index != item_index(i)) - fatal("JULY: item %lu has index %lu", item_index(i), index); - } - - JulyLFreeArray(&array, PJE0); - - return 0; -} - - |