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 */ 60 void ossl_uint_set_init(UINT_SET *s) 61 { 62 ossl_list_uint_set_init(s); 63 } 64 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) */ 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 91 static uint64_t u64_min(uint64_t x, uint64_t y) 92 { 93 return x < y ? x : y; 94 } 95 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 */ 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 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 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 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 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