1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
// Port of box2d-cpp-reference/src/table.h and src/table.c
//
// An open-addressing hash set of u64 keys (a key of 0 is the empty sentinel).
// Linear probing for lookup, backward-shift deletion to keep probe chains tight.
// The C `b2SetItem` is just a `uint64_t key`, so the backing store is a
// `Vec<u64>` whose length is always the (power-of-two) capacity.
//
// b2CountSetBits, defined in this C file, lives in bitset.rs next to the type it
// operates on.
//
// SPDX-FileCopyrightText: 2023 Erin Catto
// SPDX-License-Identifier: MIT
use crate::core::round_up_power_of2;
/// Build a symmetric key from a pair of shape indices. (B2_SHAPE_PAIR_KEY)
///
/// The smaller index goes in the high 32 bits so `(a, b)` and `(b, a)` map to
/// the same key.
pub fn shape_pair_key(k1: i32, k2: i32) -> u64 {
if k1 < k2 {
(k1 as u64) << 32 | (k2 as u64)
} else {
(k2 as u64) << 32 | (k1 as u64)
}
}
/// An open-addressing hash set of non-zero u64 keys. (b2HashSet)
#[derive(Debug, Clone, Default)]
pub struct HashSet {
/// Backing slots; `items.len()` is the capacity. A slot of 0 is empty.
pub(crate) items: Vec<u64>,
pub(crate) count: u32,
}
// Murmur hash finalizer. A good mixer matters here because keys are built from
// pairs of increasing integers, where a simple XOR hash collides heavily.
fn key_hash(key: u64) -> u64 {
let mut h = key;
h ^= h >> 33;
h = h.wrapping_mul(0xff51afd7ed558ccd);
h ^= h >> 33;
h = h.wrapping_mul(0xc4ceb9fe1a85ec53);
h ^= h >> 33;
h
}
impl HashSet {
/// Create a set with at least `capacity` slots, rounded up to a power of two
/// (minimum 16). (b2CreateSet)
pub fn new(capacity: i32) -> HashSet {
// Capacity must be a power of 2
let capacity = if capacity > 16 {
round_up_power_of2(capacity)
} else {
16
};
HashSet {
items: vec![0; capacity as usize],
count: 0,
}
}
/// Release the storage. (b2DestroySet)
pub fn destroy(&mut self) {
self.items = Vec::new();
self.count = 0;
}
/// Remove all keys, keeping capacity. (b2ClearSet)
pub fn clear(&mut self) {
self.count = 0;
self.items.iter_mut().for_each(|slot| *slot = 0);
}
/// Number of keys in the set. (b2GetSetCount)
pub fn count(&self) -> i32 {
self.count as i32
}
/// Number of allocated slots. (b2GetSetCapacity)
pub fn capacity(&self) -> i32 {
self.items.len() as i32
}
/// Byte size of the backing storage. (b2GetHashSetBytes)
pub fn bytes(&self) -> i32 {
self.items.len() as i32 * core::mem::size_of::<u64>() as i32
}
fn cap(&self) -> u32 {
self.items.len() as u32
}
// Find the slot holding `key`, or the first empty slot on its probe chain.
fn find_slot(&self, key: u64, hash: u64) -> usize {
let capacity = self.cap();
let mut index = (hash as u32) & (capacity - 1);
while self.items[index as usize] != 0 && self.items[index as usize] != key {
index = (index + 1) & (capacity - 1);
}
index as usize
}
fn add_key_have_capacity(&mut self, key: u64, hash: u64) {
let index = self.find_slot(key, hash);
debug_assert!(self.items[index] == 0);
self.items[index] = key;
self.count += 1;
}
fn grow_table(&mut self) {
let old_items = core::mem::take(&mut self.items);
self.count = 0;
// Capacity must be a power of 2
self.items = vec![0; 2 * old_items.len()];
// Transfer items into new array
for &key in &old_items {
if key == 0 {
// this item was empty
continue;
}
let hash = key_hash(key);
self.add_key_have_capacity(key, hash);
}
}
/// True if `key` is present. (b2ContainsKey)
pub fn contains_key(&self, key: u64) -> bool {
// key of zero is a sentinel
debug_assert!(key != 0);
let hash = key_hash(key);
let index = self.find_slot(key, hash);
self.items[index] == key
}
/// Add `key`. Returns true if it was already present. (b2AddKey)
pub fn add_key(&mut self, key: u64) -> bool {
// key of zero is a sentinel
debug_assert!(key != 0);
let hash = key_hash(key);
debug_assert!(hash != 0);
let index = self.find_slot(key, hash);
if self.items[index] != 0 {
// Already in set
debug_assert!(self.items[index] == key);
return true;
}
if 2 * self.count >= self.cap() {
self.grow_table();
}
self.add_key_have_capacity(key, hash);
false
}
/// Remove `key`. Returns true if it was found. (b2RemoveKey)
// See https://en.wikipedia.org/wiki/Open_addressing
pub fn remove_key(&mut self, key: u64) -> bool {
let hash = key_hash(key);
let mut i = self.find_slot(key, hash);
if self.items[i] == 0 {
// Not in set
return false;
}
// Mark item i as unoccupied
self.items[i] = 0;
debug_assert!(self.count > 0);
self.count -= 1;
// Attempt to fill item i
let mask = self.items.len() - 1;
let mut j = i;
loop {
j = (j + 1) & mask;
if self.items[j] == 0 {
break;
}
// k is the first slot for the hash of j
let hash_j = key_hash(self.items[j]);
let k = (hash_j as usize) & mask;
// determine if k lies cyclically in (i,j]
// i <= j: | i..k..j |
// i > j: |.k..j i....| or |....j i..k.|
if i <= j {
if i < k && k <= j {
continue;
}
} else if i < k || k <= j {
continue;
}
// Move j into i
self.items[i] = self.items[j];
// Mark item j as unoccupied
self.items[j] = 0;
i = j;
}
true
}
}