From c5ca718003e69ea0ef98392ce0abd4b6bfedeac8 Mon Sep 17 00:00:00 2001 From: Pauli Date: Tue, 11 Oct 2022 18:41:04 +1100 Subject: uint_set: convert uint_set to use the list data type This is instead of re-implementing a linked list itself. Reviewed-by: Tim Hudson Reviewed-by: Shane Lontis (Merged from https://github.com/openssl/openssl/pull/19377) --- ssl/quic/uint_set.c | 180 +++++++++++++++++++--------------------------------- 1 file changed, 64 insertions(+), 116 deletions(-) (limited to 'ssl/quic/uint_set.c') diff --git a/ssl/quic/uint_set.c b/ssl/quic/uint_set.c index bfa8e3f93f..9d0440b423 100644 --- a/ssl/quic/uint_set.c +++ b/ssl/quic/uint_set.c @@ -59,24 +59,23 @@ */ void ossl_uint_set_init(UINT_SET *s) { - s->head = s->tail = NULL; - s->num_ranges = 0; + ossl_list_uint_set_init(s); } void ossl_uint_set_destroy(UINT_SET *s) { UINT_SET_ITEM *x, *xnext; - for (x = s->head; x != NULL; x = xnext) { - xnext = x->next; + for (x = ossl_list_uint_set_head(s); x != NULL; x = xnext) { + xnext = ossl_list_uint_set_next(x); OPENSSL_free(x); } } -/* Possible merge of x, x->prev */ +/* Possible merge of x, prev(x) */ static void uint_set_merge_adjacent(UINT_SET *s, UINT_SET_ITEM *x) { - UINT_SET_ITEM *xprev = x->prev; + UINT_SET_ITEM *xprev = ossl_list_uint_set_prev(x); if (xprev == NULL) return; @@ -85,15 +84,8 @@ static void uint_set_merge_adjacent(UINT_SET *s, UINT_SET_ITEM *x) return; x->range.start = xprev->range.start; - x->prev = xprev->prev; - if (x->prev != NULL) - x->prev->next = x; - - if (s->head == xprev) - s->head = x; - + ossl_list_uint_set_remove(s, xprev); OPENSSL_free(xprev); - --s->num_ranges; } static uint64_t u64_min(uint64_t x, uint64_t y) @@ -117,28 +109,37 @@ static int uint_range_overlaps(const UINT_RANGE *a, >= u64_max(a->start, b->start); } +static UINT_SET_ITEM *create_set_item(uint64_t start, uint64_t end) +{ + UINT_SET_ITEM *x = OPENSSL_malloc(sizeof(UINT_SET_ITEM)); + + ossl_list_uint_set_init_elem(x); + if (x != NULL) { + x->range.start = start; + x->range.end = end; + } + return x; +} + int ossl_uint_set_insert(UINT_SET *s, const UINT_RANGE *range) { - UINT_SET_ITEM *x, *z, *xnext, *f, *fnext; + UINT_SET_ITEM *x, *xnext, *z, *zprev, *f; uint64_t start = range->start, end = range->end; if (!ossl_assert(start <= end)) return 0; - if (s->head == NULL) { + if (ossl_list_uint_set_is_empty(s)) { /* Nothing in the set yet, so just add this range. */ - x = OPENSSL_zalloc(sizeof(UINT_SET_ITEM)); + x = create_set_item(start, end); if (x == NULL) return 0; - - x->range.start = start; - x->range.end = end; - s->head = s->tail = x; - ++s->num_ranges; + ossl_list_uint_set_insert_head(s, x); return 1; } - if (start > s->tail->range.end) { + z = ossl_list_uint_set_tail(s); + if (start > z->range.end) { /* * Range is after the latest range in the set, so append. * @@ -146,42 +147,33 @@ int ossl_uint_set_insert(UINT_SET *s, const UINT_RANGE *range) * set is handled as a degenerate case of the final case below. See * optimization note (*) below. */ - if (s->tail->range.end + 1 == start) { - s->tail->range.end = end; + if (z->range.end + 1 == start) { + z->range.end = end; return 1; } - x = OPENSSL_zalloc(sizeof(UINT_SET_ITEM)); + x = create_set_item(start, end); if (x == NULL) return 0; - - x->range.start = start; - x->range.end = end; - x->prev = s->tail; - if (s->tail != NULL) - s->tail->next = x; - s->tail = x; - ++s->num_ranges; + ossl_list_uint_set_insert_tail(s, x); return 1; } - if (start <= s->head->range.start && end >= s->tail->range.end) { + f = ossl_list_uint_set_head(s); + if (start <= f->range.start && end >= z->range.end) { /* * New range dwarfs all ranges in our set. * * Free everything except the first range in the set, which we scavenge * and reuse. */ - for (x = s->head->next; x != NULL; x = xnext) { - xnext = x->next; - OPENSSL_free(x); + x = ossl_list_uint_set_head(s); + x->range.start = start; + x->range.end = end; + for (x = ossl_list_uint_set_next(x); x != NULL; x = xnext) { + xnext = ossl_list_uint_set_next(x); + ossl_list_uint_set_remove(s, x); } - - s->head->range.start = start; - s->head->range.end = end; - s->head->next = s->head->prev = NULL; - s->tail = s->head; - s->num_ranges = 1; return 1; } @@ -192,9 +184,11 @@ int ossl_uint_set_insert(UINT_SET *s, const UINT_RANGE *range) * insertion at the start and end of the space will be the most common * operations. (*) */ - z = end < s->head->range.start ? s->head : s->tail; + z = end < f->range.start ? f : z; + + for (; z != NULL; z = zprev) { + zprev = ossl_list_uint_set_prev(z); - for (; z != NULL; z = z->prev) { /* An existing range dwarfs our new range (optimisation). */ if (z->range.start <= start && z->range.end >= end) return 1; @@ -205,35 +199,26 @@ int ossl_uint_set_insert(UINT_SET *s, const UINT_RANGE *range) * existing ranges. */ UINT_SET_ITEM *ovend = z; - UINT_RANGE t; - size_t n = 0; - t.end = u64_max(end, z->range.end); + ovend->range.end = u64_max(end, z->range.end); /* Get earliest overlapping range. */ - for (; z->prev != NULL && uint_range_overlaps(&z->prev->range, range); - z = z->prev); - - t.start = u64_min(start, z->range.start); - - /* Replace sequence of nodes z..ovend with ovend only. */ - ovend->range = t; - ovend->prev = z->prev; - if (z->prev != NULL) - z->prev->next = ovend; - if (s->head == z) - s->head = ovend; - - /* Free now unused nodes. */ - for (f = z; f != ovend; f = fnext, ++n) { - fnext = f->next; - OPENSSL_free(f); + while (zprev != NULL && uint_range_overlaps(&zprev->range, range)) { + z = zprev; + zprev = ossl_list_uint_set_prev(z); } - s->num_ranges -= n; + ovend->range.start = u64_min(start, z->range.start); + + /* Replace sequence of nodes z..ovend with updated ovend only. */ + while (z != ovend) { + z = ossl_list_uint_set_next(x = z); + ossl_list_uint_set_remove(s, x); + OPENSSL_free(x); + } break; } else if (end < z->range.start - && (z->prev == NULL || start > z->prev->range.end)) { + && (zprev == NULL || start > zprev->range.end)) { if (z->range.start == end + 1) { /* We can extend the following range backwards. */ z->range.start = start; @@ -243,9 +228,9 @@ int ossl_uint_set_insert(UINT_SET *s, const UINT_RANGE *range) * consecutive nodes. */ uint_set_merge_adjacent(s, z); - } else if (z->prev != NULL && z->prev->range.end + 1 == start) { + } else if (zprev != NULL && zprev->range.end + 1 == start) { /* We can extend the preceding range forwards. */ - z->prev->range.end = end; + zprev->range.end = end; /* * If this closes a gap we now need to merge @@ -257,22 +242,10 @@ int ossl_uint_set_insert(UINT_SET *s, const UINT_RANGE *range) * The new interval is between intervals without overlapping or * touching them, so insert between, preserving sort. */ - x = OPENSSL_zalloc(sizeof(UINT_SET_ITEM)); + x = create_set_item(start, end); if (x == NULL) return 0; - - x->range.start = start; - x->range.end = end; - - x->next = z; - x->prev = z->prev; - if (x->prev != NULL) - x->prev->next = x; - z->prev = x; - if (s->head == z) - s->head = x; - - ++s->num_ranges; + ossl_list_uint_set_insert_before(s, z, x); } break; } @@ -290,8 +263,8 @@ int ossl_uint_set_remove(UINT_SET *s, const UINT_RANGE *range) return 0; /* Walk backwards since we will most often be removing at the end. */ - for (z = s->tail; z != NULL; z = zprev) { - zprev = z->prev; + for (z = ossl_list_uint_set_tail(s); z != NULL; z = zprev) { + zprev = ossl_list_uint_set_prev(z); if (start > z->range.end) /* No overlapping ranges can exist beyond this point, so stop. */ @@ -302,17 +275,8 @@ int ossl_uint_set_remove(UINT_SET *s, const UINT_RANGE *range) * The range being removed dwarfs this range, so it should be * removed. */ - if (z->next != NULL) - z->next->prev = z->prev; - if (z->prev != NULL) - z->prev->next = z->next; - if (s->head == z) - s->head = z->next; - if (s->tail == z) - s->tail = z->prev; - + ossl_list_uint_set_remove(s, z); OPENSSL_free(z); - --s->num_ranges; } else if (start <= z->range.start) { /* * The range being removed includes start of this range, but does @@ -337,24 +301,8 @@ int ossl_uint_set_remove(UINT_SET *s, const UINT_RANGE *range) * into two. Cases where a zero-length range would be created are * handled by the above cases. */ - y = OPENSSL_zalloc(sizeof(UINT_SET_ITEM)); - if (y == NULL) - return 0; - - y->range.end = z->range.end; - y->range.start = end + 1; - y->next = z->next; - y->prev = z; - if (y->next != NULL) - y->next->prev = y; - - z->range.end = start - 1; - z->next = y; - - if (s->tail == z) - s->tail = y; - - ++s->num_ranges; + y = create_set_item(end + 1, z->range.end); + ossl_list_uint_set_insert_after(s, z, y); break; } else { /* Assert no partial overlap; all cases should be covered above. */ @@ -369,10 +317,10 @@ int ossl_uint_set_query(const UINT_SET *s, uint64_t v) { UINT_SET_ITEM *x; - if (s->head == NULL) + if (ossl_list_uint_set_is_empty(s)) return 0; - for (x = s->tail; x != NULL; x = x->prev) + for (x = ossl_list_uint_set_tail(s); x != NULL; x = ossl_list_uint_set_prev(x)) if (x->range.start <= v && x->range.end >= v) return 1; else if (x->range.end < v) -- cgit v1.2.3