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