10713e232SGeorge Wilson /* 20713e232SGeorge Wilson * CDDL HEADER START 30713e232SGeorge Wilson * 40713e232SGeorge Wilson * The contents of this file are subject to the terms of the 50713e232SGeorge Wilson * Common Development and Distribution License (the "License"). 60713e232SGeorge Wilson * You may not use this file except in compliance with the License. 70713e232SGeorge Wilson * 80713e232SGeorge Wilson * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 90713e232SGeorge Wilson * or http://www.opensolaris.org/os/licensing. 100713e232SGeorge Wilson * See the License for the specific language governing permissions 110713e232SGeorge Wilson * and limitations under the License. 120713e232SGeorge Wilson * 130713e232SGeorge Wilson * When distributing Covered Code, include this CDDL HEADER in each 140713e232SGeorge Wilson * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 150713e232SGeorge Wilson * If applicable, add the following below this CDDL HEADER, with the 160713e232SGeorge Wilson * fields enclosed by brackets "[]" replaced with your own identifying 170713e232SGeorge Wilson * information: Portions Copyright [yyyy] [name of copyright owner] 180713e232SGeorge Wilson * 190713e232SGeorge Wilson * CDDL HEADER END 200713e232SGeorge Wilson */ 210713e232SGeorge Wilson /* 220713e232SGeorge Wilson * Copyright 2009 Sun Microsystems, Inc. All rights reserved. 230713e232SGeorge Wilson * Use is subject to license terms. 240713e232SGeorge Wilson */ 250713e232SGeorge Wilson 260713e232SGeorge Wilson /* 27814dcd43SSerapheim Dimitropoulos * Copyright (c) 2013, 2019 by Delphix. All rights reserved. 280713e232SGeorge Wilson */ 290713e232SGeorge Wilson 300713e232SGeorge Wilson #ifndef _SYS_RANGE_TREE_H 310713e232SGeorge Wilson #define _SYS_RANGE_TREE_H 320713e232SGeorge Wilson 33*4d7988d6SPaul Dagnelie #include <sys/btree.h> 340713e232SGeorge Wilson #include <sys/dmu.h> 350713e232SGeorge Wilson 360713e232SGeorge Wilson #ifdef __cplusplus 370713e232SGeorge Wilson extern "C" { 380713e232SGeorge Wilson #endif 390713e232SGeorge Wilson 400713e232SGeorge Wilson #define RANGE_TREE_HISTOGRAM_SIZE 64 410713e232SGeorge Wilson 420713e232SGeorge Wilson typedef struct range_tree_ops range_tree_ops_t; 430713e232SGeorge Wilson 44*4d7988d6SPaul Dagnelie typedef enum range_seg_type { 45*4d7988d6SPaul Dagnelie RANGE_SEG32, 46*4d7988d6SPaul Dagnelie RANGE_SEG64, 47*4d7988d6SPaul Dagnelie RANGE_SEG_GAP, 48*4d7988d6SPaul Dagnelie RANGE_SEG_NUM_TYPES, 49*4d7988d6SPaul Dagnelie } range_seg_type_t; 50*4d7988d6SPaul Dagnelie 515cabbc6bSPrashanth Sreenivasa /* 525cabbc6bSPrashanth Sreenivasa * Note: the range_tree may not be accessed concurrently; consumers 535cabbc6bSPrashanth Sreenivasa * must provide external locking if required. 545cabbc6bSPrashanth Sreenivasa */ 550713e232SGeorge Wilson typedef struct range_tree { 56*4d7988d6SPaul Dagnelie zfs_btree_t rt_root; /* offset-ordered segment b-tree */ 570713e232SGeorge Wilson uint64_t rt_space; /* sum of all segments in the map */ 58*4d7988d6SPaul Dagnelie range_seg_type_t rt_type; /* type of range_seg_t in use */ 59*4d7988d6SPaul Dagnelie /* 60*4d7988d6SPaul Dagnelie * All data that is stored in the range tree must have a start higher 61*4d7988d6SPaul Dagnelie * than or equal to rt_start, and all sizes and offsets must be 62*4d7988d6SPaul Dagnelie * multiples of 1 << rt_shift. 63*4d7988d6SPaul Dagnelie */ 64*4d7988d6SPaul Dagnelie uint8_t rt_shift; 65*4d7988d6SPaul Dagnelie uint64_t rt_start; 660713e232SGeorge Wilson range_tree_ops_t *rt_ops; 67*4d7988d6SPaul Dagnelie 68*4d7988d6SPaul Dagnelie /* rt_btree_compare should only be set if rt_arg is a b-tree */ 690713e232SGeorge Wilson void *rt_arg; 70*4d7988d6SPaul Dagnelie int (*rt_btree_compare)(const void *, const void *); 710713e232SGeorge Wilson 72*4d7988d6SPaul Dagnelie uint64_t rt_gap; /* allowable inter-segment gap */ 73a3874b8bSToomas Soome 740713e232SGeorge Wilson /* 750713e232SGeorge Wilson * The rt_histogram maintains a histogram of ranges. Each bucket, 760713e232SGeorge Wilson * rt_histogram[i], contains the number of ranges whose size is: 770713e232SGeorge Wilson * 2^i <= size of range in bytes < 2^(i+1) 780713e232SGeorge Wilson */ 790713e232SGeorge Wilson uint64_t rt_histogram[RANGE_TREE_HISTOGRAM_SIZE]; 800713e232SGeorge Wilson } range_tree_t; 810713e232SGeorge Wilson 82*4d7988d6SPaul Dagnelie typedef struct range_seg32 { 83*4d7988d6SPaul Dagnelie uint32_t rs_start; /* starting offset of this segment */ 84*4d7988d6SPaul Dagnelie uint32_t rs_end; /* ending offset (non-inclusive) */ 85*4d7988d6SPaul Dagnelie } range_seg32_t; 86*4d7988d6SPaul Dagnelie 87*4d7988d6SPaul Dagnelie /* 88*4d7988d6SPaul Dagnelie * Extremely large metaslabs, vdev-wide trees, and dnode-wide trees may 89*4d7988d6SPaul Dagnelie * require 64-bit integers for ranges. 90*4d7988d6SPaul Dagnelie */ 91*4d7988d6SPaul Dagnelie typedef struct range_seg64 { 92*4d7988d6SPaul Dagnelie uint64_t rs_start; /* starting offset of this segment */ 93*4d7988d6SPaul Dagnelie uint64_t rs_end; /* ending offset (non-inclusive) */ 94*4d7988d6SPaul Dagnelie } range_seg64_t; 95*4d7988d6SPaul Dagnelie 96*4d7988d6SPaul Dagnelie typedef struct range_seg_gap { 970713e232SGeorge Wilson uint64_t rs_start; /* starting offset of this segment */ 980713e232SGeorge Wilson uint64_t rs_end; /* ending offset (non-inclusive) */ 99a3874b8bSToomas Soome uint64_t rs_fill; /* actual fill if gap mode is on */ 100*4d7988d6SPaul Dagnelie } range_seg_gap_t; 101*4d7988d6SPaul Dagnelie 102*4d7988d6SPaul Dagnelie /* 103*4d7988d6SPaul Dagnelie * This type needs to be the largest of the range segs, since it will be stack 104*4d7988d6SPaul Dagnelie * allocated and then cast the actual type to do tree operations. 105*4d7988d6SPaul Dagnelie */ 106*4d7988d6SPaul Dagnelie typedef range_seg_gap_t range_seg_max_t; 107*4d7988d6SPaul Dagnelie 108*4d7988d6SPaul Dagnelie /* 109*4d7988d6SPaul Dagnelie * This is just for clarity of code purposes, so we can make it clear that a 110*4d7988d6SPaul Dagnelie * pointer is to a range seg of some type; when we need to do the actual math, 111*4d7988d6SPaul Dagnelie * we'll figure out the real type. 112*4d7988d6SPaul Dagnelie */ 113*4d7988d6SPaul Dagnelie typedef void range_seg_t; 1140713e232SGeorge Wilson 1150713e232SGeorge Wilson struct range_tree_ops { 1160713e232SGeorge Wilson void (*rtop_create)(range_tree_t *rt, void *arg); 1170713e232SGeorge Wilson void (*rtop_destroy)(range_tree_t *rt, void *arg); 118*4d7988d6SPaul Dagnelie void (*rtop_add)(range_tree_t *rt, void *rs, void *arg); 119*4d7988d6SPaul Dagnelie void (*rtop_remove)(range_tree_t *rt, void *rs, void *arg); 1200713e232SGeorge Wilson void (*rtop_vacate)(range_tree_t *rt, void *arg); 1210713e232SGeorge Wilson }; 1220713e232SGeorge Wilson 123*4d7988d6SPaul Dagnelie static inline uint64_t 124*4d7988d6SPaul Dagnelie rs_get_start_raw(const range_seg_t *rs, const range_tree_t *rt) 125*4d7988d6SPaul Dagnelie { 126*4d7988d6SPaul Dagnelie ASSERT3U(rt->rt_type, <=, RANGE_SEG_NUM_TYPES); 127*4d7988d6SPaul Dagnelie switch (rt->rt_type) { 128*4d7988d6SPaul Dagnelie case RANGE_SEG32: 129*4d7988d6SPaul Dagnelie return (((range_seg32_t *)rs)->rs_start); 130*4d7988d6SPaul Dagnelie case RANGE_SEG64: 131*4d7988d6SPaul Dagnelie return (((range_seg64_t *)rs)->rs_start); 132*4d7988d6SPaul Dagnelie case RANGE_SEG_GAP: 133*4d7988d6SPaul Dagnelie return (((range_seg_gap_t *)rs)->rs_start); 134*4d7988d6SPaul Dagnelie default: 135*4d7988d6SPaul Dagnelie VERIFY(0); 136*4d7988d6SPaul Dagnelie return (0); 137*4d7988d6SPaul Dagnelie } 138*4d7988d6SPaul Dagnelie } 139*4d7988d6SPaul Dagnelie 140*4d7988d6SPaul Dagnelie static inline uint64_t 141*4d7988d6SPaul Dagnelie rs_get_end_raw(const range_seg_t *rs, const range_tree_t *rt) 142*4d7988d6SPaul Dagnelie { 143*4d7988d6SPaul Dagnelie ASSERT3U(rt->rt_type, <=, RANGE_SEG_NUM_TYPES); 144*4d7988d6SPaul Dagnelie switch (rt->rt_type) { 145*4d7988d6SPaul Dagnelie case RANGE_SEG32: 146*4d7988d6SPaul Dagnelie return (((range_seg32_t *)rs)->rs_end); 147*4d7988d6SPaul Dagnelie case RANGE_SEG64: 148*4d7988d6SPaul Dagnelie return (((range_seg64_t *)rs)->rs_end); 149*4d7988d6SPaul Dagnelie case RANGE_SEG_GAP: 150*4d7988d6SPaul Dagnelie return (((range_seg_gap_t *)rs)->rs_end); 151*4d7988d6SPaul Dagnelie default: 152*4d7988d6SPaul Dagnelie VERIFY(0); 153*4d7988d6SPaul Dagnelie return (0); 154*4d7988d6SPaul Dagnelie } 155*4d7988d6SPaul Dagnelie } 156*4d7988d6SPaul Dagnelie 157*4d7988d6SPaul Dagnelie static inline uint64_t 158*4d7988d6SPaul Dagnelie rs_get_fill_raw(const range_seg_t *rs, const range_tree_t *rt) 159*4d7988d6SPaul Dagnelie { 160*4d7988d6SPaul Dagnelie ASSERT3U(rt->rt_type, <=, RANGE_SEG_NUM_TYPES); 161*4d7988d6SPaul Dagnelie switch (rt->rt_type) { 162*4d7988d6SPaul Dagnelie case RANGE_SEG32: { 163*4d7988d6SPaul Dagnelie const range_seg32_t *r32 = rs; 164*4d7988d6SPaul Dagnelie return (r32->rs_end - r32->rs_start); 165*4d7988d6SPaul Dagnelie } 166*4d7988d6SPaul Dagnelie case RANGE_SEG64: { 167*4d7988d6SPaul Dagnelie const range_seg64_t *r64 = rs; 168*4d7988d6SPaul Dagnelie return (r64->rs_end - r64->rs_start); 169*4d7988d6SPaul Dagnelie } 170*4d7988d6SPaul Dagnelie case RANGE_SEG_GAP: 171*4d7988d6SPaul Dagnelie return (((range_seg_gap_t *)rs)->rs_fill); 172*4d7988d6SPaul Dagnelie default: 173*4d7988d6SPaul Dagnelie VERIFY(0); 174*4d7988d6SPaul Dagnelie return (0); 175*4d7988d6SPaul Dagnelie } 176*4d7988d6SPaul Dagnelie 177*4d7988d6SPaul Dagnelie } 178*4d7988d6SPaul Dagnelie 179*4d7988d6SPaul Dagnelie static inline uint64_t 180*4d7988d6SPaul Dagnelie rs_get_start(const range_seg_t *rs, const range_tree_t *rt) 181*4d7988d6SPaul Dagnelie { 182*4d7988d6SPaul Dagnelie return ((rs_get_start_raw(rs, rt) << rt->rt_shift) + rt->rt_start); 183*4d7988d6SPaul Dagnelie } 184*4d7988d6SPaul Dagnelie 185*4d7988d6SPaul Dagnelie static inline uint64_t 186*4d7988d6SPaul Dagnelie rs_get_end(const range_seg_t *rs, const range_tree_t *rt) 187*4d7988d6SPaul Dagnelie { 188*4d7988d6SPaul Dagnelie return ((rs_get_end_raw(rs, rt) << rt->rt_shift) + rt->rt_start); 189*4d7988d6SPaul Dagnelie } 190*4d7988d6SPaul Dagnelie 191*4d7988d6SPaul Dagnelie static inline uint64_t 192*4d7988d6SPaul Dagnelie rs_get_fill(const range_seg_t *rs, const range_tree_t *rt) 193*4d7988d6SPaul Dagnelie { 194*4d7988d6SPaul Dagnelie return (rs_get_fill_raw(rs, rt) << rt->rt_shift); 195*4d7988d6SPaul Dagnelie } 196*4d7988d6SPaul Dagnelie 197*4d7988d6SPaul Dagnelie static inline void 198*4d7988d6SPaul Dagnelie rs_set_start_raw(range_seg_t *rs, range_tree_t *rt, uint64_t start) 199*4d7988d6SPaul Dagnelie { 200*4d7988d6SPaul Dagnelie ASSERT3U(rt->rt_type, <=, RANGE_SEG_NUM_TYPES); 201*4d7988d6SPaul Dagnelie switch (rt->rt_type) { 202*4d7988d6SPaul Dagnelie case RANGE_SEG32: 203*4d7988d6SPaul Dagnelie ASSERT3U(start, <=, UINT32_MAX); 204*4d7988d6SPaul Dagnelie ((range_seg32_t *)rs)->rs_start = (uint32_t)start; 205*4d7988d6SPaul Dagnelie break; 206*4d7988d6SPaul Dagnelie case RANGE_SEG64: 207*4d7988d6SPaul Dagnelie ((range_seg64_t *)rs)->rs_start = start; 208*4d7988d6SPaul Dagnelie break; 209*4d7988d6SPaul Dagnelie case RANGE_SEG_GAP: 210*4d7988d6SPaul Dagnelie ((range_seg_gap_t *)rs)->rs_start = start; 211*4d7988d6SPaul Dagnelie break; 212*4d7988d6SPaul Dagnelie default: 213*4d7988d6SPaul Dagnelie VERIFY(0); 214*4d7988d6SPaul Dagnelie } 215*4d7988d6SPaul Dagnelie } 216*4d7988d6SPaul Dagnelie 217*4d7988d6SPaul Dagnelie static inline void 218*4d7988d6SPaul Dagnelie rs_set_end_raw(range_seg_t *rs, range_tree_t *rt, uint64_t end) 219*4d7988d6SPaul Dagnelie { 220*4d7988d6SPaul Dagnelie ASSERT3U(rt->rt_type, <=, RANGE_SEG_NUM_TYPES); 221*4d7988d6SPaul Dagnelie switch (rt->rt_type) { 222*4d7988d6SPaul Dagnelie case RANGE_SEG32: 223*4d7988d6SPaul Dagnelie ASSERT3U(end, <=, UINT32_MAX); 224*4d7988d6SPaul Dagnelie ((range_seg32_t *)rs)->rs_end = (uint32_t)end; 225*4d7988d6SPaul Dagnelie break; 226*4d7988d6SPaul Dagnelie case RANGE_SEG64: 227*4d7988d6SPaul Dagnelie ((range_seg64_t *)rs)->rs_end = end; 228*4d7988d6SPaul Dagnelie break; 229*4d7988d6SPaul Dagnelie case RANGE_SEG_GAP: 230*4d7988d6SPaul Dagnelie ((range_seg_gap_t *)rs)->rs_end = end; 231*4d7988d6SPaul Dagnelie break; 232*4d7988d6SPaul Dagnelie default: 233*4d7988d6SPaul Dagnelie VERIFY(0); 234*4d7988d6SPaul Dagnelie } 235*4d7988d6SPaul Dagnelie } 236*4d7988d6SPaul Dagnelie 237*4d7988d6SPaul Dagnelie static inline void 238*4d7988d6SPaul Dagnelie rs_set_fill_raw(range_seg_t *rs, range_tree_t *rt, uint64_t fill) 239*4d7988d6SPaul Dagnelie { 240*4d7988d6SPaul Dagnelie ASSERT3U(rt->rt_type, <=, RANGE_SEG_NUM_TYPES); 241*4d7988d6SPaul Dagnelie switch (rt->rt_type) { 242*4d7988d6SPaul Dagnelie case RANGE_SEG32: 243*4d7988d6SPaul Dagnelie /* fall through */ 244*4d7988d6SPaul Dagnelie case RANGE_SEG64: 245*4d7988d6SPaul Dagnelie ASSERT3U(fill, ==, rs_get_end_raw(rs, rt) - rs_get_start_raw(rs, 246*4d7988d6SPaul Dagnelie rt)); 247*4d7988d6SPaul Dagnelie break; 248*4d7988d6SPaul Dagnelie case RANGE_SEG_GAP: 249*4d7988d6SPaul Dagnelie ((range_seg_gap_t *)rs)->rs_fill = fill; 250*4d7988d6SPaul Dagnelie break; 251*4d7988d6SPaul Dagnelie default: 252*4d7988d6SPaul Dagnelie VERIFY(0); 253*4d7988d6SPaul Dagnelie } 254*4d7988d6SPaul Dagnelie } 255*4d7988d6SPaul Dagnelie 256*4d7988d6SPaul Dagnelie static inline void 257*4d7988d6SPaul Dagnelie rs_set_start(range_seg_t *rs, range_tree_t *rt, uint64_t start) 258*4d7988d6SPaul Dagnelie { 259*4d7988d6SPaul Dagnelie ASSERT3U(start, >=, rt->rt_start); 260*4d7988d6SPaul Dagnelie ASSERT(IS_P2ALIGNED(start, 1ULL << rt->rt_shift)); 261*4d7988d6SPaul Dagnelie rs_set_start_raw(rs, rt, (start - rt->rt_start) >> rt->rt_shift); 262*4d7988d6SPaul Dagnelie } 263*4d7988d6SPaul Dagnelie 264*4d7988d6SPaul Dagnelie static inline void 265*4d7988d6SPaul Dagnelie rs_set_end(range_seg_t *rs, range_tree_t *rt, uint64_t end) 266*4d7988d6SPaul Dagnelie { 267*4d7988d6SPaul Dagnelie ASSERT3U(end, >=, rt->rt_start); 268*4d7988d6SPaul Dagnelie ASSERT(IS_P2ALIGNED(end, 1ULL << rt->rt_shift)); 269*4d7988d6SPaul Dagnelie rs_set_end_raw(rs, rt, (end - rt->rt_start) >> rt->rt_shift); 270*4d7988d6SPaul Dagnelie } 271*4d7988d6SPaul Dagnelie 272*4d7988d6SPaul Dagnelie static inline void 273*4d7988d6SPaul Dagnelie rs_set_fill(range_seg_t *rs, range_tree_t *rt, uint64_t fill) 274*4d7988d6SPaul Dagnelie { 275*4d7988d6SPaul Dagnelie ASSERT(IS_P2ALIGNED(fill, 1ULL << rt->rt_shift)); 276*4d7988d6SPaul Dagnelie rs_set_fill_raw(rs, rt, fill >> rt->rt_shift); 277*4d7988d6SPaul Dagnelie } 278*4d7988d6SPaul Dagnelie 2790713e232SGeorge Wilson typedef void range_tree_func_t(void *arg, uint64_t start, uint64_t size); 2800713e232SGeorge Wilson 281*4d7988d6SPaul Dagnelie range_tree_t *range_tree_create_impl(range_tree_ops_t *ops, 282*4d7988d6SPaul Dagnelie range_seg_type_t type, void *arg, uint64_t start, uint64_t shift, 283*4d7988d6SPaul Dagnelie int (*zfs_btree_compare) (const void *, const void *), uint64_t gap); 284*4d7988d6SPaul Dagnelie range_tree_t *range_tree_create(range_tree_ops_t *ops, range_seg_type_t type, 285*4d7988d6SPaul Dagnelie void *arg, uint64_t start, uint64_t shift); 2860713e232SGeorge Wilson void range_tree_destroy(range_tree_t *rt); 2870713e232SGeorge Wilson boolean_t range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size); 288*4d7988d6SPaul Dagnelie range_seg_t *range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size); 289af1d63abSPaul Dagnelie boolean_t range_tree_find_in(range_tree_t *rt, uint64_t start, uint64_t size, 290af1d63abSPaul Dagnelie uint64_t *ostart, uint64_t *osize); 291555d674dSSerapheim Dimitropoulos void range_tree_verify_not_present(range_tree_t *rt, 292555d674dSSerapheim Dimitropoulos uint64_t start, uint64_t size); 293a3874b8bSToomas Soome void range_tree_resize_segment(range_tree_t *rt, range_seg_t *rs, 294a3874b8bSToomas Soome uint64_t newstart, uint64_t newsize); 2950713e232SGeorge Wilson uint64_t range_tree_space(range_tree_t *rt); 296814dcd43SSerapheim Dimitropoulos uint64_t range_tree_numsegs(range_tree_t *rt); 29786714001SSerapheim Dimitropoulos boolean_t range_tree_is_empty(range_tree_t *rt); 2980713e232SGeorge Wilson void range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst); 2990713e232SGeorge Wilson void range_tree_stat_verify(range_tree_t *rt); 300cfd63e1bSMatthew Ahrens uint64_t range_tree_min(range_tree_t *rt); 301cfd63e1bSMatthew Ahrens uint64_t range_tree_max(range_tree_t *rt); 302cfd63e1bSMatthew Ahrens uint64_t range_tree_span(range_tree_t *rt); 3030713e232SGeorge Wilson 3040713e232SGeorge Wilson void range_tree_add(void *arg, uint64_t start, uint64_t size); 3050713e232SGeorge Wilson void range_tree_remove(void *arg, uint64_t start, uint64_t size); 306a3874b8bSToomas Soome void range_tree_remove_fill(range_tree_t *rt, uint64_t start, uint64_t size); 307a3874b8bSToomas Soome void range_tree_adjust_fill(range_tree_t *rt, range_seg_t *rs, int64_t delta); 308bf16b11eSMatthew Ahrens void range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size); 3090713e232SGeorge Wilson 3100713e232SGeorge Wilson void range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg); 3110713e232SGeorge Wilson void range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg); 312a3874b8bSToomas Soome range_seg_t *range_tree_first(range_tree_t *rt); 313a3874b8bSToomas Soome 314814dcd43SSerapheim Dimitropoulos void range_tree_remove_xor_add_segment(uint64_t start, uint64_t end, 315814dcd43SSerapheim Dimitropoulos range_tree_t *removefrom, range_tree_t *addto); 316814dcd43SSerapheim Dimitropoulos void range_tree_remove_xor_add(range_tree_t *rt, range_tree_t *removefrom, 317814dcd43SSerapheim Dimitropoulos range_tree_t *addto); 318814dcd43SSerapheim Dimitropoulos 319*4d7988d6SPaul Dagnelie void rt_btree_create(range_tree_t *rt, void *arg); 320*4d7988d6SPaul Dagnelie void rt_btree_destroy(range_tree_t *rt, void *arg); 321*4d7988d6SPaul Dagnelie void rt_btree_add(range_tree_t *rt, range_seg_t *rs, void *arg); 322*4d7988d6SPaul Dagnelie void rt_btree_remove(range_tree_t *rt, range_seg_t *rs, void *arg); 323*4d7988d6SPaul Dagnelie void rt_btree_vacate(range_tree_t *rt, void *arg); 324*4d7988d6SPaul Dagnelie extern range_tree_ops_t rt_btree_ops; 3250713e232SGeorge Wilson 3260713e232SGeorge Wilson #ifdef __cplusplus 3270713e232SGeorge Wilson } 3280713e232SGeorge Wilson #endif 3290713e232SGeorge Wilson 3300713e232SGeorge Wilson #endif /* _SYS_RANGE_TREE_H */ 331