Branch data Line data Source code
1 : : /* SPDX-License-Identifier: LGPL-2.1+ */
2 : :
3 : : #include <errno.h>
4 : : #include <stdlib.h>
5 : : #include <string.h>
6 : :
7 : : #include "alloc-util.h"
8 : : #include "sort-util.h"
9 : : #include "strbuf.h"
10 : :
11 : : /*
12 : : * Strbuf stores given strings in a single continuous allocated memory
13 : : * area. Identical strings are de-duplicated and return the same offset
14 : : * as the first string stored. If the tail of a string already exists
15 : : * in the buffer, the tail is returned.
16 : : *
17 : : * A trie (http://en.wikipedia.org/wiki/Trie) is used to maintain the
18 : : * information about the stored strings.
19 : : *
20 : : * Example of udev rules:
21 : : * $ ./udevadm test .
22 : : * ...
23 : : * read rules file: /usr/lib/udev/rules.d/99-systemd.rules
24 : : * rules contain 196608 bytes tokens (16384 * 12 bytes), 39742 bytes strings
25 : : * 23939 strings (207859 bytes), 20404 de-duplicated (171653 bytes), 3536 trie nodes used
26 : : * ...
27 : : */
28 : :
29 : 24 : struct strbuf *strbuf_new(void) {
30 : : struct strbuf *str;
31 : :
32 : 24 : str = new(struct strbuf, 1);
33 [ - + ]: 24 : if (!str)
34 : 0 : return NULL;
35 : 24 : *str = (struct strbuf) {
36 : 24 : .buf = new0(char, 1),
37 : 24 : .root = new0(struct strbuf_node, 1),
38 : : .len = 1,
39 : : .nodes_count = 1,
40 : : };
41 [ + - - + ]: 24 : if (!str->buf || !str->root) {
42 : 0 : free(str->buf);
43 : 0 : free(str->root);
44 : 0 : return mfree(str);
45 : : }
46 : :
47 : 24 : return str;
48 : : }
49 : :
50 : 302652 : static struct strbuf_node* strbuf_node_cleanup(struct strbuf_node *node) {
51 : : size_t i;
52 : :
53 [ + + ]: 605280 : for (i = 0; i < node->children_count; i++)
54 : 302628 : strbuf_node_cleanup(node->children[i].child);
55 : 302652 : free(node->children);
56 : 302652 : return mfree(node);
57 : : }
58 : :
59 : : /* clean up trie data, leave only the string buffer */
60 : 40 : void strbuf_complete(struct strbuf *str) {
61 [ - + ]: 40 : if (!str)
62 : 0 : return;
63 [ + + ]: 40 : if (str->root)
64 : 24 : str->root = strbuf_node_cleanup(str->root);
65 : : }
66 : :
67 : : /* clean up everything */
68 : 24 : void strbuf_cleanup(struct strbuf *str) {
69 [ - + ]: 24 : if (!str)
70 : 0 : return;
71 : :
72 : 24 : strbuf_complete(str);
73 : 24 : free(str->buf);
74 : 24 : free(str);
75 : : }
76 : :
77 : 20650693 : static int strbuf_children_cmp(const struct strbuf_child_entry *n1,
78 : : const struct strbuf_child_entry *n2) {
79 : 20650693 : return n1->c - n2->c;
80 : : }
81 : :
82 : 302628 : static void bubbleinsert(struct strbuf_node *node,
83 : : uint8_t c,
84 : : struct strbuf_node *node_child) {
85 : :
86 : 302628 : struct strbuf_child_entry new = {
87 : : .c = c,
88 : : .child = node_child,
89 : : };
90 : 302628 : int left = 0, right = node->children_count;
91 : :
92 [ + + ]: 660675 : while (right > left) {
93 : 358047 : int middle = (right + left) / 2 ;
94 [ + + ]: 358047 : if (strbuf_children_cmp(&node->children[middle], &new) <= 0)
95 : 170897 : left = middle + 1;
96 : : else
97 : 187150 : right = middle;
98 : : }
99 : :
100 : 302628 : memmove(node->children + left + 1, node->children + left,
101 : 302628 : sizeof(struct strbuf_child_entry) * (node->children_count - left));
102 : 302628 : node->children[left] = new;
103 : :
104 : 302628 : node->children_count++;
105 : 302628 : }
106 : :
107 : : /* add string, return the index/offset into the buffer */
108 : 1551464 : ssize_t strbuf_add_string(struct strbuf *str, const char *s, size_t len) {
109 : : uint8_t c;
110 : : struct strbuf_node *node;
111 : : size_t depth;
112 : : char *buf_new;
113 : : struct strbuf_child_entry *child;
114 : : struct strbuf_node *node_child;
115 : : ssize_t off;
116 : :
117 [ - + ]: 1551464 : if (!str->root)
118 : 0 : return -EINVAL;
119 : :
120 : : /* search string; start from last character to find possibly matching tails */
121 : :
122 : 1551464 : str->in_count++;
123 [ + + ]: 1551464 : if (len == 0) {
124 : 67820 : str->dedup_count++;
125 : 67820 : return 0;
126 : : }
127 : 1483644 : str->in_len += len;
128 : :
129 : 1483644 : node = str->root;
130 [ + - ]: 9068594 : for (depth = 0; depth <= len; depth++) {
131 : : struct strbuf_child_entry search;
132 : :
133 : : /* match against current node */
134 : 9068594 : off = node->value_off + node->value_len - len;
135 [ + + + + : 9068594 : if (depth == len || (node->value_len >= len && memcmp(str->buf + off, s, len) == 0)) {
+ + ]
136 : 1181016 : str->dedup_len += len;
137 : 1181016 : str->dedup_count++;
138 : 1181016 : return off;
139 : : }
140 : :
141 : 7887578 : c = s[len - 1 - depth];
142 : :
143 : : /* lookup child node */
144 : 7887578 : search.c = c;
145 : 7887578 : child = typesafe_bsearch(&search, node->children, node->children_count, strbuf_children_cmp);
146 [ + + ]: 7887578 : if (!child)
147 : 302628 : break;
148 : 7584950 : node = child->child;
149 : : }
150 : :
151 : : /* add new string */
152 : 302628 : buf_new = realloc(str->buf, str->len + len+1);
153 [ - + ]: 302628 : if (!buf_new)
154 : 0 : return -ENOMEM;
155 : 302628 : str->buf = buf_new;
156 : 302628 : off = str->len;
157 : 302628 : memcpy(str->buf + off, s, len);
158 : 302628 : str->len += len;
159 : 302628 : str->buf[str->len++] = '\0';
160 : :
161 : : /* new node */
162 : 302628 : node_child = new(struct strbuf_node, 1);
163 [ - + ]: 302628 : if (!node_child)
164 : 0 : return -ENOMEM;
165 : 302628 : *node_child = (struct strbuf_node) {
166 : : .value_off = off,
167 : : .value_len = len,
168 : : };
169 : :
170 : : /* extend array, add new entry, sort for bisection */
171 : 302628 : child = reallocarray(node->children, node->children_count + 1, sizeof(struct strbuf_child_entry));
172 [ - + ]: 302628 : if (!child) {
173 : 0 : free(node_child);
174 : 0 : return -ENOMEM;
175 : : }
176 : :
177 : 302628 : str->nodes_count++;
178 : :
179 : 302628 : node->children = child;
180 : 302628 : bubbleinsert(node, c, node_child);
181 : :
182 : 302628 : return off;
183 : : }
|
