include/internal/uint_set.h

   1 /*
   2  * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9 #ifndef OSSL_UINT_SET_H
  10 # define OSSL_UINT_SET_H
  11
  12 #include "openssl/params.h"
  13 #include "internal/list.h"
  14
  15 /*
  16  * uint64_t Integer Sets
  17  * =====================
  18  *
  19  * Utilities for managing a logical set of unsigned 64-bit integers. The
  20  * structure tracks each contiguous range of integers using one allocation and
  21  * is thus optimised for cases where integers tend to appear consecutively.
  22  * Queries are optimised under the assumption that they will generally be made
  23  * on integers near the end of the set.
  24  *
  25  * Discussion of implementation details can be found in uint_set.c.
  26  */
  27 typedef struct uint_range_st {
  28     uint64_t    start, end;
  29 } UINT_RANGE;
  30
  31 typedef struct uint_set_item_st UINT_SET_ITEM;
  32 struct uint_set_item_st {
  33     OSSL_LIST_MEMBER(uint_set, UINT_SET_ITEM);
  34     UINT_RANGE                  range;
  35 };
  36
  37 DEFINE_LIST_OF(uint_set, UINT_SET_ITEM);
  38
  39 typedef OSSL_LIST(uint_set) UINT_SET;
  40
  41 void ossl_uint_set_init(UINT_SET *s);
  42 void ossl_uint_set_destroy(UINT_SET *s);
  43
  44 /*
  45  * Insert a range into a integer set. Returns 0 on allocation failure, in which
  46  * case the integer set is in a valid but undefined state. Otherwise, returns 1.
  47  * Ranges can overlap existing ranges without limitation. If a range is a subset
  48  * of an existing range in the set, this is a no-op and returns 1.
  49  */
  50 int ossl_uint_set_insert(UINT_SET *s, const UINT_RANGE *range);
  51
  52 /*
  53  * Remove a range from the set. Returns 0 on allocation failure, in which case
  54  * the integer set is unchanged. Otherwise, returns 1. Ranges which are not
  55  * already in the set can be removed without issue. If a passed range is not in
  56  * the integer set at all, this is a no-op and returns 1.
  57  */
  58 int ossl_uint_set_remove(UINT_SET *s, const UINT_RANGE *range);
  59
  60 /* Returns 1 iff the given integer is in the integer set. */
  61 int ossl_uint_set_query(const UINT_SET *s, uint64_t v);
  62
  63 #endif