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 struct strbuf *strbuf_new(void) {
  29         struct strbuf *str;
  30
  31         str = new0(struct strbuf, 1);
  32         if (!str)
  33                 return NULL;
  34
  35         str->buf = new0(char, 1);
  36         if (!str->buf)
  37                 goto err;
  38         str->len = 1;
  39
  40         str->root = new0(struct strbuf_node, 1);
  41         if (!str->root)
  42                 goto err;
  43         str->nodes_count = 1;
  44         return str;
  45 err:
  46         free(str->buf);
  47         free(str->root);
  48         free(str);
  49         return NULL;
  50 }
  51
  52 static void strbuf_node_cleanup(struct strbuf_node *node) {
  53         size_t i;
  54
  55         for (i = 0; i < node->children_count; i++)
  56                 strbuf_node_cleanup(node->children[i].child);
  57         free(node->children);
  58         free(node);
  59 }
  60
  61 void strbuf_complete(struct strbuf *str) {
  62         if (!str)
  63                 return;
  64         if (str->root)
  65                 strbuf_node_cleanup(str->root);
  66         str->root = NULL;
  67 }
  68
  69 void strbuf_cleanup(struct strbuf *str) {
  70         if (!str)
  71                 return;
  72         if (str->root)
  73                 strbuf_node_cleanup(str->root);
  74         free(str->buf);
  75         free(str);
  76 }
  77
  78 static int strbuf_children_cmp(const void *v1, const void *v2) {
  79         const struct strbuf_child_entry *n1 = v1;
  80         const struct strbuf_child_entry *n2 = v2;
  81
  82         return n1->c - n2->c;
  83 }
  84
  85 ssize_t strbuf_add_string(struct strbuf *str, const char *s, size_t len) {
  86         uint8_t c;
  87         struct strbuf_node *node;
  88         size_t depth;
  89         char *buf_new;
  90         struct strbuf_child_entry *child;
  91         struct strbuf_node *node_child;
  92         ssize_t off;
  93
  94         if (!str->root)
  95                 return -EINVAL;
  96
  97         /* search string; start from last character to find possibly matching tails */
  98         if (len == 0)
  99                 return 0;
 100         str->in_count++;
 101         str->in_len += len;
 102
 103         node = str->root;
 104         c = s[len-1];
 105         for (depth = 0; depth <= len; depth++) {
 106                 struct strbuf_child_entry search;
 107
 108                 /* match against current node */
 109                 off = node->value_off + node->value_len - len;
 110                 if (depth == len || (node->value_len >= len && memcmp(str->buf + off, s, len) == 0)) {
 111                         str->dedup_len += len;
 112                         str->dedup_count++;
 113                         return off;
 114                 }
 115
 116                 /* lookup child node */
 117                 c = s[len - 1 - depth];
 118                 search.c = c;
 119                 child = bsearch(&search, node->children, node->children_count, sizeof(struct strbuf_child_entry),
 120                                 strbuf_children_cmp);
 121                 if (!child)
 122                         break;
 123                 node = child->child;
 124         }
 125
 126         /* add new string */
 127         buf_new = realloc(str->buf, str->len + len+1);
 128         if (!buf_new)
 129                 return -ENOMEM;
 130         str->buf = buf_new;
 131         off = str->len;
 132         memcpy(str->buf + off, s, len);
 133         str->len += len;
 134         str->buf[str->len++] = '\0';
 135
 136         /* new node */
 137         node_child = new0(struct strbuf_node, 1);
 138         if (!node_child)
 139                 return -ENOMEM;
 140         str->nodes_count++;
 141         node_child->value_off = off;
 142         node_child->value_len = len;
 143
 144         /* extend array, add new entry, sort for bisection */
 145         child = realloc(node->children, (node->children_count + 1) * sizeof(struct strbuf_child_entry));
 146         if (!child)
 147                 return -ENOMEM;
 148         node->children = child;
 149         node->children[node->children_count].c = c;
 150         node->children[node->children_count].child = node_child;
 151         node->children_count++;
 152         qsort(node->children, node->children_count, sizeof(struct strbuf_child_entry), strbuf_children_cmp);
 153
 154         return off;
 155 }