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.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
  28 /*
  29  * Strbuf stores given strings in a single continous allocated memory
  30  * area. Identical strings are de-duplicated. If the tail of a string
  31  * already exist in the buffer, the tail is returned.
  32  *
  33  * A Particia Trie is used to maintain the information about the stored
  34  * strings.
  35  *
  36  * Example of udev rules:
  37  *   $ ./udevadm test .
  38  *   ...
  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
  42  *   ...
  43  */
  44
  45 struct strbuf *strbuf_new(void) {
  46         struct strbuf *str;
  47
  48         str = new0(struct strbuf, 1);
  49         if (!str)
  50                 return NULL;
  51
  52         str->buf = new0(char, 1);
  53         if (!str->buf)
  54                 goto err;
  55         str->len = 1;
  56
  57         str->root = new0(struct strbuf_node, 1);
  58         if (!str->root)
  59                 goto err;
  60         str->nodes_count = 1;
  61         return str;
  62 err:
  63         free(str->buf);
  64         free(str->root);
  65         free(str);
  66         return NULL;
  67 }
  68
  69 static void strbuf_node_cleanup(struct strbuf_node *node) {
  70         size_t i;
  71
  72         for (i = 0; i < node->children_count; i++)
  73                 strbuf_node_cleanup(node->children[i].child);
  74         free(node->children);
  75         free(node);
  76 }
  77
  78 /* clean up trie data, leave only the string buffer */
  79 void strbuf_complete(struct strbuf *str) {
  80         if (!str)
  81                 return;
  82         if (str->root)
  83                 strbuf_node_cleanup(str->root);
  84         str->root = NULL;
  85 }
  86
  87 /* clean up everything */
  88 void strbuf_cleanup(struct strbuf *str) {
  89         if (!str)
  90                 return;
  91         if (str->root)
  92                 strbuf_node_cleanup(str->root);
  93         free(str->buf);
  94         free(str);
  95 }
  96
  97 static int strbuf_children_cmp(const void *v1, const void *v2) {
  98         const struct strbuf_child_entry *n1 = v1;
  99         const struct strbuf_child_entry *n2 = v2;
 100
 101         return n1->c - n2->c;
 102 }
 103
 104 /* add string, return the index/offset into the buffer */
 105 ssize_t strbuf_add_string(struct strbuf *str, const char *s, size_t len) {
 106         uint8_t c;
 107         struct strbuf_node *node;
 108         size_t depth;
 109         char *buf_new;
 110         struct strbuf_child_entry *child;
 111         struct strbuf_node *node_child;
 112         ssize_t off;
 113
 114         if (!str->root)
 115                 return -EINVAL;
 116
 117         /* search string; start from last character to find possibly matching tails */
 118         if (len == 0)
 119                 return 0;
 120         str->in_count++;
 121         str->in_len += len;
 122
 123         node = str->root;
 124         c = s[len-1];
 125         for (depth = 0; depth <= len; depth++) {
 126                 struct strbuf_child_entry search;
 127
 128                 /* match against current node */
 129                 off = node->value_off + node->value_len - len;
 130                 if (depth == len || (node->value_len >= len && memcmp(str->buf + off, s, len) == 0)) {
 131                         str->dedup_len += len;
 132                         str->dedup_count++;
 133                         return off;
 134                 }
 135
 136                 /* lookup child node */
 137                 c = s[len - 1 - depth];
 138                 search.c = c;
 139                 child = bsearch(&search, node->children, node->children_count, sizeof(struct strbuf_child_entry),
 140                                 strbuf_children_cmp);
 141                 if (!child)
 142                         break;
 143                 node = child->child;
 144         }
 145
 146         /* add new string */
 147         buf_new = realloc(str->buf, str->len + len+1);
 148         if (!buf_new)
 149                 return -ENOMEM;
 150         str->buf = buf_new;
 151         off = str->len;
 152         memcpy(str->buf + off, s, len);
 153         str->len += len;
 154         str->buf[str->len++] = '\0';
 155
 156         /* new node */
 157         node_child = new0(struct strbuf_node, 1);
 158         if (!node_child)
 159                 return -ENOMEM;
 160         str->nodes_count++;
 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                 return -ENOMEM;
 168         node->children = child;
 169         node->children[node->children_count].c = c;
 170         node->children[node->children_count].child = node_child;
 171         node->children_count++;
 172         qsort(node->children, node->children_count, sizeof(struct strbuf_child_entry), strbuf_children_cmp);
 173
 174         return off;
 175 }