Module BSTHashMap

BSTHashMap

C++: https://github.com/SARDONYX-forks/CommonLibVR/blob/feature/add-ng-release-ci/include/RE/B/BSTHashMap.h

Expected Memory Layout (Simplified)

This section explains the internal structure of BSTHashMap, focusing on how entries are stored and how chains are formed when collisions occur.

---

Basic Structure (Before Insertion)

Empty is represented by a byte slice of 0 bytes. This is because it is zero initialized at the same time as the memory allocation. However, it is impossible to determine whether it is already initialized or false. Therefore, when pushing, the pointer to the next entry is filled with a sentinel value(0xdeadbeef address).

In this way, it is possible to distinguish between empty and occupied. In other words, by looking at next, it is possible to tell if data is contained.

// Entry<T> array
// Accessed via get_entry_for(...)

┌────────────┬────────────┬────────────┬────────────┐
│ Entry[0]   │ Entry[1]   │ Entry[2]   │ ...        │  ← capacity N
├────────────┼────────────┼────────────┼────────────┤
│ empty      │ empty      │ empty      │ ...        │
└────────────┴────────────┴────────────┴────────────┘

---

Basic Insertion Case (Slot Is Empty)

// Emplace directly into Entry[i] corresponding to unwrap_key(a_value)!

┌────────────┬────────────┬────────────┬────────────┐
│ Entry[0]   │ Entry[1]   │ Entry[2]   │ ...        │
├────────────┼────────────┼────────────┼────────────┤
│ empty      │            │ value_data: a_value     │
│            │            │ next: _sentinel         │
└────────────┴────────────┴────────────┴────────────┘
                                   ↑
                    get_entry_for(key)

---

Collision Case (Chaining with next Pointer)

// Entry[2] is occupied → emplace into a new free Entry (e.g., Entry[4])
// Update Entry[2].next to point to Entry[4]

┌────────────┬────────────┬────────────┬────────────┬────────────┐
│ Entry[0]   │ Entry[1]   │ Entry[2]   │ Entry[3]   │ Entry[4]   │
├────────────┼────────────┼────────────┼────────────┼────────────┤
│ empty      │            │ value_data: A           │ unused     │ value_data: B
│            │            │ next ___________________/            │ next: _sentinel
└────────────┴────────────┴────────────┴────────────┴────────────┘
                            ↑
                               entry->next = &Entry[4]

---

Eviction Case (Entry Needs Relocation)

// A is in Entry[2] but belongs in Entry[0]
// Move A to Entry[4] → Emplace B into Entry[2]

┌────────────┬────────────┬────────────┬────────────┬────────────┐
│ Entry[0]   │ Entry[1]   │ Entry[2]   │ Entry[3]   │ Entry[4]   │
├────────────┼────────────┼────────────┼────────────┼────────────┤
│            │            │ value_data: B           │ unused     │ value_data: A
│            │            │ next: _sentinel         │            │ next: _sentinel
│            │            │                         │            │
│            │            │ ← emplace here          │ ← evicted  │
└────────────┴────────────┴────────────┴────────────┴────────────┘

Structs

BSTHashMap

BSTHashMapIter

BSTScatterKeyExtractor

BSTScatterTableHeapAllocator

An allocator implementation for the BSTScatterTable.

BSTStaticHashMapBaseAllocator

BSTStaticHashMapBase::Allocator equivalent in Rust using GenericArray

UnkKey

dummy type

UnkValue

dummy value

Traits

Allocator

A trait representing a generic memory allocator. Provides methods for allocating and deallocating raw bytes.

KeyStrategy