Home | History | Annotate | Line # | Download | only in internal 
      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
     64