Lines Matching +full:rs +full:-
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause
39 static void rangeset_check(struct rangeset *rs);
41 #define rangeset_check(rs) argument
54 SYSINIT(rs, SI_SUB_LOCK, SI_ORDER_ANY, rs_rangeset_init, NULL);
59 struct rangeset *rs; in rs_node_alloc() local
61 rs = __containerof(ptree, struct rangeset, rs_trie); in rs_node_alloc()
62 return (uma_zalloc(rs_node_zone, rs->rs_alloc_flags)); in rs_node_alloc()
75 rangeset_init(struct rangeset *rs, rs_dup_data_t dup_data, in rangeset_init() argument
79 pctrie_init(&rs->rs_trie); in rangeset_init()
80 rs->rs_dup_data = dup_data; in rangeset_init()
81 rs->rs_free_data = free_data; in rangeset_init()
82 rs->rs_data_ctx = data_ctx; in rangeset_init()
83 rs->rs_alloc_flags = alloc_flags; in rangeset_init()
87 rangeset_fini(struct rangeset *rs) in rangeset_fini() argument
90 rangeset_check(rs); in rangeset_fini()
91 rangeset_remove_all(rs); in rangeset_fini()
95 rangeset_check_empty(struct rangeset *rs, uint64_t start, uint64_t end) in rangeset_check_empty() argument
99 rangeset_check(rs); in rangeset_check_empty()
100 r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, end); in rangeset_check_empty()
101 return (r == NULL || r->re_end <= start); in rangeset_check_empty()
105 rangeset_insert(struct rangeset *rs, uint64_t start, uint64_t end, in rangeset_insert() argument
111 rangeset_check(rs); in rangeset_insert()
112 error = rangeset_remove(rs, start, end); in rangeset_insert()
116 r->re_start = start; in rangeset_insert()
117 r->re_end = end; in rangeset_insert()
118 error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, r); in rangeset_insert()
119 rangeset_check(rs); in rangeset_insert()
124 rangeset_remove_pred(struct rangeset *rs, uint64_t start, uint64_t end, in rangeset_remove_pred() argument
130 rangeset_check(rs); in rangeset_remove_pred()
133 r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, end - 1); in rangeset_remove_pred()
138 * ------============================--|-------|---- in rangeset_remove_pred()
139 * rs re s e in rangeset_remove_pred()
141 if (r->re_end <= start) in rangeset_remove_pred()
144 if (r->re_end <= end) { in rangeset_remove_pred()
145 if (r->re_start < start) { in rangeset_remove_pred()
147 * ------========|==============-------|---- in rangeset_remove_pred()
148 * rs s re e in rangeset_remove_pred()
150 if (pred(rs->rs_data_ctx, r)) in rangeset_remove_pred()
151 r->re_end = start; in rangeset_remove_pred()
156 * ------|--------===================----------|---- in rangeset_remove_pred()
157 * s rs re e in rangeset_remove_pred()
159 end = r->re_start; in rangeset_remove_pred()
160 if (pred(rs->rs_data_ctx, r)) { in rangeset_remove_pred()
161 RANGESET_PCTRIE_REMOVE(&rs->rs_trie, in rangeset_remove_pred()
162 r->re_start); in rangeset_remove_pred()
163 rs->rs_free_data(rs->rs_data_ctx, r); in rangeset_remove_pred()
169 * ------|--------====================|==========---- in rangeset_remove_pred()
170 * s rs e re in rangeset_remove_pred()
172 if (r->re_start >= start) { in rangeset_remove_pred()
173 if (pred(rs->rs_data_ctx, r)) { in rangeset_remove_pred()
174 RANGESET_PCTRIE_REMOVE(&rs->rs_trie, in rangeset_remove_pred()
175 r->re_start); in rangeset_remove_pred()
176 r->re_start = end; in rangeset_remove_pred()
177 error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, r); in rangeset_remove_pred()
186 end = r->re_start; in rangeset_remove_pred()
192 * ------=========|===================|==========---- in rangeset_remove_pred()
193 * rs s e re in rangeset_remove_pred()
195 if (pred(rs->rs_data_ctx, r)) { in rangeset_remove_pred()
201 rn = rs->rs_dup_data(rs->rs_data_ctx, r); in rangeset_remove_pred()
206 rn->re_start = end; in rangeset_remove_pred()
207 rn->re_end = r->re_end; in rangeset_remove_pred()
208 error = RANGESET_PCTRIE_INSERT(&rs->rs_trie, rn); in rangeset_remove_pred()
210 rs->rs_free_data(rs->rs_data_ctx, rn); in rangeset_remove_pred()
213 r->re_end = start; in rangeset_remove_pred()
217 rangeset_check(rs); in rangeset_remove_pred()
229 rangeset_remove(struct rangeset *rs, uint64_t start, uint64_t end) in rangeset_remove() argument
232 return (rangeset_remove_pred(rs, start, end, rangeset_true_pred)); in rangeset_remove()
238 struct rangeset *rs = rsv; in rangeset_remove_leaf() local
240 rs->rs_free_data(rs->rs_data_ctx, r); in rangeset_remove_leaf()
244 rangeset_remove_all(struct rangeset *rs) in rangeset_remove_all() argument
246 RANGESET_PCTRIE_RECLAIM_CALLBACK(&rs->rs_trie, in rangeset_remove_all()
247 rangeset_remove_leaf, rs); in rangeset_remove_all()
251 rangeset_containing(struct rangeset *rs, uint64_t place) in rangeset_containing() argument
255 rangeset_check(rs); in rangeset_containing()
256 r = RANGESET_PCTRIE_LOOKUP_LE(&rs->rs_trie, place); in rangeset_containing()
257 if (r != NULL && place < r->re_end) in rangeset_containing()
263 rangeset_empty(struct rangeset *rs, uint64_t start, uint64_t end) in rangeset_empty() argument
267 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, start + 1); in rangeset_empty()
268 return (r == NULL || r->re_start >= end); in rangeset_empty()
272 rangeset_beginning(struct rangeset *rs, uint64_t place) in rangeset_beginning() argument
275 rangeset_check(rs); in rangeset_beginning()
276 return (RANGESET_PCTRIE_LOOKUP(&rs->rs_trie, place)); in rangeset_beginning()
286 MPASS(pctrie_is_empty(&dst_rs->rs_trie)); in rangeset_copy()
288 MPASS(dst_rs->rs_dup_data == src_rs->rs_dup_data); in rangeset_copy()
291 for (cursor = 0;; cursor = src_r->re_start + 1) { in rangeset_copy()
292 src_r = RANGESET_PCTRIE_LOOKUP_GE(&src_rs->rs_trie, cursor); in rangeset_copy()
295 dst_r = dst_rs->rs_dup_data(dst_rs->rs_data_ctx, src_r); in rangeset_copy()
300 error = RANGESET_PCTRIE_INSERT(&dst_rs->rs_trie, dst_r); in rangeset_copy()
311 rangeset_check(struct rangeset *rs) in rangeset_check() argument
316 for (cursor = 0, rp = NULL;; cursor = r->re_start + 1, rp = r) { in rangeset_check()
317 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor); in rangeset_check()
320 KASSERT(r->re_start < r->re_end, in rangeset_check()
321 ("invalid interval rs %p elem %p (%#jx, %#jx)", in rangeset_check()
322 rs, r, (uintmax_t)r->re_start, (uintmax_t)r->re_end)); in rangeset_check()
324 KASSERT(rp->re_end <= r->re_start, in rangeset_check()
325 ("non-ascending neighbors rs %p " in rangeset_check()
327 rs, rp, (uintmax_t)rp->re_start, in rangeset_check()
328 (uintmax_t)rp->re_end, r, (uintmax_t)r->re_start, in rangeset_check()
329 (uintmax_t)r->re_end)); in rangeset_check()
342 struct rangeset *rs; in DB_SHOW_COMMAND() local
351 rs = (struct rangeset *)addr; in DB_SHOW_COMMAND()
352 db_printf("rangeset %p\n", rs); in DB_SHOW_COMMAND()
353 for (cursor = 0;; cursor = r->re_start + 1) { in DB_SHOW_COMMAND()
354 r = RANGESET_PCTRIE_LOOKUP_GE(&rs->rs_trie, cursor); in DB_SHOW_COMMAND()
358 r, r->re_start, r->re_end); in DB_SHOW_COMMAND()