1*e7be843bSPierre Pronchery /*
2*e7be843bSPierre Pronchery * Copyright 2022-2023 The OpenSSL Project Authors. All Rights Reserved.
3*e7be843bSPierre Pronchery *
4*e7be843bSPierre Pronchery * Licensed under the Apache License 2.0 (the "License"). You may not use
5*e7be843bSPierre Pronchery * this file except in compliance with the License. You can obtain a copy
6*e7be843bSPierre Pronchery * in the file LICENSE in the source distribution or at
7*e7be843bSPierre Pronchery * https://www.openssl.org/source/license.html
8*e7be843bSPierre Pronchery */
9*e7be843bSPierre Pronchery
10*e7be843bSPierre Pronchery #include "internal/uint_set.h"
11*e7be843bSPierre Pronchery #include "internal/common.h"
12*e7be843bSPierre Pronchery #include <assert.h>
13*e7be843bSPierre Pronchery
14*e7be843bSPierre Pronchery /*
15*e7be843bSPierre Pronchery * uint64_t Integer Sets
16*e7be843bSPierre Pronchery * =====================
17*e7be843bSPierre Pronchery *
18*e7be843bSPierre Pronchery * This data structure supports the following operations:
19*e7be843bSPierre Pronchery *
20*e7be843bSPierre Pronchery * Insert Range: Adds an inclusive range of integers [start, end]
21*e7be843bSPierre Pronchery * to the set. Equivalent to Insert for each number
22*e7be843bSPierre Pronchery * in the range.
23*e7be843bSPierre Pronchery *
24*e7be843bSPierre Pronchery * Remove Range: Removes an inclusive range of integers [start, end]
25*e7be843bSPierre Pronchery * from the set. Not all of the range need already be in
26*e7be843bSPierre Pronchery * the set, but any part of the range in the set is removed.
27*e7be843bSPierre Pronchery *
28*e7be843bSPierre Pronchery * Query: Is an integer in the data structure?
29*e7be843bSPierre Pronchery *
30*e7be843bSPierre Pronchery * The data structure can be iterated.
31*e7be843bSPierre Pronchery *
32*e7be843bSPierre Pronchery * For greater efficiency in tracking large numbers of contiguous integers, we
33*e7be843bSPierre Pronchery * track integer ranges rather than individual integers. The data structure
34*e7be843bSPierre Pronchery * manages a list of integer ranges [[start, end]...]. Internally this is
35*e7be843bSPierre Pronchery * implemented as a doubly linked sorted list of range structures, which are
36*e7be843bSPierre Pronchery * automatically split and merged as necessary.
37*e7be843bSPierre Pronchery *
38*e7be843bSPierre Pronchery * This data structure requires O(n) traversal of the list for insertion,
39*e7be843bSPierre Pronchery * removal and query when we are not adding/removing ranges which are near the
40*e7be843bSPierre Pronchery * beginning or end of the set of ranges. For the applications for which this
41*e7be843bSPierre Pronchery * data structure is used (e.g. QUIC PN tracking for ACK generation), it is
42*e7be843bSPierre Pronchery * expected that the number of integer ranges needed at any given time will
43*e7be843bSPierre Pronchery * generally be small and that most operations will be close to the beginning or
44*e7be843bSPierre Pronchery * end of the range.
45*e7be843bSPierre Pronchery *
46*e7be843bSPierre Pronchery * Invariant: The data structure is always sorted in ascending order by value.
47*e7be843bSPierre Pronchery *
48*e7be843bSPierre Pronchery * Invariant: No two adjacent ranges ever 'border' one another (have no
49*e7be843bSPierre Pronchery * numerical gap between them) as the data structure always ensures
50*e7be843bSPierre Pronchery * such ranges are merged.
51*e7be843bSPierre Pronchery *
52*e7be843bSPierre Pronchery * Invariant: No two ranges ever overlap.
53*e7be843bSPierre Pronchery *
54*e7be843bSPierre Pronchery * Invariant: No range [a, b] ever has a > b.
55*e7be843bSPierre Pronchery *
56*e7be843bSPierre Pronchery * Invariant: Since ranges are represented using inclusive bounds, no range
57*e7be843bSPierre Pronchery * item inside the data structure can represent a span of zero
58*e7be843bSPierre Pronchery * integers.
59*e7be843bSPierre Pronchery */
ossl_uint_set_init(UINT_SET * s)60*e7be843bSPierre Pronchery void ossl_uint_set_init(UINT_SET *s)
61*e7be843bSPierre Pronchery {
62*e7be843bSPierre Pronchery ossl_list_uint_set_init(s);
63*e7be843bSPierre Pronchery }
64*e7be843bSPierre Pronchery
ossl_uint_set_destroy(UINT_SET * s)65*e7be843bSPierre Pronchery void ossl_uint_set_destroy(UINT_SET *s)
66*e7be843bSPierre Pronchery {
67*e7be843bSPierre Pronchery UINT_SET_ITEM *x, *xnext;
68*e7be843bSPierre Pronchery
69*e7be843bSPierre Pronchery for (x = ossl_list_uint_set_head(s); x != NULL; x = xnext) {
70*e7be843bSPierre Pronchery xnext = ossl_list_uint_set_next(x);
71*e7be843bSPierre Pronchery OPENSSL_free(x);
72*e7be843bSPierre Pronchery }
73*e7be843bSPierre Pronchery }
74*e7be843bSPierre Pronchery
75*e7be843bSPierre Pronchery /* Possible merge of x, prev(x) */
uint_set_merge_adjacent(UINT_SET * s,UINT_SET_ITEM * x)76*e7be843bSPierre Pronchery static void uint_set_merge_adjacent(UINT_SET *s, UINT_SET_ITEM *x)
77*e7be843bSPierre Pronchery {
78*e7be843bSPierre Pronchery UINT_SET_ITEM *xprev = ossl_list_uint_set_prev(x);
79*e7be843bSPierre Pronchery
80*e7be843bSPierre Pronchery if (xprev == NULL)
81*e7be843bSPierre Pronchery return;
82*e7be843bSPierre Pronchery
83*e7be843bSPierre Pronchery if (x->range.start - 1 != xprev->range.end)
84*e7be843bSPierre Pronchery return;
85*e7be843bSPierre Pronchery
86*e7be843bSPierre Pronchery x->range.start = xprev->range.start;
87*e7be843bSPierre Pronchery ossl_list_uint_set_remove(s, xprev);
88*e7be843bSPierre Pronchery OPENSSL_free(xprev);
89*e7be843bSPierre Pronchery }
90*e7be843bSPierre Pronchery
u64_min(uint64_t x,uint64_t y)91*e7be843bSPierre Pronchery static uint64_t u64_min(uint64_t x, uint64_t y)
92*e7be843bSPierre Pronchery {
93*e7be843bSPierre Pronchery return x < y ? x : y;
94*e7be843bSPierre Pronchery }
95*e7be843bSPierre Pronchery
u64_max(uint64_t x,uint64_t y)96*e7be843bSPierre Pronchery static uint64_t u64_max(uint64_t x, uint64_t y)
97*e7be843bSPierre Pronchery {
98*e7be843bSPierre Pronchery return x > y ? x : y;
99*e7be843bSPierre Pronchery }
100*e7be843bSPierre Pronchery
101*e7be843bSPierre Pronchery /*
102*e7be843bSPierre Pronchery * Returns 1 if there exists an integer x which falls within both ranges a and
103*e7be843bSPierre Pronchery * b.
104*e7be843bSPierre Pronchery */
uint_range_overlaps(const UINT_RANGE * a,const UINT_RANGE * b)105*e7be843bSPierre Pronchery static int uint_range_overlaps(const UINT_RANGE *a,
106*e7be843bSPierre Pronchery const UINT_RANGE *b)
107*e7be843bSPierre Pronchery {
108*e7be843bSPierre Pronchery return u64_min(a->end, b->end)
109*e7be843bSPierre Pronchery >= u64_max(a->start, b->start);
110*e7be843bSPierre Pronchery }
111*e7be843bSPierre Pronchery
create_set_item(uint64_t start,uint64_t end)112*e7be843bSPierre Pronchery static UINT_SET_ITEM *create_set_item(uint64_t start, uint64_t end)
113*e7be843bSPierre Pronchery {
114*e7be843bSPierre Pronchery UINT_SET_ITEM *x = OPENSSL_malloc(sizeof(UINT_SET_ITEM));
115*e7be843bSPierre Pronchery
116*e7be843bSPierre Pronchery if (x == NULL)
117*e7be843bSPierre Pronchery return NULL;
118*e7be843bSPierre Pronchery
119*e7be843bSPierre Pronchery ossl_list_uint_set_init_elem(x);
120*e7be843bSPierre Pronchery x->range.start = start;
121*e7be843bSPierre Pronchery x->range.end = end;
122*e7be843bSPierre Pronchery return x;
123*e7be843bSPierre Pronchery }
124*e7be843bSPierre Pronchery
ossl_uint_set_insert(UINT_SET * s,const UINT_RANGE * range)125*e7be843bSPierre Pronchery int ossl_uint_set_insert(UINT_SET *s, const UINT_RANGE *range)
126*e7be843bSPierre Pronchery {
127*e7be843bSPierre Pronchery UINT_SET_ITEM *x, *xnext, *z, *zprev, *f;
128*e7be843bSPierre Pronchery uint64_t start = range->start, end = range->end;
129*e7be843bSPierre Pronchery
130*e7be843bSPierre Pronchery if (!ossl_assert(start <= end))
131*e7be843bSPierre Pronchery return 0;
132*e7be843bSPierre Pronchery
133*e7be843bSPierre Pronchery if (ossl_list_uint_set_is_empty(s)) {
134*e7be843bSPierre Pronchery /* Nothing in the set yet, so just add this range. */
135*e7be843bSPierre Pronchery x = create_set_item(start, end);
136*e7be843bSPierre Pronchery if (x == NULL)
137*e7be843bSPierre Pronchery return 0;
138*e7be843bSPierre Pronchery ossl_list_uint_set_insert_head(s, x);
139*e7be843bSPierre Pronchery return 1;
140*e7be843bSPierre Pronchery }
141*e7be843bSPierre Pronchery
142*e7be843bSPierre Pronchery z = ossl_list_uint_set_tail(s);
143*e7be843bSPierre Pronchery if (start > z->range.end) {
144*e7be843bSPierre Pronchery /*
145*e7be843bSPierre Pronchery * Range is after the latest range in the set, so append.
146*e7be843bSPierre Pronchery *
147*e7be843bSPierre Pronchery * Note: The case where the range is before the earliest range in the
148*e7be843bSPierre Pronchery * set is handled as a degenerate case of the final case below. See
149*e7be843bSPierre Pronchery * optimization note (*) below.
150*e7be843bSPierre Pronchery */
151*e7be843bSPierre Pronchery if (z->range.end + 1 == start) {
152*e7be843bSPierre Pronchery z->range.end = end;
153*e7be843bSPierre Pronchery return 1;
154*e7be843bSPierre Pronchery }
155*e7be843bSPierre Pronchery
156*e7be843bSPierre Pronchery x = create_set_item(start, end);
157*e7be843bSPierre Pronchery if (x == NULL)
158*e7be843bSPierre Pronchery return 0;
159*e7be843bSPierre Pronchery ossl_list_uint_set_insert_tail(s, x);
160*e7be843bSPierre Pronchery return 1;
161*e7be843bSPierre Pronchery }
162*e7be843bSPierre Pronchery
163*e7be843bSPierre Pronchery f = ossl_list_uint_set_head(s);
164*e7be843bSPierre Pronchery if (start <= f->range.start && end >= z->range.end) {
165*e7be843bSPierre Pronchery /*
166*e7be843bSPierre Pronchery * New range dwarfs all ranges in our set.
167*e7be843bSPierre Pronchery *
168*e7be843bSPierre Pronchery * Free everything except the first range in the set, which we scavenge
169*e7be843bSPierre Pronchery * and reuse.
170*e7be843bSPierre Pronchery */
171*e7be843bSPierre Pronchery x = ossl_list_uint_set_head(s);
172*e7be843bSPierre Pronchery x->range.start = start;
173*e7be843bSPierre Pronchery x->range.end = end;
174*e7be843bSPierre Pronchery for (x = ossl_list_uint_set_next(x); x != NULL; x = xnext) {
175*e7be843bSPierre Pronchery xnext = ossl_list_uint_set_next(x);
176*e7be843bSPierre Pronchery ossl_list_uint_set_remove(s, x);
177*e7be843bSPierre Pronchery }
178*e7be843bSPierre Pronchery return 1;
179*e7be843bSPierre Pronchery }
180*e7be843bSPierre Pronchery
181*e7be843bSPierre Pronchery /*
182*e7be843bSPierre Pronchery * Walk backwards since we will most often be inserting at the end. As an
183*e7be843bSPierre Pronchery * optimization, test the head node first and skip iterating over the
184*e7be843bSPierre Pronchery * entire list if we are inserting at the start. The assumption is that
185*e7be843bSPierre Pronchery * insertion at the start and end of the space will be the most common
186*e7be843bSPierre Pronchery * operations. (*)
187*e7be843bSPierre Pronchery */
188*e7be843bSPierre Pronchery z = end < f->range.start ? f : z;
189*e7be843bSPierre Pronchery
190*e7be843bSPierre Pronchery for (; z != NULL; z = zprev) {
191*e7be843bSPierre Pronchery zprev = ossl_list_uint_set_prev(z);
192*e7be843bSPierre Pronchery
193*e7be843bSPierre Pronchery /* An existing range dwarfs our new range (optimisation). */
194*e7be843bSPierre Pronchery if (z->range.start <= start && z->range.end >= end)
195*e7be843bSPierre Pronchery return 1;
196*e7be843bSPierre Pronchery
197*e7be843bSPierre Pronchery if (uint_range_overlaps(&z->range, range)) {
198*e7be843bSPierre Pronchery /*
199*e7be843bSPierre Pronchery * Our new range overlaps an existing range, or possibly several
200*e7be843bSPierre Pronchery * existing ranges.
201*e7be843bSPierre Pronchery */
202*e7be843bSPierre Pronchery UINT_SET_ITEM *ovend = z;
203*e7be843bSPierre Pronchery
204*e7be843bSPierre Pronchery ovend->range.end = u64_max(end, z->range.end);
205*e7be843bSPierre Pronchery
206*e7be843bSPierre Pronchery /* Get earliest overlapping range. */
207*e7be843bSPierre Pronchery while (zprev != NULL && uint_range_overlaps(&zprev->range, range)) {
208*e7be843bSPierre Pronchery z = zprev;
209*e7be843bSPierre Pronchery zprev = ossl_list_uint_set_prev(z);
210*e7be843bSPierre Pronchery }
211*e7be843bSPierre Pronchery
212*e7be843bSPierre Pronchery ovend->range.start = u64_min(start, z->range.start);
213*e7be843bSPierre Pronchery
214*e7be843bSPierre Pronchery /* Replace sequence of nodes z..ovend with updated ovend only. */
215*e7be843bSPierre Pronchery while (z != ovend) {
216*e7be843bSPierre Pronchery z = ossl_list_uint_set_next(x = z);
217*e7be843bSPierre Pronchery ossl_list_uint_set_remove(s, x);
218*e7be843bSPierre Pronchery OPENSSL_free(x);
219*e7be843bSPierre Pronchery }
220*e7be843bSPierre Pronchery break;
221*e7be843bSPierre Pronchery } else if (end < z->range.start
222*e7be843bSPierre Pronchery && (zprev == NULL || start > zprev->range.end)) {
223*e7be843bSPierre Pronchery if (z->range.start == end + 1) {
224*e7be843bSPierre Pronchery /* We can extend the following range backwards. */
225*e7be843bSPierre Pronchery z->range.start = start;
226*e7be843bSPierre Pronchery
227*e7be843bSPierre Pronchery /*
228*e7be843bSPierre Pronchery * If this closes a gap we now need to merge
229*e7be843bSPierre Pronchery * consecutive nodes.
230*e7be843bSPierre Pronchery */
231*e7be843bSPierre Pronchery uint_set_merge_adjacent(s, z);
232*e7be843bSPierre Pronchery } else if (zprev != NULL && zprev->range.end + 1 == start) {
233*e7be843bSPierre Pronchery /* We can extend the preceding range forwards. */
234*e7be843bSPierre Pronchery zprev->range.end = end;
235*e7be843bSPierre Pronchery
236*e7be843bSPierre Pronchery /*
237*e7be843bSPierre Pronchery * If this closes a gap we now need to merge
238*e7be843bSPierre Pronchery * consecutive nodes.
239*e7be843bSPierre Pronchery */
240*e7be843bSPierre Pronchery uint_set_merge_adjacent(s, z);
241*e7be843bSPierre Pronchery } else {
242*e7be843bSPierre Pronchery /*
243*e7be843bSPierre Pronchery * The new interval is between intervals without overlapping or
244*e7be843bSPierre Pronchery * touching them, so insert between, preserving sort.
245*e7be843bSPierre Pronchery */
246*e7be843bSPierre Pronchery x = create_set_item(start, end);
247*e7be843bSPierre Pronchery if (x == NULL)
248*e7be843bSPierre Pronchery return 0;
249*e7be843bSPierre Pronchery ossl_list_uint_set_insert_before(s, z, x);
250*e7be843bSPierre Pronchery }
251*e7be843bSPierre Pronchery break;
252*e7be843bSPierre Pronchery }
253*e7be843bSPierre Pronchery }
254*e7be843bSPierre Pronchery
255*e7be843bSPierre Pronchery return 1;
256*e7be843bSPierre Pronchery }
257*e7be843bSPierre Pronchery
ossl_uint_set_remove(UINT_SET * s,const UINT_RANGE * range)258*e7be843bSPierre Pronchery int ossl_uint_set_remove(UINT_SET *s, const UINT_RANGE *range)
259*e7be843bSPierre Pronchery {
260*e7be843bSPierre Pronchery UINT_SET_ITEM *z, *zprev, *y;
261*e7be843bSPierre Pronchery uint64_t start = range->start, end = range->end;
262*e7be843bSPierre Pronchery
263*e7be843bSPierre Pronchery if (!ossl_assert(start <= end))
264*e7be843bSPierre Pronchery return 0;
265*e7be843bSPierre Pronchery
266*e7be843bSPierre Pronchery /* Walk backwards since we will most often be removing at the end. */
267*e7be843bSPierre Pronchery for (z = ossl_list_uint_set_tail(s); z != NULL; z = zprev) {
268*e7be843bSPierre Pronchery zprev = ossl_list_uint_set_prev(z);
269*e7be843bSPierre Pronchery
270*e7be843bSPierre Pronchery if (start > z->range.end)
271*e7be843bSPierre Pronchery /* No overlapping ranges can exist beyond this point, so stop. */
272*e7be843bSPierre Pronchery break;
273*e7be843bSPierre Pronchery
274*e7be843bSPierre Pronchery if (start <= z->range.start && end >= z->range.end) {
275*e7be843bSPierre Pronchery /*
276*e7be843bSPierre Pronchery * The range being removed dwarfs this range, so it should be
277*e7be843bSPierre Pronchery * removed.
278*e7be843bSPierre Pronchery */
279*e7be843bSPierre Pronchery ossl_list_uint_set_remove(s, z);
280*e7be843bSPierre Pronchery OPENSSL_free(z);
281*e7be843bSPierre Pronchery } else if (start <= z->range.start && end >= z->range.start) {
282*e7be843bSPierre Pronchery /*
283*e7be843bSPierre Pronchery * The range being removed includes start of this range, but does
284*e7be843bSPierre Pronchery * not cover the entire range (as this would be caught by the case
285*e7be843bSPierre Pronchery * above). Shorten the range.
286*e7be843bSPierre Pronchery */
287*e7be843bSPierre Pronchery assert(end < z->range.end);
288*e7be843bSPierre Pronchery z->range.start = end + 1;
289*e7be843bSPierre Pronchery } else if (end >= z->range.end) {
290*e7be843bSPierre Pronchery /*
291*e7be843bSPierre Pronchery * The range being removed includes the end of this range, but does
292*e7be843bSPierre Pronchery * not cover the entire range (as this would be caught by the case
293*e7be843bSPierre Pronchery * above). Shorten the range. We can also stop iterating.
294*e7be843bSPierre Pronchery */
295*e7be843bSPierre Pronchery assert(start > z->range.start);
296*e7be843bSPierre Pronchery assert(start > 0);
297*e7be843bSPierre Pronchery z->range.end = start - 1;
298*e7be843bSPierre Pronchery break;
299*e7be843bSPierre Pronchery } else if (start > z->range.start && end < z->range.end) {
300*e7be843bSPierre Pronchery /*
301*e7be843bSPierre Pronchery * The range being removed falls entirely in this range, so cut it
302*e7be843bSPierre Pronchery * into two. Cases where a zero-length range would be created are
303*e7be843bSPierre Pronchery * handled by the above cases.
304*e7be843bSPierre Pronchery */
305*e7be843bSPierre Pronchery y = create_set_item(end + 1, z->range.end);
306*e7be843bSPierre Pronchery ossl_list_uint_set_insert_after(s, z, y);
307*e7be843bSPierre Pronchery z->range.end = start - 1;
308*e7be843bSPierre Pronchery break;
309*e7be843bSPierre Pronchery } else {
310*e7be843bSPierre Pronchery /* Assert no partial overlap; all cases should be covered above. */
311*e7be843bSPierre Pronchery assert(!uint_range_overlaps(&z->range, range));
312*e7be843bSPierre Pronchery }
313*e7be843bSPierre Pronchery }
314*e7be843bSPierre Pronchery
315*e7be843bSPierre Pronchery return 1;
316*e7be843bSPierre Pronchery }
317*e7be843bSPierre Pronchery
ossl_uint_set_query(const UINT_SET * s,uint64_t v)318*e7be843bSPierre Pronchery int ossl_uint_set_query(const UINT_SET *s, uint64_t v)
319*e7be843bSPierre Pronchery {
320*e7be843bSPierre Pronchery UINT_SET_ITEM *x;
321*e7be843bSPierre Pronchery
322*e7be843bSPierre Pronchery if (ossl_list_uint_set_is_empty(s))
323*e7be843bSPierre Pronchery return 0;
324*e7be843bSPierre Pronchery
325*e7be843bSPierre Pronchery for (x = ossl_list_uint_set_tail(s); x != NULL; x = ossl_list_uint_set_prev(x))
326*e7be843bSPierre Pronchery if (x->range.start <= v && x->range.end >= v)
327*e7be843bSPierre Pronchery return 1;
328*e7be843bSPierre Pronchery else if (x->range.end < v)
329*e7be843bSPierre Pronchery return 0;
330*e7be843bSPierre Pronchery
331*e7be843bSPierre Pronchery return 0;
332*e7be843bSPierre Pronchery }
333