lsquic_set.c revision 50aadb33 
1/* Copyright (c) 2017 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_set.c -- A set implementation.
4 *
5 * Deleting from a set is not supported.  Implemented as a sorted array.
6 * Optimized for reading.  Insertion may trigger realloc, memmove, or
7 * both.
8 */
9
10#include <assert.h>
11#include <errno.h>
12#include <limits.h>
13#include <stdlib.h>
14#include <string.h>
15
16#include "lsquic_set.h"
17
18
19struct lsquic_set32_elem
20{
21    uint32_t   low, high;
22};
23
24
25void
26lsquic_set32_init (struct lsquic_set32 *set)
27{
28    memset(set, 0, sizeof(*set));
29}
30
31
32void
33lsquic_set32_cleanup (struct lsquic_set32 *set)
34{
35    free(set->elems);
36}
37
38
39static int
40lsquic_set32_insert_set_elem (struct lsquic_set32 *set, int i, uint32_t value)
41{
42    struct lsquic_set32_elem *elems;
43
44    if (set->n_elems == INT_MAX)
45    {
46        errno = EOVERFLOW;
47        return -1;
48    }
49
50    if (set->n_alloc == set->n_elems)
51    {
52        if (set->n_alloc)
53            set->n_alloc *= 2;
54        else
55            set->n_alloc = 4;
56        elems = realloc(set->elems, sizeof(set->elems[0]) * set->n_alloc);
57        if (!elems)
58            return -1;
59        set->elems = elems;
60    }
61    if (i < set->n_elems)
62        memmove(&set->elems[i + 1], &set->elems[i],
63                                    (set->n_elems - i) * sizeof(set->elems[i]));
64    set->elems[i].low = set->elems[i].high = value;
65    ++set->n_elems;
66    return 0;
67}
68
69
70static void
71lsquic_set32_merge_set_elems (struct lsquic_set32 *set, int i)
72{
73    assert(i >= 0);
74    assert(i < set->n_elems - 1);
75    assert(set->elems[i].high + 1 == set->elems[i + 1].low);
76    set->elems[i].high = set->elems[i + 1].high;
77    if (i < set->n_elems - 2)
78        memmove(&set->elems[i + 1], &set->elems[i + 2],
79                                (set->n_elems - i - 2) * sizeof(set->elems[i]));
80    --set->n_elems;
81}
82
83
84#ifndef NDEBUG
85static void
86lsquic_set32_check_elems_sorted (const struct lsquic_set32 *set)
87{
88    int i;
89    for (i = 0; i < set->n_elems; ++i)
90    {
91        assert(set->elems[i].low <= set->elems[i].high);
92        if (i > 0)
93            assert(set->elems[i - 1].high + 1 < set->elems[i].low);
94    }
95}
96#endif
97
98
99int
100lsquic_set32_add (struct lsquic_set32 *set, uint32_t value)
101{
102    if (value < 64)
103    {
104        set->lowset |= 1ULL << value;
105        return 0;
106    }
107
108    int low, high, i;
109
110    if (set->n_elems > 0)
111    {
112        low = 0, high = set->n_elems - 1;
113        do
114        {
115            i = low + (high - low) / 2;
116            if (set->elems[i].low <= value && set->elems[i].high >= value)
117                return 0;
118            else if (set->elems[i].high < value)
119                low = i + 1;
120            else
121                high = i - 1;
122        }
123        while (low <= high);
124
125        if (value < set->elems[i].low)
126        {
127            if (set->elems[i].low - 1 == value)
128            {
129                set->elems[i].low = value;
130                if (i > 0 && set->elems[i - 1].high + 1 == value)
131                    lsquic_set32_merge_set_elems(set, i - 1);
132            }
133            else if (i > 0 && set->elems[i - 1].high + 1 == value)
134                set->elems[i - 1].high = value;
135            else if (0 != lsquic_set32_insert_set_elem(set, i, value))
136                return -1;
137        }
138        else
139        {
140            assert(value > set->elems[i].high);
141            if (set->elems[i].high + 1 == value)
142            {
143                set->elems[i].high = value;
144                if (i + 1 < set->n_elems && set->elems[i + 1].low - 1== value)
145                    lsquic_set32_merge_set_elems(set, i);
146            }
147            else if (i + 1 < set->n_elems && set->elems[i + 1].low - 1 == value)
148                set->elems[i + 1].low = value;
149            else if (0 != lsquic_set32_insert_set_elem(set, i + 1, value))
150                return 0;
151        }
152    }
153    else
154    {
155        assert(NULL == set->elems);
156        if (0 != lsquic_set32_insert_set_elem(set, 0, value))
157            return -1;
158    }
159#ifndef NDEBUG
160    lsquic_set32_check_elems_sorted(set);
161#endif
162    return 0;
163}
164
165
166int
167lsquic_set32_has (const struct lsquic_set32 *set, uint32_t value)
168{
169    if (value < 64)
170    {
171        return !!(set->lowset & (1ULL << value));
172    }
173
174    int low, high, i;
175
176    low = 0, high = set->n_elems - 1;
177    while (low <= high)
178    {
179        i = low + (high - low) / 2;
180        if (set->elems[i].low <= value && set->elems[i].high >= value)
181            return 1;
182        else if (set->elems[i].high < value)
183            low = i + 1;
184        else
185            high = i - 1;
186    }
187
188    return 0;
189}
190
191
192/* ******* ******* ******** *******
193 *
194 * The following code is a set of two replacements:
195 *
196 * :.,$s/lsquic_set32/lsquic_set64/g
197 * :.,$s/uint32_t/uint64_t/g
198 */
199struct lsquic_set64_elem
200{
201    uint64_t   low, high;
202};
203
204
205void
206lsquic_set64_init (struct lsquic_set64 *set)
207{
208    memset(set, 0, sizeof(*set));
209}
210
211
212void
213lsquic_set64_cleanup (struct lsquic_set64 *set)
214{
215    free(set->elems);
216}
217
218
219static int
220lsquic_set64_insert_set_elem (struct lsquic_set64 *set, int i, uint64_t value)
221{
222    struct lsquic_set64_elem *elems;
223
224    if (set->n_elems == INT_MAX)
225    {
226        errno = EOVERFLOW;
227        return -1;
228    }
229
230    if (set->n_alloc == set->n_elems)
231    {
232        if (set->n_alloc)
233            set->n_alloc *= 2;
234        else
235            set->n_alloc = 4;
236        elems = realloc(set->elems, sizeof(set->elems[0]) * set->n_alloc);
237        if (!elems)
238            return -1;
239        set->elems = elems;
240    }
241    if (i < set->n_elems)
242        memmove(&set->elems[i + 1], &set->elems[i],
243                                    (set->n_elems - i) * sizeof(set->elems[i]));
244    set->elems[i].low = set->elems[i].high = value;
245    ++set->n_elems;
246    return 0;
247}
248
249
250static void
251lsquic_set64_merge_set_elems (struct lsquic_set64 *set, int i)
252{
253    assert(i >= 0);
254    assert(i < set->n_elems - 1);
255    assert(set->elems[i].high + 1 == set->elems[i + 1].low);
256    set->elems[i].high = set->elems[i + 1].high;
257    if (i < set->n_elems - 2)
258        memmove(&set->elems[i + 1], &set->elems[i + 2],
259                                (set->n_elems - i - 2) * sizeof(set->elems[i]));
260    --set->n_elems;
261}
262
263
264#ifndef NDEBUG
265static void
266lsquic_set64_check_elems_sorted (const struct lsquic_set64 *set)
267{
268    int i;
269    for (i = 0; i < set->n_elems; ++i)
270    {
271        assert(set->elems[i].low <= set->elems[i].high);
272        if (i > 0)
273            assert(set->elems[i - 1].high + 1 < set->elems[i].low);
274    }
275}
276#endif
277
278
279int
280lsquic_set64_add (struct lsquic_set64 *set, uint64_t value)
281{
282    if (value < 64)
283    {
284        set->lowset |= 1ULL << value;
285        return 0;
286    }
287
288    int low, high, i;
289
290    if (set->n_elems > 0)
291    {
292        low = 0, high = set->n_elems - 1;
293        do
294        {
295            i = low + (high - low) / 2;
296            if (set->elems[i].low <= value && set->elems[i].high >= value)
297                return 0;
298            else if (set->elems[i].high < value)
299                low = i + 1;
300            else
301                high = i - 1;
302        }
303        while (low <= high);
304
305        if (value < set->elems[i].low)
306        {
307            if (set->elems[i].low - 1 == value)
308            {
309                set->elems[i].low = value;
310                if (i > 0 && set->elems[i - 1].high + 1 == value)
311                    lsquic_set64_merge_set_elems(set, i - 1);
312            }
313            else if (i > 0 && set->elems[i - 1].high + 1 == value)
314                set->elems[i - 1].high = value;
315            else if (0 != lsquic_set64_insert_set_elem(set, i, value))
316                return -1;
317        }
318        else
319        {
320            assert(value > set->elems[i].high);
321            if (set->elems[i].high + 1 == value)
322            {
323                set->elems[i].high = value;
324                if (i + 1 < set->n_elems && set->elems[i + 1].low - 1== value)
325                    lsquic_set64_merge_set_elems(set, i);
326            }
327            else if (i + 1 < set->n_elems && set->elems[i + 1].low - 1 == value)
328                set->elems[i + 1].low = value;
329            else if (0 != lsquic_set64_insert_set_elem(set, i + 1, value))
330                return 0;
331        }
332    }
333    else
334    {
335        assert(NULL == set->elems);
336        if (0 != lsquic_set64_insert_set_elem(set, 0, value))
337            return -1;
338    }
339#ifndef NDEBUG
340    lsquic_set64_check_elems_sorted(set);
341#endif
342    return 0;
343}
344
345
346int
347lsquic_set64_has (const struct lsquic_set64 *set, uint64_t value)
348{
349    if (value < 64)
350    {
351        return !!(set->lowset & (1ULL << value));
352    }
353
354    int low, high, i;
355
356    low = 0, high = set->n_elems - 1;
357    while (low <= high)
358    {
359        i = low + (high - low) / 2;
360        if (set->elems[i].low <= value && set->elems[i].high >= value)
361            return 1;
362        else if (set->elems[i].high < value)
363            low = i + 1;
364        else
365            high = i - 1;
366    }
367
368    return 0;
369}
370
371
372