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
// SPDX-License-Identifier: BSD-3-Clause
// Copyright (c) 2026 Fernando Sahmkow
/// @file string_utils.h
/// @brief Shared string utilities for CASC (and other storage) modules.
#pragma once
#include <whiteout/common_types.h>
#include <algorithm>
#include <cctype>
#include <string>
#include <string_view>
namespace whiteout::storages::common {
/// Return a lowercased copy of @p s (ASCII-only, locale-independent).
inline std::string toLower(const std::string& s) {
std::string r = s;
std::transform(r.begin(), r.end(), r.begin(),
[](unsigned char c) { return char(std::tolower(c)); });
return r;
}
/// Normalize a CASC path for lookup: lowercase, '/' → '\\', strip leading/trailing separators.
inline std::string normalizeCascPath(const std::string& s) {
std::string r = s;
for (auto& c : r) {
if (c == '/')
c = '\\';
c = static_cast<char>(std::tolower(static_cast<unsigned char>(c)));
}
// Strip leading separators without O(n²) erase(begin).
size_t start = 0;
while (start < r.size() && r[start] == '\\')
++start;
// Strip trailing separators.
size_t end = r.size();
while (end > start && r[end - 1] == '\\')
--end;
if (start == 0 && end == r.size())
return r;
return r.substr(start, end - start);
}
// ---------------------------------------------------------------------------
// Allocation-free counterparts
//
// Root index builds run these over millions of entries, where materializing a
// normalized std::string per entry dominates the cost.
// ---------------------------------------------------------------------------
/// Apply normalizeCascPath's per-character rule to a single character.
inline char normalizeCascChar(char c) {
if (c == '/')
return '\\';
return static_cast<char>(std::tolower(static_cast<unsigned char>(c)));
}
/// The span of @p s that survives normalizeCascPath's leading/trailing trim.
inline std::string_view trimCascSeparators(std::string_view s) {
size_t start = 0;
while (start < s.size() && (s[start] == '\\' || s[start] == '/'))
++start;
size_t end = s.size();
while (end > start && (s[end - 1] == '\\' || s[end - 1] == '/'))
--end;
return s.substr(start, end - start);
}
/// FNV-1a 64 with a MurmurHash3 finalizer, so low bits are well distributed for
/// power-of-2 masking. Never returns 0 — FlatHashMap reserves it as its empty
/// sentinel.
inline u64 cascPathHash64(std::string_view normalized) {
u64 h = 14695981039346656037ULL;
for (char c : normalized) {
h ^= static_cast<u64>(static_cast<u8>(c));
h *= 1099511628211ULL;
}
h ^= h >> 33;
h *= 0xff51afd7ed558ccdULL;
h ^= h >> 33;
h *= 0xc4ceb9fe1a85ec53ULL;
h ^= h >> 33;
return h == 0 ? 1 : h;
}
/// cascPathHash64 of @p raw's normalized form, without materializing it.
inline u64 normalizedCascPathHash64(std::string_view raw) {
std::string_view const body = trimCascSeparators(raw);
u64 h = 14695981039346656037ULL;
for (char c : body) {
h ^= static_cast<u64>(static_cast<u8>(normalizeCascChar(c)));
h *= 1099511628211ULL;
}
h ^= h >> 33;
h *= 0xff51afd7ed558ccdULL;
h ^= h >> 33;
h *= 0xc4ceb9fe1a85ec53ULL;
h ^= h >> 33;
return h == 0 ? 1 : h;
}
/// True if @p raw normalizes to @p normalizedKey, without materializing it.
inline bool normalizedCascPathEquals(std::string_view raw, std::string_view normalizedKey) {
std::string_view const body = trimCascSeparators(raw);
if (body.size() != normalizedKey.size())
return false;
for (size_t i = 0; i < body.size(); ++i) {
if (normalizeCascChar(body[i]) != normalizedKey[i])
return false;
}
return true;
}
} // namespace whiteout::storages::common