+++ /dev/null
-/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
-
-/***
- This file is part of systemd.
-
- Copyright 2012 Kay Sievers <kay@vrfy.org>
-
- systemd is free software; you can redistribute it and/or modify it
- under the terms of the GNU Lesser General Public License as published by
- the Free Software Foundation; either version 2.1 of the License, or
- (at your option) any later version.
-
- systemd is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public License
- along with systemd; If not, see <http://www.gnu.org/licenses/>.
-***/
-
-#include <stdlib.h>
-#include <string.h>
-
-#include "util.h"
-#include "strbuf.h"
-
-/*
- * Strbuf stores given strings in a single continuous allocated memory
- * area. Identical strings are de-duplicated and return the same offset
- * as the first string stored. If the tail of a string already exists
- * in the buffer, the tail is returned.
- *
- * A trie (http://en.wikipedia.org/wiki/Trie) is used to maintain the
- * information about the stored strings.
- *
- * Example of udev rules:
- * $ ./udevadm test .
- * ...
- * read rules file: /usr/lib/udev/rules.d/99-systemd.rules
- * rules contain 196608 bytes tokens (16384 * 12 bytes), 39742 bytes strings
- * 23939 strings (207859 bytes), 20404 de-duplicated (171653 bytes), 3536 trie nodes used
- * ...
- */
-
-struct strbuf *strbuf_new(void) {
- struct strbuf *str;
-
- str = new0(struct strbuf, 1);
- if (!str)
- return NULL;
-
- str->buf = new0(char, 1);
- if (!str->buf)
- goto err;
- str->len = 1;
-
- str->root = new0(struct strbuf_node, 1);
- if (!str->root)
- goto err;
- str->nodes_count = 1;
- return str;
-err:
- free(str->buf);
- free(str->root);
- free(str);
- return NULL;
-}
-
-static void strbuf_node_cleanup(struct strbuf_node *node) {
- size_t i;
-
- for (i = 0; i < node->children_count; i++)
- strbuf_node_cleanup(node->children[i].child);
- free(node->children);
- free(node);
-}
-
-/* clean up trie data, leave only the string buffer */
-void strbuf_complete(struct strbuf *str) {
- if (!str)
- return;
- if (str->root)
- strbuf_node_cleanup(str->root);
- str->root = NULL;
-}
-
-/* clean up everything */
-void strbuf_cleanup(struct strbuf *str) {
- if (!str)
- return;
- if (str->root)
- strbuf_node_cleanup(str->root);
- free(str->buf);
- free(str);
-}
-
-static int strbuf_children_cmp(const struct strbuf_child_entry *n1,
- const struct strbuf_child_entry *n2) {
- return n1->c - n2->c;
-}
-
-static void bubbleinsert(struct strbuf_node *node,
- uint8_t c,
- struct strbuf_node *node_child) {
-
- struct strbuf_child_entry new = {
- .c = c,
- .child = node_child,
- };
- int left = 0, right = node->children_count;
-
- while (right > left) {
- int middle = (right + left) / 2 ;
- if (strbuf_children_cmp(&node->children[middle], &new) <= 0)
- left = middle + 1;
- else
- right = middle;
- }
-
- memmove(node->children + left + 1, node->children + left,
- sizeof(struct strbuf_child_entry) * (node->children_count - left));
- node->children[left] = new;
-
- node->children_count ++;
-}
-
-/* add string, return the index/offset into the buffer */
-ssize_t strbuf_add_string(struct strbuf *str, const char *s, size_t len) {
- uint8_t c;
- struct strbuf_node *node;
- size_t depth;
- char *buf_new;
- struct strbuf_child_entry *child;
- struct strbuf_node *node_child;
- ssize_t off;
-
- if (!str->root)
- return -EINVAL;
-
- /* search string; start from last character to find possibly matching tails */
- if (len == 0)
- return 0;
- str->in_count++;
- str->in_len += len;
-
- node = str->root;
- c = s[len-1];
- for (depth = 0; depth <= len; depth++) {
- struct strbuf_child_entry search;
-
- /* match against current node */
- off = node->value_off + node->value_len - len;
- if (depth == len || (node->value_len >= len && memcmp(str->buf + off, s, len) == 0)) {
- str->dedup_len += len;
- str->dedup_count++;
- return off;
- }
-
- /* lookup child node */
- c = s[len - 1 - depth];
- search.c = c;
- child = bsearch(&search, node->children, node->children_count,
- sizeof(struct strbuf_child_entry),
- (__compar_fn_t) strbuf_children_cmp);
- if (!child)
- break;
- node = child->child;
- }
-
- /* add new string */
- buf_new = realloc(str->buf, str->len + len+1);
- if (!buf_new)
- return -ENOMEM;
- str->buf = buf_new;
- off = str->len;
- memcpy(str->buf + off, s, len);
- str->len += len;
- str->buf[str->len++] = '\0';
-
- /* new node */
- node_child = new0(struct strbuf_node, 1);
- if (!node_child)
- return -ENOMEM;
- node_child->value_off = off;
- node_child->value_len = len;
-
- /* extend array, add new entry, sort for bisection */
- child = realloc(node->children, (node->children_count + 1) * sizeof(struct strbuf_child_entry));
- if (!child) {
- free(node_child);
- return -ENOMEM;
- }
-
- str->nodes_count++;
-
- node->children = child;
- bubbleinsert(node, c, node_child);
-
- return off;
-}
~ianmdlvl / elogind.git / blobdiff