Lines Matching refs:xas
35 static inline void xas_lock_type(struct xa_state *xas, unsigned int lock_type) in xas_lock_type() argument
38 xas_lock_irq(xas); in xas_lock_type()
40 xas_lock_bh(xas); in xas_lock_type()
42 xas_lock(xas); in xas_lock_type()
45 static inline void xas_unlock_type(struct xa_state *xas, unsigned int lock_type) in xas_unlock_type() argument
48 xas_unlock_irq(xas); in xas_unlock_type()
50 xas_unlock_bh(xas); in xas_unlock_type()
52 xas_unlock(xas); in xas_unlock_type()
123 static void xas_squash_marks(const struct xa_state *xas) in xas_squash_marks() argument
126 unsigned int limit = xas->xa_offset + xas->xa_sibs + 1; in xas_squash_marks()
128 if (!xas->xa_sibs) in xas_squash_marks()
132 unsigned long *marks = xas->xa_node->marks[mark]; in xas_squash_marks()
133 if (find_next_bit(marks, limit, xas->xa_offset + 1) == limit) in xas_squash_marks()
135 __set_bit(xas->xa_offset, marks); in xas_squash_marks()
136 bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs); in xas_squash_marks()
146 static void xas_set_offset(struct xa_state *xas) in xas_set_offset() argument
148 xas->xa_offset = get_offset(xas->xa_index, xas->xa_node); in xas_set_offset()
152 static void xas_move_index(struct xa_state *xas, unsigned long offset) in xas_move_index() argument
154 unsigned int shift = xas->xa_node->shift; in xas_move_index()
155 xas->xa_index &= ~XA_CHUNK_MASK << shift; in xas_move_index()
156 xas->xa_index += offset << shift; in xas_move_index()
159 static void xas_advance(struct xa_state *xas) in xas_advance() argument
161 xas->xa_offset++; in xas_advance()
162 xas_move_index(xas, xas->xa_offset); in xas_advance()
165 static void *set_bounds(struct xa_state *xas) in set_bounds() argument
167 xas->xa_node = XAS_BOUNDS; in set_bounds()
178 static void *xas_start(struct xa_state *xas) in xas_start() argument
182 if (xas_valid(xas)) in xas_start()
183 return xas_reload(xas); in xas_start()
184 if (xas_error(xas)) in xas_start()
187 entry = xa_head(xas->xa); in xas_start()
189 if (xas->xa_index) in xas_start()
190 return set_bounds(xas); in xas_start()
192 if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK) in xas_start()
193 return set_bounds(xas); in xas_start()
196 xas->xa_node = NULL; in xas_start()
200 static void *xas_descend(struct xa_state *xas, struct xa_node *node) in xas_descend() argument
202 unsigned int offset = get_offset(xas->xa_index, node); in xas_descend()
203 void *entry = xa_entry(xas->xa, node, offset); in xas_descend()
205 xas->xa_node = node; in xas_descend()
208 entry = xa_entry(xas->xa, node, offset); in xas_descend()
211 xas->xa_offset = offset; in xas_descend()
230 void *xas_load(struct xa_state *xas) in xas_load() argument
232 void *entry = xas_start(xas); in xas_load()
237 if (xas->xa_shift > node->shift) in xas_load()
239 entry = xas_descend(xas, node); in xas_load()
266 static void xas_destroy(struct xa_state *xas) in xas_destroy() argument
268 struct xa_node *node = xas->xa_alloc; in xas_destroy()
274 xas->xa_alloc = NULL; in xas_destroy()
295 bool xas_nomem(struct xa_state *xas, gfp_t gfp) in xas_nomem() argument
297 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in xas_nomem()
298 xas_destroy(xas); in xas_nomem()
301 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in xas_nomem()
303 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp); in xas_nomem()
304 if (!xas->xa_alloc) in xas_nomem()
306 XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list)); in xas_nomem()
307 xas->xa_node = XAS_RESTART; in xas_nomem()
321 static bool __xas_nomem(struct xa_state *xas, gfp_t gfp) in __xas_nomem() argument
322 __must_hold(xas->xa->xa_lock) in __xas_nomem()
324 unsigned int lock_type = xa_lock_type(xas->xa); in __xas_nomem()
326 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in __xas_nomem()
327 xas_destroy(xas); in __xas_nomem()
330 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in __xas_nomem()
333 xas_unlock_type(xas, lock_type); in __xas_nomem()
334 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp); in __xas_nomem()
335 xas_lock_type(xas, lock_type); in __xas_nomem()
337 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp); in __xas_nomem()
339 if (!xas->xa_alloc) in __xas_nomem()
341 XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list)); in __xas_nomem()
342 xas->xa_node = XAS_RESTART; in __xas_nomem()
346 static void xas_update(struct xa_state *xas, struct xa_node *node) in xas_update() argument
348 if (xas->xa_update) in xas_update()
349 xas->xa_update(node); in xas_update()
354 static void *xas_alloc(struct xa_state *xas, unsigned int shift) in xas_alloc() argument
356 struct xa_node *parent = xas->xa_node; in xas_alloc()
357 struct xa_node *node = xas->xa_alloc; in xas_alloc()
359 if (xas_invalid(xas)) in xas_alloc()
363 xas->xa_alloc = NULL; in xas_alloc()
367 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in xas_alloc()
372 xas_set_err(xas, -ENOMEM); in xas_alloc()
378 node->offset = xas->xa_offset; in xas_alloc()
381 xas_update(xas, parent); in xas_alloc()
388 RCU_INIT_POINTER(node->parent, xas->xa_node); in xas_alloc()
389 node->array = xas->xa; in xas_alloc()
396 static unsigned long xas_size(const struct xa_state *xas) in xas_size() argument
398 return (xas->xa_sibs + 1UL) << xas->xa_shift; in xas_size()
408 static unsigned long xas_max(struct xa_state *xas) in xas_max() argument
410 unsigned long max = xas->xa_index; in xas_max()
413 if (xas->xa_shift || xas->xa_sibs) { in xas_max()
414 unsigned long mask = xas_size(xas) - 1; in xas_max()
432 static void xas_shrink(struct xa_state *xas) in xas_shrink() argument
434 struct xarray *xa = xas->xa; in xas_shrink()
435 struct xa_node *node = xas->xa_node; in xas_shrink()
450 xas->xa_node = XAS_BOUNDS; in xas_shrink()
460 xas_update(xas, node); in xas_shrink()
476 static void xas_delete_node(struct xa_state *xas) in xas_delete_node() argument
478 struct xa_node *node = xas->xa_node; in xas_delete_node()
487 parent = xa_parent_locked(xas->xa, node); in xas_delete_node()
488 xas->xa_node = parent; in xas_delete_node()
489 xas->xa_offset = node->offset; in xas_delete_node()
493 xas->xa->xa_head = NULL; in xas_delete_node()
494 xas->xa_node = XAS_BOUNDS; in xas_delete_node()
498 parent->slots[xas->xa_offset] = NULL; in xas_delete_node()
502 xas_update(xas, node); in xas_delete_node()
506 xas_shrink(xas); in xas_delete_node()
518 static void xas_free_nodes(struct xa_state *xas, struct xa_node *top) in xas_free_nodes() argument
524 void *entry = xa_entry_locked(xas->xa, node, offset); in xas_free_nodes()
537 parent = xa_parent_locked(xas->xa, node); in xas_free_nodes()
541 xas_update(xas, node); in xas_free_nodes()
554 static int xas_expand(struct xa_state *xas, void *head) in xas_expand() argument
556 struct xarray *xa = xas->xa; in xas_expand()
559 unsigned long max = xas_max(xas); in xas_expand()
571 xas->xa_node = NULL; in xas_expand()
577 node = xas_alloc(xas, shift); in xas_expand()
612 xas_update(xas, node); in xas_expand()
617 xas->xa_node = node; in xas_expand()
634 static void *xas_create(struct xa_state *xas, bool allow_root) in xas_create() argument
636 struct xarray *xa = xas->xa; in xas_create()
639 struct xa_node *node = xas->xa_node; in xas_create()
641 unsigned int order = xas->xa_shift; in xas_create()
645 xas->xa_node = NULL; in xas_create()
648 shift = xas_expand(xas, entry); in xas_create()
655 } else if (xas_error(xas)) { in xas_create()
658 unsigned int offset = xas->xa_offset; in xas_create()
672 node = xas_alloc(xas, shift); in xas_create()
683 entry = xas_descend(xas, node); in xas_create()
684 slot = &node->slots[xas->xa_offset]; in xas_create()
699 void xas_create_range(struct xa_state *xas) in xas_create_range() argument
701 unsigned long index = xas->xa_index; in xas_create_range()
702 unsigned char shift = xas->xa_shift; in xas_create_range()
703 unsigned char sibs = xas->xa_sibs; in xas_create_range()
705 xas->xa_index |= ((sibs + 1) << shift) - 1; in xas_create_range()
706 if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift) in xas_create_range()
707 xas->xa_offset |= sibs; in xas_create_range()
708 xas->xa_shift = 0; in xas_create_range()
709 xas->xa_sibs = 0; in xas_create_range()
712 xas_create(xas, true); in xas_create_range()
713 if (xas_error(xas)) in xas_create_range()
715 if (xas->xa_index <= (index | XA_CHUNK_MASK)) in xas_create_range()
717 xas->xa_index -= XA_CHUNK_SIZE; in xas_create_range()
720 struct xa_node *node = xas->xa_node; in xas_create_range()
721 xas->xa_node = xa_parent_locked(xas->xa, node); in xas_create_range()
722 xas->xa_offset = node->offset - 1; in xas_create_range()
729 xas->xa_shift = shift; in xas_create_range()
730 xas->xa_sibs = sibs; in xas_create_range()
731 xas->xa_index = index; in xas_create_range()
734 xas->xa_index = index; in xas_create_range()
735 if (xas->xa_node) in xas_create_range()
736 xas_set_offset(xas); in xas_create_range()
740 static void update_node(struct xa_state *xas, struct xa_node *node, in update_node() argument
750 xas_update(xas, node); in update_node()
752 xas_delete_node(xas); in update_node()
768 void *xas_store(struct xa_state *xas, void *entry) in xas_store() argument
771 void __rcu **slot = &xas->xa->xa_head; in xas_store()
780 first = xas_create(xas, allow_root); in xas_store()
782 first = xas_load(xas); in xas_store()
785 if (xas_invalid(xas)) in xas_store()
787 node = xas->xa_node; in xas_store()
788 if (node && (xas->xa_shift < node->shift)) in xas_store()
789 xas->xa_sibs = 0; in xas_store()
790 if ((first == entry) && !xas->xa_sibs) in xas_store()
794 offset = xas->xa_offset; in xas_store()
795 max = xas->xa_offset + xas->xa_sibs; in xas_store()
798 if (xas->xa_sibs) in xas_store()
799 xas_squash_marks(xas); in xas_store()
802 xas_init_marks(xas); in xas_store()
814 xas_free_nodes(xas, xa_to_node(next)); in xas_store()
823 entry = xa_mk_sibling(xas->xa_offset); in xas_store()
828 next = xa_entry_locked(xas->xa, node, ++offset); in xas_store()
837 update_node(xas, node, count, values); in xas_store()
850 bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark) in xas_get_mark() argument
852 if (xas_invalid(xas)) in xas_get_mark()
854 if (!xas->xa_node) in xas_get_mark()
855 return xa_marked(xas->xa, mark); in xas_get_mark()
856 return node_get_mark(xas->xa_node, xas->xa_offset, mark); in xas_get_mark()
869 void xas_set_mark(const struct xa_state *xas, xa_mark_t mark) in xas_set_mark() argument
871 struct xa_node *node = xas->xa_node; in xas_set_mark()
872 unsigned int offset = xas->xa_offset; in xas_set_mark()
874 if (xas_invalid(xas)) in xas_set_mark()
881 node = xa_parent_locked(xas->xa, node); in xas_set_mark()
884 if (!xa_marked(xas->xa, mark)) in xas_set_mark()
885 xa_mark_set(xas->xa, mark); in xas_set_mark()
898 void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark) in xas_clear_mark() argument
900 struct xa_node *node = xas->xa_node; in xas_clear_mark()
901 unsigned int offset = xas->xa_offset; in xas_clear_mark()
903 if (xas_invalid(xas)) in xas_clear_mark()
913 node = xa_parent_locked(xas->xa, node); in xas_clear_mark()
916 if (xa_marked(xas->xa, mark)) in xas_clear_mark()
917 xa_mark_clear(xas->xa, mark); in xas_clear_mark()
932 void xas_init_marks(const struct xa_state *xas) in xas_init_marks() argument
937 if (xa_track_free(xas->xa) && mark == XA_FREE_MARK) in xas_init_marks()
938 xas_set_mark(xas, mark); in xas_init_marks()
940 xas_clear_mark(xas, mark); in xas_init_marks()
963 void xas_pause(struct xa_state *xas) in xas_pause() argument
965 struct xa_node *node = xas->xa_node; in xas_pause()
967 if (xas_invalid(xas)) in xas_pause()
971 unsigned int offset = xas->xa_offset; in xas_pause()
973 if (!xa_is_sibling(xa_entry(xas->xa, node, offset))) in xas_pause()
976 xas->xa_index += (offset - xas->xa_offset) << node->shift; in xas_pause()
978 xas->xa_index++; in xas_pause()
980 xas->xa_node = XAS_RESTART; in xas_pause()
991 void *__xas_prev(struct xa_state *xas) in __xas_prev() argument
995 if (!xas_frozen(xas->xa_node)) in __xas_prev()
996 xas->xa_index--; in __xas_prev()
997 if (!xas->xa_node) in __xas_prev()
998 return set_bounds(xas); in __xas_prev()
999 if (xas_not_node(xas->xa_node)) in __xas_prev()
1000 return xas_load(xas); in __xas_prev()
1002 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node)) in __xas_prev()
1003 xas->xa_offset--; in __xas_prev()
1005 while (xas->xa_offset == 255) { in __xas_prev()
1006 xas->xa_offset = xas->xa_node->offset - 1; in __xas_prev()
1007 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_prev()
1008 if (!xas->xa_node) in __xas_prev()
1009 return set_bounds(xas); in __xas_prev()
1013 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_prev()
1017 xas->xa_node = xa_to_node(entry); in __xas_prev()
1018 xas_set_offset(xas); in __xas_prev()
1030 void *__xas_next(struct xa_state *xas) in __xas_next() argument
1034 if (!xas_frozen(xas->xa_node)) in __xas_next()
1035 xas->xa_index++; in __xas_next()
1036 if (!xas->xa_node) in __xas_next()
1037 return set_bounds(xas); in __xas_next()
1038 if (xas_not_node(xas->xa_node)) in __xas_next()
1039 return xas_load(xas); in __xas_next()
1041 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node)) in __xas_next()
1042 xas->xa_offset++; in __xas_next()
1044 while (xas->xa_offset == XA_CHUNK_SIZE) { in __xas_next()
1045 xas->xa_offset = xas->xa_node->offset + 1; in __xas_next()
1046 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_next()
1047 if (!xas->xa_node) in __xas_next()
1048 return set_bounds(xas); in __xas_next()
1052 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_next()
1056 xas->xa_node = xa_to_node(entry); in __xas_next()
1057 xas_set_offset(xas); in __xas_next()
1078 void *xas_find(struct xa_state *xas, unsigned long max) in xas_find() argument
1082 if (xas_error(xas)) in xas_find()
1085 if (!xas->xa_node) { in xas_find()
1086 xas->xa_index = 1; in xas_find()
1087 return set_bounds(xas); in xas_find()
1088 } else if (xas_top(xas->xa_node)) { in xas_find()
1089 entry = xas_load(xas); in xas_find()
1090 if (entry || xas_not_node(xas->xa_node)) in xas_find()
1092 } else if (!xas->xa_node->shift && in xas_find()
1093 xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)) { in xas_find()
1094 xas->xa_offset = ((xas->xa_index - 1) & XA_CHUNK_MASK) + 1; in xas_find()
1097 xas_advance(xas); in xas_find()
1099 while (xas->xa_node && (xas->xa_index <= max)) { in xas_find()
1100 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) { in xas_find()
1101 xas->xa_offset = xas->xa_node->offset + 1; in xas_find()
1102 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find()
1106 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find()
1108 xas->xa_node = xa_to_node(entry); in xas_find()
1109 xas->xa_offset = 0; in xas_find()
1115 xas_advance(xas); in xas_find()
1118 if (!xas->xa_node) in xas_find()
1119 xas->xa_node = XAS_BOUNDS; in xas_find()
1145 void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark) in xas_find_marked() argument
1151 if (xas_error(xas)) in xas_find_marked()
1154 if (!xas->xa_node) { in xas_find_marked()
1155 xas->xa_index = 1; in xas_find_marked()
1157 } else if (xas_top(xas->xa_node)) { in xas_find_marked()
1159 entry = xa_head(xas->xa); in xas_find_marked()
1160 xas->xa_node = NULL; in xas_find_marked()
1161 if (xas->xa_index > max_index(entry)) in xas_find_marked()
1164 if (xa_marked(xas->xa, mark)) in xas_find_marked()
1166 xas->xa_index = 1; in xas_find_marked()
1169 xas->xa_node = xa_to_node(entry); in xas_find_marked()
1170 xas->xa_offset = xas->xa_index >> xas->xa_node->shift; in xas_find_marked()
1173 while (xas->xa_index <= max) { in xas_find_marked()
1174 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) { in xas_find_marked()
1175 xas->xa_offset = xas->xa_node->offset + 1; in xas_find_marked()
1176 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find_marked()
1177 if (!xas->xa_node) in xas_find_marked()
1184 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1186 xas->xa_offset = xa_to_sibling(entry); in xas_find_marked()
1187 xas_move_index(xas, xas->xa_offset); in xas_find_marked()
1191 offset = xas_find_chunk(xas, advance, mark); in xas_find_marked()
1192 if (offset > xas->xa_offset) { in xas_find_marked()
1194 xas_move_index(xas, offset); in xas_find_marked()
1196 if ((xas->xa_index - 1) >= max) in xas_find_marked()
1198 xas->xa_offset = offset; in xas_find_marked()
1203 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1206 xas->xa_node = xa_to_node(entry); in xas_find_marked()
1207 xas_set_offset(xas); in xas_find_marked()
1211 if (xas->xa_index > max) in xas_find_marked()
1213 return set_bounds(xas); in xas_find_marked()
1215 xas->xa_node = XAS_RESTART; in xas_find_marked()
1229 void *xas_find_conflict(struct xa_state *xas) in xas_find_conflict() argument
1233 if (xas_error(xas)) in xas_find_conflict()
1236 if (!xas->xa_node) in xas_find_conflict()
1239 if (xas_top(xas->xa_node)) { in xas_find_conflict()
1240 curr = xas_start(xas); in xas_find_conflict()
1245 curr = xas_descend(xas, node); in xas_find_conflict()
1251 if (xas->xa_node->shift > xas->xa_shift) in xas_find_conflict()
1255 if (xas->xa_node->shift == xas->xa_shift) { in xas_find_conflict()
1256 if ((xas->xa_offset & xas->xa_sibs) == xas->xa_sibs) in xas_find_conflict()
1258 } else if (xas->xa_offset == XA_CHUNK_MASK) { in xas_find_conflict()
1259 xas->xa_offset = xas->xa_node->offset; in xas_find_conflict()
1260 xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node); in xas_find_conflict()
1261 if (!xas->xa_node) in xas_find_conflict()
1265 curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset); in xas_find_conflict()
1269 xas->xa_node = xa_to_node(curr); in xas_find_conflict()
1270 xas->xa_offset = 0; in xas_find_conflict()
1271 curr = xa_entry_locked(xas->xa, xas->xa_node, 0); in xas_find_conflict()
1276 xas->xa_offset -= xas->xa_sibs; in xas_find_conflict()
1291 XA_STATE(xas, xa, index); in xa_load()
1296 entry = xas_load(&xas); in xa_load()
1299 } while (xas_retry(&xas, entry)); in xa_load()
1306 static void *xas_result(struct xa_state *xas, void *curr) in xas_result() argument
1310 if (xas_error(xas)) in xas_result()
1311 curr = xas->xa_node; in xas_result()
1329 XA_STATE(xas, xa, index); in __xa_erase()
1330 return xas_result(&xas, xas_store(&xas, NULL)); in __xa_erase()
1375 XA_STATE(xas, xa, index); in __xa_store()
1384 curr = xas_store(&xas, entry); in __xa_store()
1386 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_store()
1387 } while (__xas_nomem(&xas, gfp)); in __xa_store()
1389 return xas_result(&xas, curr); in __xa_store()
1441 XA_STATE(xas, xa, index); in __xa_cmpxchg()
1448 curr = xas_load(&xas); in __xa_cmpxchg()
1450 xas_store(&xas, entry); in __xa_cmpxchg()
1452 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_cmpxchg()
1454 } while (__xas_nomem(&xas, gfp)); in __xa_cmpxchg()
1456 return xas_result(&xas, curr); in __xa_cmpxchg()
1478 XA_STATE(xas, xa, index); in __xa_insert()
1487 curr = xas_load(&xas); in __xa_insert()
1489 xas_store(&xas, entry); in __xa_insert()
1491 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_insert()
1493 xas_set_err(&xas, -EBUSY); in __xa_insert()
1495 } while (__xas_nomem(&xas, gfp)); in __xa_insert()
1497 return xas_error(&xas); in __xa_insert()
1502 static void xas_set_range(struct xa_state *xas, unsigned long first, in xas_set_range() argument
1509 xas_set(xas, first); in xas_set_range()
1529 xas->xa_shift = shift; in xas_set_range()
1530 xas->xa_sibs = sibs; in xas_set_range()
1554 XA_STATE(xas, xa, 0); in xa_store_range()
1562 xas_lock(&xas); in xa_store_range()
1567 xas_set_order(&xas, last, order); in xa_store_range()
1568 xas_create(&xas, true); in xa_store_range()
1569 if (xas_error(&xas)) in xa_store_range()
1573 xas_set_range(&xas, first, last); in xa_store_range()
1574 xas_store(&xas, entry); in xa_store_range()
1575 if (xas_error(&xas)) in xa_store_range()
1577 first += xas_size(&xas); in xa_store_range()
1580 xas_unlock(&xas); in xa_store_range()
1581 } while (xas_nomem(&xas, gfp)); in xa_store_range()
1583 return xas_result(&xas, NULL); in xa_store_range()
1608 XA_STATE(xas, xa, 0); in __xa_alloc()
1619 xas.xa_index = limit.min; in __xa_alloc()
1620 xas_find_marked(&xas, limit.max, XA_FREE_MARK); in __xa_alloc()
1621 if (xas.xa_node == XAS_RESTART) in __xa_alloc()
1622 xas_set_err(&xas, -EBUSY); in __xa_alloc()
1624 *id = xas.xa_index; in __xa_alloc()
1625 xas_store(&xas, entry); in __xa_alloc()
1626 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_alloc()
1627 } while (__xas_nomem(&xas, gfp)); in __xa_alloc()
1629 return xas_error(&xas); in __xa_alloc()
1695 XA_STATE(xas, xa, index); in __xa_set_mark()
1696 void *entry = xas_load(&xas); in __xa_set_mark()
1699 xas_set_mark(&xas, mark); in __xa_set_mark()
1713 XA_STATE(xas, xa, index); in __xa_clear_mark()
1714 void *entry = xas_load(&xas); in __xa_clear_mark()
1717 xas_clear_mark(&xas, mark); in __xa_clear_mark()
1735 XA_STATE(xas, xa, index); in xa_get_mark()
1739 entry = xas_start(&xas); in xa_get_mark()
1740 while (xas_get_mark(&xas, mark)) { in xa_get_mark()
1743 entry = xas_descend(&xas, xa_to_node(entry)); in xa_get_mark()
1809 XA_STATE(xas, xa, *indexp); in xa_find()
1815 entry = xas_find_marked(&xas, max, filter); in xa_find()
1817 entry = xas_find(&xas, max); in xa_find()
1818 } while (xas_retry(&xas, entry)); in xa_find()
1822 *indexp = xas.xa_index; in xa_find()
1847 XA_STATE(xas, xa, *indexp + 1); in xa_find_after()
1853 entry = xas_find_marked(&xas, max, filter); in xa_find_after()
1855 entry = xas_find(&xas, max); in xa_find_after()
1856 if (xas.xa_node == XAS_BOUNDS) in xa_find_after()
1858 if (xas.xa_shift) { in xa_find_after()
1859 if (xas.xa_index & ((1UL << xas.xa_shift) - 1)) in xa_find_after()
1862 if (xas.xa_offset < (xas.xa_index & XA_CHUNK_MASK)) in xa_find_after()
1865 if (!xas_retry(&xas, entry)) in xa_find_after()
1871 *indexp = xas.xa_index; in xa_find_after()
1876 static unsigned int xas_extract_present(struct xa_state *xas, void **dst, in xas_extract_present() argument
1883 xas_for_each(xas, entry, max) { in xas_extract_present()
1884 if (xas_retry(xas, entry)) in xas_extract_present()
1895 static unsigned int xas_extract_marked(struct xa_state *xas, void **dst, in xas_extract_marked() argument
1902 xas_for_each_marked(xas, entry, max, mark) { in xas_extract_marked()
1903 if (xas_retry(xas, entry)) in xas_extract_marked()
1945 XA_STATE(xas, xa, start); in xa_extract()
1951 return xas_extract_marked(&xas, dst, max, n, filter); in xa_extract()
1952 return xas_extract_present(&xas, dst, max, n); in xa_extract()
1968 XA_STATE(xas, xa, 0); in xa_destroy()
1972 xas.xa_node = NULL; in xa_destroy()
1973 xas_lock_irqsave(&xas, flags); in xa_destroy()
1976 xas_init_marks(&xas); in xa_destroy()
1981 xas_free_nodes(&xas, xa_to_node(entry)); in xa_destroy()
1982 xas_unlock_irqrestore(&xas, flags); in xa_destroy()