Lines Matching refs:xas
36 static inline void xas_lock_type(struct xa_state *xas, unsigned int lock_type) in xas_lock_type() argument
39 xas_lock_irq(xas); in xas_lock_type()
41 xas_lock_bh(xas); in xas_lock_type()
43 xas_lock(xas); in xas_lock_type()
46 static inline void xas_unlock_type(struct xa_state *xas, unsigned int lock_type) in xas_unlock_type() argument
49 xas_unlock_irq(xas); in xas_unlock_type()
51 xas_unlock_bh(xas); in xas_unlock_type()
53 xas_unlock(xas); in xas_unlock_type()
124 static void xas_squash_marks(const struct xa_state *xas) in xas_squash_marks() argument
127 unsigned int limit = xas->xa_offset + xas->xa_sibs + 1; in xas_squash_marks()
129 if (!xas->xa_sibs) in xas_squash_marks()
133 unsigned long *marks = xas->xa_node->marks[mark]; in xas_squash_marks()
134 if (find_next_bit(marks, limit, xas->xa_offset + 1) == limit) in xas_squash_marks()
136 __set_bit(xas->xa_offset, marks); in xas_squash_marks()
137 bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs); in xas_squash_marks()
147 static void xas_set_offset(struct xa_state *xas) in xas_set_offset() argument
149 xas->xa_offset = get_offset(xas->xa_index, xas->xa_node); in xas_set_offset()
153 static void xas_move_index(struct xa_state *xas, unsigned long offset) in xas_move_index() argument
155 unsigned int shift = xas->xa_node->shift; in xas_move_index()
156 xas->xa_index &= ~XA_CHUNK_MASK << shift; in xas_move_index()
157 xas->xa_index += offset << shift; in xas_move_index()
160 static void xas_advance(struct xa_state *xas) in xas_advance() argument
162 xas->xa_offset++; in xas_advance()
163 xas_move_index(xas, xas->xa_offset); in xas_advance()
166 static void *set_bounds(struct xa_state *xas) in set_bounds() argument
168 xas->xa_node = XAS_BOUNDS; in set_bounds()
179 static void *xas_start(struct xa_state *xas) in xas_start() argument
183 if (xas_valid(xas)) in xas_start()
184 return xas_reload(xas); in xas_start()
185 if (xas_error(xas)) in xas_start()
188 entry = xa_head(xas->xa); in xas_start()
190 if (xas->xa_index) in xas_start()
191 return set_bounds(xas); in xas_start()
193 if ((xas->xa_index >> xa_to_node(entry)->shift) > XA_CHUNK_MASK) in xas_start()
194 return set_bounds(xas); in xas_start()
197 xas->xa_node = NULL; in xas_start()
201 static void *xas_descend(struct xa_state *xas, struct xa_node *node) in xas_descend() argument
203 unsigned int offset = get_offset(xas->xa_index, node); in xas_descend()
204 void *entry = xa_entry(xas->xa, node, offset); in xas_descend()
206 xas->xa_node = node; in xas_descend()
209 entry = xa_entry(xas->xa, node, offset); in xas_descend()
212 xas->xa_offset = offset; in xas_descend()
231 void *xas_load(struct xa_state *xas) in xas_load() argument
233 void *entry = xas_start(xas); in xas_load()
238 if (xas->xa_shift > node->shift) in xas_load()
240 entry = xas_descend(xas, node); in xas_load()
267 static void xas_destroy(struct xa_state *xas) in xas_destroy() argument
269 struct xa_node *next, *node = xas->xa_alloc; in xas_destroy()
275 xas->xa_alloc = node = next; in xas_destroy()
297 bool xas_nomem(struct xa_state *xas, gfp_t gfp) in xas_nomem() argument
299 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in xas_nomem()
300 xas_destroy(xas); in xas_nomem()
303 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in xas_nomem()
305 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp); in xas_nomem()
306 if (!xas->xa_alloc) in xas_nomem()
308 xas->xa_alloc->parent = NULL; in xas_nomem()
309 XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list)); in xas_nomem()
310 xas->xa_node = XAS_RESTART; in xas_nomem()
324 static bool __xas_nomem(struct xa_state *xas, gfp_t gfp) in __xas_nomem() argument
325 __must_hold(xas->xa->xa_lock) in __xas_nomem()
327 unsigned int lock_type = xa_lock_type(xas->xa); in __xas_nomem()
329 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in __xas_nomem()
330 xas_destroy(xas); in __xas_nomem()
333 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in __xas_nomem()
336 xas_unlock_type(xas, lock_type); in __xas_nomem()
337 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp); in __xas_nomem()
338 xas_lock_type(xas, lock_type); in __xas_nomem()
340 xas->xa_alloc = kmem_cache_alloc(radix_tree_node_cachep, gfp); in __xas_nomem()
342 if (!xas->xa_alloc) in __xas_nomem()
344 xas->xa_alloc->parent = NULL; in __xas_nomem()
345 XA_NODE_BUG_ON(xas->xa_alloc, !list_empty(&xas->xa_alloc->private_list)); in __xas_nomem()
346 xas->xa_node = XAS_RESTART; in __xas_nomem()
350 static void xas_update(struct xa_state *xas, struct xa_node *node) in xas_update() argument
352 if (xas->xa_update) in xas_update()
353 xas->xa_update(node); in xas_update()
358 static void *xas_alloc(struct xa_state *xas, unsigned int shift) in xas_alloc() argument
360 struct xa_node *parent = xas->xa_node; in xas_alloc()
361 struct xa_node *node = xas->xa_alloc; in xas_alloc()
363 if (xas_invalid(xas)) in xas_alloc()
367 xas->xa_alloc = NULL; in xas_alloc()
371 if (xas->xa->xa_flags & XA_FLAGS_ACCOUNT) in xas_alloc()
376 xas_set_err(xas, -ENOMEM); in xas_alloc()
382 node->offset = xas->xa_offset; in xas_alloc()
385 xas_update(xas, parent); in xas_alloc()
392 RCU_INIT_POINTER(node->parent, xas->xa_node); in xas_alloc()
393 node->array = xas->xa; in xas_alloc()
400 static unsigned long xas_size(const struct xa_state *xas) in xas_size() argument
402 return (xas->xa_sibs + 1UL) << xas->xa_shift; in xas_size()
412 static unsigned long xas_max(struct xa_state *xas) in xas_max() argument
414 unsigned long max = xas->xa_index; in xas_max()
417 if (xas->xa_shift || xas->xa_sibs) { in xas_max()
418 unsigned long mask = xas_size(xas) - 1; in xas_max()
436 static void xas_shrink(struct xa_state *xas) in xas_shrink() argument
438 struct xarray *xa = xas->xa; in xas_shrink()
439 struct xa_node *node = xas->xa_node; in xas_shrink()
454 xas->xa_node = XAS_BOUNDS; in xas_shrink()
464 xas_update(xas, node); in xas_shrink()
480 static void xas_delete_node(struct xa_state *xas) in xas_delete_node() argument
482 struct xa_node *node = xas->xa_node; in xas_delete_node()
491 parent = xa_parent_locked(xas->xa, node); in xas_delete_node()
492 xas->xa_node = parent; in xas_delete_node()
493 xas->xa_offset = node->offset; in xas_delete_node()
497 xas->xa->xa_head = NULL; in xas_delete_node()
498 xas->xa_node = XAS_BOUNDS; in xas_delete_node()
502 parent->slots[xas->xa_offset] = NULL; in xas_delete_node()
506 xas_update(xas, node); in xas_delete_node()
510 xas_shrink(xas); in xas_delete_node()
522 static void xas_free_nodes(struct xa_state *xas, struct xa_node *top) in xas_free_nodes() argument
528 void *entry = xa_entry_locked(xas->xa, node, offset); in xas_free_nodes()
541 parent = xa_parent_locked(xas->xa, node); in xas_free_nodes()
545 xas_update(xas, node); in xas_free_nodes()
558 static int xas_expand(struct xa_state *xas, void *head) in xas_expand() argument
560 struct xarray *xa = xas->xa; in xas_expand()
563 unsigned long max = xas_max(xas); in xas_expand()
575 xas->xa_node = NULL; in xas_expand()
581 node = xas_alloc(xas, shift); in xas_expand()
616 xas_update(xas, node); in xas_expand()
621 xas->xa_node = node; in xas_expand()
638 static void *xas_create(struct xa_state *xas, bool allow_root) in xas_create() argument
640 struct xarray *xa = xas->xa; in xas_create()
643 struct xa_node *node = xas->xa_node; in xas_create()
645 unsigned int order = xas->xa_shift; in xas_create()
649 xas->xa_node = NULL; in xas_create()
652 shift = xas_expand(xas, entry); in xas_create()
659 } else if (xas_error(xas)) { in xas_create()
662 unsigned int offset = xas->xa_offset; in xas_create()
676 node = xas_alloc(xas, shift); in xas_create()
687 entry = xas_descend(xas, node); in xas_create()
688 slot = &node->slots[xas->xa_offset]; in xas_create()
703 void xas_create_range(struct xa_state *xas) in xas_create_range() argument
705 unsigned long index = xas->xa_index; in xas_create_range()
706 unsigned char shift = xas->xa_shift; in xas_create_range()
707 unsigned char sibs = xas->xa_sibs; in xas_create_range()
709 xas->xa_index |= ((sibs + 1UL) << shift) - 1; in xas_create_range()
710 if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift) in xas_create_range()
711 xas->xa_offset |= sibs; in xas_create_range()
712 xas->xa_shift = 0; in xas_create_range()
713 xas->xa_sibs = 0; in xas_create_range()
716 xas_create(xas, true); in xas_create_range()
717 if (xas_error(xas)) in xas_create_range()
719 if (xas->xa_index <= (index | XA_CHUNK_MASK)) in xas_create_range()
721 xas->xa_index -= XA_CHUNK_SIZE; in xas_create_range()
724 struct xa_node *node = xas->xa_node; in xas_create_range()
727 xas->xa_node = xa_parent_locked(xas->xa, node); in xas_create_range()
728 xas->xa_offset = node->offset - 1; in xas_create_range()
735 xas->xa_shift = shift; in xas_create_range()
736 xas->xa_sibs = sibs; in xas_create_range()
737 xas->xa_index = index; in xas_create_range()
740 xas->xa_index = index; in xas_create_range()
741 if (xas->xa_node) in xas_create_range()
742 xas_set_offset(xas); in xas_create_range()
746 static void update_node(struct xa_state *xas, struct xa_node *node, in update_node() argument
756 xas_update(xas, node); in update_node()
758 xas_delete_node(xas); in update_node()
774 void *xas_store(struct xa_state *xas, void *entry) in xas_store() argument
777 void __rcu **slot = &xas->xa->xa_head; in xas_store()
786 first = xas_create(xas, allow_root); in xas_store()
788 first = xas_load(xas); in xas_store()
791 if (xas_invalid(xas)) in xas_store()
793 node = xas->xa_node; in xas_store()
794 if (node && (xas->xa_shift < node->shift)) in xas_store()
795 xas->xa_sibs = 0; in xas_store()
796 if ((first == entry) && !xas->xa_sibs) in xas_store()
800 offset = xas->xa_offset; in xas_store()
801 max = xas->xa_offset + xas->xa_sibs; in xas_store()
804 if (xas->xa_sibs) in xas_store()
805 xas_squash_marks(xas); in xas_store()
808 xas_init_marks(xas); in xas_store()
820 xas_free_nodes(xas, xa_to_node(next)); in xas_store()
829 entry = xa_mk_sibling(xas->xa_offset); in xas_store()
834 next = xa_entry_locked(xas->xa, node, ++offset); in xas_store()
843 update_node(xas, node, count, values); in xas_store()
856 bool xas_get_mark(const struct xa_state *xas, xa_mark_t mark) in xas_get_mark() argument
858 if (xas_invalid(xas)) in xas_get_mark()
860 if (!xas->xa_node) in xas_get_mark()
861 return xa_marked(xas->xa, mark); in xas_get_mark()
862 return node_get_mark(xas->xa_node, xas->xa_offset, mark); in xas_get_mark()
875 void xas_set_mark(const struct xa_state *xas, xa_mark_t mark) in xas_set_mark() argument
877 struct xa_node *node = xas->xa_node; in xas_set_mark()
878 unsigned int offset = xas->xa_offset; in xas_set_mark()
880 if (xas_invalid(xas)) in xas_set_mark()
887 node = xa_parent_locked(xas->xa, node); in xas_set_mark()
890 if (!xa_marked(xas->xa, mark)) in xas_set_mark()
891 xa_mark_set(xas->xa, mark); in xas_set_mark()
904 void xas_clear_mark(const struct xa_state *xas, xa_mark_t mark) in xas_clear_mark() argument
906 struct xa_node *node = xas->xa_node; in xas_clear_mark()
907 unsigned int offset = xas->xa_offset; in xas_clear_mark()
909 if (xas_invalid(xas)) in xas_clear_mark()
919 node = xa_parent_locked(xas->xa, node); in xas_clear_mark()
922 if (xa_marked(xas->xa, mark)) in xas_clear_mark()
923 xa_mark_clear(xas->xa, mark); in xas_clear_mark()
938 void xas_init_marks(const struct xa_state *xas) in xas_init_marks() argument
943 if (xa_track_free(xas->xa) && mark == XA_FREE_MARK) in xas_init_marks()
944 xas_set_mark(xas, mark); in xas_init_marks()
946 xas_clear_mark(xas, mark); in xas_init_marks()
1002 void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order, in xas_split_alloc() argument
1006 unsigned int mask = xas->xa_sibs; in xas_split_alloc()
1009 if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT < order)) in xas_split_alloc()
1011 if (xas->xa_shift + XA_CHUNK_SHIFT > order) in xas_split_alloc()
1022 node->array = xas->xa; in xas_split_alloc()
1031 RCU_INIT_POINTER(node->parent, xas->xa_alloc); in xas_split_alloc()
1032 xas->xa_alloc = node; in xas_split_alloc()
1037 xas_destroy(xas); in xas_split_alloc()
1038 xas_set_err(xas, -ENOMEM); in xas_split_alloc()
1052 void xas_split(struct xa_state *xas, void *entry, unsigned int order) in xas_split() argument
1057 void *curr = xas_load(xas); in xas_split()
1060 node = xas->xa_node; in xas_split()
1064 marks = node_get_marks(node, xas->xa_offset); in xas_split()
1066 offset = xas->xa_offset + sibs; in xas_split()
1068 if (xas->xa_shift < node->shift) { in xas_split()
1069 struct xa_node *child = xas->xa_alloc; in xas_split()
1071 xas->xa_alloc = rcu_dereference_raw(child->parent); in xas_split()
1083 xas_update(xas, child); in xas_split()
1085 unsigned int canon = offset - xas->xa_sibs; in xas_split()
1093 (xas->xa_sibs + 1); in xas_split()
1095 } while (offset-- > xas->xa_offset); in xas_split()
1098 xas_update(xas, node); in xas_split()
1118 void xas_pause(struct xa_state *xas) in xas_pause() argument
1120 struct xa_node *node = xas->xa_node; in xas_pause()
1122 if (xas_invalid(xas)) in xas_pause()
1125 xas->xa_node = XAS_RESTART; in xas_pause()
1127 unsigned long offset = xas->xa_offset; in xas_pause()
1129 if (!xa_is_sibling(xa_entry(xas->xa, node, offset))) in xas_pause()
1132 xas->xa_index += (offset - xas->xa_offset) << node->shift; in xas_pause()
1133 if (xas->xa_index == 0) in xas_pause()
1134 xas->xa_node = XAS_BOUNDS; in xas_pause()
1136 xas->xa_index++; in xas_pause()
1148 void *__xas_prev(struct xa_state *xas) in __xas_prev() argument
1152 if (!xas_frozen(xas->xa_node)) in __xas_prev()
1153 xas->xa_index--; in __xas_prev()
1154 if (!xas->xa_node) in __xas_prev()
1155 return set_bounds(xas); in __xas_prev()
1156 if (xas_not_node(xas->xa_node)) in __xas_prev()
1157 return xas_load(xas); in __xas_prev()
1159 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node)) in __xas_prev()
1160 xas->xa_offset--; in __xas_prev()
1162 while (xas->xa_offset == 255) { in __xas_prev()
1163 xas->xa_offset = xas->xa_node->offset - 1; in __xas_prev()
1164 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_prev()
1165 if (!xas->xa_node) in __xas_prev()
1166 return set_bounds(xas); in __xas_prev()
1170 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_prev()
1174 xas->xa_node = xa_to_node(entry); in __xas_prev()
1175 xas_set_offset(xas); in __xas_prev()
1187 void *__xas_next(struct xa_state *xas) in __xas_next() argument
1191 if (!xas_frozen(xas->xa_node)) in __xas_next()
1192 xas->xa_index++; in __xas_next()
1193 if (!xas->xa_node) in __xas_next()
1194 return set_bounds(xas); in __xas_next()
1195 if (xas_not_node(xas->xa_node)) in __xas_next()
1196 return xas_load(xas); in __xas_next()
1198 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node)) in __xas_next()
1199 xas->xa_offset++; in __xas_next()
1201 while (xas->xa_offset == XA_CHUNK_SIZE) { in __xas_next()
1202 xas->xa_offset = xas->xa_node->offset + 1; in __xas_next()
1203 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_next()
1204 if (!xas->xa_node) in __xas_next()
1205 return set_bounds(xas); in __xas_next()
1209 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_next()
1213 xas->xa_node = xa_to_node(entry); in __xas_next()
1214 xas_set_offset(xas); in __xas_next()
1235 void *xas_find(struct xa_state *xas, unsigned long max) in xas_find() argument
1239 if (xas_error(xas) || xas->xa_node == XAS_BOUNDS) in xas_find()
1241 if (xas->xa_index > max) in xas_find()
1242 return set_bounds(xas); in xas_find()
1244 if (!xas->xa_node) { in xas_find()
1245 xas->xa_index = 1; in xas_find()
1246 return set_bounds(xas); in xas_find()
1247 } else if (xas->xa_node == XAS_RESTART) { in xas_find()
1248 entry = xas_load(xas); in xas_find()
1249 if (entry || xas_not_node(xas->xa_node)) in xas_find()
1251 } else if (!xas->xa_node->shift && in xas_find()
1252 xas->xa_offset != (xas->xa_index & XA_CHUNK_MASK)) { in xas_find()
1253 xas->xa_offset = ((xas->xa_index - 1) & XA_CHUNK_MASK) + 1; in xas_find()
1256 xas_advance(xas); in xas_find()
1258 while (xas->xa_node && (xas->xa_index <= max)) { in xas_find()
1259 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) { in xas_find()
1260 xas->xa_offset = xas->xa_node->offset + 1; in xas_find()
1261 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find()
1265 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find()
1267 xas->xa_node = xa_to_node(entry); in xas_find()
1268 xas->xa_offset = 0; in xas_find()
1274 xas_advance(xas); in xas_find()
1277 if (!xas->xa_node) in xas_find()
1278 xas->xa_node = XAS_BOUNDS; in xas_find()
1304 void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark) in xas_find_marked() argument
1310 if (xas_error(xas)) in xas_find_marked()
1312 if (xas->xa_index > max) in xas_find_marked()
1315 if (!xas->xa_node) { in xas_find_marked()
1316 xas->xa_index = 1; in xas_find_marked()
1318 } else if (xas_top(xas->xa_node)) { in xas_find_marked()
1320 entry = xa_head(xas->xa); in xas_find_marked()
1321 xas->xa_node = NULL; in xas_find_marked()
1322 if (xas->xa_index > max_index(entry)) in xas_find_marked()
1325 if (xa_marked(xas->xa, mark)) in xas_find_marked()
1327 xas->xa_index = 1; in xas_find_marked()
1330 xas->xa_node = xa_to_node(entry); in xas_find_marked()
1331 xas->xa_offset = xas->xa_index >> xas->xa_node->shift; in xas_find_marked()
1334 while (xas->xa_index <= max) { in xas_find_marked()
1335 if (unlikely(xas->xa_offset == XA_CHUNK_SIZE)) { in xas_find_marked()
1336 xas->xa_offset = xas->xa_node->offset + 1; in xas_find_marked()
1337 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find_marked()
1338 if (!xas->xa_node) in xas_find_marked()
1345 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1347 xas->xa_offset = xa_to_sibling(entry); in xas_find_marked()
1348 xas_move_index(xas, xas->xa_offset); in xas_find_marked()
1352 offset = xas_find_chunk(xas, advance, mark); in xas_find_marked()
1353 if (offset > xas->xa_offset) { in xas_find_marked()
1355 xas_move_index(xas, offset); in xas_find_marked()
1357 if ((xas->xa_index - 1) >= max) in xas_find_marked()
1359 xas->xa_offset = offset; in xas_find_marked()
1364 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1365 if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK)) in xas_find_marked()
1369 xas->xa_node = xa_to_node(entry); in xas_find_marked()
1370 xas_set_offset(xas); in xas_find_marked()
1374 if (xas->xa_index > max) in xas_find_marked()
1376 return set_bounds(xas); in xas_find_marked()
1378 xas->xa_node = XAS_RESTART; in xas_find_marked()
1392 void *xas_find_conflict(struct xa_state *xas) in xas_find_conflict() argument
1396 if (xas_error(xas)) in xas_find_conflict()
1399 if (!xas->xa_node) in xas_find_conflict()
1402 if (xas_top(xas->xa_node)) { in xas_find_conflict()
1403 curr = xas_start(xas); in xas_find_conflict()
1408 curr = xas_descend(xas, node); in xas_find_conflict()
1414 if (xas->xa_node->shift > xas->xa_shift) in xas_find_conflict()
1418 if (xas->xa_node->shift == xas->xa_shift) { in xas_find_conflict()
1419 if ((xas->xa_offset & xas->xa_sibs) == xas->xa_sibs) in xas_find_conflict()
1421 } else if (xas->xa_offset == XA_CHUNK_MASK) { in xas_find_conflict()
1422 xas->xa_offset = xas->xa_node->offset; in xas_find_conflict()
1423 xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node); in xas_find_conflict()
1424 if (!xas->xa_node) in xas_find_conflict()
1428 curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset); in xas_find_conflict()
1432 xas->xa_node = xa_to_node(curr); in xas_find_conflict()
1433 xas->xa_offset = 0; in xas_find_conflict()
1434 curr = xa_entry_locked(xas->xa, xas->xa_node, 0); in xas_find_conflict()
1439 xas->xa_offset -= xas->xa_sibs; in xas_find_conflict()
1454 XA_STATE(xas, xa, index); in xa_load()
1459 entry = xas_load(&xas); in xa_load()
1462 } while (xas_retry(&xas, entry)); in xa_load()
1469 static void *xas_result(struct xa_state *xas, void *curr) in xas_result() argument
1473 if (xas_error(xas)) in xas_result()
1474 curr = xas->xa_node; in xas_result()
1492 XA_STATE(xas, xa, index); in __xa_erase()
1493 return xas_result(&xas, xas_store(&xas, NULL)); in __xa_erase()
1538 XA_STATE(xas, xa, index); in __xa_store()
1547 curr = xas_store(&xas, entry); in __xa_store()
1549 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_store()
1550 } while (__xas_nomem(&xas, gfp)); in __xa_store()
1552 return xas_result(&xas, curr); in __xa_store()
1604 XA_STATE(xas, xa, index); in __xa_cmpxchg()
1611 curr = xas_load(&xas); in __xa_cmpxchg()
1613 xas_store(&xas, entry); in __xa_cmpxchg()
1615 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_cmpxchg()
1617 } while (__xas_nomem(&xas, gfp)); in __xa_cmpxchg()
1619 return xas_result(&xas, curr); in __xa_cmpxchg()
1641 XA_STATE(xas, xa, index); in __xa_insert()
1650 curr = xas_load(&xas); in __xa_insert()
1652 xas_store(&xas, entry); in __xa_insert()
1654 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_insert()
1656 xas_set_err(&xas, -EBUSY); in __xa_insert()
1658 } while (__xas_nomem(&xas, gfp)); in __xa_insert()
1660 return xas_error(&xas); in __xa_insert()
1665 static void xas_set_range(struct xa_state *xas, unsigned long first, in xas_set_range() argument
1672 xas_set(xas, first); in xas_set_range()
1692 xas->xa_shift = shift; in xas_set_range()
1693 xas->xa_sibs = sibs; in xas_set_range()
1717 XA_STATE(xas, xa, 0); in xa_store_range()
1725 xas_lock(&xas); in xa_store_range()
1730 xas_set_order(&xas, last, order); in xa_store_range()
1731 xas_create(&xas, true); in xa_store_range()
1732 if (xas_error(&xas)) in xa_store_range()
1736 xas_set_range(&xas, first, last); in xa_store_range()
1737 xas_store(&xas, entry); in xa_store_range()
1738 if (xas_error(&xas)) in xa_store_range()
1740 first += xas_size(&xas); in xa_store_range()
1743 xas_unlock(&xas); in xa_store_range()
1744 } while (xas_nomem(&xas, gfp)); in xa_store_range()
1746 return xas_result(&xas, NULL); in xa_store_range()
1759 XA_STATE(xas, xa, index); in xa_get_order()
1764 entry = xas_load(&xas); in xa_get_order()
1769 if (!xas.xa_node) in xa_get_order()
1773 unsigned int slot = xas.xa_offset + (1 << order); in xa_get_order()
1777 if (!xa_is_sibling(xas.xa_node->slots[slot])) in xa_get_order()
1782 order += xas.xa_node->shift; in xa_get_order()
1811 XA_STATE(xas, xa, 0); in __xa_alloc()
1822 xas.xa_index = limit.min; in __xa_alloc()
1823 xas_find_marked(&xas, limit.max, XA_FREE_MARK); in __xa_alloc()
1824 if (xas.xa_node == XAS_RESTART) in __xa_alloc()
1825 xas_set_err(&xas, -EBUSY); in __xa_alloc()
1827 *id = xas.xa_index; in __xa_alloc()
1828 xas_store(&xas, entry); in __xa_alloc()
1829 xas_clear_mark(&xas, XA_FREE_MARK); in __xa_alloc()
1830 } while (__xas_nomem(&xas, gfp)); in __xa_alloc()
1832 return xas_error(&xas); in __xa_alloc()
1898 XA_STATE(xas, xa, index); in __xa_set_mark()
1899 void *entry = xas_load(&xas); in __xa_set_mark()
1902 xas_set_mark(&xas, mark); in __xa_set_mark()
1916 XA_STATE(xas, xa, index); in __xa_clear_mark()
1917 void *entry = xas_load(&xas); in __xa_clear_mark()
1920 xas_clear_mark(&xas, mark); in __xa_clear_mark()
1938 XA_STATE(xas, xa, index); in xa_get_mark()
1942 entry = xas_start(&xas); in xa_get_mark()
1943 while (xas_get_mark(&xas, mark)) { in xa_get_mark()
1946 entry = xas_descend(&xas, xa_to_node(entry)); in xa_get_mark()
2012 XA_STATE(xas, xa, *indexp); in xa_find()
2018 entry = xas_find_marked(&xas, max, filter); in xa_find()
2020 entry = xas_find(&xas, max); in xa_find()
2021 } while (xas_retry(&xas, entry)); in xa_find()
2025 *indexp = xas.xa_index; in xa_find()
2030 static bool xas_sibling(struct xa_state *xas) in xas_sibling() argument
2032 struct xa_node *node = xas->xa_node; in xas_sibling()
2038 return (xas->xa_index & mask) > in xas_sibling()
2039 ((unsigned long)xas->xa_offset << node->shift); in xas_sibling()
2062 XA_STATE(xas, xa, *indexp + 1); in xa_find_after()
2065 if (xas.xa_index == 0) in xa_find_after()
2071 entry = xas_find_marked(&xas, max, filter); in xa_find_after()
2073 entry = xas_find(&xas, max); in xa_find_after()
2075 if (xas_invalid(&xas)) in xa_find_after()
2077 if (xas_sibling(&xas)) in xa_find_after()
2079 if (!xas_retry(&xas, entry)) in xa_find_after()
2085 *indexp = xas.xa_index; in xa_find_after()
2090 static unsigned int xas_extract_present(struct xa_state *xas, void **dst, in xas_extract_present() argument
2097 xas_for_each(xas, entry, max) { in xas_extract_present()
2098 if (xas_retry(xas, entry)) in xas_extract_present()
2109 static unsigned int xas_extract_marked(struct xa_state *xas, void **dst, in xas_extract_marked() argument
2116 xas_for_each_marked(xas, entry, max, mark) { in xas_extract_marked()
2117 if (xas_retry(xas, entry)) in xas_extract_marked()
2159 XA_STATE(xas, xa, start); in xa_extract()
2165 return xas_extract_marked(&xas, dst, max, n, filter); in xa_extract()
2166 return xas_extract_present(&xas, dst, max, n); in xa_extract()
2179 struct xa_state xas = { in xa_delete_node() local
2189 xas_store(&xas, NULL); in xa_delete_node()
2205 XA_STATE(xas, xa, 0); in xa_destroy()
2209 xas.xa_node = NULL; in xa_destroy()
2210 xas_lock_irqsave(&xas, flags); in xa_destroy()
2213 xas_init_marks(&xas); in xa_destroy()
2218 xas_free_nodes(&xas, xa_to_node(entry)); in xa_destroy()
2219 xas_unlock_irqrestore(&xas, flags); in xa_destroy()