// SPDX-License-Identifier: GPL-3.0-or-later

#include "../libnetdata.h"
#include <Judy.h>

// ----------------------------------------------------------------------------
// STRING implementation - dedup all STRING

#define STRING_PARTITION_SHIFTS (0)
#define STRING_PARTITIONS (256 >> STRING_PARTITION_SHIFTS)
#define string_partition_str(str) ((uint8_t)((str)[0]) >> STRING_PARTITION_SHIFTS)
#define string_partition(string) (string_partition_str((string)->str))

struct netdata_string {
    uint32_t length;    // the string length including the terminating '\0'

    REFCOUNT refcount;  // how many times this string is used
                        // We use a signed number to be able to detect duplicate frees of a string.
                        // If at any point this goes below zero, we have a duplicate free.
                        
#ifdef FSANITIZE_ADDRESS
    STACKTRACE_ARRAY stacktraces;   // stack traces from all acquisition points
#endif

    const char str[];   // the string itself, is appended to this structure
};

static struct string_partition {
    RW_SPINLOCK spinlock;       // the R/W spinlock to protect the Judy array

    Pvoid_t JudyHSArray;        // the Judy array - hashtable

    size_t inserts;             // the number of successful inserts to the index
    size_t deletes;             // the number of successful deleted from the index

    long int entries;           // the number of entries in the index
    long int memory;            // the memory used
    long int memory_index;      // JudyHS (accurate)

#ifdef FSANITIZE_ADDRESS
    Pvoid_t JudyLPointers;      // JudyL array to keep track of all string pointers for traversal
#endif

#ifdef NETDATA_INTERNAL_CHECKS
    // internal statistics
    struct {
        size_t searches;            // the number of successful searches in the index
        size_t releases;            // when a string is unreferenced
        size_t duplications;        // when a string is referenced
        long int active_references; // the number of active references alive
    } atomic;

    size_t found_deleted_on_search;
    size_t found_available_on_search;
    size_t found_deleted_on_insert;
    size_t found_available_on_insert;
    size_t spins;
#endif

} string_base[STRING_PARTITIONS] = { 0 };

#ifdef NETDATA_INTERNAL_CHECKS
#define string_stats_atomic_increment(partition, var) __atomic_add_fetch(&string_base[partition].atomic.var, 1, __ATOMIC_RELAXED)
#define string_stats_atomic_decrement(partition, var) __atomic_sub_fetch(&string_base[partition].atomic.var, 1, __ATOMIC_RELAXED)
#define string_internal_stats_add(partition, var, val) __atomic_add_fetch(&string_base[partition].var, val, __ATOMIC_RELAXED)
#else
#define string_stats_atomic_increment(partition, var) do {;} while(0)
#define string_stats_atomic_decrement(partition, var) do {;} while(0)
#define string_internal_stats_add(partition, var, val) do {;} while(0)
#endif

void string_statistics(size_t *inserts, size_t *deletes, size_t *searches, size_t *entries, size_t *references, size_t *memory, size_t *memory_index, size_t *duplications, size_t *releases) {
    if (inserts) *inserts = 0;
    if (deletes) *deletes = 0;
    if (searches) *searches = 0;
    if (entries) *entries = 0;
    if (references) *references = 0;
    if (memory) *memory = 0;
    if (memory_index) *memory_index = 0;
    if (duplications) *duplications = 0;
    if (releases) *releases = 0;

    for(size_t i = 0; i < STRING_PARTITIONS ;i++) {
        if (inserts)        *inserts        += string_base[i].inserts;
        if (deletes)        *deletes        += string_base[i].deletes;
        if (entries)        *entries        += (size_t) string_base[i].entries;
        if (memory)         *memory         += (size_t) string_base[i].memory;
        if (memory_index)   *memory_index   += (string_base[i].memory_index > 0) ? string_base[i].memory_index : 0;

#ifdef NETDATA_INTERNAL_CHECKS
        if (searches)       *searches       += string_base[i].atomic.searches;
        if (references)     *references     += (size_t) string_base[i].atomic.active_references;
        if (duplications)   *duplications   += string_base[i].atomic.duplications;
        if (releases)       *releases       += string_base[i].atomic.releases;
#endif
    }
}

static inline bool string_entry_check_and_acquire(STRING *se) {
#ifdef NETDATA_INTERNAL_CHECKS
    uint8_t partition = string_partition(se);
#endif

    if(!refcount_acquire(&se->refcount))
        return false;

    // statistics
    // string_base.active_references is altered at the in string_strdupz() and string_freez()
    string_stats_atomic_increment(partition, duplications);

    return true;
}

ALWAYS_INLINE
STRING *string_dup(STRING *string) {
    if(unlikely(!string)) return NULL;

    if(!refcount_acquire(&string->refcount))
        fatal("STRING: tried to %s() a string that is deleted (refcount %d).", __FUNCTION__, string->refcount);

#ifdef NETDATA_INTERNAL_CHECKS
    uint8_t partition = string_partition(string);
#endif

#ifdef FSANITIZE_ADDRESS
    stacktrace_array_add(&string->stacktraces, 0);
#endif

    // statistics
    string_stats_atomic_increment(partition, active_references);
    string_stats_atomic_increment(partition, duplications);

    return string;
}

// Search the index and return an ACQUIRED string entry, or NULL
static STRING *string_index_search(const char *str, size_t length, uint8_t partition) {
    STRING *string;

    // Find the string in the index
    // With a read-lock so that multiple readers can use the index concurrently.

    rw_spinlock_read_lock(&string_base[partition].spinlock);

    Pvoid_t *Rc;
    Rc = JudyHSGet(string_base[partition].JudyHSArray, (void *)str, length - 1);
    if(likely(Rc)) {
        // found in the hash table
        string = *Rc;

        if(string_entry_check_and_acquire(string)) {
            // we can use this entry
            string_internal_stats_add(partition, found_available_on_search, 1);
        }
        else {
            // this entry is about to be deleted by another thread
            // do not touch it, let it go...
            string = NULL;
            string_internal_stats_add(partition, found_deleted_on_search, 1);
        }
    }
    else {
        // not found in the hash table
        string = NULL;
    }

    string_stats_atomic_increment(partition, searches);
    rw_spinlock_read_unlock(&string_base[partition].spinlock);

    return string;
}

// Insert a string to the index and return an ACQUIRED string entry,
// or NULL if the call needs to be retried (a deleted entry with the same key is still in the index)
// The returned entry is ACQUIRED, and it can either be:
//   1. a new item inserted, or
//   2. an item found in the index that is not currently deleted
static STRING *string_index_insert(const char *str, size_t length, uint8_t partition) {
    STRING *string;

    rw_spinlock_write_lock(&string_base[partition].spinlock);

    int64_t judy_mem = 0;

    STRING **ptr;
    {
        JError_t J_Error;

        JudyAllocThreadPulseReset();

        Pvoid_t *Rc = JudyHSIns(&string_base[partition].JudyHSArray, (void *)str, length - 1, &J_Error);

        judy_mem = JudyAllocThreadPulseGetAndReset();

        if (unlikely(Rc == PJERR)) {
            fatal(
                "STRING: Cannot insert entry to JudyHS, JU_ERRNO_* == %u, ID == %d",
                JU_ERRNO(&J_Error),
                JU_ERRID(&J_Error));
        }
        ptr = (STRING **)Rc;
    }

    if (likely(*ptr == 0)) {
        // a new item added to the index
        long mem_size = (long)sizeof(STRING) + (long)length;
        string = mallocz(mem_size);
        memcpy((char *)string->str, str, length - 1);
        ((char *)string->str)[length - 1] = '\0';
        string->length = length;
        string->refcount = 1;
        
#ifdef FSANITIZE_ADDRESS
        // Initialize stacktrace tracking
        stacktrace_array_init(&string->stacktraces);
        
        // Add to JudyL array for tracking strings by pointer
        Pvoid_t *PValue;
        PValue = JudyLIns(&string_base[partition].JudyLPointers, (Word_t)string, PJE0);
        if (PValue != PJERR)
            *PValue = (void *)1;  // Use a simple value of 1 for now
#endif
        
        *ptr = string;
        string_base[partition].inserts++;
        string_base[partition].entries++;
        string_base[partition].memory += mem_size;
        string_base[partition].memory_index += judy_mem;
    }
    else {
        // the item is already in the index
        string = *ptr;

        if(string_entry_check_and_acquire(string)) {
            // we can use this entry
            string_internal_stats_add(partition, found_available_on_insert, 1);
        }
        else {
            // this entry is about to be deleted by another thread
            // do not touch it, let it go...
            string = NULL;
            string_internal_stats_add(partition, found_deleted_on_insert, 1);
        }

        string_stats_atomic_increment(partition, searches);
    }

    rw_spinlock_write_unlock(&string_base[partition].spinlock);
    return string;
}

// delete an entry from the index
static void string_index_delete(STRING *string) {
    uint8_t partition = string_partition(string);

    rw_spinlock_write_lock(&string_base[partition].spinlock);

    bool deleted = false;
    int64_t judy_mem = 0;

    if (likely(string_base[partition].JudyHSArray)) {
        JError_t J_Error;

        JudyAllocThreadPulseReset();

        int ret = JudyHSDel(&string_base[partition].JudyHSArray, (void *)string->str, string->length - 1, &J_Error);

        judy_mem = JudyAllocThreadPulseGetAndReset();

        if (unlikely(ret == JERR)) {
            netdata_log_error(
                "STRING: Cannot delete entry with name '%s' from JudyHS, JU_ERRNO_* == %u, ID == %d",
                string->str,
                JU_ERRNO(&J_Error),
                JU_ERRID(&J_Error));
        } else
            deleted = true;
    }

    if (unlikely(!deleted))
        netdata_log_error("STRING: tried to delete '%s' that is not in the index. Ignoring it.", string->str);
    else {
        long mem_size = (long)sizeof(STRING) + (long)string->length;
        string_base[partition].deletes++;
        string_base[partition].entries--;
        string_base[partition].memory -= mem_size;
        string_base[partition].memory_index += judy_mem;
        
#ifdef FSANITIZE_ADDRESS
        // Remove from the JudyL array if it exists
        if (string_base[partition].JudyLPointers)
            JudyLDel(&string_base[partition].JudyLPointers, (Word_t)string, PJE0);
#endif
        
        freez(string);
    }

    rw_spinlock_write_unlock(&string_base[partition].spinlock);
}

ALWAYS_INLINE
STRING *string_strdupz(const char *str) {
    size_t length = 0;
    if(likely(str))
        length = strlen(str);

    if(unlikely(!length)) return NULL;

    length++;
    uint8_t partition = string_partition_str(str);
    STRING *string = string_index_search(str, length, partition);

    while(!string) {
        // The search above did not find anything,
        // We loop here, because during insert we may find an entry that is being deleted by another thread.
        // So, we have to let it go and retry to insert it again.

        string = string_index_insert(str, length, partition);
    }

    // statistics
    string_stats_atomic_increment(partition, active_references);

#ifdef FSANITIZE_ADDRESS
    // Add a stacktrace for this acquisition point too
    stacktrace_array_add(&string->stacktraces, 0);
#endif

    return string;
}

ALWAYS_INLINE
STRING *string_strndupz(const char *str, size_t len) {
    if(unlikely(!str || !*str || !len)) return NULL;

    uint8_t partition = string_partition_str(str);

    STRING *string = string_index_search(str, len + 1, partition);
    while(!string)
        string = string_index_insert(str, len + 1, partition);

    string_stats_atomic_increment(partition, active_references);

#ifdef FSANITIZE_ADDRESS
    // Add a stacktrace for this acquisition point too
    stacktrace_array_add(&string->stacktraces, 0);
#endif

    return string;
}

ALWAYS_INLINE
void string_freez(STRING *string) {
    if(unlikely(!string)) return;

#ifdef NETDATA_INTERNAL_CHECKS
    uint8_t partition = string_partition(string);
#endif

    if(unlikely(refcount_release_and_acquire_for_deletion(&string->refcount)))
        string_index_delete(string);

    // statistics
    string_stats_atomic_decrement(partition, active_references);
    string_stats_atomic_increment(partition, releases);
}

ALWAYS_INLINE
size_t string_strlen(const STRING *string) {
    if(unlikely(!string)) return 0;
    return string->length - 1;
}

ALWAYS_INLINE
const char *string2str(const STRING *string) {
    if(unlikely(!string)) return "";
    return string->str;
}

ALWAYS_INLINE
bool string_ends_with_string(const STRING *whole, const STRING *end) {
    if(whole == end) return true;
    if(!whole || !end) return false;
    if(end->length > whole->length) return false;
    if(end->length == whole->length) return strcmp(string2str(whole), string2str(end)) == 0;
    const char *we = string2str(whole);
    we = &we[string_strlen(whole) - string_strlen(end)];
    return strncmp(we, end->str, string_strlen(end)) == 0;
}

ALWAYS_INLINE
bool string_ends_with_string_nocase(const STRING *whole, const STRING *end) {
    if(whole == end) return true;
    if(!whole || !end) return false;
    if(end->length > whole->length) return false;
    if(end->length == whole->length) return strcasecmp(string2str(whole), string2str(end)) == 0;
    const char *we = string2str(whole);
    we = &we[string_strlen(whole) - string_strlen(end)];
    return strncasecmp(we, end->str, string_strlen(end)) == 0;
}

ALWAYS_INLINE
bool string_starts_with_string(const STRING *whole, const STRING *end) {
    if(whole == end) return true;
    if(!whole || !end) return false;
    if(end->length > whole->length) return false;
    if(end->length == whole->length) return strcmp(string2str(whole), string2str(end)) == 0;
    return strncmp(string2str(whole), string2str(end), string_strlen(end)) == 0;
}

ALWAYS_INLINE
bool string_starts_with_string_nocase(const STRING *whole, const STRING *prefix) {
    if(whole == prefix) return true;
    if(!whole || !prefix) return false;
    if(prefix->length > whole->length) return false;
    if(prefix->length == whole->length) return strcasecmp(string2str(whole), string2str(prefix)) == 0;
    return strncasecmp(string2str(whole), string2str(prefix), string_strlen(prefix)) == 0;
}

ALWAYS_INLINE
bool string_equals_string_nocase(const STRING *a, const STRING *b) {
    if(a == b) return true;
    if(!a || !b) return false;
    if(a->length != b->length) return false;
    return strcasecmp(string2str(a), string2str(b)) == 0;
}

// Static X used by string_2way_merge
static STRING *string_2way_merge_X = NULL;

STRING *string_2way_merge(STRING *a, STRING *b) {
    if(unlikely(!string_2way_merge_X))
        string_2way_merge_X = string_strdupz("[x]");

    if(unlikely(a == b)) return string_dup(a);
    if(unlikely(a == string_2way_merge_X)) return string_dup(a);
    if(unlikely(b == string_2way_merge_X)) return string_dup(b);
    if(unlikely(!a)) return string_dup(string_2way_merge_X);
    if(unlikely(!b)) return string_dup(string_2way_merge_X);

    size_t alen = string_strlen(a);
    size_t blen = string_strlen(b);
    size_t length = alen + blen + string_strlen(string_2way_merge_X) + 1;
    CLEAN_CHAR_P *buf1 = mallocz(length + 1);
    CLEAN_CHAR_P *buf2 = mallocz(length + 1);
    char *dst1;
    const char *s1, *s2;

    s1 = string2str(a);
    s2 = string2str(b);
    dst1 = buf1;
    for( ; *s1 && *s2 && *s1 == *s2 ;s1++, s2++)
        *dst1++ = *s1;

    *dst1 = '\0';

    if(*s1 != '\0' || *s2 != '\0') {
        *dst1++ = '[';
        *dst1++ = 'x';
        *dst1++ = ']';

        s1 = &(string2str(a))[alen - 1];
        s2 = &(string2str(b))[blen - 1];
        char *dst2 = &buf2[length];
        *dst2 = '\0';
        for (; *s1 && *s2 && *s1 == *s2; s1--, s2--)
            *(--dst2) = *s1;

        strcpy(dst1, dst2);
    }

    return string_strdupz(buf1);
}

// ----------------------------------------------------------------------------
// STRING unit test

struct thread_unittest {
    int join;
    int dups;
};

static void string_thread(void *arg) {
    struct thread_unittest *tu = arg;

    for(; 1 ;) {
        if(__atomic_load_n(&tu->join, __ATOMIC_RELAXED))
            break;

        STRING *s = string_strdupz("string thread checking 1234567890");

        for(int i = 0; i < tu->dups ; i++)
            string_dup(s);

        for(int i = 0; i < tu->dups ; i++)
            string_freez(s);

        string_freez(s);
    }
}

static char **string_unittest_generate_names(size_t entries) {
    char **names = mallocz(sizeof(char *) * entries);
    for(size_t i = 0; i < entries ;i++) {
        char buf[25 + 1] = "";
        snprintfz(buf, sizeof(buf) - 1, "name.%zu.0123456789.%zu \t !@#$%%^&*(),./[]{}\\|~`", i, entries / 2 + i);
        names[i] = strdupz(buf);
    }
    return names;
}

static void string_unittest_free_char_pp(char **pp, size_t entries) {
    for(size_t i = 0; i < entries ;i++)
        freez(pp[i]);

    freez(pp);
}

static long unittest_string_entries(void) {
    long entries = 0;
    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
        entries += string_base[p].entries;

    return entries;
}

// returns the number of strings that were freed, but were still referenced
size_t string_destroy(void) {
    size_t referenced = 0;

    // Free the static X string used by string_2way_merge
    string_freez(string_2way_merge_X);
    string_2way_merge_X = NULL;

#ifdef FSANITIZE_ADDRESS
    // Create JudyL array for tracking stats by stacktrace
    Pvoid_t string_counts = NULL;    // JudyL array to count strings per stacktrace

    BUFFER *wb = buffer_create(16384, NULL);
    
    fprintf(stderr, "\n========= STRINGS GROUPED BY CREATION STACKTRACE =========\n");
    size_t total_strings = 0;
#endif

    // Traverse all partitions
    for (size_t partition = 0; partition < STRING_PARTITIONS; partition++) {
        // Lock the partition to prevent new entries while we're cleaning up
        rw_spinlock_write_lock(&string_base[partition].spinlock);

#ifdef FSANITIZE_ADDRESS
        // First, collect statistics about remaining strings
        if (string_base[partition].JudyLPointers) {
            // Traverse the JudyL array to count strings by stacktrace
            Word_t string_idx = 0;
            Pvoid_t *PValue;

            PValue = JudyLFirst(string_base[partition].JudyLPointers, &string_idx, PJE0);
            while (PValue) {
                STRING *string = (STRING *)string_idx;
                if(string) {
                    fprintf(stderr, " > STRING REMAINING No %zu: %d references on: '%s'\n",
                            ++total_strings, string->refcount, string2str(string));

                    for (int i = 0; i < string->stacktraces.num_stacktraces; i++) {
                        if (string->stacktraces.stacktraces[i]) {
                            Word_t key = (Word_t)string->stacktraces.stacktraces[i];
                            PValue = JudyLGet(string_counts, key, PJE0);
                            if (PValue) {
                                // Increment existing count
                                size_t count = (size_t)(uintptr_t)*PValue;
                                count++;
                                *PValue = (Pvoid_t)(uintptr_t)count;
                            } else {
                                // Insert new count
                                PValue = JudyLIns(&string_counts, key, PJE0);
                                if (PValue != PJERR)
                                    *PValue = (Pvoid_t)(uintptr_t)1;
                            }
                        }
                    }
                }
                
                PValue = JudyLNext(string_base[partition].JudyLPointers, &string_idx, PJE0);
            }
            
            // Free the JudyL pointers array
            JudyLFreeArray(&string_base[partition].JudyLPointers, PJE0);
            string_base[partition].JudyLPointers = NULL;
        }
#endif

        // Since JudyHS doesn't have simple traversal functions,
        // we'll free the entire array at once.
        if (string_base[partition].JudyHSArray) {
            // We'll count all entries as "referenced" since we can't check them individually
            referenced += string_base[partition].entries;

            // Free the JudyHS array
            JudyHSFreeArray(&string_base[partition].JudyHSArray, PJE0);
            string_base[partition].JudyHSArray = NULL;
        }

        // Reset partition statistics
        string_base[partition].inserts = 0;
        string_base[partition].deletes = 0;
        string_base[partition].entries = 0;
        string_base[partition].memory = 0;
        string_base[partition].memory_index = 0;

#ifdef NETDATA_INTERNAL_CHECKS
        string_base[partition].atomic.searches = 0;
        string_base[partition].atomic.releases = 0;
        string_base[partition].atomic.duplications = 0;
        string_base[partition].atomic.active_references = 0;
        string_base[partition].found_deleted_on_search = 0;
        string_base[partition].found_available_on_search = 0;
        string_base[partition].found_deleted_on_insert = 0;
        string_base[partition].found_available_on_insert = 0;
        string_base[partition].spins = 0;
#endif

        rw_spinlock_write_unlock(&string_base[partition].spinlock);
    }

#ifdef FSANITIZE_ADDRESS
    // Collect stacktraces into an array for sorting
    typedef struct {
        STACKTRACE st;
        size_t count;
    } StacktraceEntry;

    // First, count the number of unique stacktraces
    Word_t Index = 0;
    Pvoid_t *PValue;
    size_t unique_stacktraces = 0;
    
    if (string_counts) {
        PValue = JudyLFirst(string_counts, &Index, PJE0);
        while (PValue) {
            unique_stacktraces++;
            PValue = JudyLNext(string_counts, &Index, PJE0);
        }
    }
    
    // Allocate an array for sorting
    StacktraceEntry *entries = mallocz(sizeof(StacktraceEntry) * unique_stacktraces);
    size_t entry_count = 0;
    
    // Populate the array with stacktraces and counts
    if (string_counts && unique_stacktraces > 0) {
        Index = 0;
        PValue = JudyLFirst(string_counts, &Index, PJE0);
        while (PValue) {
            entries[entry_count].st = (STACKTRACE)Index;
            entries[entry_count].count = (size_t)(uintptr_t)*PValue;
            entry_count++;
            PValue = JudyLNext(string_counts, &Index, PJE0);
        }
    }
    
    // Sort by count in descending order
    // Simple insertion sort is sufficient for a small number of entries
    for (size_t i = 1; i < entry_count; i++) {
        StacktraceEntry key = entries[i];
        ssize_t j = i - 1;
        
        // Move elements that are greater than key to one position ahead of their current position
        while (j >= 0 && entries[j].count < key.count) {
            entries[j + 1] = entries[j];
            j--;
        }
        entries[j + 1] = key;
    }
    
    // Print sorted stacktraces
    fprintf(stderr, "\nTop string creation stacktraces by count:\n");

    for (size_t i = 0; i < entry_count; i++) {
        // Format stacktrace to buffer
        buffer_flush(wb);
        stacktrace_to_buffer(entries[i].st, wb);
        
        fprintf(stderr, "\n > STRINGS BACKTRACE %zu: %zu strings created from:\n%s\n",
                i + 1, entries[i].count, buffer_tostring(wb));
    }
    
    fprintf(stderr, "==================================================================\n\n");
    
    // Clean up
    freez(entries);
    if (string_counts)
        JudyLFreeArray(&string_counts, PJE0);
    buffer_free(wb);
#endif

    memset(&string_base, 0, sizeof(string_base));
    return referenced;
}

#ifdef NETDATA_INTERNAL_CHECKS

static size_t unittest_string_found_deleted_on_search(void) {
    size_t entries = 0;
    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
        entries += string_base[p].found_deleted_on_search;

    return entries;
}
static size_t unittest_string_found_available_on_search(void) {
    size_t entries = 0;
    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
        entries += string_base[p].found_available_on_search;

    return entries;
}
static size_t unittest_string_found_deleted_on_insert(void) {
    size_t entries = 0;
    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
        entries += string_base[p].found_deleted_on_insert;

    return entries;
}
static size_t unittest_string_found_available_on_insert(void) {
    size_t entries = 0;
    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
        entries += string_base[p].found_available_on_insert;

    return entries;
}
static size_t unittest_string_spins(void) {
    size_t entries = 0;
    for(size_t p = 0; p < STRING_PARTITIONS ;p++)
        entries += string_base[p].spins;

    return entries;
}

#endif // NETDATA_INTERNAL_CHECKS

int string_unittest(size_t entries) {
    size_t errors = 0;

    fprintf(stderr, "Generating %zu names and values...\n", entries);
    char **names = string_unittest_generate_names(entries);

    // check string
    {
        long entries_starting = unittest_string_entries();

        fprintf(stderr, "\nChecking strings...\n");

        STRING *s1 = string_strdupz("hello unittest");
        STRING *s2 = string_strdupz("hello unittest");
        if(s1 != s2) {
            errors++;
            fprintf(stderr, "ERROR: duplicating strings are not deduplicated\n");
        }
        else
            fprintf(stderr, "OK: duplicating string are deduplicated\n");

        STRING *s3 = string_dup(s1);
        if(s3 != s1) {
            errors++;
            fprintf(stderr, "ERROR: cloning strings are not deduplicated\n");
        }
        else
            fprintf(stderr, "OK: cloning string are deduplicated\n");

        if(s1->refcount != 3) {
            errors++;
            fprintf(stderr, "ERROR: string refcount is not 3\n");
        }
        else
            fprintf(stderr, "OK: string refcount is 3\n");

        STRING *s4 = string_strdupz("world unittest");
        if(s4 == s1) {
            errors++;
            fprintf(stderr, "ERROR: string is sharing pointers on different strings\n");
        }
        else
            fprintf(stderr, "OK: string is properly handling different strings\n");

        STRING *s_null = string_strdupz(NULL);
        if(s_null != NULL) {
            errors++;
            fprintf(stderr, "ERROR: NULL string input should return NULL\n");
        }
        else
            fprintf(stderr, "OK: NULL string input returns NULL\n");

        STRING *s_empty = string_strdupz("");
        if(s_empty != NULL) {
            errors++;
            fprintf(stderr, "ERROR: empty string input should return NULL\n");
        }
        else
            fprintf(stderr, "OK: empty string input returns NULL\n");

        usec_t start_ut, end_ut;
        STRING **strings = mallocz(entries * sizeof(STRING *));

        start_ut = now_realtime_usec();
        for(size_t i = 0; i < entries ;i++) {
            strings[i] = string_strdupz(names[i]);
        }
        end_ut = now_realtime_usec();
        fprintf(stderr, "Created %zu strings in %"PRIu64" usecs\n", entries, end_ut - start_ut);

        start_ut = now_realtime_usec();
        for(size_t i = 0; i < entries ;i++) {
            strings[i] = string_dup(strings[i]);
        }
        end_ut = now_realtime_usec();
        fprintf(stderr, "Cloned %zu strings in %"PRIu64" usecs\n", entries, end_ut - start_ut);

        start_ut = now_realtime_usec();
        for(size_t i = 0; i < entries ;i++) {
            strings[i] = string_strdupz(string2str(strings[i]));
        }
        end_ut = now_realtime_usec();
        fprintf(stderr, "Found %zu existing strings in %"PRIu64" usecs\n", entries, end_ut - start_ut);

        start_ut = now_realtime_usec();
        for(size_t i = 0; i < entries ;i++) {
            string_freez(strings[i]);
        }
        end_ut = now_realtime_usec();
        fprintf(stderr, "Released %zu referenced strings in %"PRIu64" usecs\n", entries, end_ut - start_ut);

        start_ut = now_realtime_usec();
        for(size_t i = 0; i < entries ;i++) {
            string_freez(strings[i]);
        }
        end_ut = now_realtime_usec();
        fprintf(stderr, "Released (again) %zu referenced strings in %"PRIu64" usecs\n", entries, end_ut - start_ut);

        start_ut = now_realtime_usec();
        for(size_t i = 0; i < entries ;i++) {
            string_freez(strings[i]);
        }
        end_ut = now_realtime_usec();
        fprintf(stderr, "Freed %zu strings in %"PRIu64" usecs\n", entries, end_ut - start_ut);

        freez(strings);

        if(unittest_string_entries() != entries_starting + 2) {
            errors++;
            fprintf(stderr, "ERROR: strings dictionary should have %ld items but it has %ld\n",
                    entries_starting + 2, unittest_string_entries());
        }
        else
            fprintf(stderr, "OK: strings dictionary has 2 items\n");
    }

    // check 2-way merge
    {
        struct testcase {
            char *src1; char *src2; char *expected;
        } tests[] = {
            { "", "", ""},
            { "a", "", "[x]"},
            { "", "a", "[x]"},
            { "a", "a", "a"},
            { "abcd", "abcd", "abcd"},
            { "foo_cs", "bar_cs", "[x]_cs"},
            { "cp_UNIQUE_INFIX_cs", "cp_unique_infix_cs", "cp_[x]_cs"},
            { "cp_UNIQUE_INFIX_ci_unique_infix_cs", "cp_unique_infix_ci_UNIQUE_INFIX_cs", "cp_[x]_cs"},
            { "foo[1234]", "foo[4321]", "foo[[x]]"},
            { NULL, NULL, NULL },
        };

        for (struct testcase *tc = &tests[0]; tc->expected != NULL; tc++) {
            STRING *src1 = string_strdupz(tc->src1);
            STRING *src2 = string_strdupz(tc->src2);
            STRING *expected = string_strdupz(tc->expected);

            STRING *result = string_2way_merge(src1, src2);
            if (string_cmp(result, expected) != 0) {
                fprintf(stderr, "string_2way_merge(\"%s\", \"%s\") -> \"%s\" (expected=\"%s\")\n",
                        string2str(src1),
                        string2str(src2),
                        string2str(result),
                        string2str(expected));
                errors++;
            }

            string_freez(src1);
            string_freez(src2);
            string_freez(expected);
            string_freez(result);
        }
    }

    // threads testing of string
    {
        struct thread_unittest tu = {
            .dups = 1,
            .join = 0,
        };

#ifdef NETDATA_INTERNAL_CHECKS
        size_t ofound_deleted_on_search = unittest_string_found_deleted_on_search(),
               ofound_available_on_search = unittest_string_found_available_on_search(),
               ofound_deleted_on_insert = unittest_string_found_deleted_on_insert(),
               ofound_available_on_insert = unittest_string_found_available_on_insert(),
               ospins = unittest_string_spins();
#endif

        size_t oinserts, odeletes, osearches, oentries, oreferences, omemory, omemory_index, oduplications, oreleases;
        string_statistics(&oinserts, &odeletes, &osearches, &oentries, &oreferences, &omemory, &omemory_index, &oduplications, &oreleases);

        time_t seconds_to_run = 5;
        enum { STRING_UNITTEST_THREADS = 2 };
        fprintf(
            stderr,
            "Checking string concurrency with %d threads for %lld seconds...\n",
            STRING_UNITTEST_THREADS,
            (long long)seconds_to_run);
        // check string concurrency
        ND_THREAD *threads[STRING_UNITTEST_THREADS];
        tu.join = 0;
        for (int i = 0; i < STRING_UNITTEST_THREADS; i++) {
            char buf[100 + 1];
            snprintf(buf, 100, "string%d", i);
            threads[i] = nd_thread_create(buf, NETDATA_THREAD_OPTION_DONT_LOG, string_thread, &tu);
        }
        sleep_usec(seconds_to_run * USEC_PER_SEC);

        __atomic_store_n(&tu.join, 1, __ATOMIC_RELAXED);
        for (int i = 0; i < STRING_UNITTEST_THREADS; i++)
            nd_thread_join(threads[i]);

        size_t inserts, deletes, searches, sentries, references, memory, memory_index, duplications, releases;
        string_statistics(&inserts, &deletes, &searches, &sentries, &references, &memory, &memory_index, &duplications, &releases);

        fprintf(stderr, "inserts %zu, deletes %zu, searches %zu, entries %zu, references %zu, memory %zu, duplications %zu, releases %zu\n",
                inserts - oinserts, deletes - odeletes, searches - osearches, sentries - oentries, references - oreferences, memory - omemory, duplications - oduplications, releases - oreleases);

#ifdef NETDATA_INTERNAL_CHECKS
        size_t found_deleted_on_search = unittest_string_found_deleted_on_search(),
               found_available_on_search = unittest_string_found_available_on_search(),
               found_deleted_on_insert = unittest_string_found_deleted_on_insert(),
               found_available_on_insert = unittest_string_found_available_on_insert(),
               spins = unittest_string_spins();

        fprintf(stderr, "on insert: %zu ok + %zu deleted\non search: %zu ok + %zu deleted\nspins: %zu\n",
                found_available_on_insert - ofound_available_on_insert,
                found_deleted_on_insert - ofound_deleted_on_insert,
                found_available_on_search - ofound_available_on_search,
                found_deleted_on_search - ofound_deleted_on_search,
                spins - ospins
        );
#endif
    }

    string_unittest_free_char_pp(names, entries);

    fprintf(stderr, "\n%zu errors found\n", errors);
    return  errors ? 1 : 0;
}

void string_init(void) {
    for (size_t i = 0; i != STRING_PARTITIONS; i++) {
        rw_spinlock_init(&string_base[i].spinlock);
        
#ifdef FSANITIZE_ADDRESS
        // Initialize the JudyL pointers array to NULL
        string_base[i].JudyLPointers = NULL;
#endif
    }
}