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 continous 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 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
 105 /* add string, return the index/offset into the buffer */
 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         node_child->value_off = off;
 162         node_child->value_len = len;
 163
 164         /* extend array, add new entry, sort for bisection */
 165         child = realloc(node->children, (node->children_count + 1) * sizeof(struct strbuf_child_entry));
 166         if (!child) {
 167                 free(node_child);
 168                 return -ENOMEM;
 169         }
 170
 171         str->nodes_count++;
 172
 173         node->children = child;
 174         node->children[node->children_count].c = c;
 175         node->children[node->children_count].child = node_child;
 176         node->children_count++;
 177         qsort(node->children, node->children_count, sizeof(struct strbuf_child_entry), strbuf_children_cmp);
 178
 179         return off;
 180 }