bloom filter

/*
 * practice31_bloom_filter.c — Bloom Filter (PG bloomfilter.c 简化版)
 * =====================================================
 * 对应 PG 模块:
 *   src/backend/lib/bloomfilter.c        — 通用 bloom filter 实现
 *   src/backend/executor/nodeHashjoin.c  — hash join 用 bloom filter 优化
 *   contrib/bloom/                       — bloom 索引扩展
 *
 * 为什么重要:
 *   Bloom filter 是概率数据结构: 能确认"肯定不存在", 但只能说"可能存在"。
 *   PG 用它:
 *     - hash join: 先用 bloom filter 过滤 probe 端, 减少不必要的 hash 查找
 *     - parallel seqscan: worker 之间用 bloom filter 同步"已扫过的块"
 *     - bloom index: 索引本身就是一个 bloom filter
 *   特点: 有假阳性 (false positive), 无假阴性 (false negative)。
 *
 * 核心原理:
 *   1. 位数组 (bit array): m 个 bit, 初始全 0
 *   2. k 个哈希函数: 把元素映射到 [0, m) 的 k 个位置
 *   3. 插入: 算 k 个位置, 全部置 1
 *   4. 查询: 算 k 个位置, 全为 1 → "可能存在"; 有 0 → "肯定不存在"
 *
 * 位数组实现 (本题重点):
 *   用 uint8_t bits[] 存储, 每个字节 8 位
 *     bit i 在 bits[i / 8] 的第 (i % 8) 位
 *     set: bits[i/8] |=  (1 << (i % 8))
 *     get: (bits[i/8] >> (i % 8)) & 1
 *
 * 难度: ★★☆☆☆
 *
 * 学习目标:
 *   1. 位运算 (<< >> | & ~) 的实战使用
 *   2. 位数组 (bit array) 的索引映射 (字节/位)
 *   3. 概率数据结构思维 (假阳性/假阴性)
 *   4. 哈希函数基础 (乘法哈希)
 *
 * 编译: gcc -Wall -Wextra -O2 -o practice31 practice31_bloom_filter.c
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <stdbool.h>
#include <assert.h>

/* ============================================================
 * 常量
 * ============================================================ */

#define BLOOM_BYTES     256     /* 位数组字节数 (256 * 8 = 2048 位) */
#define BLOOM_BITS      (BLOOM_BYTES * 8)
#define BLOOM_K         3       /* 哈希函数个数 */

/* ============================================================
 * 数据结构
 * ============================================================ */

typedef struct {
    uint8_t  bits[BLOOM_BYTES];   /* 位数组 */
    size_t   n_added;             /* 已插入元素数 (统计用) */
} BloomFilter;

/* ============================================================
 * 哈希函数 (已实现)
 *   乘法哈希: h = seed, 每个字节 h = h * 31 + byte
 *   不同 seed 产生不同哈希 (模拟 k 个独立哈希函数)
 * ============================================================ */

static uint32_t bloom_hash(const void *data, size_t len, uint32_t seed) {
    const uint8_t *p = (const uint8_t *)data;
    uint32_t h = seed;
    for (size_t i = 0; i < len; i++) {
        h = h * 31 + p[i];
    }
    return h;
}

/*
 * 用第 k 个哈希函数算出 bit 位置 (0 .. BLOOM_BITS-1)
 *   k = 0, 1, ..., BLOOM_K-1
 */
static uint32_t bloom_hash_pos(const void *data, size_t len, int k) {
    /* 不同 seed 模拟不同哈希函数 */
    uint32_t seed = (k + 1) * 2654435761u;   /* Knuth 乘法常数 */
    uint32_t h = bloom_hash(data, len, seed);
    return h % BLOOM_BITS;
}

/* ============================================================
 * 位数组操作 (核心! 重点练位运算)
 * ============================================================ */

/*
 * 设置第 i 位为 1
 *   对应 PG 的 bloom_filter.c 里的位操作 (用 word 数组, 本题用 byte 数组简化)
 *
 * 实现:
 *   - 字节索引: byte_idx = i / 8
 *   - 位偏移:   bit_idx  = i % 8
 *   - 设置:     bits[byte_idx] |= (1 << bit_idx)
 *
 * 图示 (i = 10):
 *   10 / 8 = 1  → bits[1]
 *   10 % 8 = 2  → 第 2 位
 *   bits[1] |= (1 << 2)  即 bits[1] |= 0b00000100
 *
 *        bits[0]              bits[1]
 *   [b7 b6 b5 b4 b3 b2 b1 b0] [b7 b6 b5 b4 b3 b2 b1 b0]
 *                                ↑ 设置这一位 (bit 2)
 *   bit 0 在最右 (最低位), bit 7 在最左
 */
void bloom_set_bit(BloomFilter *bf, uint32_t i) {
    assert(1 < BLOOM_BITS);
    uint32_t byte_idx = i / 8;
    uint32_t bit_idx = i % 8;
    bf->bits[byte_idx] |= (1 << bit_idx);
}

/*
 * 获取第 i 位的值 (0 或 1)
 *
 * 实现:
 *   - byte_idx = i / 8
 *   - bit_idx  = i % 8
 *   - return (bf->bits[byte_idx] >> bit_idx) & 1
 *
 * 为什么用 >> 再 & 1?
 *   - >> bit_idx 把目标位移到最低位
 *   - & 1 只保留最低位, 屏蔽其他位
 *   例: bits[1] = 0b00000100, 取 bit 2:
 *       0b00000100 >> 2 = 0b00000001
 *       0b00000001 & 1  = 1
 */
int bloom_get_bit(const BloomFilter *bf, uint32_t i) {
    uint32_t byte_idx = i / 8;
    uint32_t bit_idx = i % 8;
    return (bf->bits[byte_idx] >> bit_idx) & 1;
}

/* ============================================================
 * Bloom Filter API
 * ============================================================ */

/*
 * 初始化 (清零位数组)
 *   对应 PG 的 bloom_init
 */
void bloom_init(BloomFilter *bf) {
    memset(bf->bits, 0, BLOOM_BYTES);
    bf->n_added = 0;
}

/*
 * 插入元素
 *   对应 PG 的 bloom_add_element
 *
 * 流程:
 *   - 用 BLOOM_K 个哈希函数算出 k 个位置
 *   - 每个位置 bloom_set_bit 置 1
 *   - n_added++
 */
void bloom_add(BloomFilter *bf, const void *data, size_t len) {
    for(int k=0; k<BLOOM_K; k++)
    {
        bloom_set_bit(bf, bloom_hash_pos(data, len,k));
    }
    bf->n_added++;
}

/*
 * 查询元素是否"可能存在"
 *   对应 PG 的 bloom_contains
 *
 * 流程:
 *   - 用 BLOOM_K 个哈希函数算出 k 个位置
 *   - 若所有位置都是 1 → 返回 true (可能存在, 可能假阳性)
 *   - 若有任一位置为 0 → 返回 false (肯定不存在)
 *
 * 注意: 返回 true 不代表一定存在 (假阳性), 返回 false 代表一定不存在
 */
bool bloom_might_contain(const BloomFilter *bf, const void *data, size_t len) {
    for(int k=0; k<BLOOM_K; k++)
    {
        if(bloom_get_bit(bf,bloom_hash_pos(data,len,k)) == 0)
        {
            return false;
        }
    }
    return true;
}

/* ============================================================
 * 工具函数 (已实现)
 * ============================================================ */

static void bloom_dump(const BloomFilter *bf, const char *label) {
    printf("--- %s ---\n", label);
    printf("  n_added = %zu, bits = %d, k = %d\n",
           bf->n_added, BLOOM_BITS, BLOOM_K);
    int set_bits = 0;
    for (int i = 0; i < BLOOM_BITS; i++) {
        if (bloom_get_bit(bf, i)) set_bits++;
    }
    printf("  set bits = %d / %d (%.1f%%)\n",
           set_bits, BLOOM_BITS, 100.0 * set_bits / BLOOM_BITS);
}

/* ============================================================
 * 测试
 * ============================================================ */

static void test_bit_ops(void) {
    printf("=== test_bit_ops ===\n");
    BloomFilter bf;
    bloom_init(&bf);

    /* 初始全 0 */
    for (int i = 0; i < BLOOM_BITS; i++) {
        assert(bloom_get_bit(&bf, i) == 0);
    }
    printf("  初始全 0: OK\n");

    /* 设置几个位 */
    bloom_set_bit(&bf, 0);
    bloom_set_bit(&bf, 7);
    bloom_set_bit(&bf, 8);
    bloom_set_bit(&bf, 100);
    bloom_set_bit(&bf, 2047);

    assert(bloom_get_bit(&bf, 0) == 1);
    assert(bloom_get_bit(&bf, 7) == 1);
    assert(bloom_get_bit(&bf, 8) == 1);
    assert(bloom_get_bit(&bf, 100) == 1);
    assert(bloom_get_bit(&bf, 2047) == 1);

    /* 相邻位不受影响 */
    assert(bloom_get_bit(&bf, 1) == 0);
    assert(bloom_get_bit(&bf, 6) == 0);
    assert(bloom_get_bit(&bf, 9) == 0);
    assert(bloom_get_bit(&bf, 99) == 0);
    assert(bloom_get_bit(&bf, 2046) == 0);

    printf("  设置 bit 0,7,8,100,2047 后读取: OK\n");

    /* 重复设置同一 bit 不影响 */
    bloom_set_bit(&bf, 0);
    bloom_set_bit(&bf, 0);
    assert(bloom_get_bit(&bf, 0) == 1);
    printf("  重复设置同一 bit: OK (幂等)\n");

    printf("  PASS\n\n");
}

static void test_add_and_query(void) {
    printf("=== test_add_and_query ===\n");
    BloomFilter bf;
    bloom_init(&bf);

    /* 插入几个字符串 */
    const char *items[] = {"hello", "world", "postgres", "bloom"};
    for (int i = 0; i < 4; i++) {
        bloom_add(&bf, items[i], strlen(items[i]) + 1);
    }
    bloom_dump(&bf, "插入 4 个元素后");

    /* 查询已插入的: 应该都返回 true */
    for (int i = 0; i < 4; i++) {
        bool found = bloom_might_contain(&bf, items[i], strlen(items[i]) + 1);
        assert(found);
        printf("  \"%s\" → 可能存在: %s\n", items[i], found ? "YES" : "NO");
    }

    printf("  PASS\n\n");
}

static void test_true_negative(void) {
    printf("=== test_true_negative ===\n");
    BloomFilter bf;
    bloom_init(&bf);

    /* 只插入 "hello" */
    bloom_add(&bf, "hello", 6);

    /* 查询 "world" (没插入过): 应该返回 false (肯定不存在) */
    bool found = bloom_might_contain(&bf, "world", 6);
    assert(!found);
    printf("  \"world\" (未插入) → 肯定不存在: %s\n", found ? "YES" : "NO");

    /* 查询 "postgres" (没插入过) */
    found = bloom_might_contain(&bf, "postgres", 9);
    assert(!found);
    printf("  \"postgres\" (未插入) → 肯定不存在: %s\n", found ? "YES" : "NO");

    printf("  PASS (无假阴性)\n\n");
}

static void test_false_positive_rate(void) {
    printf("=== test_false_positive_rate ===\n");
    BloomFilter bf;
    bloom_init(&bf);

    /* 插入 50 个元素 */
    char buf[32];
    for (int i = 0; i < 50; i++) {
        snprintf(buf, sizeof(buf), "item_%d", i);
        bloom_add(&bf, buf, strlen(buf) + 1);
    }
    bloom_dump(&bf, "插入 50 个元素后");

    /* 查询 1000 个未插入的元素, 统计假阳性 */
    int false_positives = 0;
    for (int i = 1000; i < 2000; i++) {
        snprintf(buf, sizeof(buf), "item_%d", i);
        if (bloom_might_contain(&bf, buf, strlen(buf) + 1)) {
            false_positives++;
        }
    }
    printf("  查询 1000 个未插入元素, 假阳性数 = %d (%.1f%%)\n",
           false_positives, false_positives / 10.0);

    /* 假阳性率应该比较低 (< 20%) */
    assert(false_positives < 200);
    printf("  PASS (假阳性率 < 20%%)\n\n");
}

static void test_reset(void) {
    printf("=== test_reset ===\n");
    BloomFilter bf;
    bloom_init(&bf);

    bloom_add(&bf, "test", 5);
    assert(bloom_might_contain(&bf, "test", 5));

    /* 重置 */
    bloom_init(&bf);
    assert(!bloom_might_contain(&bf, "test", 5));
    assert(bf.n_added == 0);
    printf("  重置后所有元素消失: OK\n");

    printf("  PASS\n\n");
}

int main(void) {
    test_bit_ops();
    test_add_and_query();
    test_true_negative();
    test_false_positive_rate();
    test_reset();

    printf("========================================\n");
    printf("practice31 全部通过!\n");
    printf("========================================\n");
    return 0;
}

/*
 * 进阶思考题:
 *
 * 1. 为什么 bloom filter "无假阴性"?
 *    (提示: 插入时所有位置 1, 查询时只要有一个 0 就返回 false;
 *           已插入的元素所有位都是 1, 不会返回 false)
 *
 * 2. 为什么有假阳性?
 *    (提示: 不同元素的哈希可能撞到同一位置, 导致未插入的元素
 *           恰好所有位都被其他元素设成 1)
 *
 * 3. 假阳性率和什么有关?
 *    (提示: (a) 位数组大小 m; (b) 哈希函数个数 k; (c) 已插入元素数 n)
 *    m 越大 → 假阳性越低 (但占内存)
 *    k 太少 → 覆盖不够; k 太多 → 位数组被填满太快
 *    最优 k ≈ (m/n) * ln(2)
 *
 * 4. PG 的 hash join 怎么用 bloom filter?
 *    (提示: build 端建 bloom filter, probe 端先查 bloom filter,
 *           过滤掉肯定不匹配的行, 减少实际 hash 查找)
 *    为什么不用 hash table 直接查? (提示: bloom filter 更小, cache 友好)
 *
 * 5. 为什么用 byte 数组而不是 int 数组存 bit?
 *    (提示: byte 更细粒度, int 可能浪费; 但 int 操作更少次数)
 *    PG 用 uint64 数组 (一次处理 64 位), 为什么? (提示: 性能)
 *
 * 6. 能不能从 bloom filter 删除元素?
 *    (提示: 不能! 因为多个元素可能共享同一 bit, 删一个会影响其他)
 *    Counting bloom filter 用计数器代替 bit, 支持删除, 代价是什么?
 *
 * 7. 本题用 3 个哈希函数 (BLOOM_K=3), 2048 位, 插入 50 个元素。
 *    理论假阳性率约多少?
 *    (公式: (1 - e^(-kn/m))^k = (1 - e^(-3*50/2048))^3 ≈ 0.7%)
 *    和你测出的假阳性率对比?
 *
 * 8. Bloom filter 和 hash table 的区别?
 *    (提示: bloom filter 不存原始数据, 只存 bit; 不能遍历, 不能取值,
 *           只能查"可能存在"; 优势: 极省内存)
 */