]>
Commit | Line | Data |
---|---|---|
955bd501 KS |
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.sievers@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 | ||
4693cfb3 KS |
28 | /* |
29 | * Strbuf stores given strings in a single continous allocated memory | |
f1c0ece1 KS |
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. | |
4693cfb3 | 33 | * |
f1c0ece1 KS |
34 | * A trie (http://en.wikipedia.org/wiki/Trie) is used to maintain the |
35 | * information about the stored strings. | |
4693cfb3 KS |
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 | ||
955bd501 KS |
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 | ||
4693cfb3 | 79 | /* clean up trie data, leave only the string buffer */ |
955bd501 KS |
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 | ||
4693cfb3 | 88 | /* clean up everything */ |
955bd501 KS |
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 void *v1, const void *v2) { | |
99 | const struct strbuf_child_entry *n1 = v1; | |
100 | const struct strbuf_child_entry *n2 = v2; | |
101 | ||
102 | return n1->c - n2->c; | |
103 | } | |
104 | ||
4693cfb3 | 105 | /* add string, return the index/offset into the buffer */ |
955bd501 KS |
106 | ssize_t strbuf_add_string(struct strbuf *str, const char *s, size_t len) { |
107 | uint8_t c; | |
108 | struct strbuf_node *node; | |
109 | size_t depth; | |
110 | char *buf_new; | |
111 | struct strbuf_child_entry *child; | |
112 | struct strbuf_node *node_child; | |
113 | ssize_t off; | |
114 | ||
115 | if (!str->root) | |
116 | return -EINVAL; | |
117 | ||
118 | /* search string; start from last character to find possibly matching tails */ | |
119 | if (len == 0) | |
120 | return 0; | |
121 | str->in_count++; | |
122 | str->in_len += len; | |
123 | ||
124 | node = str->root; | |
125 | c = s[len-1]; | |
126 | for (depth = 0; depth <= len; depth++) { | |
127 | struct strbuf_child_entry search; | |
128 | ||
129 | /* match against current node */ | |
130 | off = node->value_off + node->value_len - len; | |
131 | if (depth == len || (node->value_len >= len && memcmp(str->buf + off, s, len) == 0)) { | |
132 | str->dedup_len += len; | |
133 | str->dedup_count++; | |
134 | return off; | |
135 | } | |
136 | ||
137 | /* lookup child node */ | |
138 | c = s[len - 1 - depth]; | |
139 | search.c = c; | |
140 | child = bsearch(&search, node->children, node->children_count, sizeof(struct strbuf_child_entry), | |
141 | strbuf_children_cmp); | |
142 | if (!child) | |
143 | break; | |
144 | node = child->child; | |
145 | } | |
146 | ||
147 | /* add new string */ | |
148 | buf_new = realloc(str->buf, str->len + len+1); | |
149 | if (!buf_new) | |
150 | return -ENOMEM; | |
151 | str->buf = buf_new; | |
152 | off = str->len; | |
153 | memcpy(str->buf + off, s, len); | |
154 | str->len += len; | |
155 | str->buf[str->len++] = '\0'; | |
156 | ||
157 | /* new node */ | |
158 | node_child = new0(struct strbuf_node, 1); | |
159 | if (!node_child) | |
160 | return -ENOMEM; | |
161 | str->nodes_count++; | |
162 | node_child->value_off = off; | |
163 | node_child->value_len = len; | |
164 | ||
165 | /* extend array, add new entry, sort for bisection */ | |
166 | child = realloc(node->children, (node->children_count + 1) * sizeof(struct strbuf_child_entry)); | |
167 | if (!child) | |
168 | return -ENOMEM; | |
169 | node->children = child; | |
170 | node->children[node->children_count].c = c; | |
171 | node->children[node->children_count].child = node_child; | |
172 | node->children_count++; | |
173 | qsort(node->children, node->children_count, sizeof(struct strbuf_child_entry), strbuf_children_cmp); | |
174 | ||
175 | return off; | |
176 | } |