1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2019 The FreeBSD Foundation 5 * 6 * This software was developed by Konstantin Belousov <kib@FreeBSD.org> 7 * under sponsorship from the FreeBSD Foundation. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 28 * SUCH DAMAGE. 29 */ 30 31 #ifndef _SYS_RANGESET_H 32 #define _SYS_RANGESET_H 33 34 #ifdef _KERNEL 35 36 #include <sys/_rangeset.h> 37 38 typedef bool (*rs_pred_t)(void *ctx, void *r); 39 40 /* 41 * This structure must be embedded at the start of the rangeset element. 42 */ 43 struct rs_el { 44 uint64_t re_start; /* pctrie key */ 45 uint64_t re_end; 46 }; 47 48 void rangeset_init(struct rangeset *rs, rs_dup_data_t dup_data, 49 rs_free_data_t free_data, void *rs_data_ctx, u_int alloc_flags); 50 void rangeset_fini(struct rangeset *rs); 51 52 bool rangeset_check_empty(struct rangeset *rs, uint64_t start, 53 uint64_t end); 54 55 /* 56 * r point to the app data with struct rs_el at the beginning. 57 */ 58 int rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end, 59 void *r); 60 61 /* 62 * Guarantees that on error the rangeset is not modified. Remove 63 * might need to split element if its start/end completely cover the 64 * removed range, in which case ENOMEM might be returned. 65 */ 66 void rangeset_remove_all(struct rangeset *rs); 67 int rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end); 68 int rangeset_remove_pred(struct rangeset *rs, uint64_t start, 69 uint64_t end, rs_pred_t pred); 70 71 /* 72 * Finds the range that contains place, if any. 73 */ 74 void *rangeset_containing(struct rangeset *rs, uint64_t place); 75 76 /* 77 * Report whether no range begins between start and end. 78 */ 79 bool rangeset_empty(struct rangeset *rs, uint64_t start, uint64_t end); 80 81 /* 82 * Finds the range that begins at place, if any. 83 */ 84 void *rangeset_beginning(struct rangeset *rs, uint64_t place); 85 86 /* 87 * Copies src_rs entries into dst_rs. dst_rs must be empty. 88 * Leaves dst_rs empty on failure. 89 */ 90 int rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs); 91 92 #endif 93 94 #endif 95