ssl/quic/uint_set.c - third_party/openssl - Git at Google

 /*
  * Copyright 2022-2023 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
  * in the file LICENSE in the source distribution or at
  * https://www.openssl.org/source/license.html
  */

 #include "internal/uint_set.h"
 #include "internal/common.h"
 #include <assert.h>

 /*
  * uint64_t Integer Sets
  * =====================
  *
  * This data structure supports the following operations:
  *
  *   Insert Range: Adds an inclusive range of integers [start, end]
  *                 to the set. Equivalent to Insert for each number
  *                 in the range.
  *
  *   Remove Range: Removes an inclusive range of integers [start, end]
  *                 from the set. Not all of the range need already be in
  *                 the set, but any part of the range in the set is removed.
  *
  *   Query:        Is an integer in the data structure?
  *
  * The data structure can be iterated.
  *
  * For greater efficiency in tracking large numbers of contiguous integers, we
  * track integer ranges rather than individual integers. The data structure
  * manages a list of integer ranges [[start, end]...]. Internally this is
  * implemented as a doubly linked sorted list of range structures, which are
  * automatically split and merged as necessary.
  *
  * This data structure requires O(n) traversal of the list for insertion,
  * removal and query when we are not adding/removing ranges which are near the
  * beginning or end of the set of ranges. For the applications for which this
  * data structure is used (e.g. QUIC PN tracking for ACK generation), it is
  * expected that the number of integer ranges needed at any given time will
  * generally be small and that most operations will be close to the beginning or
  * end of the range.
  *
  * Invariant: The data structure is always sorted in ascending order by value.
  *
  * Invariant: No two adjacent ranges ever 'border' one another (have no
  *            numerical gap between them) as the data structure always ensures
  *            such ranges are merged.
  *
  * Invariant: No two ranges ever overlap.
  *
  * Invariant: No range [a, b] ever has a > b.
  *
  * Invariant: Since ranges are represented using inclusive bounds, no range
  *            item inside the data structure can represent a span of zero
  *            integers.
  */
 void ossl_uint_set_init(UINT_SET *s)
 {
     ossl_list_uint_set_init(s);
 }

 void ossl_uint_set_destroy(UINT_SET *s)
 {
     UINT_SET_ITEM *x, *xnext;

     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, prev(x) */
 static void uint_set_merge_adjacent(UINT_SET *s, UINT_SET_ITEM *x)
 {
     UINT_SET_ITEM *xprev = ossl_list_uint_set_prev(x);

     if (xprev == NULL)
         return;

     if (x->range.start - 1 != xprev->range.end)
         return;

     x->range.start = xprev->range.start;
     ossl_list_uint_set_remove(s, xprev);
     OPENSSL_free(xprev);
 }

 static uint64_t u64_min(uint64_t x, uint64_t y)
 {
     return x < y ? x : y;
 }

 static uint64_t u64_max(uint64_t x, uint64_t y)
 {
     return x > y ? x : y;
 }

 /*
  * Returns 1 if there exists an integer x which falls within both ranges a and
  * b.
  */
 static int uint_range_overlaps(const UINT_RANGE *a,
                                const UINT_RANGE *b)
 {
     return u64_min(a->end, b->end)
         >= 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));

     if (x == NULL)
         return NULL;

     ossl_list_uint_set_init_elem(x);
     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, *xnext, *z, *zprev, *f;
     uint64_t start = range->start, end = range->end;

     if (!ossl_assert(start <= end))
         return 0;

     if (ossl_list_uint_set_is_empty(s)) {
         /* Nothing in the set yet, so just add this range. */
         x = create_set_item(start, end);
         if (x == NULL)
             return 0;
         ossl_list_uint_set_insert_head(s, x);
         return 1;
     }

     z = ossl_list_uint_set_tail(s);
     if (start > z->range.end) {
         /*
          * Range is after the latest range in the set, so append.
          *
          * Note: The case where the range is before the earliest range in the
          * set is handled as a degenerate case of the final case below. See
          * optimization note (*) below.
          */
         if (z->range.end + 1 == start) {
             z->range.end = end;
             return 1;
         }

         x = create_set_item(start, end);
         if (x == NULL)
             return 0;
         ossl_list_uint_set_insert_tail(s, x);
         return 1;
     }

     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.
          */
         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);
         }
         return 1;
     }

     /*
      * Walk backwards since we will most often be inserting at the end. As an
      * optimization, test the head node first and skip iterating over the
      * entire list if we are inserting at the start. The assumption is that
      * insertion at the start and end of the space will be the most common
      * operations. (*)
      */
     z = end < f->range.start ? f : z;

     for (; z != NULL; z = zprev) {
         zprev = ossl_list_uint_set_prev(z);

         /* An existing range dwarfs our new range (optimisation). */
         if (z->range.start <= start && z->range.end >= end)
             return 1;

         if (uint_range_overlaps(&z->range, range)) {
             /*
              * Our new range overlaps an existing range, or possibly several
              * existing ranges.
              */
             UINT_SET_ITEM *ovend = z;

             ovend->range.end = u64_max(end, z->range.end);

             /* Get earliest overlapping range. */
             while (zprev != NULL && uint_range_overlaps(&zprev->range, range)) {
                 z = zprev;
                 zprev = ossl_list_uint_set_prev(z);
             }

             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
                     && (zprev == NULL || start > zprev->range.end)) {
             if (z->range.start == end + 1) {
                 /* We can extend the following range backwards. */
                 z->range.start = start;

                 /*
                  * If this closes a gap we now need to merge
                  * consecutive nodes.
                  */
                 uint_set_merge_adjacent(s, z);
             } else if (zprev != NULL && zprev->range.end + 1 == start) {
                 /* We can extend the preceding range forwards. */
                 zprev->range.end = end;

                 /*
                  * If this closes a gap we now need to merge
                  * consecutive nodes.
                  */
                 uint_set_merge_adjacent(s, z);
             } else {
                 /*
                  * The new interval is between intervals without overlapping or
                  * touching them, so insert between, preserving sort.
                  */
                 x = create_set_item(start, end);
                 if (x == NULL)
                     return 0;
                 ossl_list_uint_set_insert_before(s, z, x);
             }
             break;
         }
     }

     return 1;
 }

 int ossl_uint_set_remove(UINT_SET *s, const UINT_RANGE *range)
 {
     UINT_SET_ITEM *z, *zprev, *y;
     uint64_t start = range->start, end = range->end;

     if (!ossl_assert(start <= end))
         return 0;

     /* Walk backwards since we will most often be removing at the end. */
     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. */
             break;

         if (start <= z->range.start && end >= z->range.end) {
             /*
              * The range being removed dwarfs this range, so it should be
              * removed.
              */
             ossl_list_uint_set_remove(s, z);
             OPENSSL_free(z);
         } else if (start <= z->range.start && end >= z->range.start) {
             /*
              * The range being removed includes start of this range, but does
              * not cover the entire range (as this would be caught by the case
              * above). Shorten the range.
              */
             assert(end < z->range.end);
             z->range.start = end + 1;
         } else if (end >= z->range.end) {
             /*
              * The range being removed includes the end of this range, but does
              * not cover the entire range (as this would be caught by the case
              * above). Shorten the range. We can also stop iterating.
              */
             assert(start > z->range.start);
             assert(start > 0);
             z->range.end = start - 1;
             break;
         } else if (start > z->range.start && end < z->range.end) {
             /*
              * The range being removed falls entirely in this range, so cut it
              * into two. Cases where a zero-length range would be created are
              * handled by the above cases.
              */
             y = create_set_item(end + 1, z->range.end);
             ossl_list_uint_set_insert_after(s, z, y);
             z->range.end = start - 1;
             break;
         } else {
             /* Assert no partial overlap; all cases should be covered above. */
             assert(!uint_range_overlaps(&z->range, range));
         }
     }

     return 1;
 }

 int ossl_uint_set_query(const UINT_SET *s, uint64_t v)
 {
     UINT_SET_ITEM *x;

     if (ossl_list_uint_set_is_empty(s))
         return 0;

     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)
             return 0;

     return 0;
 }
	/*
	* Copyright 2022-2023 The OpenSSL Project Authors. All Rights Reserved.
	*
	* Licensed under the Apache License 2.0 (the "License"). You may not use
	* this file except in compliance with the License. You can obtain a copy
	* in the file LICENSE in the source distribution or at
	* https://www.openssl.org/source/license.html
	*/

	#include "internal/uint_set.h"
	#include "internal/common.h"
	#include <assert.h>

	/*
	* uint64_t Integer Sets
	* =====================
	*
	* This data structure supports the following operations:
	*
	* Insert Range: Adds an inclusive range of integers [start, end]
	* to the set. Equivalent to Insert for each number
	* in the range.
	*
	* Remove Range: Removes an inclusive range of integers [start, end]
	* from the set. Not all of the range need already be in
	* the set, but any part of the range in the set is removed.
	*
	* Query: Is an integer in the data structure?
	*
	* The data structure can be iterated.
	*
	* For greater efficiency in tracking large numbers of contiguous integers, we
	* track integer ranges rather than individual integers. The data structure
	* manages a list of integer ranges [[start, end]...]. Internally this is
	* implemented as a doubly linked sorted list of range structures, which are
	* automatically split and merged as necessary.
	*
	* This data structure requires O(n) traversal of the list for insertion,
	* removal and query when we are not adding/removing ranges which are near the
	* beginning or end of the set of ranges. For the applications for which this
	* data structure is used (e.g. QUIC PN tracking for ACK generation), it is
	* expected that the number of integer ranges needed at any given time will
	* generally be small and that most operations will be close to the beginning or
	* end of the range.
	*
	* Invariant: The data structure is always sorted in ascending order by value.
	*
	* Invariant: No two adjacent ranges ever 'border' one another (have no
	* numerical gap between them) as the data structure always ensures
	* such ranges are merged.
	*
	* Invariant: No two ranges ever overlap.
	*
	* Invariant: No range [a, b] ever has a > b.
	*
	* Invariant: Since ranges are represented using inclusive bounds, no range
	* item inside the data structure can represent a span of zero
	* integers.
	*/
	void ossl_uint_set_init(UINT_SET *s)
	{
	ossl_list_uint_set_init(s);
	}

	void ossl_uint_set_destroy(UINT_SET *s)
	{
	UINT_SET_ITEM x, xnext;

	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, prev(x) */
	static void uint_set_merge_adjacent(UINT_SET s, UINT_SET_ITEM x)
	{
	UINT_SET_ITEM *xprev = ossl_list_uint_set_prev(x);

	if (xprev == NULL)
	return;

	if (x->range.start - 1 != xprev->range.end)
	return;

	x->range.start = xprev->range.start;
	ossl_list_uint_set_remove(s, xprev);
	OPENSSL_free(xprev);
	}

	static uint64_t u64_min(uint64_t x, uint64_t y)
	{
	return x < y ? x : y;
	}

	static uint64_t u64_max(uint64_t x, uint64_t y)
	{
	return x > y ? x : y;
	}

	/*
	* Returns 1 if there exists an integer x which falls within both ranges a and
	* b.
	*/
	static int uint_range_overlaps(const UINT_RANGE *a,
	const UINT_RANGE *b)
	{
	return u64_min(a->end, b->end)
	>= 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));

	if (x == NULL)
	return NULL;

	ossl_list_uint_set_init_elem(x);
	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, xnext, z, zprev, *f;
	uint64_t start = range->start, end = range->end;

	if (!ossl_assert(start <= end))
	return 0;

	if (ossl_list_uint_set_is_empty(s)) {
	/* Nothing in the set yet, so just add this range. */
	x = create_set_item(start, end);
	if (x == NULL)
	return 0;
	ossl_list_uint_set_insert_head(s, x);
	return 1;
	}

	z = ossl_list_uint_set_tail(s);
	if (start > z->range.end) {
	/*
	* Range is after the latest range in the set, so append.
	*
	* Note: The case where the range is before the earliest range in the
	* set is handled as a degenerate case of the final case below. See
	* optimization note (*) below.
	*/
	if (z->range.end + 1 == start) {
	z->range.end = end;
	return 1;
	}

	x = create_set_item(start, end);
	if (x == NULL)
	return 0;
	ossl_list_uint_set_insert_tail(s, x);
	return 1;
	}

	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.
	*/
	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);
	}
	return 1;
	}

	/*
	* Walk backwards since we will most often be inserting at the end. As an
	* optimization, test the head node first and skip iterating over the
	* entire list if we are inserting at the start. The assumption is that
	* insertion at the start and end of the space will be the most common
	* operations. (*)
	*/
	z = end < f->range.start ? f : z;

	for (; z != NULL; z = zprev) {
	zprev = ossl_list_uint_set_prev(z);

	/* An existing range dwarfs our new range (optimisation). */
	if (z->range.start <= start && z->range.end >= end)
	return 1;

	if (uint_range_overlaps(&z->range, range)) {
	/*
	* Our new range overlaps an existing range, or possibly several
	* existing ranges.
	*/
	UINT_SET_ITEM *ovend = z;

	ovend->range.end = u64_max(end, z->range.end);

	/* Get earliest overlapping range. */
	while (zprev != NULL && uint_range_overlaps(&zprev->range, range)) {
	z = zprev;
	zprev = ossl_list_uint_set_prev(z);
	}

	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
	&& (zprev == NULL \|\| start > zprev->range.end)) {
	if (z->range.start == end + 1) {
	/* We can extend the following range backwards. */
	z->range.start = start;

	/*
	* If this closes a gap we now need to merge
	* consecutive nodes.
	*/
	uint_set_merge_adjacent(s, z);
	} else if (zprev != NULL && zprev->range.end + 1 == start) {
	/* We can extend the preceding range forwards. */
	zprev->range.end = end;

	/*
	* If this closes a gap we now need to merge
	* consecutive nodes.
	*/
	uint_set_merge_adjacent(s, z);
	} else {
	/*
	* The new interval is between intervals without overlapping or
	* touching them, so insert between, preserving sort.
	*/
	x = create_set_item(start, end);
	if (x == NULL)
	return 0;
	ossl_list_uint_set_insert_before(s, z, x);
	}
	break;
	}
	}

	return 1;
	}

	int ossl_uint_set_remove(UINT_SET s, const UINT_RANGE range)
	{
	UINT_SET_ITEM z, zprev, *y;
	uint64_t start = range->start, end = range->end;

	if (!ossl_assert(start <= end))
	return 0;

	/* Walk backwards since we will most often be removing at the end. */
	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. */
	break;

	if (start <= z->range.start && end >= z->range.end) {
	/*
	* The range being removed dwarfs this range, so it should be
	* removed.
	*/
	ossl_list_uint_set_remove(s, z);
	OPENSSL_free(z);
	} else if (start <= z->range.start && end >= z->range.start) {
	/*
	* The range being removed includes start of this range, but does
	* not cover the entire range (as this would be caught by the case
	* above). Shorten the range.
	*/
	assert(end < z->range.end);
	z->range.start = end + 1;
	} else if (end >= z->range.end) {
	/*
	* The range being removed includes the end of this range, but does
	* not cover the entire range (as this would be caught by the case
	* above). Shorten the range. We can also stop iterating.
	*/
	assert(start > z->range.start);
	assert(start > 0);
	z->range.end = start - 1;
	break;
	} else if (start > z->range.start && end < z->range.end) {
	/*
	* The range being removed falls entirely in this range, so cut it
	* into two. Cases where a zero-length range would be created are
	* handled by the above cases.
	*/
	y = create_set_item(end + 1, z->range.end);
	ossl_list_uint_set_insert_after(s, z, y);
	z->range.end = start - 1;
	break;
	} else {
	/* Assert no partial overlap; all cases should be covered above. */
	assert(!uint_range_overlaps(&z->range, range));
	}
	}

	return 1;
	}

	int ossl_uint_set_query(const UINT_SET *s, uint64_t v)
	{
	UINT_SET_ITEM *x;

	if (ossl_list_uint_set_is_empty(s))
	return 0;

	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)
	return 0;

	return 0;
	}