From 5d8dfe892a2ea89f706ee140c3bdcfd89fe03fda Mon Sep 17 00:00:00 2001 From: Mitja Felicijan Date: Wed, 21 Jan 2026 22:40:55 +0100 Subject: Add Redis source code for testing --- examples/redis-unstable/src/fwtree.c | 237 +++++++++++++++++++++++++++++++++++ 1 file changed, 237 insertions(+) create mode 100644 examples/redis-unstable/src/fwtree.c (limited to 'examples/redis-unstable/src/fwtree.c') diff --git a/examples/redis-unstable/src/fwtree.c b/examples/redis-unstable/src/fwtree.c new file mode 100644 index 0000000..f284eeb --- /dev/null +++ b/examples/redis-unstable/src/fwtree.c @@ -0,0 +1,237 @@ +/* + * fwtree.c -- FENWICK TREE (Binary Indexed Tree) + * + * Copyright (c) 2011-Present, Redis Ltd. + * All rights reserved. + * + * Licensed under your choice of (a) the Redis Source Available License 2.0 + * (RSALv2); or (b) the Server Side Public License v1 (SSPLv1); or (c) the + * GNU Affero General Public License v3 (AGPLv3). + */ + +#include "server.h" +#include "fwtree.h" +#include "zmalloc.h" +#include "redisassert.h" +#include + +struct _fenwickTree { + unsigned long long *tree; + int size_bits; + int size; + uint64_t total; +}; + +/* Create a new Fenwick tree with 2^sizeBits elements (all initialized to 0) */ +fenwickTree *fwTreeCreate(int sizeBits) { + fenwickTree *ft = zmalloc(sizeof(fenwickTree)); + ft->size_bits = sizeBits; + ft->size = 1 << sizeBits; + /* Fenwick tree is 1-based, so we need size + 1 elements */ + ft->tree = zcalloc(sizeof(unsigned long long) * (ft->size + 1)); + ft->total = 0; + return ft; +} + +void fwTreeDestroy(fenwickTree *ft) { + if (!ft) return; + zfree(ft->tree); + zfree(ft); +} + +/* Query cumulative sum from index 0 to idx (inclusive, 0-based) */ +unsigned long long fwTreePrefixSum(fenwickTree *ft, int idx) { + if (!ft || idx < 0) return 0; + if (idx >= ft->size) idx = ft->size - 1; + + /* Convert to 1-based indexing */ + idx++; + + unsigned long long sum = 0; + while (idx > 0) { + sum += ft->tree[idx]; + idx -= (idx & -idx); + } + return sum; +} + +/* Update the tree by adding delta to the element at idx (0-based) */ +void fwTreeUpdate(fenwickTree *ft, int idx, long long delta) { + if (!ft || idx < 0 || idx >= ft->size) return; + + /* Convert to 1-based indexing */ + idx++; + ft->total += delta; + + while (idx <= ft->size) { + if (delta < 0) { + assert(ft->tree[idx] >= (unsigned long long)(-delta)); + } + ft->tree[idx] += delta; + idx += (idx & -idx); + } + debugAssert(ft->total == fwTreePrefixSum(ft, ft->size - 1)); +} + +/* Find the 0-based index where the cumulative sum first reaches or exceeds target. + * target should be in range [1..total]. + * Returns the 0-based index, or 0 if target <= 0 or tree is empty. + */ +int fwTreeFindIndex(fenwickTree *ft, unsigned long long target) { + debugAssert(ft); + + if (target <= 0) return 0; + + int result = 0, bit_mask = 1 << ft->size_bits; + for (int i = bit_mask; i != 0; i >>= 1) { + int current = result + i; + /* When the target index is greater than 'current' node value the we will update + * the target and search in the 'current' node tree. */ + if (target > ft->tree[current]) { + target -= ft->tree[current]; + result = current; + } + } + /* Adjust the result to get the correct index: + * 1. result += 1; + * After the calculations, the index of target in the tree should be the next one, + * so we should add 1. + * 2. result -= 1; + * Unlike BIT (tree is 1-based), the API uses 0-based indexing, so we need to subtract 1. + * As the addition and subtraction cancel each other out, we can simply return the result. */ + return result; +} + +/* Find the first non-empty index (equivalent to fwTreeFindIndex(ft, 1)) */ +int fwTreeFindFirstNonEmpty(fenwickTree *ft) { + debugAssert(ft); + return fwTreeFindIndex(ft, 1); +} + +/* Find the next non-empty index after idx (0-based). + * Returns the 0-based index of the next non-empty element, or -1 if no such element exists. + * If idx is -1, finds the first non-empty index. + * Time complexity: O(log n) + */ +int fwTreeFindNextNonEmpty(fenwickTree *ft, int idx) { + if (!ft || idx < 0 || idx >= ft->size) return -1; + /* Get cumulative sum up to current index */ + unsigned long long next_sum = fwTreePrefixSum(ft, idx) + 1; + /* Find the index that contains the next key (curr_sum + 1) */ + return (next_sum <= ft->total) ? fwTreeFindIndex(ft, next_sum) : -1; +} + +/* Clear all values in the tree */ +void fwTreeClear(fenwickTree *ft) { + debugAssert(ft); + memset(ft->tree, 0, sizeof(unsigned long long) * (ft->size + 1)); + ft->total = 0; +} + +#ifdef REDIS_TEST +#include + +#define TEST(name) printf("%s\n", name); + +int fwtreeTest(int argc, char *argv[], int flags) { + UNUSED(argc); + UNUSED(argv); + UNUSED(flags); + /* Test basic operations */ + int sizeBits = 3; /*size = 8*/ + fenwickTree *ft = fwTreeCreate(sizeBits); + assert(ft != NULL); + + TEST("estore - Test updates and queries") { + fwTreeUpdate(ft, 0, 5); /* index 0 += 5 */ + fwTreeUpdate(ft, 2, 3); /* index 2 += 3 */ + fwTreeUpdate(ft, 4, 7); /* index 4 += 7 */ + fwTreeUpdate(ft, 6, 2); /* index 6 += 2 */ + } + + TEST("estore - Test cumulative queries") { + assert(fwTreePrefixSum(ft, 0) == 5); /* sum[0..0] = 5 */ + assert(fwTreePrefixSum(ft, 1) == 5); /* sum[0..1] = 5 */ + assert(fwTreePrefixSum(ft, 2) == 8); /* sum[0..2] = 5+3 = 8 */ + assert(fwTreePrefixSum(ft, 3) == 8); /* sum[0..3] = 8 */ + assert(fwTreePrefixSum(ft, 4) == 15); /* sum[0..4] = 5+3+7 = 15 */ + assert(fwTreePrefixSum(ft, 5) == 15); /* sum[0..5] = 15 */ + assert(fwTreePrefixSum(ft, 6) == 17); /* sum[0..6] = 5+3+7+2 = 17 */ + assert(fwTreePrefixSum(ft, 7) == 17); /* sum[0..7] = 17 */ + } + + + + TEST("estore - Test find_index functionality") { + assert(fwTreeFindIndex(ft, 1) == 0); /* target 1 -> index 0 */ + assert(fwTreeFindIndex(ft, 5) == 0); /* target 5 -> index 0 */ + assert(fwTreeFindIndex(ft, 6) == 2); /* target 6 -> index 2 */ + assert(fwTreeFindIndex(ft, 8) == 2); /* target 8 -> index 2 */ + assert(fwTreeFindIndex(ft, 9) == 4); /* target 9 -> index 4 */ + assert(fwTreeFindIndex(ft, 15) == 4); /* target 15 -> index 4 */ + assert(fwTreeFindIndex(ft, 16) == 6); /* target 16 -> index 6 */ + assert(fwTreeFindIndex(ft, 17) == 6); /* target 17 -> index 6 */ + } + + TEST("estore - Test fwTreeFindNextNonEmpty functionality") { + /* Current state: indices 0, 2, 4, 6 have values 5, 3, 7, 2 respectively */ + assert(fwTreeFindNextNonEmpty(ft, -1) == -1); /* Invalid index */ + assert(fwTreeFindNextNonEmpty(ft, 0) == 2); /* Next after 0 is index 2 */ + assert(fwTreeFindNextNonEmpty(ft, 1) == 2); /* Next after 1 is index 2 */ + assert(fwTreeFindNextNonEmpty(ft, 2) == 4); /* Next after 2 is index 4 */ + assert(fwTreeFindNextNonEmpty(ft, 3) == 4); /* Next after 3 is index 4 */ + assert(fwTreeFindNextNonEmpty(ft, 4) == 6); /* Next after 4 is index 6 */ + assert(fwTreeFindNextNonEmpty(ft, 5) == 6); /* Next after 5 is index 6 */ + assert(fwTreeFindNextNonEmpty(ft, 6) == -1); /* No next after 6 */ + assert(fwTreeFindNextNonEmpty(ft, 7) == -1); /* No next after 7 */ + } + + TEST("estore - Test negative updates") { + fwTreeUpdate(ft, 2, -1); /* index 2 -= 1 */ + assert(fwTreePrefixSum(ft, 2) == 7); /* sum[0..2] = 5+2 = 7 */ + assert(fwTreePrefixSum(ft, 7) == 16); /* total = 16 */ + } + + TEST("estore - Test making an index empty") { + fwTreeUpdate(ft, 2, -2); /* index 2 -= 2, should become empty */ + assert(fwTreePrefixSum(ft, 2) == 5); /* sum[0..2] = 5+0 = 5 */ + } + + TEST("estore - Test fwTreeFindNextNonEmpty after making index 2 empty") { + /* Current state: indices 0, 4, 6 have values 5, 7, 2 respectively (index 2 is now empty) */ + assert(fwTreeFindNextNonEmpty(ft, 0) == 4); /* Next after 0 is now index 4 (skipping empty 2) */ + assert(fwTreeFindNextNonEmpty(ft, 1) == 4); /* Next after 1 is index 4 */ + assert(fwTreeFindNextNonEmpty(ft, 2) == 4); /* Next after 2 is index 4 */ + assert(fwTreeFindNextNonEmpty(ft, 3) == 4); /* Next after 3 is index 4 */ + } + + TEST("estore - Operations on empty tree") { + fwTreeClear(ft); + assert(fwTreePrefixSum(ft, 7) == 0); + + /* Test fwTreeFindNextNonEmpty on empty tree */ + assert(fwTreeFindNextNonEmpty(ft, -1) == -1); /* Empty tree */ + assert(fwTreeFindNextNonEmpty(ft, 0) == -1); /* Empty tree */ + } + + fwTreeDestroy(ft); + + TEST("estore - misc") { + ft = fwTreeCreate(0); + + fwTreeUpdate(ft, 0, 10); /* add 10 to index 0 */ + assert(fwTreePrefixSum(ft, 0) == 10); + + assert(fwTreeFindIndex(ft, 5) == 0); + + /* Test fwTreeFindNextNonEmpty on single element tree */ + assert(fwTreeFindNextNonEmpty(ft, -1) == -1); /* Invalid index */ + assert(fwTreeFindNextNonEmpty(ft, 0) == -1); /* No next after 0 in single element tree */ + + fwTreeDestroy(ft); + } + + return 0; +} + +#endif -- cgit v1.2.3