← Back to branch summary

~ubuntu-branches/ubuntu/trusty/systemd/trusty

« back to all changes in this revision

Viewing changes to src/shared/strbuf.c

Tags: upstream-202
Import upstream version 202

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/shared/strbuf.c
26
26
#include "strbuf.h"
27
27
 
28
28
/*
29
 
 * Strbuf stores given strings in a single continous allocated memory
 
29
 * Strbuf stores given strings in a single continuous allocated memory
30
30
 * area. Identical strings are de-duplicated and return the same offset
31
31
 * as the first string stored. If the tail of a string already exists
32
32
 * in the buffer, the tail is returned.
95
95
        free(str);
96
96
}
97
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
 
 
 
98
static int strbuf_children_cmp(const struct strbuf_child_entry *n1,
 
99
                               const struct strbuf_child_entry *n2) {
102
100
        return n1->c - n2->c;
103
101
}
104
102
 
 
103
static void bubbleinsert(struct strbuf_node *node,
 
104
                         uint8_t c,
 
105
                         struct strbuf_node *node_child) {
 
106
 
 
107
        struct strbuf_child_entry new = {
 
108
                .c = c,
 
109
                .child = node_child,
 
110
        };
 
111
        int left = 0, right = node->children_count;
 
112
 
 
113
        while (right > left) {
 
114
                int middle = (right + left) / 2 ;
 
115
                if (strbuf_children_cmp(&node->children[middle], &new) <= 0)
 
116
                        left = middle + 1;
 
117
                else
 
118
                        right = middle;
 
119
        }
 
120
 
 
121
        memmove(node->children + left + 1, node->children + left,
 
122
                sizeof(struct strbuf_child_entry) * (node->children_count - left));
 
123
        node->children[left] = new;
 
124
 
 
125
        node->children_count ++;
 
126
}
 
127
 
105
128
/* add string, return the index/offset into the buffer */
106
129
ssize_t strbuf_add_string(struct strbuf *str, const char *s, size_t len) {
107
130
        uint8_t c;
137
160
                /* lookup child node */
138
161
                c = s[len - 1 - depth];
139
162
                search.c = c;
140
 
                child = bsearch(&search, node->children, node->children_count, sizeof(struct strbuf_child_entry),
141
 
                                strbuf_children_cmp);
 
163
                child = bsearch(&search, node->children, node->children_count,
 
164
                                sizeof(struct strbuf_child_entry),
 
165
                                (__compar_fn_t) strbuf_children_cmp);
142
166
                if (!child)
143
167
                        break;
144
168
                node = child->child;
158
182
        node_child = new0(struct strbuf_node, 1);
159
183
        if (!node_child)
160
184
                return -ENOMEM;
161
 
        str->nodes_count++;
162
185
        node_child->value_off = off;
163
186
        node_child->value_len = len;
164
187
 
165
188
        /* extend array, add new entry, sort for bisection */
166
189
        child = realloc(node->children, (node->children_count + 1) * sizeof(struct strbuf_child_entry));
167
 
        if (!child)
 
190
        if (!child) {
 
191
                free(node_child);
168
192
                return -ENOMEM;
 
193
        }
 
194
 
 
195
        str->nodes_count++;
 
196
 
169
197
        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);
 
198
        bubbleinsert(node, c, node_child);
174
199
 
175
200
        return off;
176
201
}