tint/utils: Optimise HashmapBase::Scan()
Avoid an integer modulo for each scan iteration.
Change-Id: Ie80af4620b39769db622b4ab175b5639cf9ade8e
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/108260
Reviewed-by: Corentin Wallez <cwallez@chromium.org>
Kokoro: Ben Clayton <bclayton@google.com>
Commit-Queue: Ben Clayton <bclayton@google.com>
Auto-Submit: Ben Clayton <bclayton@google.com>
diff --git a/src/tint/utils/hashmap_base.h b/src/tint/utils/hashmap_base.h
index 0460373..ca0712a 100644
--- a/src/tint/utils/hashmap_base.h
+++ b/src/tint/utils/hashmap_base.h
@@ -453,12 +453,18 @@
/// * must return Action::kStop within one whole cycle of the slots.
template <typename F>
void Scan(size_t start, F&& f) const {
- size_t index = start;
- for (size_t distance = 0; distance < slots_.Length(); distance++) {
+ size_t distance = 0;
+ for (size_t index = start; index < slots_.Length(); index++) {
if (f(distance, index) == Action::kStop) {
return;
}
- index = Wrap(index + 1);
+ distance++;
+ }
+ for (size_t index = 0; index < start; index++) {
+ if (f(distance, index) == Action::kStop) {
+ return;
+ }
+ distance++;
}
tint::diag::List diags;
TINT_ICE(Utils, diags) << "HashmapBase::Scan() looped entire map without finding a slot";