Branch data Line data Source code
1 : : /**
2 : : * @file decoder.c
3 : : * @brief Dictionary lifecycle: open compiled .trp buffer, lookup keys.
4 : : *
5 : : * Copyright (c) 2026 M. A. Chatterjee <deftio at deftio dot com>
6 : : * BSD-2-Clause — see LICENSE.txt
7 : : */
8 : :
9 : : #include "core_internal.h"
10 : :
11 : : /* ── Internal: parse trie config and symbol table ───────────────────── */
12 : :
13 : 3362 : static tp_result parse_trie_config(tp_bitstream_reader *r, tp_dict *dict)
14 : : {
15 : : uint64_t val;
16 : : tp_result rc;
17 : :
18 : : /* bits_per_symbol (4 bits) */
19 : 3362 : rc = tp_bs_read_bits(r, 4, &val);
20 [ + + ]: 3362 : if (rc != TP_OK)
21 : 2 : return rc;
22 : : /* Symbol codes index 256-entry maps, so a symbol may not be wider than a
23 : : byte; 0 would make the trie unreadable. */
24 [ + + + + ]: 3360 : if (val < 1 || val > 8)
25 : 6 : return TP_ERR_ALPHABET;
26 : 3354 : dict->sym.bits_per_symbol = (uint8_t)val;
27 : 3354 : dict->info.bits_per_symbol = (uint8_t)val;
28 : :
29 : : /* symbol_count (8 bits) */
30 : 3354 : rc = tp_bs_read_bits(r, 8, &val);
31 [ + + ]: 3354 : if (rc != TP_OK)
32 : 3 : return rc;
33 : : /* Must leave room for the control codes and fit in bits_per_symbol. */
34 [ + + + + ]: 3351 : if (val < TP_NUM_CONTROL_CODES || val > (1u << dict->sym.bits_per_symbol))
35 : 19 : return TP_ERR_ALPHABET;
36 : 3332 : dict->sym.symbol_count = (uint16_t)val;
37 : :
38 : : /* special_symbol_map: 6 control codes */
39 : 3332 : memset(dict->sym.code_is_ctrl, 0, sizeof(dict->sym.code_is_ctrl));
40 [ + + ]: 23298 : for (int c = 0; c < TP_NUM_CONTROL_CODES; c++) {
41 : 19975 : rc = tp_bs_read_bits(r, dict->sym.bits_per_symbol, &val);
42 [ + + ]: 19975 : if (rc != TP_OK)
43 : 9 : return rc;
44 : 19966 : dict->sym.ctrl_codes[c] = (uint32_t)val;
45 [ + - ]: 19966 : if (val < 256)
46 : 19966 : dict->sym.code_is_ctrl[val] = true;
47 : : }
48 : :
49 : : /* Read symbol table */
50 : 3323 : memset(dict->sym.reverse_map, 0, sizeof(dict->sym.reverse_map));
51 : 3323 : memset(dict->sym.symbol_map, 0, sizeof(dict->sym.symbol_map));
52 : 3323 : uint32_t max_code = dict->sym.symbol_count;
53 [ + + ]: 57658 : for (uint32_t code = TP_NUM_CONTROL_CODES; code < max_code; code++) {
54 : : uint64_t cp;
55 : 54442 : rc = tp_bs_read_varint_u(r, &cp);
56 [ + + ]: 54442 : if (rc != TP_OK)
57 : 107 : return rc;
58 [ + - + + ]: 54335 : if (code < 256 && cp < 256) {
59 : 54212 : dict->sym.reverse_map[code] = (uint8_t)cp;
60 : 54212 : dict->sym.symbol_map[cp] = code;
61 : : }
62 : : }
63 : :
64 : 3216 : return TP_OK;
65 : : }
66 : :
67 : : /* ── Open / Close ────────────────────────────────────────────────────── */
68 : :
69 : 3462 : static tp_result dict_open_impl(tp_dict **out, const uint8_t *buf, size_t len, bool check_crc)
70 : : {
71 [ + + + + ]: 3462 : if (!out || !buf)
72 : 2 : return TP_ERR_INVALID_PARAM;
73 [ + + ]: 3460 : if (len < TP_HEADER_SIZE)
74 : 7 : return TP_ERR_TRUNCATED;
75 : :
76 : : /* Parse header */
77 : : /* Allocation failure paths are excluded from coverage (LCOV_EXCL). */
78 : 3453 : tp_bitstream_reader *r = NULL;
79 : 3453 : tp_result rc = tp_bs_reader_create(&r, buf, (uint64_t)len * 8);
80 : 3453 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
81 : : return rc; /* LCOV_EXCL_LINE */
82 : :
83 : : tp_header hdr;
84 : 3453 : rc = tp_header_read(r, &hdr);
85 [ + + ]: 3453 : if (rc != TP_OK) {
86 : 19 : tp_bs_reader_destroy(&r);
87 : 19 : return rc;
88 : : }
89 : :
90 : : /* CRC verification */
91 [ + + + - ]: 3434 : if (check_crc && len >= 4) {
92 : 2590 : size_t crc_data_len = len - 4;
93 : 2590 : uint32_t expected_crc =
94 : 2590 : ((uint32_t)buf[crc_data_len] << 24) | ((uint32_t)buf[crc_data_len + 1] << 16) |
95 : 2590 : ((uint32_t)buf[crc_data_len + 2] << 8) | ((uint32_t)buf[crc_data_len + 3]);
96 : 2590 : uint32_t actual_crc = tp_crc32(buf, crc_data_len);
97 [ + + ]: 2590 : if (actual_crc != expected_crc) {
98 : 70 : tp_bs_reader_destroy(&r);
99 : 70 : return TP_ERR_CORRUPT;
100 : : }
101 : : }
102 : :
103 : : /* Check for unsupported features */
104 [ + + ]: 3364 : if (hdr.flags & TP_FLAG_HAS_SUFFIX_TABLE) {
105 : 2 : tp_bs_reader_destroy(&r);
106 : 2 : return TP_ERR_VERSION;
107 : : }
108 : :
109 : : /* Allocate dict */
110 : 3362 : tp_dict *dict = calloc(1, sizeof(*dict));
111 : 3362 : if (!dict) { /* LCOV_EXCL_BR_LINE */
112 : : /* LCOV_EXCL_START */
113 : : tp_bs_reader_destroy(&r);
114 : : return TP_ERR_ALLOC;
115 : : /* LCOV_EXCL_STOP */
116 : : }
117 : :
118 : 3362 : dict->buf = buf;
119 : 3362 : dict->len = len;
120 : 3362 : dict->hdr = hdr;
121 : :
122 : : /* Populate info */
123 : 3362 : dict->info.format_version_major = hdr.version_major;
124 : 3362 : dict->info.format_version_minor = hdr.version_minor;
125 : 3362 : dict->info.num_keys = hdr.num_keys;
126 : 3362 : dict->info.has_values = (hdr.flags & TP_FLAG_HAS_VALUES) != 0;
127 : 3362 : dict->info.has_suffix_table = false;
128 : 3362 : dict->info.compact_mode = (hdr.flags & TP_FLAG_COMPACT_MODE) != 0;
129 : 3362 : dict->info.total_bytes = len;
130 : 3362 : dict->info.checksum_type = TP_CHECKSUM_CRC32;
131 : 3362 : dict->info.trie_mode = TP_ADDR_BIT;
132 : 3362 : dict->info.value_mode = TP_ADDR_BYTE;
133 : :
134 : : /* Parse trie config and symbol table */
135 : : /* Reader is at bit 256 (byte 32, start of data stream) */
136 : 3362 : rc = parse_trie_config(r, dict);
137 [ + + ]: 3362 : if (rc != TP_OK) {
138 : 146 : tp_bs_reader_destroy(&r);
139 : 146 : free(dict);
140 : 146 : return rc;
141 : : }
142 : :
143 : 3216 : uint64_t data_start = (uint64_t)TP_HEADER_SIZE * 8;
144 : 3216 : dict->trie_start = data_start + hdr.trie_data_offset;
145 : 3216 : dict->value_start = data_start + hdr.value_store_offset;
146 : :
147 : 3216 : tp_bs_reader_destroy(&r);
148 : 3216 : *out = dict;
149 : 3216 : return TP_OK;
150 : : }
151 : :
152 : 2605 : tp_result tp_dict_open(tp_dict **out, const uint8_t *buf, size_t len)
153 : : {
154 : 2605 : return dict_open_impl(out, buf, len, true);
155 : : }
156 : :
157 : 857 : tp_result tp_dict_open_unchecked(tp_dict **out, const uint8_t *buf, size_t len)
158 : : {
159 : 857 : return dict_open_impl(out, buf, len, false);
160 : : }
161 : :
162 : 3240 : tp_result tp_dict_close(tp_dict **dict)
163 : : {
164 [ + + ]: 3240 : if (!dict)
165 : 1 : return TP_ERR_INVALID_PARAM;
166 : 3239 : free(*dict);
167 : 3239 : *dict = NULL;
168 : 3239 : return TP_OK;
169 : : }
170 : :
171 : : /* ── Query ───────────────────────────────────────────────────────────── */
172 : :
173 : 2315 : uint32_t tp_dict_count(const tp_dict *dict)
174 : : {
175 [ + + ]: 2315 : if (!dict)
176 : 1 : return 0;
177 : 2314 : return dict->info.num_keys;
178 : : }
179 : :
180 : : /* ── Lookup ──────────────────────────────────────────────────────────── */
181 : :
182 : 22521 : tp_result tp_dict_lookup(const tp_dict *dict, const char *key, tp_value *val)
183 : : {
184 [ + + - + ]: 22521 : if (!dict || !key)
185 : 1 : return TP_ERR_INVALID_PARAM;
186 : 22520 : return tp_dict_lookup_n(dict, key, strlen(key), val);
187 : : }
188 : :
189 : 41195 : tp_result tp_dict_lookup_n(const tp_dict *dict, const char *key, size_t key_len, tp_value *val)
190 : : {
191 [ + + - + ]: 41195 : if (!dict || !key)
192 : 1 : return TP_ERR_INVALID_PARAM;
193 : :
194 : : /* Empty dictionary: nothing to find */
195 [ + + ]: 41194 : if (dict->info.num_keys == 0)
196 : 2 : return TP_ERR_NOT_FOUND;
197 : :
198 : 41192 : tp_bitstream_reader *r = NULL;
199 : 41192 : tp_result rc = tp_bs_reader_create(&r, dict->buf, (uint64_t)dict->len * 8);
200 : 41192 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
201 : : return rc; /* LCOV_EXCL_LINE */
202 : :
203 : 41192 : rc = tp_bs_reader_seek(r, dict->trie_start);
204 [ + + ]: 41192 : if (rc != TP_OK) {
205 : 1 : tp_bs_reader_destroy(&r);
206 : : return rc; /* LCOV_EXCL_LINE */
207 : : }
208 : :
209 : 41191 : uint8_t bps = dict->sym.bits_per_symbol;
210 : 41191 : size_t key_idx = 0;
211 : 41191 : uint32_t value_index = 0;
212 : 41191 : bool found_value = false;
213 : 41191 : bool expect_branch = false; /* set after END/END_VAL when key not consumed */
214 : :
215 : 400979 : while (true) {
216 : : uint64_t sym_raw;
217 : 442170 : rc = tp_bs_read_bits(r, bps, &sym_raw);
218 [ + + ]: 442170 : if (rc != TP_OK) {
219 : 10 : tp_bs_reader_destroy(&r);
220 : : /* If we were expecting a BRANCH after a terminal but hit
221 : : EOF, the key doesn't exist. */
222 [ + + ]: 10 : if (expect_branch)
223 : 14943 : return TP_ERR_NOT_FOUND;
224 : 9 : return rc;
225 : : }
226 : 442160 : uint32_t sym = (uint32_t)sym_raw;
227 : :
228 [ + + ]: 442160 : if (sym == dict->sym.ctrl_codes[TP_CTRL_END]) {
229 [ + + ]: 21577 : if (key_idx == key_len) {
230 : 12042 : tp_bs_reader_destroy(&r);
231 [ + + ]: 12042 : if (val)
232 : 12041 : *val = tp_value_null();
233 : 12042 : return TP_OK;
234 : : }
235 : : /* Key not fully consumed: a BRANCH may follow this terminal
236 : : for children sharing this prefix. */
237 : 9535 : expect_branch = true;
238 : 400979 : continue;
239 : : }
240 : :
241 [ + + ]: 420583 : if (sym == dict->sym.ctrl_codes[TP_CTRL_END_VAL]) {
242 : : uint64_t vi;
243 : 36205 : rc = tp_bs_read_varint_u(r, &vi);
244 [ + + ]: 36205 : if (rc != TP_OK) {
245 : 5 : tp_bs_reader_destroy(&r);
246 : 5 : return rc;
247 : : }
248 [ + + ]: 36200 : if (key_idx == key_len) {
249 : 26248 : value_index = (uint32_t)vi;
250 : 26248 : found_value = true;
251 : 26248 : break;
252 : : }
253 : : /* Key not fully consumed: a BRANCH may follow. */
254 : 9952 : expect_branch = true;
255 : 9952 : continue;
256 : : }
257 : :
258 [ + + ]: 384378 : if (sym == dict->sym.ctrl_codes[TP_CTRL_BRANCH]) {
259 : 156149 : expect_branch = false;
260 : : uint64_t child_count;
261 : 156149 : rc = tp_bs_read_varint_u(r, &child_count);
262 [ + + ]: 156149 : if (rc != TP_OK) {
263 : 4 : tp_bs_reader_destroy(&r);
264 : 1559 : return rc;
265 : : }
266 : :
267 [ + + ]: 156145 : if (key_idx >= key_len) {
268 : 114 : tp_bs_reader_destroy(&r);
269 : 114 : return TP_ERR_NOT_FOUND;
270 : : }
271 : :
272 : 156031 : uint8_t target = (uint8_t)key[key_idx];
273 : 156031 : bool found_child = false;
274 : :
275 [ + + ]: 588550 : for (uint64_t ci = 0; ci < child_count; ci++) {
276 : 587546 : bool has_skip = (ci < child_count - 1);
277 : 587546 : uint64_t skip_dist = 0;
278 : :
279 [ + + ]: 587546 : if (has_skip) {
280 : : /* Read SKIP control code */
281 : : uint64_t skip_sym;
282 : 556678 : rc = tp_bs_read_bits(r, bps, &skip_sym);
283 [ + + ]: 556678 : if (rc != TP_OK) {
284 : 11 : tp_bs_reader_destroy(&r);
285 : 18 : return rc;
286 : : }
287 : : /* Read skip distance */
288 : 556667 : rc = tp_bs_read_varint_u(r, &skip_dist);
289 [ + + ]: 556667 : if (rc != TP_OK) {
290 : 7 : tp_bs_reader_destroy(&r);
291 : 7 : return rc;
292 : : }
293 : : }
294 : :
295 : : /* Peek at first symbol of this child */
296 : : uint64_t child_first_sym;
297 : 587528 : rc = tp_bs_peek_bits(r, bps, &child_first_sym);
298 [ + + ]: 587528 : if (rc != TP_OK) {
299 : 5 : tp_bs_reader_destroy(&r);
300 : 5 : return rc;
301 : : }
302 : :
303 : : /* Determine if this is a regular symbol */
304 : 587523 : uint32_t csym = (uint32_t)child_first_sym;
305 [ + - + + ]: 587523 : bool is_ctrl = (csym < 256) && dict->sym.code_is_ctrl[csym];
306 : :
307 [ + + ]: 587523 : if (!is_ctrl) {
308 : : /* It's a regular symbol; check if it matches */
309 : 586943 : uint32_t expected_code = dict->sym.symbol_map[target];
310 [ + + ]: 586943 : if (csym == expected_code) {
311 : : /* Match! Consume this symbol and continue */
312 : 154590 : tp_bs_reader_advance(r, bps);
313 : 154590 : key_idx++;
314 : 154590 : found_child = true;
315 : 154590 : break;
316 : : }
317 : : }
318 : :
319 : : /* Check if it's an END/END_VAL (terminal with no more key
320 : : chars). These can only match if target matches nothing,
321 : : so skip to next sibling. */
322 : :
323 [ + + ]: 432933 : if (has_skip) {
324 : : /* Skip to next sibling */
325 : 431959 : rc = tp_bs_reader_advance(r, skip_dist);
326 [ + + ]: 431959 : if (rc != TP_OK) {
327 : 414 : tp_bs_reader_destroy(&r);
328 : 414 : return rc;
329 : : }
330 : : }
331 : : }
332 : :
333 [ + + ]: 155594 : if (!found_child) {
334 : 1004 : tp_bs_reader_destroy(&r);
335 : 1004 : return TP_ERR_NOT_FOUND;
336 : : }
337 : 154590 : continue;
338 : : }
339 : :
340 : : /* If we expected a BRANCH after a terminal but got something
341 : : else, the key extends beyond a leaf node — not found. */
342 [ + + ]: 228229 : if (expect_branch) {
343 : 217 : tp_bs_reader_destroy(&r);
344 : 217 : return TP_ERR_NOT_FOUND;
345 : : }
346 : :
347 : : /* Regular symbol */
348 [ + - + + ]: 228012 : if (!dict->sym.code_is_ctrl[sym < 256 ? sym : 0]) {
349 [ + + ]: 227878 : if (key_idx >= key_len) {
350 : 54 : tp_bs_reader_destroy(&r);
351 : 54 : return TP_ERR_NOT_FOUND;
352 : : }
353 : 227824 : uint32_t expected_code = dict->sym.symbol_map[(uint8_t)key[key_idx]];
354 [ + + ]: 227824 : if (sym != expected_code) {
355 : 922 : tp_bs_reader_destroy(&r);
356 : 922 : return TP_ERR_NOT_FOUND;
357 : : }
358 : 226902 : key_idx++;
359 : 226902 : continue;
360 : : }
361 : :
362 : : /* Unknown control code */
363 : 134 : tp_bs_reader_destroy(&r);
364 : 134 : return TP_ERR_INVALID_PARAM;
365 : : }
366 : :
367 : : /* Decode value if found */
368 [ + - + + : 26248 : if (found_value && val && dict->info.has_values) {
+ - ]
369 : : /* Seek to value store and skip to the right value */
370 : 26247 : rc = tp_bs_reader_seek(r, dict->value_start);
371 [ + + ]: 26247 : if (rc != TP_OK) {
372 : 72 : tp_bs_reader_destroy(&r);
373 : 72 : return rc;
374 : : }
375 : :
376 : : /* Skip value_index values */
377 [ + + ]: 50263373 : for (uint32_t i = 0; i < value_index; i++) {
378 : : tp_value tmp;
379 : 50237454 : rc = tp_value_decode(r, &tmp, dict->buf);
380 [ + + ]: 50237454 : if (rc != TP_OK) {
381 : 256 : tp_bs_reader_destroy(&r);
382 : 256 : return rc;
383 : : }
384 : : }
385 : :
386 : 25919 : rc = tp_value_decode(r, val, dict->buf);
387 : 25919 : tp_bs_reader_destroy(&r);
388 : 25919 : return rc;
389 : : }
390 : :
391 : : /* LCOV_EXCL_START — found_value is only set via CTRL_END_VAL which
392 : : implies has_values, so the condition above always takes priority. */
393 : : if (found_value && val) {
394 : : *val = tp_value_null();
395 : : }
396 : : /* LCOV_EXCL_STOP */
397 : :
398 : 1 : tp_bs_reader_destroy(&r);
399 : 1 : return TP_OK;
400 : : }
401 : :
402 : 10037 : tp_result tp_dict_contains(const tp_dict *dict, const char *key, bool *out)
403 : : {
404 [ + + + - : 10037 : if (!dict || !key || !out)
- + ]
405 : 4 : return TP_ERR_INVALID_PARAM;
406 : :
407 : : tp_value val;
408 : 10033 : tp_result rc = tp_dict_lookup(dict, key, &val);
409 [ + + ]: 10033 : if (rc == TP_OK) {
410 : 10021 : *out = true;
411 : 10021 : return TP_OK;
412 : : }
413 [ + + ]: 12 : if (rc == TP_ERR_NOT_FOUND) {
414 : 7 : *out = false;
415 : 7 : return TP_OK;
416 : : }
417 : 5 : return rc;
418 : : }
419 : :
420 : : /* ── Info ────────────────────────────────────────────────────────────── */
421 : :
422 : 10 : tp_result tp_dict_get_info(const tp_dict *dict, tp_dict_info *info)
423 : : {
424 [ + + - + ]: 10 : if (!dict || !info)
425 : 3 : return TP_ERR_INVALID_PARAM;
426 : 7 : *info = dict->info;
427 : 7 : return TP_OK;
428 : : }
429 : :
430 : : /* ── Iteration ──────────────────────────────────────────────────────── */
431 : :
432 : : /**
433 : : * The trie stream does not say where a subtree ends, so the walk carries the
434 : : * bound: a child with a SKIP ends at child_start + skip, the last child ends
435 : : * where its parent does, and the root ends at the value store. A terminal is
436 : : * followed by a BRANCH exactly when its subtree has not reached that bound.
437 : : */
438 : :
439 : 29891 : static tp_result iter_key_reserve(tp_iterator *it, size_t needed)
440 : : {
441 [ + + ]: 29891 : if (needed <= it->key_buf_cap)
442 : 29886 : return TP_OK;
443 [ + - ]: 5 : size_t cap = it->key_buf_cap ? it->key_buf_cap : 256;
444 [ + + ]: 11 : while (cap < needed)
445 : 6 : cap *= 2;
446 : 5 : char *grown = realloc(it->key_buf, cap);
447 : 5 : if (!grown) /* LCOV_EXCL_BR_LINE */
448 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
449 : 5 : it->key_buf = grown;
450 : 5 : it->key_buf_cap = cap;
451 : 5 : return TP_OK;
452 : : }
453 : :
454 : 28063 : static tp_result iter_push_key(tp_iterator *it, uint8_t byte)
455 : : {
456 : 28063 : tp_result rc = iter_key_reserve(it, it->key_len + 1);
457 : 28063 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
458 : : return rc; /* LCOV_EXCL_LINE */
459 : 28063 : it->key_buf[it->key_len++] = (char)byte;
460 : 28063 : return TP_OK;
461 : : }
462 : :
463 : : /** Decode the value at store index `index`, keeping the cursor in step. */
464 : 7825 : static tp_result iter_value_at(tp_iterator *it, uint64_t index, tp_value *val)
465 : : {
466 [ + + ]: 7825 : if (!it->dict->info.has_values) {
467 : 17 : *val = tp_value_null();
468 : 17 : return TP_OK;
469 : : }
470 : :
471 : 7808 : tp_bitstream_reader *r = NULL;
472 : 7808 : tp_result rc = tp_bs_reader_create(&r, it->dict->buf, (uint64_t)it->dict->len * 8);
473 : 7808 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
474 : : return rc; /* LCOV_EXCL_LINE */
475 : :
476 [ + + ]: 7808 : if (index != it->value_index) {
477 : : /* Cursor is elsewhere — walk the store from the start. */
478 : 1271 : rc = tp_bs_reader_seek(r, it->dict->value_start);
479 [ + + + + ]: 5806 : for (uint64_t i = 0; rc == TP_OK && i < index; i++) {
480 : : tp_value skip;
481 : 4535 : rc = tp_value_decode(r, &skip, it->dict->buf);
482 : : }
483 [ + + ]: 1271 : if (rc != TP_OK) {
484 : 127 : tp_bs_reader_destroy(&r);
485 : 127 : return rc;
486 : : }
487 : 1144 : it->value_pos = tp_bs_reader_position(r);
488 : 1144 : it->value_index = index;
489 : : }
490 : :
491 : 7681 : rc = tp_bs_reader_seek(r, it->value_pos);
492 [ + + ]: 7681 : if (rc == TP_OK)
493 : 7631 : rc = tp_value_decode(r, val, it->dict->buf);
494 [ + + ]: 7681 : if (rc == TP_OK) {
495 : 7583 : it->value_pos = tp_bs_reader_position(r);
496 : 7583 : it->value_index = index + 1;
497 : : }
498 : 7681 : tp_bs_reader_destroy(&r);
499 : 7681 : return rc;
500 : : }
501 : :
502 : 4411 : tp_result tp_dict_iterate(const tp_dict *dict, tp_iterator **out)
503 : : {
504 [ + + - + ]: 4411 : if (!dict || !out)
505 : 1 : return TP_ERR_INVALID_PARAM;
506 : :
507 : 4410 : tp_iterator *it = calloc(1, sizeof(*it));
508 : 4410 : if (!it) /* LCOV_EXCL_BR_LINE */
509 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
510 : :
511 : 4410 : it->dict = dict;
512 : 4410 : it->key_buf = malloc(256);
513 : 4410 : if (!it->key_buf) { /* LCOV_EXCL_BR_LINE */
514 : : /* LCOV_EXCL_START */
515 : : free(it);
516 : : return TP_ERR_ALLOC;
517 : : /* LCOV_EXCL_STOP */
518 : : }
519 : 4410 : it->key_buf_cap = 256;
520 : 4410 : it->root_pos = dict->trie_start;
521 : 4410 : it->root_end = dict->value_start;
522 : 4410 : it->root_key_len = 0;
523 : 4410 : tp_iter_reset(it);
524 : 4410 : *out = it;
525 : 4410 : return TP_OK;
526 : : }
527 : :
528 : 11796 : tp_result tp_iter_next(tp_iterator *it, const char **key, size_t *key_len, tp_value *val)
529 : : {
530 [ + + ]: 11796 : if (!it)
531 : 1 : return TP_ERR_INVALID_PARAM;
532 [ + + ]: 11795 : if (it->done)
533 : 1607 : return TP_ERR_EOF;
534 [ + + ]: 10188 : if (it->dict->info.num_keys == 0) {
535 : 1 : it->done = true;
536 : 1 : return TP_ERR_EOF;
537 : : }
538 : :
539 : 10187 : const tp_symbol_info *sym = &it->dict->sym;
540 : 10187 : uint8_t bps = sym->bits_per_symbol;
541 : :
542 : 10187 : tp_bitstream_reader *r = NULL;
543 : 10187 : tp_result rc = tp_bs_reader_create(&r, it->dict->buf, (uint64_t)it->dict->len * 8);
544 : 10187 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
545 : : return rc; /* LCOV_EXCL_LINE */
546 : :
547 : : uint64_t subtree_end;
548 : : bool descending;
549 : :
550 [ + + ]: 10187 : if (!it->started) {
551 : 2583 : it->started = true;
552 : 2583 : it->pos = it->root_pos;
553 : 2583 : it->key_len = it->root_key_len;
554 : 2583 : subtree_end = it->root_end;
555 : 2583 : descending = true;
556 : : } else {
557 : 7604 : subtree_end = 0;
558 : 7604 : descending = false;
559 : : }
560 : :
561 : : #define ITER_FAIL(code) \
562 : : do { \
563 : : tp_bs_reader_destroy(&r); \
564 : : it->done = true; \
565 : : return (code); \
566 : : } while (0)
567 : :
568 : 3186 : for (;;) {
569 [ + + ]: 13373 : if (!descending) {
570 : : /* Move to the next unvisited sibling, unwinding finished frames. */
571 [ + + + + ]: 14660 : while (it->stack_top >= 0 && it->stack[it->stack_top].remaining == 0)
572 : 3870 : it->stack_top--;
573 [ + + ]: 10790 : if (it->stack_top < 0) {
574 : 1947 : tp_bs_reader_destroy(&r);
575 : 1947 : it->done = true;
576 : 1947 : return TP_ERR_EOF;
577 : : }
578 : :
579 : 8843 : tp_iter_frame *f = &it->stack[it->stack_top];
580 : 8843 : it->key_len = f->key_prefix_len;
581 : 8843 : rc = tp_bs_reader_seek(r, f->next_child_pos);
582 : 8843 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
583 : : ITER_FAIL(rc); /* LCOV_EXCL_LINE */
584 : :
585 [ + + ]: 8843 : if (f->remaining > 1) {
586 : : /* Every child but the last is introduced by SKIP + distance,
587 : : which is also where the following sibling begins. */
588 : : uint64_t skip_sym;
589 : 4399 : rc = tp_bs_read_bits(r, bps, &skip_sym);
590 [ - + ]: 4399 : if (rc != TP_OK)
591 : 120 : ITER_FAIL(rc);
592 [ + + ]: 4399 : if ((uint32_t)skip_sym != sym->ctrl_codes[TP_CTRL_SKIP])
593 : 119 : ITER_FAIL(TP_ERR_CORRUPT);
594 : : uint64_t dist;
595 : 4280 : rc = tp_bs_read_varint_u(r, &dist);
596 [ + + ]: 4280 : if (rc != TP_OK)
597 : 1 : ITER_FAIL(rc);
598 : 4279 : it->pos = tp_bs_reader_position(r);
599 : 4279 : subtree_end = it->pos + dist;
600 : 4279 : f->next_child_pos = it->pos + dist;
601 : : } else {
602 : 4444 : it->pos = f->next_child_pos;
603 : 4444 : subtree_end = f->subtree_end;
604 : : }
605 : 8723 : f->remaining--;
606 : 8723 : descending = true;
607 : : }
608 : :
609 : 11306 : rc = tp_bs_reader_seek(r, it->pos);
610 [ + + ]: 11306 : if (rc != TP_OK)
611 : : ITER_FAIL(rc); /* LCOV_EXCL_LINE */
612 : :
613 : : /* Walk down this subtree until it yields a key or a branch. */
614 : 11283 : bool emitted = false;
615 [ + + ]: 39346 : while (tp_bs_reader_position(r) < subtree_end) {
616 : : uint64_t raw;
617 : 39327 : rc = tp_bs_read_bits(r, bps, &raw);
618 [ + + ]: 39327 : if (rc != TP_OK)
619 : 489 : ITER_FAIL(rc);
620 : 39326 : uint32_t code = (uint32_t)raw;
621 : :
622 : 39326 : bool terminal =
623 [ + + + + ]: 39326 : (code == sym->ctrl_codes[TP_CTRL_END] || code == sym->ctrl_codes[TP_CTRL_END_VAL]);
624 : :
625 [ + + ]: 39326 : if (terminal) {
626 : : /* END carries no index because its value is null; END_VAL
627 : : names the slot in the value store. */
628 : 8012 : bool has_index = (code == sym->ctrl_codes[TP_CTRL_END_VAL]);
629 : 8012 : uint64_t vi = 0;
630 [ + + ]: 8012 : if (has_index) {
631 : 7909 : rc = tp_bs_read_varint_u(r, &vi);
632 [ - + ]: 7909 : if (rc != TP_OK)
633 : 404 : ITER_FAIL(rc);
634 : : }
635 : :
636 : : /* A BRANCH follows exactly when the subtree continues. */
637 [ + + ]: 8012 : if (tp_bs_reader_position(r) < subtree_end) {
638 : : uint64_t bsym;
639 : 2001 : rc = tp_bs_read_bits(r, bps, &bsym);
640 [ - + ]: 2001 : if (rc != TP_OK)
641 : 179 : ITER_FAIL(rc);
642 [ + + ]: 2001 : if ((uint32_t)bsym != sym->ctrl_codes[TP_CTRL_BRANCH])
643 : 178 : ITER_FAIL(TP_ERR_CORRUPT);
644 : : uint64_t nchildren;
645 : 1823 : rc = tp_bs_read_varint_u(r, &nchildren);
646 [ - + ]: 1823 : if (rc != TP_OK)
647 : 0 : ITER_FAIL(rc);
648 [ + + ]: 1823 : if (it->stack_top + 1 >= TP_ITER_MAX_DEPTH)
649 : 1 : ITER_FAIL(TP_ERR_OVERFLOW);
650 : 1822 : tp_iter_frame *nf = &it->stack[++it->stack_top];
651 : 1822 : nf->subtree_end = subtree_end;
652 : 1822 : nf->next_child_pos = tp_bs_reader_position(r);
653 : 1822 : nf->remaining = (uint32_t)nchildren;
654 : 1822 : nf->key_prefix_len = it->key_len;
655 : : }
656 : :
657 : 7833 : tp_value decoded = tp_value_null();
658 [ + + ]: 7833 : if (has_index) {
659 : 7825 : rc = iter_value_at(it, vi, &decoded);
660 [ + + ]: 7825 : if (rc != TP_OK)
661 : 225 : ITER_FAIL(rc);
662 : : }
663 [ + - ]: 7608 : if (val)
664 : 7608 : *val = decoded;
665 [ + - ]: 7608 : if (key)
666 : 7608 : *key = it->key_buf;
667 [ + - ]: 7608 : if (key_len)
668 : 7608 : *key_len = it->key_len;
669 : 7608 : emitted = true;
670 : 7608 : break;
671 : : }
672 : :
673 [ + + ]: 31314 : if (code == sym->ctrl_codes[TP_CTRL_BRANCH]) {
674 : : uint64_t nchildren;
675 : 3167 : rc = tp_bs_read_varint_u(r, &nchildren);
676 [ - + ]: 3167 : if (rc != TP_OK)
677 : 0 : ITER_FAIL(rc);
678 [ - + ]: 3167 : if (it->stack_top + 1 >= TP_ITER_MAX_DEPTH)
679 : 0 : ITER_FAIL(TP_ERR_OVERFLOW);
680 : 3167 : tp_iter_frame *nf = &it->stack[++it->stack_top];
681 : 3167 : nf->subtree_end = subtree_end;
682 : 3167 : nf->next_child_pos = tp_bs_reader_position(r);
683 : 3167 : nf->remaining = (uint32_t)nchildren;
684 : 3167 : nf->key_prefix_len = it->key_len;
685 : 3167 : descending = false;
686 : 3167 : break;
687 : : }
688 : :
689 : : /* Regular symbol: extends the key. */
690 [ + - + + ]: 28147 : if (code < 256 && sym->code_is_ctrl[code])
691 : 84 : ITER_FAIL(TP_ERR_CORRUPT);
692 [ + - ]: 28063 : rc = iter_push_key(it, code < 256 ? sym->reverse_map[code] : 0);
693 : 28063 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
694 : : ITER_FAIL(rc); /* LCOV_EXCL_LINE */
695 : : }
696 : :
697 [ + + ]: 10794 : if (emitted) {
698 : 7608 : tp_bs_reader_destroy(&r);
699 : 7608 : return TP_OK;
700 : : }
701 [ + + ]: 3186 : if (descending) {
702 : : /* Ran to the subtree end without a terminal: try the next sibling. */
703 : 19 : descending = false;
704 : : }
705 : : }
706 : :
707 : : #undef ITER_FAIL
708 : : }
709 : :
710 : 6243 : tp_result tp_iter_reset(tp_iterator *it)
711 : : {
712 [ + + ]: 6243 : if (!it)
713 : 1 : return TP_ERR_INVALID_PARAM;
714 : 6242 : it->pos = it->root_pos;
715 : 6242 : it->done = false;
716 : 6242 : it->key_len = it->root_key_len;
717 : 6242 : it->stack_top = -1;
718 : 6242 : it->started = false;
719 : 6242 : it->value_pos = it->dict->value_start;
720 : 6242 : it->value_index = 0;
721 : 6242 : return TP_OK;
722 : : }
723 : :
724 : 4414 : tp_result tp_iter_destroy(tp_iterator **it)
725 : : {
726 [ + + ]: 4414 : if (!it)
727 : 1 : return TP_ERR_INVALID_PARAM;
728 [ + + ]: 4413 : if (*it) {
729 : 4410 : free((*it)->key_buf);
730 : 4410 : free(*it);
731 : 4410 : *it = NULL;
732 : : }
733 : 4413 : return TP_OK;
734 : : }
735 : :
736 : : /* ── Search ─────────────────────────────────────────────────────────── */
737 : :
738 : : /**
739 : : * Walk down the trie consuming `prefix`, and report the subtree that holds
740 : : * every key starting with it.
741 : : *
742 : : * On success *sub_pos / *sub_end bound that subtree. TP_ERR_NOT_FOUND means no
743 : : * key has the prefix.
744 : : */
745 : 3655 : static tp_result descend_to_prefix(const tp_dict *dict, const uint8_t *prefix, size_t prefix_len,
746 : : uint64_t *sub_pos, uint64_t *sub_end)
747 : : {
748 : 3655 : const tp_symbol_info *sym = &dict->sym;
749 : 3655 : uint8_t bps = sym->bits_per_symbol;
750 : :
751 : 3655 : tp_bitstream_reader *r = NULL;
752 : 3655 : tp_result rc = tp_bs_reader_create(&r, dict->buf, (uint64_t)dict->len * 8);
753 : 3655 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
754 : : return rc; /* LCOV_EXCL_LINE */
755 : :
756 : 3655 : uint64_t pos = dict->trie_start;
757 : 3655 : uint64_t end = dict->value_start;
758 : 3655 : size_t matched = 0;
759 : :
760 : : #define PREFIX_FAIL(code) \
761 : : do { \
762 : : tp_bs_reader_destroy(&r); \
763 : : return (code); \
764 : : } while (0)
765 : :
766 : 13886 : for (;;) {
767 [ + + ]: 17541 : if (matched == prefix_len) {
768 : 1828 : *sub_pos = pos;
769 : 1828 : *sub_end = end;
770 : 1828 : tp_bs_reader_destroy(&r);
771 : 3655 : return TP_OK;
772 : : }
773 [ + + ]: 15713 : if (pos >= end)
774 : 123 : PREFIX_FAIL(TP_ERR_NOT_FOUND);
775 : :
776 : 15590 : rc = tp_bs_reader_seek(r, pos);
777 : 15590 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
778 : : PREFIX_FAIL(rc); /* LCOV_EXCL_LINE */
779 : :
780 : : uint64_t raw;
781 : 15590 : rc = tp_bs_read_bits(r, bps, &raw);
782 [ - + ]: 15590 : if (rc != TP_OK)
783 : 0 : PREFIX_FAIL(rc);
784 : 15590 : uint32_t code = (uint32_t)raw;
785 : :
786 : 15590 : bool at_branch = false;
787 [ + + + + ]: 15590 : if (code == sym->ctrl_codes[TP_CTRL_END] || code == sym->ctrl_codes[TP_CTRL_END_VAL]) {
788 [ + + ]: 1090 : if (code == sym->ctrl_codes[TP_CTRL_END_VAL]) {
789 : : uint64_t vi;
790 : 1079 : rc = tp_bs_read_varint_u(r, &vi);
791 [ - + ]: 1079 : if (rc != TP_OK)
792 : 0 : PREFIX_FAIL(rc);
793 : : }
794 : : /* The prefix is longer than this key, so it can only continue
795 : : through the BRANCH that follows — if the subtree continues. */
796 [ + + ]: 1090 : if (tp_bs_reader_position(r) >= end)
797 : 488 : PREFIX_FAIL(TP_ERR_NOT_FOUND);
798 : 602 : rc = tp_bs_read_bits(r, bps, &raw);
799 [ - + ]: 602 : if (rc != TP_OK)
800 : 0 : PREFIX_FAIL(rc);
801 [ + + ]: 602 : if ((uint32_t)raw != sym->ctrl_codes[TP_CTRL_BRANCH])
802 : 56 : PREFIX_FAIL(TP_ERR_CORRUPT);
803 : 546 : at_branch = true;
804 [ + + ]: 14500 : } else if (code == sym->ctrl_codes[TP_CTRL_BRANCH]) {
805 : 4628 : at_branch = true;
806 : : }
807 : :
808 [ + + ]: 15046 : if (!at_branch) {
809 : : /* Literal symbol: it has to be the prefix byte we are looking for. */
810 [ + - + + ]: 9872 : if (code < 256 && sym->code_is_ctrl[code])
811 : 21 : PREFIX_FAIL(TP_ERR_CORRUPT);
812 [ + - ]: 9851 : uint8_t byte = code < 256 ? sym->reverse_map[code] : 0;
813 [ + + ]: 9851 : if (byte != prefix[matched])
814 : 186 : PREFIX_FAIL(TP_ERR_NOT_FOUND);
815 : 9665 : matched++;
816 : 9665 : pos = tp_bs_reader_position(r);
817 : 9665 : continue;
818 : : }
819 : :
820 : : /* At a BRANCH: take the child whose first symbol is the prefix byte. */
821 : : uint64_t nchildren;
822 : 5174 : rc = tp_bs_read_varint_u(r, &nchildren);
823 [ - + ]: 5174 : if (rc != TP_OK)
824 : 0 : PREFIX_FAIL(rc);
825 : :
826 : 5174 : uint64_t child_preamble = tp_bs_reader_position(r);
827 : 5174 : uint32_t want = sym->symbol_map[prefix[matched]];
828 : 5174 : bool descended = false;
829 : :
830 [ + + ]: 9859 : for (uint64_t c = 0; c < nchildren; c++) {
831 : 9050 : rc = tp_bs_reader_seek(r, child_preamble);
832 [ + + ]: 9050 : if (rc != TP_OK)
833 : : PREFIX_FAIL(rc); /* LCOV_EXCL_LINE */
834 : :
835 : : uint64_t child_start, child_end;
836 [ + + ]: 9021 : if (c + 1 < nchildren) {
837 : : uint64_t skip_sym;
838 : 4668 : rc = tp_bs_read_bits(r, bps, &skip_sym);
839 [ - + ]: 4668 : if (rc != TP_OK)
840 : 115 : PREFIX_FAIL(rc);
841 [ + + ]: 4668 : if ((uint32_t)skip_sym != sym->ctrl_codes[TP_CTRL_SKIP])
842 : 115 : PREFIX_FAIL(TP_ERR_CORRUPT);
843 : : uint64_t dist;
844 : 4553 : rc = tp_bs_read_varint_u(r, &dist);
845 [ - + ]: 4553 : if (rc != TP_OK)
846 : 0 : PREFIX_FAIL(rc);
847 : 4553 : child_start = tp_bs_reader_position(r);
848 : 4553 : child_end = child_start + dist;
849 : 4553 : child_preamble = child_start + dist;
850 : : } else {
851 : 4353 : child_start = child_preamble;
852 : 4353 : child_end = end;
853 : : }
854 : :
855 : : uint64_t first;
856 : 8906 : rc = tp_bs_read_bits_at(dict->buf, child_start, bps, &first);
857 : 8906 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
858 : : PREFIX_FAIL(rc); /* LCOV_EXCL_LINE */
859 : :
860 [ + + ]: 8906 : if ((uint32_t)first == want) {
861 : 4221 : pos = child_start;
862 : 4221 : end = child_end;
863 : 4221 : descended = true;
864 : 4221 : break;
865 : : }
866 : : }
867 : :
868 [ + + ]: 5030 : if (!descended)
869 : 809 : PREFIX_FAIL(TP_ERR_NOT_FOUND);
870 : : }
871 : :
872 : : #undef PREFIX_FAIL
873 : : }
874 : :
875 : 3657 : tp_result tp_dict_find_prefix(const tp_dict *dict, const char *prefix, tp_iterator **out)
876 : : {
877 [ + + + - : 3657 : if (!dict || !prefix || !out)
- + ]
878 : 1 : return TP_ERR_INVALID_PARAM;
879 : :
880 : 3656 : tp_iterator *it = NULL;
881 : 3656 : tp_result rc = tp_dict_iterate(dict, &it);
882 : 3656 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
883 : : return rc; /* LCOV_EXCL_LINE */
884 : :
885 : 3656 : size_t prefix_len = strlen(prefix);
886 [ + + - + ]: 3656 : if (prefix_len == 0 || dict->info.num_keys == 0) {
887 : 1 : *out = it;
888 : 1 : return TP_OK;
889 : : }
890 : :
891 : 3655 : uint64_t sub_pos = 0, sub_end = 0;
892 : 3655 : rc = descend_to_prefix(dict, (const uint8_t *)prefix, prefix_len, &sub_pos, &sub_end);
893 [ + + ]: 3655 : if (rc == TP_ERR_NOT_FOUND) {
894 : : /* No key has this prefix: hand back an iterator that yields nothing. */
895 : 1606 : it->done = true;
896 : 1606 : *out = it;
897 : 1606 : return TP_OK;
898 : : }
899 [ + + ]: 2049 : if (rc != TP_OK) {
900 : 221 : tp_iter_destroy(&it);
901 : 221 : return rc;
902 : : }
903 : :
904 : : /* Seed the iterator with the prefix already in place, then let it walk
905 : : only the subtree below it. */
906 : 1828 : if (iter_key_reserve(it, prefix_len) != TP_OK) { /* LCOV_EXCL_BR_LINE */
907 : : /* LCOV_EXCL_START */
908 : : tp_iter_destroy(&it);
909 : : return TP_ERR_ALLOC;
910 : : /* LCOV_EXCL_STOP */
911 : : }
912 : 1828 : memcpy(it->key_buf, prefix, prefix_len);
913 : 1828 : it->root_pos = sub_pos;
914 : 1828 : it->root_end = sub_end;
915 : 1828 : it->root_key_len = prefix_len;
916 : :
917 : 1828 : tp_iter_reset(it);
918 : 1828 : *out = it;
919 : 1828 : return TP_OK;
920 : : }
921 : :
922 : 2 : tp_result tp_dict_find_fuzzy(const tp_dict *dict, const char *query, uint8_t max_dist,
923 : : tp_iterator **out)
924 : : {
925 [ + + + - : 2 : if (!dict || !query || !out)
- + ]
926 : 1 : return TP_ERR_INVALID_PARAM;
927 : : /* Bounded edit-distance search over the trie is not implemented. Saying so
928 : : beats handing back an iterator over every key, which — now that
929 : : iteration works — would look like a successful fuzzy match for
930 : : anything. */
931 : : (void)max_dist;
932 : 1 : *out = NULL;
933 : 1 : return TP_ERR_UNSUPPORTED;
934 : : }
935 : :
936 : 3 : tp_result tp_iter_get_distance(const tp_iterator *it, uint8_t *dist)
937 : : {
938 [ + + - + ]: 3 : if (!it || !dist)
939 : 2 : return TP_ERR_INVALID_PARAM;
940 : 1 : *dist = it->distance;
941 : 1 : return TP_OK;
942 : : }
|
