Lines Matching refs:xa_node
78 static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark) in node_marks()
83 static inline bool node_get_mark(struct xa_node *node, in node_get_mark()
90 static inline bool node_set_mark(struct xa_node *node, unsigned int offset, in node_set_mark()
97 static inline bool node_clear_mark(struct xa_node *node, unsigned int offset, in node_clear_mark()
103 static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark) in node_any_mark()
108 static inline void node_mark_all(struct xa_node *node, xa_mark_t mark) in node_mark_all()
133 unsigned long *marks = xas->xa_node->marks[mark]; in xas_squash_marks()
142 static unsigned int get_offset(unsigned long index, struct xa_node *node) in get_offset()
149 xas->xa_offset = get_offset(xas->xa_index, xas->xa_node); in xas_set_offset()
155 unsigned int shift = xas->xa_node->shift; in xas_move_index()
168 xas->xa_node = XAS_BOUNDS; in set_bounds()
197 xas->xa_node = NULL; in xas_start()
201 static void *xas_descend(struct xa_state *xas, struct xa_node *node) in xas_descend()
206 xas->xa_node = node; in xas_descend()
238 struct xa_node *node = xa_to_node(entry); in xas_load()
256 static void xa_node_free(struct xa_node *node) in xa_node_free()
272 struct xa_node *next, *node = xas->xa_alloc; in xas_destroy()
302 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in xas_nomem()
313 xas->xa_node = XAS_RESTART; in xas_nomem()
332 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in __xas_nomem()
349 xas->xa_node = XAS_RESTART; in __xas_nomem()
353 static void xas_update(struct xa_state *xas, struct xa_node *node) in xas_update()
363 struct xa_node *parent = xas->xa_node; in xas_alloc()
364 struct xa_node *node = xas->xa_alloc; in xas_alloc()
395 RCU_INIT_POINTER(node->parent, xas->xa_node); in xas_alloc()
442 struct xa_node *node = xas->xa_node; in xas_shrink()
457 xas->xa_node = XAS_BOUNDS; in xas_shrink()
485 struct xa_node *node = xas->xa_node; in xas_delete_node()
488 struct xa_node *parent; in xas_delete_node()
495 xas->xa_node = parent; in xas_delete_node()
501 xas->xa_node = XAS_BOUNDS; in xas_delete_node()
525 static void xas_free_nodes(struct xa_state *xas, struct xa_node *top) in xas_free_nodes()
528 struct xa_node *node = top; in xas_free_nodes()
542 struct xa_node *parent; in xas_free_nodes()
564 struct xa_node *node = NULL; in xas_expand()
578 xas->xa_node = NULL; in xas_expand()
624 xas->xa_node = node; in xas_expand()
646 struct xa_node *node = xas->xa_node; in xas_create()
652 xas->xa_node = NULL; in xas_create()
713 if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift) in xas_create_range()
727 struct xa_node *node = xas->xa_node; in xas_create_range()
730 xas->xa_node = xa_parent_locked(xas->xa, node); in xas_create_range()
744 if (xas->xa_node) in xas_create_range()
749 static void update_node(struct xa_state *xas, struct xa_node *node, in update_node()
779 struct xa_node *node; in xas_store()
796 node = xas->xa_node; in xas_store()
863 if (!xas->xa_node) in xas_get_mark()
865 return node_get_mark(xas->xa_node, xas->xa_offset, mark); in xas_get_mark()
880 struct xa_node *node = xas->xa_node; in xas_set_mark()
909 struct xa_node *node = xas->xa_node; in xas_clear_mark()
958 static unsigned int node_get_marks(struct xa_node *node, unsigned int offset) in node_get_marks()
974 static void node_set_marks(struct xa_node *node, unsigned int offset, in node_set_marks()
975 struct xa_node *child, unsigned int marks) in node_set_marks()
1020 struct xa_node *node; in xas_split_alloc()
1060 struct xa_node *node; in xas_split()
1064 node = xas->xa_node; in xas_split()
1073 struct xa_node *child = xas->xa_alloc; in xas_split()
1124 struct xa_node *node = xas->xa_node; in xas_pause()
1129 xas->xa_node = XAS_RESTART; in xas_pause()
1138 xas->xa_node = XAS_BOUNDS; in xas_pause()
1156 if (!xas_frozen(xas->xa_node)) in __xas_prev()
1158 if (!xas->xa_node) in __xas_prev()
1160 if (xas_not_node(xas->xa_node)) in __xas_prev()
1163 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node)) in __xas_prev()
1167 xas->xa_offset = xas->xa_node->offset - 1; in __xas_prev()
1168 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_prev()
1169 if (!xas->xa_node) in __xas_prev()
1174 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_prev()
1178 xas->xa_node = xa_to_node(entry); in __xas_prev()
1195 if (!xas_frozen(xas->xa_node)) in __xas_next()
1197 if (!xas->xa_node) in __xas_next()
1199 if (xas_not_node(xas->xa_node)) in __xas_next()
1202 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node)) in __xas_next()
1206 xas->xa_offset = xas->xa_node->offset + 1; in __xas_next()
1207 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_next()
1208 if (!xas->xa_node) in __xas_next()
1213 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_next()
1217 xas->xa_node = xa_to_node(entry); in __xas_next()
1243 if (xas_error(xas) || xas->xa_node == XAS_BOUNDS) in xas_find()
1248 if (!xas->xa_node) { in xas_find()
1251 } else if (xas->xa_node == XAS_RESTART) { in xas_find()
1253 if (entry || xas_not_node(xas->xa_node)) in xas_find()
1255 } else if (!xas->xa_node->shift && in xas_find()
1262 while (xas->xa_node && (xas->xa_index <= max)) { in xas_find()
1264 xas->xa_offset = xas->xa_node->offset + 1; in xas_find()
1265 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find()
1269 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find()
1271 xas->xa_node = xa_to_node(entry); in xas_find()
1281 if (!xas->xa_node) in xas_find()
1282 xas->xa_node = XAS_BOUNDS; in xas_find()
1319 if (!xas->xa_node) { in xas_find_marked()
1322 } else if (xas_top(xas->xa_node)) { in xas_find_marked()
1325 xas->xa_node = NULL; in xas_find_marked()
1334 xas->xa_node = xa_to_node(entry); in xas_find_marked()
1335 xas->xa_offset = xas->xa_index >> xas->xa_node->shift; in xas_find_marked()
1340 xas->xa_offset = xas->xa_node->offset + 1; in xas_find_marked()
1341 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find_marked()
1342 if (!xas->xa_node) in xas_find_marked()
1349 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1368 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1373 xas->xa_node = xa_to_node(entry); in xas_find_marked()
1382 xas->xa_node = XAS_RESTART; in xas_find_marked()
1403 if (!xas->xa_node) in xas_find_conflict()
1406 if (xas_top(xas->xa_node)) { in xas_find_conflict()
1411 struct xa_node *node = xa_to_node(curr); in xas_find_conflict()
1418 if (xas->xa_node->shift > xas->xa_shift) in xas_find_conflict()
1422 if (xas->xa_node->shift == xas->xa_shift) { in xas_find_conflict()
1426 xas->xa_offset = xas->xa_node->offset; in xas_find_conflict()
1427 xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node); in xas_find_conflict()
1428 if (!xas->xa_node) in xas_find_conflict()
1432 curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset); in xas_find_conflict()
1436 xas->xa_node = xa_to_node(curr); in xas_find_conflict()
1438 curr = xa_entry_locked(xas->xa, xas->xa_node, 0); in xas_find_conflict()
1478 curr = xas->xa_node; in xas_result()
1773 if (!xas.xa_node) in xa_get_order()
1781 if (!xa_is_sibling(xas.xa_node->slots[slot])) in xa_get_order()
1786 order += xas.xa_node->shift; in xa_get_order()
1828 if (xas.xa_node == XAS_RESTART) in __xa_alloc()
2036 struct xa_node *node = xas->xa_node; in xas_sibling()
2181 void xa_delete_node(struct xa_node *node, xa_update_node_t update) in xa_delete_node()
2189 .xa_node = xa_parent_locked(node->array, node), in xa_delete_node()
2213 xas.xa_node = NULL; in xa_destroy()
2228 void xa_dump_node(const struct xa_node *node) in xa_dump_node()
2272 struct xa_node *node = xa_to_node(entry); in xa_dump_entry()