《游戏引擎实现原理》7.2 位集合、环形缓冲与侵入式链表

// file: src/core/bitset.ts
// tier: L1
// verify: npx vitest run src/core/bitset.test.ts
//
// 位集合：用 Uint32Array 的每一位表示一个布尔状态。1M 个标记只占 128 KB，
// 且「计数」和「找下一个置位」都用位运算一次处理 32 个，比布尔数组快得多。

export class BitSet {
  #words: Uint32Array;
  #size: number;

  constructor(size: number) {
    if (size < 0) throw new RangeError('size must be >= 0');
    this.#size = size;
    this.#words = new Uint32Array((size + 31) >>> 5);
  }

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

  /** 容量以 32 位字为单位向上取整。 */
  get wordCount(): number {
    return this.#words.length;
  }

  set(i: number): void {
    if (i < 0 || i >= this.#size) throw new RangeError(`bit ${i} out of range`);
    this.#words[i >>> 5] |= 1 << (i & 31);
  }

  clear(i: number): void {
    if (i < 0 || i >= this.#size) throw new RangeError(`bit ${i} out of range`);
    this.#words[i >>> 5] &= ~(1 << (i & 31));
  }

  toggle(i: number): void {
    this.#words[i >>> 5] ^= 1 << (i & 31);
  }

  test(i: number): boolean {
    if (i < 0 || i >= this.#size) return false;
    return (this.#words[i >>> 5] & (1 << (i & 31))) !== 0;
  }

  /** 置位总数：每个字用 popcount 位技巧一次数完 32 位。 */
  popcount(): number {
    let total = 0;
    for (let w = 0; w < this.#words.length; w++) {
      let x = this.#words[w];
      x = x - ((x >>> 1) & 0x55555555);
      x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
      x = (x + (x >>> 4)) & 0x0f0f0f0f;
      total += Math.imul(x, 0x01010101) >>> 24;
    }
    return total;
  }

  /** 只遍历置位的下标，跳过成片的 0。 */
  *setBits(): Generator<number> {
    for (let w = 0; w < this.#words.length; w++) {
      let x = this.#words[w];
      while (x !== 0) {
        const lsb = x & -x; // 最低置位
        const bit = 31 - Math.clz32(lsb);
        yield (w << 5) + bit;
        x ^= lsb; // 抹掉这一位
      }
    }
  }
}

// file: src/core/ring-buffer.ts
// tier: L1
// verify: npx vitest run src/core/ring-buffer.test.ts
//
// 环形缓冲：固定容量、首尾相接的队列。构造时一次性分配底层数组，
// 之后 push / pop / shift 都不再分配——这是它在帧内热路径上的全部价值。

export class RingBuffer<T> {
  #buf: (T | undefined)[];
  #cap: number;
  #head = 0; // 指向最早元素
  #count = 0;

  constructor(capacity: number) {
    if (capacity <= 0) throw new RangeError('capacity must be > 0');
    this.#cap = capacity;
    this.#buf = new Array(capacity);
  }

  get capacity(): number {
    return this.#cap;
  }

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

  get isFull(): boolean {
    return this.#count === this.#cap;
  }

  get isEmpty(): boolean {
    return this.#count === 0;
  }

  /** 入队；满则返回 false（不覆盖、不分配）。 */
  push(value: T): boolean {
    if (this.#count === this.#cap) return false;
    this.#buf[(this.#head + this.#count) % this.#cap] = value;
    this.#count++;
    return true;
  }

  /** 入队；满则覆盖最旧元素并返回 true（用于「最近 N 帧」这类场景）。 */
  pushOverwrite(value: T): void {
    if (this.#count < this.#cap) {
      this.#buf[(this.#head + this.#count) % this.#cap] = value;
      this.#count++;
    } else {
      this.#buf[this.#head] = value;
      this.#head = (this.#head + 1) % this.#cap;
    }
  }

  /** 出队（先进先出）。 */
  shift(): T | undefined {
    if (this.#count === 0) return undefined;
    const v = this.#buf[this.#head];
    this.#buf[this.#head] = undefined;
    this.#head = (this.#head + 1) % this.#cap;
    this.#count--;
    return v;
  }

  /** 看队头但不移除。 */
  peek(): T | undefined {
    return this.#count === 0 ? undefined : this.#buf[this.#head];
  }

  /** 按入队顺序遍历，不回绕到预留槽。 */
  *[Symbol.iterator](): Generator<T> {
    for (let i = 0; i < this.#count; i++) {
      yield this.#buf[(this.#head + i) % this.#cap] as T;
    }
  }

  toArray(): T[] {
    return [...this];
  }
}

// file: src/core/intrusive-list.ts
// tier: L1
// verify: npx vitest run src/core/intrusive-list.test.ts
//
// 侵入式链表：链表节点（next / prev）不额外分配，直接长在对象自己身上。
// 这里的对象是一段按索引编号的池，next / prev 是两条平行的 Int32Array，
// 所以「挂进链表」不产生任何新分配，O(1) 插入与删除。

const NIL = -1;

export class IntrusiveList {
  #next: Int32Array;
  #prev: Int32Array;
  #capacity: number;
  #head = NIL;
  #tail = NIL;
  #count = 0;

  constructor(capacity: number) {
    if (capacity <= 0) throw new RangeError('capacity must be > 0');
    this.#capacity = capacity;
    this.#next = new Int32Array(capacity).fill(NIL);
    this.#prev = new Int32Array(capacity).fill(NIL);
  }

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

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

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

  /** 越界 id 必须显式拒绝：Int32Array 越界写入是静默丢弃的。 */
  #check(id: number): void {
    if (id < 0 || id >= this.#capacity) {
      throw new RangeError(`node id ${id} out of capacity ${this.#capacity}`);
    }
  }

  /** 把节点 id 挂到链表尾部，O(1)，零分配。 */
  pushBack(id: number): void {
    this.#check(id);
    this.#prev[id] = this.#tail;
    this.#next[id] = NIL;
    if (this.#tail === NIL) this.#head = id;
    else this.#next[this.#tail] = id;
    this.#tail = id;
    this.#count++;
  }

  /** 把节点 id 挂到链表头部，O(1)。 */
  pushFront(id: number): void {
    this.#check(id);
    this.#next[id] = this.#head;
    this.#prev[id] = NIL;
    if (this.#head === NIL) this.#tail = id;
    else this.#prev[this.#head] = id;
    this.#head = id;
    this.#count++;
  }

  /** 从链表中摘除节点 id，O(1)，不需要遍历。 */
  remove(id: number): void {
    this.#check(id);
    const p = this.#prev[id];
    const n = this.#next[id];
    if (p === NIL) this.#head = n;
    else this.#next[p] = n;
    if (n === NIL) this.#tail = p;
    else this.#prev[n] = p;
    this.#prev[id] = NIL;
    this.#next[id] = NIL;
    this.#count--;
  }

  /** 弹出头部节点并返回其 id。 */
  popFront(): number {
    if (this.#head === NIL) return NIL;
    const id = this.#head;
    this.remove(id);
    return id;
  }

  /** 从任意节点出发向后遍历（含它自己）。id 越界或为 NIL 时不产出。 */
  *from(id: number): Generator<number> {
    if (id < 0 || id >= this.#capacity) return;
    let cur = id;
    while (cur !== NIL) {
      yield cur;
      cur = this.#next[cur];
    }
  }

  /** 顺序遍历整条链表。 */
  *[Symbol.iterator](): Generator<number> {
    yield* this.from(this.#head);
  }

  toArray(): number[] {
    return [...this];
  }
}

export { NIL };