Blender V5.3
identifier.hh
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Clement Foucault
2 *
3 * SPDX-License-Identifier: MIT */
4
5#pragma once
6
7#include <algorithm>
8#include <array>
9#include <cstdint>
10#include <string_view>
11#include <vector>
12
13#include "types.hh"
14#include "vector.hh"
15
16#if defined(_MSC_VER)
17# define INLINE_METHOD __forceinline
18#else
19# define INLINE_METHOD inline __attribute__((always_inline))
20#endif
21
22namespace lexit {
23
24static constexpr uint64_t padded_string_masks[8] = {
25 uint64_t(0xFFFFFFFFFFFFFFFF),
26 uint64_t(0x00000000000000FF),
27 uint64_t(0x000000000000FFFF),
28 uint64_t(0x0000000000FFFFFF),
29 uint64_t(0x00000000FFFFFFFF),
30 uint64_t(0x000000FFFFFFFFFF),
31 uint64_t(0x0000FFFFFFFFFFFF),
32 uint64_t(0x00FFFFFFFFFFFFFF),
33};
34
43template<int Size> struct PaddedString {
45 uint32_t size;
46
47 PaddedString() = default;
48
49 /* Caller need to ensure enough bytes are accessible after the end of string. */
50 explicit PaddedString(std::string_view str)
51 {
52 size = str.size();
53 assert(str.size() > 8 * (Size - 1));
54 assert(str.size() <= 8 * Size);
55
56 std::memcpy(data, (const char *)str.data(), sizeof(data));
57 /* Fast way of masking the excess chars. */
58 data[Size - 1] &= padded_string_masks[str.size() & (sizeof(data[0]) - 1)];
59 }
60
61 operator std::string_view() const
62 {
63 return {(const char *)data, size};
64 }
65};
66
67struct Keyword {
68 std::string_view str;
71
72 Keyword() = default;
73
75 {
76 }
77};
78
80 struct alignas(8) Identifier {
81 uint16_t next;
82 uint16_t size;
83 uint32_t hash;
84
86 uint64_t *data() const
87 {
88 return (uint64_t *)(&hash + 1);
89 }
90
91 /* Caller must ensure size matches. */
92 template<int Size> bool operator==(const PaddedString<Size> &str) const
93 {
94 if (size != str.size) {
95 return false;
96 }
97 return std::equal(data(), data() + Size, str.data);
98 }
99
100 bool operator==(std::string_view str) const
101 {
102 return std::string_view{(const char *)data(), size} == str;
103 }
104 };
105
107
108 /* Note: Must be power of two size. */
109 static constexpr uint32_t hash_table_size = 16384;
110 static constexpr uint32_t hash_table_index_mask = (hash_table_size - 1);
111 std::array<uint16_t, hash_table_size> hash_table;
112
114 {
115 /* Set invalid values for all the table. */
116 std::memset(hash_table.data(), 0xFFu, sizeof(uint16_t) * hash_table.size());
117 }
118
119 void reserve(int token_count)
120 {
121 identifier_buffer.reserve(token_count);
122 }
123
124 /* Return the maximum value for the currently allocated atoms. */
126 {
127 return identifier_buffer.size();
128 }
129
130 static constexpr uint32_t str_hash(std::string_view s)
131 {
132 uint32_t hash = 5381;
133 hash = ((hash << 5) + hash) + s.size();
137 return static_cast<uint16_t>(hash);
138 }
139
140 template<typename StringT> INLINE_METHOD TokenAtom lookup_or_add(StringT str)
141 {
142 uint32_t hash = str_hash(str);
144
145 Identifier *id = nullptr;
146 for (; index != 0xFFFFu; index = id->next) {
148 if (id->hash == hash && *id == str) [[likely]] {
149 return index;
150 }
151 }
152 return add_after(hash, str, id);
153 }
154
155 TokenAtom add_after(uint32_t hash, std::string_view str, Identifier *id = nullptr)
156 {
157 /* Cache miss. Add new. */
158 uint16_t new_index = identifier_buffer.size();
159 if (id) {
160 /* Update previous element in the list. */
161 id->next = new_index;
162 }
163 else {
164 /* Update entry in table. */
166 }
167
168 {
169 /* Fast malloc replacement. */
170 int str_as_id_size = ((str.size() + (sizeof(Identifier) - 1)) / sizeof(Identifier));
171 identifier_buffer.reserve(new_index + 1 + str_as_id_size);
174 /* Construct new identifier. */
175 id.next = 0xFFFFu;
176 id.size = str.size();
177 id.hash = hash;
178 /* Zero the end of the memcpy for the fast comparison. */
179 id.data()[((str.size() - 1) / sizeof(Identifier))] = 0;
180 std::memcpy(id.data(), str.data(), str.size());
181 }
182 return new_index;
183 }
184
185 Keyword make_keyword(std::string_view str, TokenType type)
186 {
187 return Keyword(str, type, lookup_or_add(str));
188 }
189};
190
191/* Convert Atom to Keyword types. */
193 /* Indexed by string TokenAtom. */
194 alignas(64) std::array<TokenType, 64> map;
195
196 KeywordTable(const std::vector<Keyword> &vector)
197 {
198 /* We only lookup words, so a word mismatch should be a Noop. */
199 map.fill(Word);
200 for (auto keyword : vector) {
201 /* Check for overflow. */
202 assert(keyword.atom < 128);
203 /* Check default case not being overwritten. */
204 assert(keyword.atom != 0);
205 map[keyword.atom / 2] = keyword.type;
206 }
207 }
208
210 {
211 /* Identifier are always allocated in 2 or more consecutive slots. Which means TokenAtom values
212 * always increment by at least 2. Avoid wasting slots in the map by dividing the atom by 2.
213 * If atom is bigger than the table, revert to 0 atom (invalid) which becomes a Noop by
214 * returning Word. */
215 return map[(atom / 2) * (atom < 128)];
216 }
217};
218
219} // namespace lexit
unsigned long long int uint64_t
#define str(s)
#define assert(assertion)
#define index(i)
#define INLINE_METHOD
Definition identifier.hh:19
uint16_t TokenAtom
Definition types.hh:159
TokenType
Definition types.hh:41
@ Word
Definition types.hh:43
static constexpr uint64_t padded_string_masks[8]
Definition identifier.hh:24
#define hash
Definition noise_c.cc:156
bool operator==(std::string_view str) const
bool operator==(const PaddedString< Size > &str) const
Definition identifier.hh:92
static constexpr uint32_t str_hash(std::string_view s)
Keyword make_keyword(std::string_view str, TokenType type)
static constexpr uint32_t hash_table_size
TokenAtom add_after(uint32_t hash, std::string_view str, Identifier *id=nullptr)
static constexpr uint32_t hash_table_index_mask
lexit::Vector< Identifier > identifier_buffer
INLINE_METHOD TokenAtom lookup_or_add(StringT str)
std::array< uint16_t, hash_table_size > hash_table
TokenAtom max_atom_value() const
void reserve(int token_count)
TokenType operator[](TokenAtom atom) const
KeywordTable(const std::vector< Keyword > &vector)
std::array< TokenType, 64 > map
Keyword(std::string_view str, TokenType type, TokenAtom atom)
Definition identifier.hh:74
Keyword()=default
std::string_view str
Definition identifier.hh:68
TokenAtom atom
Definition identifier.hh:70
TokenType type
Definition identifier.hh:69
PaddedString(std::string_view str)
Definition identifier.hh:50
uint64_t data[Size]
Definition identifier.hh:44
PaddedString()=default
void increase_size_by_unchecked(int elem_count)
Definition vector.hh:135
int size() const
Definition vector.hh:130
void reserve(int new_size)
Definition vector.hh:78