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
|
/*
* Simple trie interface
*
* Copyright (c) 2020 Ákos Uzonyi <uzonyi.akos@gmail.com>
* All rights reserved.
*
* SPDX-License-Identifier: LGPL-2.1-or-later
*/
#ifndef STRACE_TRIE_H
# define STRACE_TRIE_H
# include <stdbool.h>
# include <stdint.h>
/**
* Trie control structure.
* Trie implemented here has the following properties:
* * It allows storing values of the same size, the size can vary from 1 bit to
* 64 bit values (only power of 2 sizes are allowed).
* * The key can be up to 64 bits in size.
* * It has separate configuration for node size and data block size.
*
* How bits of key are used for different node levels:
*
* highest bits lowest bits
* | node_key_bits | node_key_bits | ... | <remainder> | data_block_key_bits |
* \_________________________________________________________________________/
* key_size
*
* So, the remainder is used on the lowest non-data node level.
*
* As of now, it doesn't implement any mechanisms for resizing/changing key
* size. De-fragmentation is also unsupported currently.
*/
struct trie {
/** Return value of trie_get if key is not found */
uint64_t empty_value;
/** Pointer to root node */
void *data;
/** Key size in bits (0..64). */
uint8_t key_size;
/**
* Size of the stored values in log2 bits (0..6).
* (6: 64 bit values, 5: 32 bit values, ...)
*/
uint8_t item_size_lg;
/**
* Number of bits in the key that make a symbol for a node.
* (equals to log2 of the child count of the node)
*/
uint8_t node_key_bits;
/**
* Number of bits in the key that make a symbol for the data block (leaf).
* (equals to log2 of the value count stored in a data block)
*/
uint8_t data_block_key_bits;
/** The depth of the data block. Calculated from the values above */
uint8_t max_depth;
};
struct trie* trie_create(uint8_t key_size, uint8_t item_size_lg,
uint8_t node_key_bits, uint8_t data_block_key_bits,
uint64_t empty_value);
bool trie_set(struct trie *t, uint64_t key, uint64_t val);
uint64_t trie_get(struct trie *t, uint64_t key);
typedef void (*trie_iterate_fn)(void *data, uint64_t key, uint64_t val);
/**
* Calls trie_iterate_fn for each key-value pair where
* key is inside the [start, end] interval (inclusive).
*
* @param t The trie.
* @param start The start of the key interval (inclusive).
* @param end The end of the key interval (inclusive).
* @param fn The function to be called.
* @param fn_data The value to be passed to fn.
*/
uint64_t trie_iterate_keys(struct trie *t, uint64_t start, uint64_t end,
trie_iterate_fn fn, void *fn_data);
void trie_free(struct trie *t);
#endif /* !STRACE_TRIE_H */
|
