typedef struct _NXMapTable {
    const struct _NXMapTablePrototype *prototype;
    unsigned count;
    unsigned nbBucketsMinusOne;
    void *buckets;
} NXMapTable;

typedef struct _NXMapTablePrototype {
    unsigned (*hash)(NXMapTable *table, const void *key);
    int      (*isEqual)(NXMapTable *table, const void *key1, const void *key2);
    void     (*free)(NXMapTable *table, void *key, void *value);
    int style;
} NXMapTablePrototype;

typedef struct _MapPair {
    const void *key;
    const void *value;
} MapPair;

#define NX_MAPNOTAKEY ((void *)(-1))

static inline unsigned bucketOfHash(NXMapTable *table, unsigned hash) {
    // 桶数始终是 2 的幂，所以 hash & (bucketCount - 1)
    // 等价于 hash % bucketCount，但比除法取模更快。
    return hash & table->nbBucketsMinusOne;
}

static inline unsigned nextIndex(NXMapTable *table, unsigned index) {
    // 线性探测的“下一个桶”。
    // & mask 让 index 到尾部后自然绕回 0。
    return (index + 1) & table->nbBucketsMinusOne;
}

NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity) {
    NXMapTable *table = malloc(sizeof(NXMapTable));

    // prototype 必须提供三个核心回调，style 当前必须为 0。
    if (!prototype.hash || !prototype.isEqual || !prototype.free || prototype.style) {
        return NULL;
    }

    // runtime 会复用内容相同的 prototype，避免每张表都复制一份策略。
    table->prototype = canonicalizePrototype(prototype);
    table->count = 0;

    // 计算桶数：exp2u(log2u(capacity) + 1)。
    // 结果是一个 2 的幂；字段保存 bucketCount - 1。
    table->nbBucketsMinusOne = nextPowerOfTwoAboveCapacity(capacity) - 1;

    // 所有桶初始都写成 NX_MAPNOTAKEY，表示空。
    table->buckets = allocBuckets(table->nbBucketsMinusOne + 1);
    return table;
}

static inline void *
_NXMapMemberWithHash(NXMapTable *table, const void *key,
                     unsigned hash, void **value)
{
    MapPair *pairs = (MapPair *)table->buckets;
    unsigned index = bucketOfHash(table, hash);

    for (;;) {
        MapPair *pair = pairs + index;

        // 开放寻址中，探测链一旦遇到空桶，就说明 key 不存在。
        // 如果目标 key 曾经插入过，它一定会位于空桶之前。
        if (pair->key == NX_MAPNOTAKEY) {
            return NX_MAPNOTAKEY;
        }

        // 先做指针身份比较，失败后才走 prototype 的 isEqual 回调。
        if (pair->key == key || table->prototype->isEqual(table, pair->key, key)) {
            *value = (void *)pair->value;
            return (void *)pair->key; // 返回表里保存的原始 key。
        }

        // 冲突：继续看下一个桶。mask 会让 index 环形回绕。
        index = nextIndex(table, index);
    }
}

void *NXMapInsertWithHash(NXMapTable *table, const void *key,
                          unsigned hash, const void *value)
{
    if (key == NX_MAPNOTAKEY) {
        // -1 是内部空桶标记，不能作为用户 key。
        return NULL;
    }

    MapPair *pairs = (MapPair *)table->buckets;
    unsigned index = bucketOfHash(table, hash);
    unsigned bucketCount = table->nbBucketsMinusOne + 1;

    for (;;) {
        MapPair *pair = pairs + index;

        if (pair->key == NX_MAPNOTAKEY) {
            // 找到空桶：插入新 key/value。
            pair->key = key;
            pair->value = value;
            table->count++;

            // 负载因子超过 3/4 后扩容，降低后续探测长度。
            if (table->count * 4 > bucketCount * 3) {
                _NXMapRehash(table);
            }
            return NULL; // 新插入，没有旧 value。
        }

        if (pair->key == key || table->prototype->isEqual(table, pair->key, key)) {
            // key 已存在：只替换 value，不替换原始 key。
            const void *old = pair->value;
            if (old != value) pair->value = value;
            return (void *)old;
        }

        // 冲突：线性探测下一个桶。
        index = nextIndex(table, index);
    }
}

static void _NXMapRehash(NXMapTable *table) {
    MapPair *oldPairs = (MapPair *)table->buckets;
    unsigned oldBucketCount = table->nbBucketsMinusOne + 1;
    unsigned oldCount = table->count;

    // 桶数翻倍。因为字段保存的是 bucketCount - 1，
    // 新 mask = 2 * oldBucketCount - 1。
    table->nbBucketsMinusOne = 2 * oldBucketCount - 1;
    table->count = 0;
    table->buckets = allocBuckets(table->nbBucketsMinusOne + 1);

    // 不能直接 memcpy。桶位置依赖 mask，扩容后每个 key 都要重新定位。
    for (unsigned i = 0; i < oldBucketCount; i++) {
        if (oldPairs[i].key != NX_MAPNOTAKEY) {
            NXMapInsert(table, oldPairs[i].key, oldPairs[i].value);
        }
    }

    // 如果重插后 count 变了，通常说明 hash/isEqual 的不变量被破坏。
    assert(oldCount == table->count);
    freeBuckets(oldPairs);
}

void *NXMapRemove(NXMapTable *table, const void *key) {
    unsigned start = bucketOf(table, key);

    // 1. 从 start 开始扫描连续非空桶，找到目标 key。
    //    同时计算 chain 长度：这段连续桶都可能依赖彼此保持可查找。
    unsigned chain = scanUntilEmptyBucket(table, start, key);
    if (chain == 0) return NULL;

    // 2. 把这段连续桶临时保存下来，目标 key 除外。
    MapPair saved[...];
    void *oldValue = copyChainExceptRemovedKey(saved, table, start, chain, key);

    // 3. 把原连续桶全部清空，并相应减少 count。
    clearChain(table, start, chain);

    // 4. 重新插入剩余元素，让它们按当前 mask 形成新的正确探测链。
    for (each pair in saved) {
        NXMapInsert(table, pair.key, pair.value);
    }

    return oldValue;
}

// _read_images 第一次运行时创建类名表。
NXMapTablePrototype namedClassesPrototype = NXStrValueMapPrototype;
gdb_objc_realized_classes =
    NXCreateMapTable(namedClassesPrototype, namedClassesSize);

// 添加类名映射时，调用方已经算好 hash。
unsigned hash = namedClassTableHash(name);
NXMapInsertWithHash(gdb_objc_realized_classes, name, hash, signedCls);

// 查找类时复用同一个 hash，避免重复计算字符串 hash。
void *result = NXMapGetWithHash(gdb_objc_realized_classes, name, hash);

void *NXMapKeyCopyingInsert(NXMapTable *table, const void *key, const void *value)
{
    void *realValue = NULL;
    void *realKey = NXMapMember(table, key, &realValue);

    if (realKey == NX_MAPNOTAKEY) {
        // 表里还没有这个 key：如果 key 来自可卸载镜像，复制一份稳定字符串。
        realKey = strdupIfMutable((char *)key);
    }

    // 表里已有 key 时，沿用表内原始 key，避免同名字符串重复分配。
    return NXMapInsert(table, realKey, value);
}

void *NXMapKeyFreeingRemove(NXMapTable *table, const void *key)
{
    void *realValue = NULL;
    void *realKey = NXMapMember(table, key, &realValue);

    if (realKey != NX_MAPNOTAKEY) {
        realValue = NXMapRemove(table, realKey);
        // 释放表内保存的真实 key，而不是调用方传入的那个 key。
        freeIfMutable((char *)realKey);
    }
    return realValue;
}