2 This file is part of systemd.
4 Copyright 2012 Kay Sievers <kay@vrfy.org>
6 systemd is free software; you can redistribute it and/or modify it
7 under the terms of the GNU Lesser General Public License as published by
8 the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version.
11 systemd is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public License
17 along with systemd; If not, see <http://www.gnu.org/licenses/>.
24 #include "alloc-util.h"
28 * Strbuf stores given strings in a single continuous allocated memory
29 * area. Identical strings are de-duplicated and return the same offset
30 * as the first string stored. If the tail of a string already exists
31 * in the buffer, the tail is returned.
33 * A trie (http://en.wikipedia.org/wiki/Trie) is used to maintain the
34 * information about the stored strings.
36 * Example of udev rules:
39 * read rules file: /usr/lib/udev/rules.d/99-systemd.rules
40 * rules contain 196608 bytes tokens (16384 * 12 bytes), 39742 bytes strings
41 * 23939 strings (207859 bytes), 20404 de-duplicated (171653 bytes), 3536 trie nodes used
45 struct strbuf
*strbuf_new(void) {
48 str
= new0(struct strbuf
, 1);
52 str
->buf
= new0(char, 1);
57 str
->root
= new0(struct strbuf_node
, 1);
69 static void strbuf_node_cleanup(struct strbuf_node
*node
) {
72 for (i
= 0; i
< node
->children_count
; i
++)
73 strbuf_node_cleanup(node
->children
[i
].child
);
78 /* clean up trie data, leave only the string buffer */
79 void strbuf_complete(struct strbuf
*str
) {
83 strbuf_node_cleanup(str
->root
);
87 /* clean up everything */
88 void strbuf_cleanup(struct strbuf
*str
) {
92 strbuf_node_cleanup(str
->root
);
97 static int strbuf_children_cmp(const struct strbuf_child_entry
*n1
,
98 const struct strbuf_child_entry
*n2
) {
102 static void bubbleinsert(struct strbuf_node
*node
,
104 struct strbuf_node
*node_child
) {
106 struct strbuf_child_entry
new = {
110 int left
= 0, right
= node
->children_count
;
112 while (right
> left
) {
113 int middle
= (right
+ left
) / 2 ;
114 if (strbuf_children_cmp(&node
->children
[middle
], &new) <= 0)
120 memmove(node
->children
+ left
+ 1, node
->children
+ left
,
121 sizeof(struct strbuf_child_entry
) * (node
->children_count
- left
));
122 node
->children
[left
] = new;
124 node
->children_count
++;
127 /* add string, return the index/offset into the buffer */
128 ssize_t
strbuf_add_string(struct strbuf
*str
, const char *s
, size_t len
) {
130 struct strbuf_node
*node
;
133 struct strbuf_child_entry
*child
;
134 struct strbuf_node
*node_child
;
140 /* search string; start from last character to find possibly matching tails */
148 for (depth
= 0; depth
<= len
; depth
++) {
149 struct strbuf_child_entry search
;
151 /* match against current node */
152 off
= node
->value_off
+ node
->value_len
- len
;
153 if (depth
== len
|| (node
->value_len
>= len
&& memcmp(str
->buf
+ off
, s
, len
) == 0)) {
154 str
->dedup_len
+= len
;
159 /* bsearch is not allowed on a NULL sequence */
160 if (node
->children_count
== 0)
163 /* lookup child node */
164 c
= s
[len
- 1 - depth
];
166 child
= bsearch(&search
, node
->children
, node
->children_count
,
167 sizeof(struct strbuf_child_entry
),
168 (__compar_fn_t
) strbuf_children_cmp
);
175 buf_new
= realloc(str
->buf
, str
->len
+ len
+1);
180 memcpy(str
->buf
+ off
, s
, len
);
182 str
->buf
[str
->len
++] = '\0';
185 node_child
= new0(struct strbuf_node
, 1);
188 node_child
->value_off
= off
;
189 node_child
->value_len
= len
;
191 /* extend array, add new entry, sort for bisection */
192 child
= realloc(node
->children
, (node
->children_count
+ 1) * sizeof(struct strbuf_child_entry
));
200 node
->children
= child
;
201 bubbleinsert(node
, c
, node_child
);