chiark / gitweb /
do not create /dev/rtc symlink, let systemd search for it if needed
[elogind.git] / src / shared / strbuf.c
1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
2
3 /***
4   This file is part of systemd.
5
6   Copyright 2012 Kay Sievers <kay@vrfy.org>
7
8   systemd is free software; you can redistribute it and/or modify it
9   under the terms of the GNU Lesser General Public License as published by
10   the Free Software Foundation; either version 2.1 of the License, or
11   (at your option) any later version.
12
13   systemd is distributed in the hope that it will be useful, but
14   WITHOUT ANY WARRANTY; without even the implied warranty of
15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16   Lesser General Public License for more details.
17
18   You should have received a copy of the GNU Lesser General Public License
19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
20 ***/
21
22 #include <stdlib.h>
23 #include <string.h>
24
25 #include "util.h"
26 #include "strbuf.h"
27
28 /*
29  * Strbuf stores given strings in a single continuous allocated memory
30  * area. Identical strings are de-duplicated and return the same offset
31  * as the first string stored. If the tail of a string already exists
32  * in the buffer, the tail is returned.
33  *
34  * A trie (http://en.wikipedia.org/wiki/Trie) is used to maintain the
35  * information about the stored strings.
36  *
37  * Example of udev rules:
38  *   $ ./udevadm test .
39  *   ...
40  *   read rules file: /usr/lib/udev/rules.d/99-systemd.rules
41  *   rules contain 196608 bytes tokens (16384 * 12 bytes), 39742 bytes strings
42  *   23939 strings (207859 bytes), 20404 de-duplicated (171653 bytes), 3536 trie nodes used
43  *   ...
44  */
45
46 struct strbuf *strbuf_new(void) {
47         struct strbuf *str;
48
49         str = new0(struct strbuf, 1);
50         if (!str)
51                 return NULL;
52
53         str->buf = new0(char, 1);
54         if (!str->buf)
55                 goto err;
56         str->len = 1;
57
58         str->root = new0(struct strbuf_node, 1);
59         if (!str->root)
60                 goto err;
61         str->nodes_count = 1;
62         return str;
63 err:
64         free(str->buf);
65         free(str->root);
66         free(str);
67         return NULL;
68 }
69
70 static void strbuf_node_cleanup(struct strbuf_node *node) {
71         size_t i;
72
73         for (i = 0; i < node->children_count; i++)
74                 strbuf_node_cleanup(node->children[i].child);
75         free(node->children);
76         free(node);
77 }
78
79 /* clean up trie data, leave only the string buffer */
80 void strbuf_complete(struct strbuf *str) {
81         if (!str)
82                 return;
83         if (str->root)
84                 strbuf_node_cleanup(str->root);
85         str->root = NULL;
86 }
87
88 /* clean up everything */
89 void strbuf_cleanup(struct strbuf *str) {
90         if (!str)
91                 return;
92         if (str->root)
93                 strbuf_node_cleanup(str->root);
94         free(str->buf);
95         free(str);
96 }
97
98 static int strbuf_children_cmp(const struct strbuf_child_entry *n1,
99                                const struct strbuf_child_entry *n2) {
100         return n1->c - n2->c;
101 }
102
103 static void bubbleinsert(struct strbuf_node *node,
104                          uint8_t c,
105                          struct strbuf_node *node_child) {
106
107         struct strbuf_child_entry new = {
108                 .c = c,
109                 .child = node_child,
110         };
111         int left = 0, right = node->children_count;
112
113         while (right > left) {
114                 int middle = (right + left) / 2 ;
115                 if (strbuf_children_cmp(&node->children[middle], &new) <= 0)
116                         left = middle + 1;
117                 else
118                         right = middle;
119         }
120
121         memmove(node->children + left + 1, node->children + left,
122                 sizeof(struct strbuf_child_entry) * (node->children_count - left));
123         node->children[left] = new;
124
125         node->children_count ++;
126 }
127
128 /* add string, return the index/offset into the buffer */
129 ssize_t strbuf_add_string(struct strbuf *str, const char *s, size_t len) {
130         uint8_t c;
131         struct strbuf_node *node;
132         size_t depth;
133         char *buf_new;
134         struct strbuf_child_entry *child;
135         struct strbuf_node *node_child;
136         ssize_t off;
137
138         if (!str->root)
139                 return -EINVAL;
140
141         /* search string; start from last character to find possibly matching tails */
142         if (len == 0)
143                 return 0;
144         str->in_count++;
145         str->in_len += len;
146
147         node = str->root;
148         c = s[len-1];
149         for (depth = 0; depth <= len; depth++) {
150                 struct strbuf_child_entry search;
151
152                 /* match against current node */
153                 off = node->value_off + node->value_len - len;
154                 if (depth == len || (node->value_len >= len && memcmp(str->buf + off, s, len) == 0)) {
155                         str->dedup_len += len;
156                         str->dedup_count++;
157                         return off;
158                 }
159
160                 /* lookup child node */
161                 c = s[len - 1 - depth];
162                 search.c = c;
163                 child = bsearch(&search, node->children, node->children_count,
164                                 sizeof(struct strbuf_child_entry),
165                                 (__compar_fn_t) strbuf_children_cmp);
166                 if (!child)
167                         break;
168                 node = child->child;
169         }
170
171         /* add new string */
172         buf_new = realloc(str->buf, str->len + len+1);
173         if (!buf_new)
174                 return -ENOMEM;
175         str->buf = buf_new;
176         off = str->len;
177         memcpy(str->buf + off, s, len);
178         str->len += len;
179         str->buf[str->len++] = '\0';
180
181         /* new node */
182         node_child = new0(struct strbuf_node, 1);
183         if (!node_child)
184                 return -ENOMEM;
185         node_child->value_off = off;
186         node_child->value_len = len;
187
188         /* extend array, add new entry, sort for bisection */
189         child = realloc(node->children, (node->children_count + 1) * sizeof(struct strbuf_child_entry));
190         if (!child) {
191                 free(node_child);
192                 return -ENOMEM;
193         }
194
195         str->nodes_count++;
196
197         node->children = child;
198         bubbleinsert(node, c, node_child);
199
200         return off;
201 }