An implementation of JudyL with fewer memory allocations, when items are mainly appended to the array

JulyL.c

// 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_cleanup(void) {
    netdata_spinlock_lock(&julyl_globals.protected.spinlock);

    while(julyl_globals.protected.available_items && julyl_globals.protected.available > 10) {
        struct JulyL *item = julyl_globals.protected.available_items;
        DOUBLE_LINKED_LIST_REMOVE_UNSAFE(julyl_globals.protected.available_items, item, cache.prev, cache.next);
        size_t bytes = item->bytes;
        freez(item);
        julyl_globals.protected.available--;
        __atomic_sub_fetch(&julyl_globals.atomics.bytes, bytes, __ATOMIC_RELAXED);
        __atomic_sub_fetch(&julyl_globals.atomics.allocated, 1, __ATOMIC_RELAXED);
    }

    netdata_spinlock_unlock(&julyl_globals.protected.spinlock);
}

struct JulyL *julyl_get(void) {
    struct JulyL *j;

    netdata_spinlock_lock(&julyl_globals.protected.spinlock);

    j = julyl_globals.protected.available_items;
    if(likely(j)) {
        DOUBLE_LINKED_LIST_REMOVE_UNSAFE(julyl_globals.protected.available_items, j, cache.prev, cache.next);
        julyl_globals.protected.available--;
    }

    netdata_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);

    netdata_spinlock_lock(&julyl_globals.protected.spinlock);
    DOUBLE_LINKED_LIST_APPEND_UNSAFE(julyl_globals.protected.available_items, j, cache.prev, cache.next);
    julyl_globals.protected.available++;
    netdata_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;
}