35#include <sys/kernel.h>
37#include <sys/pctrie.h>
38#include <sys/rangeset.h>
44#define rangeset_check(rs)
64 rs = __containerof(ptree,
struct rangeset, rs_trie);
77 rs_free_data_t free_data,
void *data_ctx, u_int alloc_flags)
80 pctrie_init(&rs->rs_trie);
81 rs->rs_dup_data = dup_data;
82 rs->rs_free_data = free_data;
83 rs->rs_data_ctx = data_ctx;
84 rs->rs_alloc_flags = alloc_flags;
104 r = __containerof(r1,
struct rs_el, re_start);
105 if (r->re_end >
start)
134 struct rs_el *r, *rn;
140 for (; end > 0 &&
start < end;) {
144 r = __containerof(r1,
struct rs_el, re_start);
150 if (r->re_end <=
start)
153 if (r->re_end <= end) {
154 if (r->re_start <
start) {
159 if (pred(rs->rs_data_ctx, r))
169 if (pred(rs->rs_data_ctx, r)) {
172 rs->rs_free_data(rs->rs_data_ctx, r);
181 if (r->re_start >=
start) {
182 if (pred(rs->rs_data_ctx, r)) {
205 if (pred(rs->rs_data_ctx, r)) {
211 rn = rs->rs_dup_data(rs->rs_data_ctx, r);
217 rn->re_end = r->re_end;
221 rs->rs_free_data(rs->rs_data_ctx, rn);
256 r = __containerof(r1,
struct rs_el, re_start);
258 rs->rs_free_data(rs->rs_data_ctx, r);
272 r = __containerof(r1,
struct rs_el, re_start);
273 if (r->re_end <= place)
281 struct rs_el *src_r, *dst_r;
282 uint64_t cursor, *r1;
285 MPASS(pctrie_is_empty(&dst_rs->rs_trie));
287 MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data);
290 for (cursor = 0;; cursor = src_r->re_start + 1) {
294 src_r = __containerof(r1,
struct rs_el, re_start);
295 dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r);
314 struct rs_el *r, *rp;
315 uint64_t cursor, *r1;
317 for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) {
321 r = __containerof(r1,
struct rs_el, re_start);
322 KASSERT(r->re_start < r->re_end,
323 (
"invalid interval rs %p elem %p (%#jx, %#jx)",
324 rs, r, (uintmax_t)r->re_start, (uintmax_t)r->re_end));
326 KASSERT(rp->re_end <= r->re_start,
327 (
"non-ascending neighbors rs %p "
328 "prev elem %p (%#jx, %#jx) elem %p (%#jx, %#jx)",
329 rs, rp, (uintmax_t)rp->re_start,
330 (uintmax_t)rp->re_end, r, (uintmax_t)r->re_start,
331 (uintmax_t)r->re_end));
339#include <sys/kernel.h>
342DB_SHOW_COMMAND(rangeset, rangeset_show_fn)
346 uint64_t cursor, *r1;
349 db_printf(
"show rangeset addr\n");
353 rs = (
struct rangeset *)
addr;
354 db_printf(
"rangeset %p\n", rs);
355 for (cursor = 0;; cursor = r->re_start + 1) {
359 r = __containerof(r1,
struct rs_el, re_start);
360 db_printf(
" el %p start %#jx end %#jx\n",
361 r, r->re_start, r->re_end);
size_t pctrie_node_size(void)
int pctrie_zone_init(void *mem, int size __unused, int flags __unused)
int pctrie_insert(struct pctrie *ptree, uint64_t *val, pctrie_alloc_t allocfn)
uint64_t * pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
uint64_t * pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
void pctrie_remove(struct pctrie *ptree, uint64_t index, pctrie_free_t freefn)
#define rangeset_check(rs)
static void rs_rangeset_init(void *arg __unused)
static uma_zone_t rs_node_zone
static bool rangeset_true_pred(void *ctx __unused, void *r __unused)
void rangeset_remove_all(struct rangeset *rs)
void * rangeset_lookup(struct rangeset *rs, uint64_t place)
int rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end, void *data)
bool rangeset_check_empty(struct rangeset *rs, uint64_t start, uint64_t end)
void rangeset_init(struct rangeset *rs, rs_dup_data_t dup_data, rs_free_data_t free_data, void *data_ctx, u_int alloc_flags)
int rangeset_copy(struct rangeset *dst_rs, struct rangeset *src_rs)
static void rs_node_free(struct pctrie *ptree __unused, void *node)
int rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end)
void rangeset_fini(struct rangeset *rs)
static void * rs_node_alloc(struct pctrie *ptree)
int rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end, rs_pred_t pred)
SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL)