20  *   Insert Range: Adds an inclusive range of integers [start, end]
22  *                 in the range.
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.
35  * implemented as a doubly linked sorted list of range structures, which are
44  * end of the range.
54  * Invariant: No range [a, b] ever has a > b.
56  * Invariant: Since ranges are represented using inclusive bounds, no range
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()
120     x->range.start = start;  in create_set_item()
121     x->range.end   = end;  in create_set_item()
125 int ossl_uint_set_insert(UINT_SET *s, const UINT_RANGE *range)  in ossl_uint_set_insert()  argument
128     uint64_t start = range->start, end = range->end;  in ossl_uint_set_insert()
134         /* Nothing in the set yet, so just add this range. */  in ossl_uint_set_insert()
143     if (start > z->range.end) {  in ossl_uint_set_insert()
145          * Range is after the latest range in the set, so append.  in ossl_uint_set_insert()
147          * Note: The case where the range is before the earliest range in the  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()
166          * New range dwarfs all ranges in our set.  in ossl_uint_set_insert()
168          * Free everything except the first range in the set, which we scavenge  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()
193         /* An existing range dwarfs our new range (optimisation). */  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()
199              * Our new range overlaps an existing range, or possibly several  in ossl_uint_set_insert()
204             ovend->range.end = u64_max(end, z->range.end);  in ossl_uint_set_insert()
206             /* Get earliest overlapping range. */  in ossl_uint_set_insert()
207             while (zprev != NULL && uint_range_overlaps(&zprev->range, range)) {  in ossl_uint_set_insert()
212             ovend->range.start = u64_min(start, z->range.start);  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()
224                 /* We can extend the following range backwards. */  in ossl_uint_set_insert()
225                 z->range.start = start;  in ossl_uint_set_insert()
232             } else if (zprev != NULL && zprev->range.end + 1 == start) {  in ossl_uint_set_insert()
233                 /* We can extend the preceding range forwards. */  in ossl_uint_set_insert()
234                 zprev->range.end = end;  in ossl_uint_set_insert()
258 int ossl_uint_set_remove(UINT_SET *s, const UINT_RANGE *range)  in ossl_uint_set_remove()  argument
261     uint64_t start = range->start, end = range->end;  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()
276              * The range being removed dwarfs this range, so it should be  in ossl_uint_set_remove()
281         } else if (start <= z->range.start && end >= z->range.start) {  in ossl_uint_set_remove()
283              * The range being removed includes start of this range, but does  in ossl_uint_set_remove()
284              * not cover the entire range (as this would be caught by the case  in ossl_uint_set_remove()
285              * above). Shorten the range.  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()
291              * The range being removed includes the end of this range, but does  in ossl_uint_set_remove()
292              * not cover the entire range (as this would be caught by the case  in ossl_uint_set_remove()
293              * above). Shorten the range. We can also stop iterating.  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()
301              * The range being removed falls entirely in this range, so cut it  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()
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()