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
118
119
120
121
122
123
124
|
#ifndef MERCURY_KERNEL_UTILITY_HPP
#define MERCURY_KERNEL_UTILITY_HPP
#include <optional>
#include <cstdint>
namespace mercury::kernel::utility {
template <class t>
static inline t min(t a, t b) {
return a < b ? a : b;
}
//includes start_i, does not include end_i
void mark_bitmap_region_zero(uint64_t *bitmap, uint64_t start_i, uint64_t end_i);
//includes start_i, does not include end_i
void mark_bitmap_region_one(uint64_t *bitmap, uint64_t start_i, uint64_t end_i);
struct uuid {
uint8_t bytes[16];
};
template <class value_t>
struct string_tree {
std::optional<value_t> value_here = {};
string_tree<value_t> *parent = 0;
string_tree<value_t> *subtrees[256] = {};
//if there is a node whose key has a prefix in common with str, then this
//returns the deepest such node, and sets leftover_out to point to the
//character of str after the common prefix with that returned node. if
//there is no such node, this returns the current node and sets
//leftover_out to a null pointer.
string_tree &max_common_prefix(
const char *str, size_t str_len, const char *&leftover_out) {
string_tree<value_t> *last_with_value = 0;
const char *leftover_at_last_with_value = 0;
string_tree<value_t> *on = this;
size_t len_so_far = 0;
while (true) {
if (on->value_here) {
last_with_value = on;
leftover_at_last_with_value = str + len_so_far;
}
if (len_so_far == str_len)
break;
on = on->subtrees[(uint8_t)str[len_so_far]];
if (!on)
break;
++len_so_far;
}
if (last_with_value) {
leftover_out = leftover_at_last_with_value;
return *last_with_value;
}
leftover_out = 0;
return *this;
}
bool try_insert(const char *str, size_t str_len, value_t value) {
string_tree<value_t> *on = this;
for (size_t i = 0; i < str_len; ++i) {
string_tree<value_t> *&subtree = on->subtrees[(uint8_t)str[i]];
if (!subtree) {
subtree = new string_tree<value_t>();
subtree->parent = on;
}
on = subtree;
}
if (on->value_here)
return false;
on->value_here = value;
return true;
}
};
//if c appears in str, this returns the index of the first time it appears.
//otherwise, this returns len.
static inline size_t find(const char *str, size_t len, char c) {
for (size_t i = 0; i < len; ++i)
if (str[i] == c)
return i;
return len;
}
template <class value_t>
struct flist {
struct node {
value_t value;
node *next;
};
node *first;
flist() : first(0) {}
void insert(value_t value) {
first = new node {
.value = value,
.next = first
};
}
};
}
#endif
|