2  * Copyright 2022-2023 The OpenSSL Project Authors. All Rights Reserved.
83     if (x->range.start - 1 != xprev->range.end)  in uint_set_merge_adjacent()
86     x->range.start = xprev->range.start;  in uint_set_merge_adjacent()
108     return u64_min(a->end, b->end)  in uint_range_overlaps()
109         >= u64_max(a->start, b->start);  in uint_range_overlaps()
120     x->range.start = start;  in create_set_item()
121     x->range.end   = end;  in create_set_item()
127     UINT_SET_ITEM *x, *xnext, *z, *zprev, *f;  in ossl_uint_set_insert()  local
128     uint64_t start = range->start, end = range->end;  in ossl_uint_set_insert()
142     z = ossl_list_uint_set_tail(s);  in ossl_uint_set_insert()
143     if (start > z->range.end) {  in ossl_uint_set_insert()
151         if (z->range.end + 1 == start) {  in ossl_uint_set_insert()
152             z->range.end = end;  in ossl_uint_set_insert()
164     if (start <= f->range.start && end >= z->range.end) {  in ossl_uint_set_insert()
172         x->range.start = start;  in ossl_uint_set_insert()
173         x->range.end = end;  in ossl_uint_set_insert()
188     z = end < f->range.start ? f : z;  in ossl_uint_set_insert()
190     for (; z != NULL; z = zprev) {  in ossl_uint_set_insert()
191         zprev = ossl_list_uint_set_prev(z);  in ossl_uint_set_insert()
194         if (z->range.start <= start && z->range.end >= end)  in ossl_uint_set_insert()
197         if (uint_range_overlaps(&z->range, range)) {  in ossl_uint_set_insert()
202             UINT_SET_ITEM *ovend = z;  in ossl_uint_set_insert()
204             ovend->range.end = u64_max(end, z->range.end);  in ossl_uint_set_insert()
207             while (zprev != NULL && uint_range_overlaps(&zprev->range, range)) {  in ossl_uint_set_insert()
208                 z = zprev;  in ossl_uint_set_insert()
209                 zprev = ossl_list_uint_set_prev(z);  in ossl_uint_set_insert()
212             ovend->range.start = u64_min(start, z->range.start);  in ossl_uint_set_insert()
214             /* Replace sequence of nodes z..ovend with updated ovend only. */  in ossl_uint_set_insert()
215             while (z != ovend) {  in ossl_uint_set_insert()
216                 z = ossl_list_uint_set_next(x = z);  in ossl_uint_set_insert()
221         } else if (end < z->range.start  in ossl_uint_set_insert()
222                     && (zprev == NULL || start > zprev->range.end)) {  in ossl_uint_set_insert()
223             if (z->range.start == end + 1) {  in ossl_uint_set_insert()
225                 z->range.start = start;  in ossl_uint_set_insert()
231                 uint_set_merge_adjacent(s, z);  in ossl_uint_set_insert()
232             } else if (zprev != NULL && zprev->range.end + 1 == start) {  in ossl_uint_set_insert()
234                 zprev->range.end = end;  in ossl_uint_set_insert()
240                 uint_set_merge_adjacent(s, z);  in ossl_uint_set_insert()
249                 ossl_list_uint_set_insert_before(s, z, x);  in ossl_uint_set_insert()
260     UINT_SET_ITEM *z, *zprev, *y;  in ossl_uint_set_remove()  local
261     uint64_t start = range->start, end = range->end;  in ossl_uint_set_remove()
267     for (z = ossl_list_uint_set_tail(s); z != NULL; z = zprev) {  in ossl_uint_set_remove()
268         zprev = ossl_list_uint_set_prev(z);  in ossl_uint_set_remove()
270         if (start > z->range.end)  in ossl_uint_set_remove()
274         if (start <= z->range.start && end >= z->range.end) {  in ossl_uint_set_remove()
279             ossl_list_uint_set_remove(s, z);  in ossl_uint_set_remove()
280             OPENSSL_free(z);  in ossl_uint_set_remove()
281         } else if (start <= z->range.start && end >= z->range.start) {  in ossl_uint_set_remove()
287             assert(end < z->range.end);  in ossl_uint_set_remove()
288             z->range.start = end + 1;  in ossl_uint_set_remove()
289         } else if (end >= z->range.end) {  in ossl_uint_set_remove()
295             assert(start > z->range.start);  in ossl_uint_set_remove()
297             z->range.end = start - 1;  in ossl_uint_set_remove()
299         } else if (start > z->range.start && end < z->range.end) {  in ossl_uint_set_remove()
302              * into two. Cases where a zero-length range would be created are  in ossl_uint_set_remove()
305             y = create_set_item(end + 1, z->range.end);  in ossl_uint_set_remove()
306             ossl_list_uint_set_insert_after(s, z, y);  in ossl_uint_set_remove()
307             z->range.end = start - 1;  in ossl_uint_set_remove()
311             assert(!uint_range_overlaps(&z->range, range));  in ossl_uint_set_remove()
326         if (x->range.start <= v && x->range.end >= v)  in ossl_uint_set_query()
328         else if (x->range.end < v)  in ossl_uint_set_query()