box3d_rust/
table.rs

1// Port of box3d-cpp-reference/src/table.h and src/table.c
2//
3// An open-addressing hash set of u64 keys. Unlike Box2D (which stores only the
4// key and treats 0 as empty), Box3D stores `{ key, hash }` and empty slots are
5// identified by `hash == 0`. Linear probing for lookup; backward-shift deletion
6// to keep probe chains tight. The stored hash is reused on grow and on deletion
7// repair so the home slot is known without recomputing.
8//
9// `b3CountSetBits` is defined in table.c in C but lives on `BitSet` in this port.
10//
11// SPDX-FileCopyrightText: 2025 Erin Catto
12// SPDX-License-Identifier: MIT
13
14use crate::constants::{CHILD_MASK, SHAPE_MASK, SHAPE_POWER};
15use crate::core::round_up_power_of2;
16
17/// One slot in the open-addressing table. (b3SetItem)
18///
19/// Empty slots have `hash == 0` (and typically `key == 0`). Occupied slots store
20/// both the key and its Murmur-mixed hash so grow/remove can reuse it.
21#[derive(Debug, Clone, Copy, Default)]
22#[repr(C)]
23pub struct SetItem {
24    pub key: u64,
25    pub hash: u32,
26}
27
28/// Build a symmetric key from a pair of shape indices and a child index.
29/// (b3ShapePairKey)
30///
31/// The smaller shape index goes in the high bits so `(a, b, c)` and `(b, a, c)`
32/// map to the same key. Layout: `[shape_lo : 22][shape_hi : 22][child : 20]`.
33pub fn shape_pair_key(s1: i32, s2: i32, c: i32) -> u64 {
34    if s1 < s2 {
35        ((SHAPE_MASK & s1 as u64) << (64 - SHAPE_POWER))
36            | ((SHAPE_MASK & s2 as u64) << (64 - 2 * SHAPE_POWER))
37            | (CHILD_MASK & c as u64)
38    } else {
39        ((SHAPE_MASK & s2 as u64) << (64 - SHAPE_POWER))
40            | ((SHAPE_MASK & s1 as u64) << (64 - 2 * SHAPE_POWER))
41            | (CHILD_MASK & c as u64)
42    }
43}
44
45/// An open-addressing hash set of non-zero u64 keys. (b3HashSet)
46#[derive(Debug, Clone, Default)]
47pub struct HashSet {
48    /// Backing slots; `items.len()` is the capacity. A slot with `hash == 0` is empty.
49    pub(crate) items: Vec<SetItem>,
50    pub(crate) count: u32,
51}
52
53// Murmur hash finalizer truncated to u32. A good mixer matters here because
54// keys are built from pairs of increasing integers, where a simple XOR hash
55// collides heavily.
56// https://lemire.me/blog/2018/08/15/fast-strongly-universal-64-bit-hashing-everywhere/
57fn key_hash(key: u64) -> u32 {
58    let mut h = key;
59    h ^= h >> 33;
60    h = h.wrapping_mul(0xff51afd7ed558ccd);
61    h ^= h >> 33;
62    h = h.wrapping_mul(0xc4ceb9fe1a85ec53);
63    h ^= h >> 33;
64    h as u32
65}
66
67impl HashSet {
68    /// Create a set with at least `capacity` slots, rounded up to a power of two
69    /// (minimum 16). (b3CreateSet)
70    pub fn new(capacity: i32) -> HashSet {
71        // Capacity must be a power of 2
72        let capacity = if capacity > 16 {
73            round_up_power_of2(capacity)
74        } else {
75            16
76        };
77
78        HashSet {
79            items: vec![SetItem::default(); capacity as usize],
80            count: 0,
81        }
82    }
83
84    /// Release the storage. (b3DestroySet)
85    pub fn destroy(&mut self) {
86        self.items = Vec::new();
87        self.count = 0;
88    }
89
90    /// Remove all keys, keeping capacity. (b3ClearSet)
91    pub fn clear(&mut self) {
92        self.count = 0;
93        self.items
94            .iter_mut()
95            .for_each(|slot| *slot = SetItem::default());
96    }
97
98    /// Number of keys in the set.
99    pub fn count(&self) -> i32 {
100        self.count as i32
101    }
102
103    /// Number of allocated slots.
104    pub fn capacity(&self) -> i32 {
105        self.items.len() as i32
106    }
107
108    /// Byte size of the backing storage. (b3GetHashSetBytes)
109    pub fn bytes(&self) -> i32 {
110        self.items.len() as i32 * core::mem::size_of::<SetItem>() as i32
111    }
112
113    fn cap(&self) -> u32 {
114        self.items.len() as u32
115    }
116
117    // Find the slot holding `key`, or the first empty slot on its probe chain.
118    fn find_slot(&self, key: u64, hash: u32) -> usize {
119        let capacity = self.cap();
120        let mut index = hash & (capacity - 1);
121        while self.items[index as usize].hash != 0 && self.items[index as usize].key != key {
122            index = (index + 1) & (capacity - 1);
123        }
124        index as usize
125    }
126
127    fn add_key_have_capacity(&mut self, key: u64, hash: u32) {
128        let index = self.find_slot(key, hash);
129        debug_assert!(self.items[index].hash == 0);
130        self.items[index].key = key;
131        self.items[index].hash = hash;
132        self.count += 1;
133    }
134
135    fn grow_table(&mut self) {
136        let old_items = core::mem::take(&mut self.items);
137
138        self.count = 0;
139        // Capacity must be a power of 2
140        self.items = vec![SetItem::default(); 2 * old_items.len()];
141
142        // Transfer items into new array
143        for item in &old_items {
144            if item.hash == 0 {
145                // this item was empty
146                continue;
147            }
148
149            self.add_key_have_capacity(item.key, item.hash);
150        }
151    }
152
153    /// True if `key` is present. (b3ContainsKey)
154    pub fn contains_key(&self, key: u64) -> bool {
155        // key of zero is a sentinel
156        debug_assert!(key != 0);
157        let hash = key_hash(key);
158        let index = self.find_slot(key, hash);
159        self.items[index].key == key
160    }
161
162    /// Add `key`. Returns true if it was already present. (b3AddKey)
163    pub fn add_key(&mut self, key: u64) -> bool {
164        // key of zero is a sentinel
165        debug_assert!(key != 0);
166
167        let hash = key_hash(key);
168        debug_assert!(hash != 0);
169
170        let index = self.find_slot(key, hash);
171        if self.items[index].hash != 0 {
172            // Already in set
173            debug_assert!(self.items[index].hash == hash && self.items[index].key == key);
174            return true;
175        }
176
177        if 2 * self.count >= self.cap() {
178            self.grow_table();
179        }
180
181        self.add_key_have_capacity(key, hash);
182        false
183    }
184
185    /// Remove `key`. Returns true if it was found. (b3RemoveKey)
186    // See https://en.wikipedia.org/wiki/Open_addressing
187    pub fn remove_key(&mut self, key: u64) -> bool {
188        let hash = key_hash(key);
189        let mut i = self.find_slot(key, hash);
190        if self.items[i].hash == 0 {
191            // Not in set
192            return false;
193        }
194
195        // Mark item i as unoccupied
196        self.items[i].key = 0;
197        self.items[i].hash = 0;
198
199        debug_assert!(self.count > 0);
200        self.count -= 1;
201
202        // Attempt to fill item i
203        let capacity = self.cap() as usize;
204        let mut j = i;
205        loop {
206            j = (j + 1) & (capacity - 1);
207            if self.items[j].hash == 0 {
208                break;
209            }
210
211            // k is the first item for the hash of j
212            let k = (self.items[j].hash as usize) & (capacity - 1);
213
214            // determine if k lies cyclically in (i,j]
215            // i <= j: | i..k..j |
216            // i > j: |.k..j  i....| or |....j     i..k.|
217            if i <= j {
218                if i < k && k <= j {
219                    continue;
220                }
221            } else if i < k || k <= j {
222                continue;
223            }
224
225            // Move j into i
226            self.items[i] = self.items[j];
227
228            // Mark item j as unoccupied
229            self.items[j].key = 0;
230            self.items[j].hash = 0;
231
232            i = j;
233        }
234
235        true
236    }
237}
box3d_rust/table.rs

box3d_rust/
table.rs
