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 <tjh@openssl.org>
Reviewed-by: Shane Lontis <shane.lontis@oracle.com>
(Merged from https://github.com/openssl/openssl/pull/19377)

1 files changed, 64 insertions, 116 deletions

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)