diff options
| author | Mitja Felicijan <mitja.felicijan@gmail.com> | 2026-01-21 22:52:54 +0100 |
|---|---|---|
| committer | Mitja Felicijan <mitja.felicijan@gmail.com> | 2026-01-21 22:52:54 +0100 |
| commit | dcacc00e3750300617ba6e16eb346713f91a783a (patch) | |
| tree | 38e2d4fb5ed9d119711d4295c6eda4b014af73fd /examples/redis-unstable/src/chk.h | |
| parent | 58dac10aeb8f5a041c46bddbeaf4c7966a99b998 (diff) | |
| download | crep-dcacc00e3750300617ba6e16eb346713f91a783a.tar.gz | |
Remove testing data
Diffstat (limited to 'examples/redis-unstable/src/chk.h')
| -rw-r--r-- | examples/redis-unstable/src/chk.h | 89 |
1 files changed, 0 insertions, 89 deletions
diff --git a/examples/redis-unstable/src/chk.h b/examples/redis-unstable/src/chk.h deleted file mode 100644 index a974fd6..0000000 --- a/examples/redis-unstable/src/chk.h +++ /dev/null @@ -1,89 +0,0 @@ -/* Implementation of a topK structure using CuckooHeavyKeeper algorithm - * - * Implementation is based on the paper "Cuckoo Heavy Keeper and the balancing - * act of maintaining heavy hitters in stream processing" by Vinh Quang Ngo and - * Marina Papatriantafilou. Also, the accompanying C++ implementation was used - * as a reference point: https://github.com/vinhqngo5/Cuckoo_Heavy_Keeper - * Main changes are addition of a min-heap so we can keep names of the top K - * elements - idea comes from RedisBloom's TopK structure. - * - * Copyright (c) 2026-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). - */ - -#pragma once - -#include "sds.h" - -#include <stddef.h> -#include <stdint.h> - -#define CHK_LUT_SIZE 256 -#define CHK_HEAVY_ENTRIES_PER_BUCKET 2 -#define CHK_NUM_TABLES 2 - -typedef uint64_t counter_t; -typedef uint16_t fingerprint_t; -typedef uint8_t lobby_counter_t; - -typedef struct { - counter_t count; - fingerprint_t fp; -} chkHeavyEntry; - -typedef struct { - fingerprint_t fp; - lobby_counter_t count; -} chkLobbyEntry; - -typedef struct { - chkHeavyEntry heavy_entries[CHK_HEAVY_ENTRIES_PER_BUCKET]; - chkLobbyEntry lobby_entry; -} chkBucket; - -typedef struct { - counter_t count; - sds item; - uint64_t fp; /* Fingerprint used to identify the item. Internal use only */ -} chkHeapBucket; - -typedef struct chkTopK { - chkBucket *tables[CHK_NUM_TABLES]; /* Cuckoo tables */ - chkHeapBucket *heap; /* Min-heap for storing top-K item's names */ - - size_t alloc_size; /* Used for memory tracking only */ - - /* Expected number of operations to decay count i to 0 */ - double lut_decay_exp[CHK_LUT_SIZE + 1]; - - /* Minimum number of decay operations to decay count i with 1 */ - double lut_min_decay[CHK_LUT_SIZE + 1]; - - /* Probability of decaying i with 1. As per paper probability is decay^-i - * but we actually store (1/decay)^i for faster computation. */ - double lut_decay_prob[CHK_LUT_SIZE + 1]; - - double decay; /* Decay constant */ - double inv_decay; /* Cache 1/decay for faster computations */ - - counter_t total; /* Total recorded count for all updates */ - - int k; - int numbuckets; -} chkTopK; - -chkTopK *chkTopKCreate(int k, int numbuckets, double decay); -void chkTopKRelease(chkTopK *topk); -sds chkTopKUpdate(chkTopK *topk, char *item, int itemlen, counter_t weight); -chkHeapBucket *chkTopKList(chkTopK *topk); -size_t chkTopKGetMemoryUsage(chkTopK *topk); - -#ifdef REDIS_TEST - -int chkTopKTest(int argc, char *argv[], int flags); - -#endif /* REDIS_TEST */ |
