《游戏引擎实现原理》6.2 slot map 与世代句柄

// file: src/core/slotmap.ts
// tier: L1
// verify: npx vitest run src/core/slotmap.test.ts
//
// helio 内核：世代句柄（generational handle）+ 稀疏集（sparse set）。
// 用 32 位整数索引代替指针：索引 20 位 + 世代 12 位，句柄失效可检测。

/** 句柄：高位是世代，低位是槽位索引。0 是「空句柄」。 */
export type Handle = number;

const INDEX_BITS = 20;
const INDEX_MASK = (1 << INDEX_BITS) - 1;
const GEN_MASK = 0xfff; // 12 位世代

export function makeHandle(index: number, generation: number): Handle {
  return (((generation & GEN_MASK) << INDEX_BITS) | (index & INDEX_MASK)) >>> 0;
}

export function handleIndex(h: Handle): number {
  return h & INDEX_MASK;
}

export function handleGeneration(h: Handle): number {
  return (h >>> INDEX_BITS) & GEN_MASK;
}

export const NULL_HANDLE: Handle = 0;

/** 带世代校验的稀疏集：句柄失效（dangling）在访问时立即暴露。 */
export class SlotMap<T> {
  #slots: (T | undefined)[] = [];
  #generations: number[] = [];
  #free: number[] = [];
  #live = 0;

  get size(): number {
    return this.#live;
  }

  /** 分配一个新槽位，返回句柄。 */
  insert(value: T): Handle {
    let index: number;
    if (this.#free.length > 0) {
      index = this.#free.pop()!;
    } else {
      index = this.#slots.length;
      this.#slots.push(undefined);
      this.#generations.push(1);
    }
    this.#slots[index] = value;
    this.#live++;
    return makeHandle(index, this.#generations[index]);
  }

  /** 句柄有效则返回其值，否则 undefined（世代不符即失效）。 */
  get(h: Handle): T | undefined {
    if (h === NULL_HANDLE) return undefined;
    const i = handleIndex(h);
    if (i >= this.#slots.length) return undefined;
    if (this.#generations[i] !== handleGeneration(h)) return undefined;
    return this.#slots[i];
  }

  has(h: Handle): boolean {
    return this.get(h) !== undefined;
  }

  /** 校验句柄并返回其值；失效则抛错——用于「本应有效」的场景。 */
  expect(h: Handle): T {
    const v = this.get(h);
    if (v === undefined) {
      throw new Error(`Stale handle: 0x${h.toString(16)} (slot ${handleIndex(h)})`);
    }
    return v;
  }

  /** 移除并让世代自增，使所有旧句柄立即失效。 */
  remove(h: Handle): boolean {
    if (!this.has(h)) return false;
    const i = handleIndex(h);
    this.#slots[i] = undefined;
    this.#generations[i] = (this.#generations[i] + 1) & GEN_MASK;
    this.#free.push(i);
    this.#live--;
    return true;
  }

  /** 遍历所有活跃 (句柄, 值) 对，顺序按槽位索引。 */
  *entries(): Generator<[Handle, T]> {
    for (let i = 0; i < this.#slots.length; i++) {
      const v = this.#slots[i];
      if (v !== undefined) yield [makeHandle(i, this.#generations[i]), v];
    }
  }
}

// file: src/core/slotmap.test.ts
// tier: L1
// verify: npx vitest run src/core/slotmap.test.ts

import { describe, expect, it } from 'vitest';
import {
  NULL_HANDLE,
  SlotMap,
  handleGeneration,
  handleIndex,
  makeHandle,
} from './slotmap.ts';

describe('Handle 编解码', () => {
  it('往返一致', () => {
    const h = makeHandle(12345, 7);
    expect(handleIndex(h)).toBe(12345);
    expect(handleGeneration(h)).toBe(7);
  });

  it('NULL_HANDLE 索引与世代都是 0', () => {
    expect(handleIndex(NULL_HANDLE)).toBe(0);
    expect(handleGeneration(NULL_HANDLE)).toBe(0);
  });
});

describe('SlotMap', () => {
  it('插入后可取回', () => {
    const m = new SlotMap<string>();
    const h = m.insert('alpha');
    expect(m.get(h)).toBe('alpha');
    expect(m.size).toBe(1);
  });

  it('移除后旧句柄立即失效（世代自增）', () => {
    const m = new SlotMap<string>();
    const h = m.insert('alpha');
    m.remove(h);
    expect(m.get(h)).toBeUndefined();
    expect(m.has(h)).toBe(false);
  });

  it('槽位复用但新句柄与旧句柄不等（防悬垂引用）', () => {
    const m = new SlotMap<string>();
    const h1 = m.insert('alpha');
    m.remove(h1);
    const h2 = m.insert('beta');
    expect(handleIndex(h2)).toBe(handleIndex(h1)); // 复用同一槽位
    expect(h2).not.toBe(h1); // 但世代不同
    expect(m.get(h1)).toBeUndefined(); // 旧句柄不会读到新值
    expect(m.get(h2)).toBe('beta');
  });

  it('expect 对失效句柄抛错', () => {
    const m = new SlotMap<number>();
    const h = m.insert(42);
    m.remove(h);
    expect(() => m.expect(h)).toThrow(/Stale handle/);
  });

  it('NULL_HANDLE 永远取不到值', () => {
    const m = new SlotMap<number>();
    m.insert(1);
    expect(m.get(NULL_HANDLE)).toBeUndefined();
  });

  it('entries 只遍历活跃槽位', () => {
    const m = new SlotMap<number>();
    const a = m.insert(1);
    m.insert(2);
    const c = m.insert(3);
    m.remove(c);
    const seen = [...m.entries()].map(([, v]) => v);
    expect(seen).toEqual([1, 2]);
    expect(m.has(a)).toBe(true);
  });
});