summaryrefslogtreecommitdiff
path: root/examples/redis-unstable/src/fwtree.h
diff options
context:
space:
mode:
authorMitja Felicijan <mitja.felicijan@gmail.com>2026-01-21 22:52:54 +0100
committerMitja Felicijan <mitja.felicijan@gmail.com>2026-01-21 22:52:54 +0100
commitdcacc00e3750300617ba6e16eb346713f91a783a (patch)
tree38e2d4fb5ed9d119711d4295c6eda4b014af73fd /examples/redis-unstable/src/fwtree.h
parent58dac10aeb8f5a041c46bddbeaf4c7966a99b998 (diff)
downloadcrep-dcacc00e3750300617ba6e16eb346713f91a783a.tar.gz
Remove testing data
Diffstat (limited to 'examples/redis-unstable/src/fwtree.h')
-rw-r--r--examples/redis-unstable/src/fwtree.h71
1 files changed, 0 insertions, 71 deletions
diff --git a/examples/redis-unstable/src/fwtree.h b/examples/redis-unstable/src/fwtree.h
deleted file mode 100644
index 31e0ea2..0000000
--- a/examples/redis-unstable/src/fwtree.h
+++ /dev/null
@@ -1,71 +0,0 @@
-/*
- * 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).
- *
- *
- * FENWICK TREE (Binary Indexed Tree)
- * ----------------------------------
- * A Fenwick tree is a data structure that efficiently supports:
- * - Point updates: Add/subtract values at specific indices in O(log n) time
- * - Prefix sum queries: Calculate cumulative sums from index 0 to any index in O(log n) time
- * - Range queries: Calculate sums over any range [i,j] in O(log n) time
- * - Space complexity: O(n)
- *
- * USAGE IN REDIS
- * --------------
- * This implementation is used by KVSTORE and ESTORE to efficiently track:
- * - Cumulative key counts across dictionary slots (KVSTORE)
- * - Cumulative item counts across expiration buckets (ESTORE)
- *
- * This enables efficient operations like:
- * - Finding which dictionary/bucket contains the Nth key/item
- * - Iterating through non-empty dictionaries/buckets
- * - Load balancing and random key selection
- *
- * IMPLEMENTATION NOTES
- * -------------------
- * - The tree uses 1-based indexing internally for mathematical convenience
- * - The public API uses 0-based indexing for consistency with Redis codebase
- * - Tree size must be a power of 2 (specified as sizeBits where size = 2^sizeBits)
- * - All operations have O(log n) time complexity where n is the tree size
- *
- * REFERENCES
- * ----------
- * For more details on Fenwick trees: https://en.wikipedia.org/wiki/Fenwick_tree
- */
-
-#ifndef __FWTREE_H
-#define __FWTREE_H
-
-#include <stdint.h>
-
-/* Forward declaration of the fenwick tree structure */
-typedef struct _fenwickTree fenwickTree;
-
-/* Fenwick Tree API */
-
-fenwickTree *fwTreeCreate(int sizeBits);
-
-void fwTreeDestroy(fenwickTree *ft);
-
-unsigned long long fwTreePrefixSum(fenwickTree *ft, int idx);
-
-void fwTreeUpdate(fenwickTree *ft, int idx, long long delta);
-
-int fwTreeFindIndex(fenwickTree *ft, unsigned long long target);
-
-int fwTreeFindFirstNonEmpty(fenwickTree *ft);
-
-int fwTreeFindNextNonEmpty(fenwickTree *ft, int idx);
-
-void fwTreeClear(fenwickTree *ft);
-
-#ifdef REDIS_TEST
-int fwtreeTest(int argc, char *argv[], int flags);
-#endif
-
-#endif /* __FWTREE_H */