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);
68 static void strbuf_node_cleanup(struct strbuf_node
*node
) {
71 for (i
= 0; i
< node
->children_count
; i
++)
72 strbuf_node_cleanup(node
->children
[i
].child
);
77 /* clean up trie data, leave only the string buffer */
78 void strbuf_complete(struct strbuf
*str
) {
82 strbuf_node_cleanup(str
->root
);
86 /* clean up everything */
87 void strbuf_cleanup(struct strbuf
*str
) {
91 strbuf_node_cleanup(str
->root
);
96 static int strbuf_children_cmp(const struct strbuf_child_entry
*n1
,
97 const struct strbuf_child_entry
*n2
) {
101 static void bubbleinsert(struct strbuf_node
*node
,
103 struct strbuf_node
*node_child
) {
105 struct strbuf_child_entry
new = {
109 int left
= 0, right
= node
->children_count
;
111 while (right
> left
) {
112 int middle
= (right
+ left
) / 2 ;
113 if (strbuf_children_cmp(&node
->children
[middle
], &new) <= 0)
119 memmove(node
->children
+ left
+ 1, node
->children
+ left
,
120 sizeof(struct strbuf_child_entry
) * (node
->children_count
- left
));
121 node
->children
[left
] = new;
123 node
->children_count
++;
126 /* add string, return the index/offset into the buffer */
127 ssize_t
strbuf_add_string(struct strbuf
*str
, const char *s
, size_t len
) {
129 struct strbuf_node
*node
;
132 struct strbuf_child_entry
*child
;
133 struct strbuf_node
*node_child
;
139 /* search string; start from last character to find possibly matching tails */
147 for (depth
= 0; depth
<= len
; depth
++) {
148 struct strbuf_child_entry search
;
150 /* match against current node */
151 off
= node
->value_off
+ node
->value_len
- len
;
152 if (depth
== len
|| (node
->value_len
>= len
&& memcmp(str
->buf
+ off
, s
, len
) == 0)) {
153 str
->dedup_len
+= len
;
158 c
= s
[len
- 1 - depth
];
160 /* bsearch is not allowed on a NULL sequence */
161 if (node
->children_count
== 0)
164 /* lookup child node */
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
);