summaryrefslogtreecommitdiffstats
path: root/libnetdata/july
diff options
context:
space:
mode:
Diffstat (limited to 'libnetdata/july')
-rw-r--r--libnetdata/july/Makefile.am8
-rw-r--r--libnetdata/july/README.md14
-rw-r--r--libnetdata/july/july.c453
-rw-r--r--libnetdata/july/july.h40
4 files changed, 515 insertions, 0 deletions
diff --git a/libnetdata/july/Makefile.am b/libnetdata/july/Makefile.am
new file mode 100644
index 00000000..161784b8
--- /dev/null
+++ b/libnetdata/july/Makefile.am
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+AUTOMAKE_OPTIONS = subdir-objects
+MAINTAINERCLEANFILES = $(srcdir)/Makefile.in
+
+dist_noinst_DATA = \
+ README.md \
+ $(NULL)
diff --git a/libnetdata/july/README.md b/libnetdata/july/README.md
new file mode 100644
index 00000000..99584912
--- /dev/null
+++ b/libnetdata/july/README.md
@@ -0,0 +1,14 @@
+<!--
+custom_edit_url: https://github.com/netdata/netdata/edit/master/libnetdata/july/README.md
+sidebar_label: "July interface"
+learn_status: "Published"
+learn_topic_type: "Tasks"
+learn_rel_path: "Developers/libnetdata"
+-->
+
+
+# July
+
+An interface similar to `Judy` that uses minimal allocations (that can be cached)
+for items that are mainly appended (just a few insertions in the middle)
+
diff --git a/libnetdata/july/july.c b/libnetdata/july/july.c
new file mode 100644
index 00000000..56b8494b
--- /dev/null
+++ b/libnetdata/july/july.c
@@ -0,0 +1,453 @@
+// 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;
+}
+
+
diff --git a/libnetdata/july/july.h b/libnetdata/july/july.h
new file mode 100644
index 00000000..672ed44e
--- /dev/null
+++ b/libnetdata/july/july.h
@@ -0,0 +1,40 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef NETDATA_JULY_H
+#define NETDATA_JULY_H 1
+
+#include "../libnetdata.h"
+
+// #define PDC_USE_JULYL 1
+
+PPvoid_t JulyLGet(Pcvoid_t PArray, Word_t Index, PJError_t PJError);
+PPvoid_t JulyLIns(PPvoid_t PPArray, Word_t Index, PJError_t PJError);
+PPvoid_t JulyLFirst(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+PPvoid_t JulyLNext(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+PPvoid_t JulyLLast(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+PPvoid_t JulyLPrev(Pcvoid_t PArray, Word_t *Index, PJError_t PJError);
+Word_t JulyLFreeArray(PPvoid_t PPArray, PJError_t PJError);
+
+static inline PPvoid_t JulyLFirstThenNext(Pcvoid_t PArray, Word_t * PIndex, bool *first) {
+ if(unlikely(*first)) {
+ *first = false;
+ return JulyLFirst(PArray, PIndex, PJE0);
+ }
+
+ return JulyLNext(PArray, PIndex, PJE0);
+}
+
+static inline PPvoid_t JulyLLastThenPrev(Pcvoid_t PArray, Word_t * PIndex, bool *first) {
+ if(unlikely(*first)) {
+ *first = false;
+ return JulyLLast(PArray, PIndex, PJE0);
+ }
+
+ return JulyLPrev(PArray, PIndex, PJE0);
+}
+
+void julyl_cleanup1(void);
+size_t julyl_cache_size(void);
+size_t julyl_bytes_moved(void);
+
+#endif // NETDATA_JULY_H
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-04 09:44:29 +0000