Lines Matching refs:xa_node
80 static inline unsigned long *node_marks(struct xa_node *node, xa_mark_t mark) in node_marks()
85 static inline bool node_get_mark(struct xa_node *node, in node_get_mark()
92 static inline bool node_set_mark(struct xa_node *node, unsigned int offset, in node_set_mark()
99 static inline bool node_clear_mark(struct xa_node *node, unsigned int offset, in node_clear_mark()
105 static inline bool node_any_mark(struct xa_node *node, xa_mark_t mark) in node_any_mark()
110 static inline void node_mark_all(struct xa_node *node, xa_mark_t mark) in node_mark_all()
132 unsigned long *marks = node_marks(xas->xa_node, mark); in xas_squash_marks()
145 static unsigned int get_offset(unsigned long index, struct xa_node *node) in get_offset()
152 xas->xa_offset = get_offset(xas->xa_index, xas->xa_node); in xas_set_offset()
158 unsigned int shift = xas->xa_node->shift; in xas_move_index()
171 xas->xa_node = XAS_BOUNDS; in set_bounds()
200 xas->xa_node = NULL; in xas_start()
205 struct xa_node *node) in xas_descend()
210 xas->xa_node = node; in xas_descend()
242 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()
303 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in xas_nomem()
314 xas->xa_node = XAS_RESTART; in xas_nomem()
333 if (xas->xa_node != XA_ERROR(-ENOMEM)) { in __xas_nomem()
350 xas->xa_node = XAS_RESTART; in __xas_nomem()
354 static void xas_update(struct xa_state *xas, struct xa_node *node) in xas_update()
364 struct xa_node *parent = xas->xa_node; in xas_alloc()
365 struct xa_node *node = xas->xa_alloc; in xas_alloc()
396 RCU_INIT_POINTER(node->parent, xas->xa_node); in xas_alloc()
448 struct xa_node *node = xas->xa_node; in xas_shrink()
463 xas->xa_node = XAS_BOUNDS; in xas_shrink()
491 struct xa_node *node = xas->xa_node; in xas_delete_node()
494 struct xa_node *parent; in xas_delete_node()
501 xas->xa_node = parent; in xas_delete_node()
507 xas->xa_node = XAS_BOUNDS; in xas_delete_node()
531 static void xas_free_nodes(struct xa_state *xas, struct xa_node *top) in xas_free_nodes()
534 struct xa_node *node = top; in xas_free_nodes()
548 struct xa_node *parent; in xas_free_nodes()
570 struct xa_node *node = NULL; in xas_expand()
584 xas->xa_node = NULL; in xas_expand()
630 xas->xa_node = node; in xas_expand()
652 struct xa_node *node = xas->xa_node; in xas_create()
658 xas->xa_node = NULL; in xas_create()
719 if (xas_is_node(xas) && xas->xa_node->shift == xas->xa_shift) in xas_create_range()
733 struct xa_node *node = xas->xa_node; in xas_create_range()
736 xas->xa_node = xa_parent_locked(xas->xa, node); in xas_create_range()
750 if (xas->xa_node) in xas_create_range()
755 static void update_node(struct xa_state *xas, struct xa_node *node, in update_node()
785 struct xa_node *node; in xas_store()
802 node = xas->xa_node; in xas_store()
869 if (!xas->xa_node) in xas_get_mark()
871 return node_get_mark(xas->xa_node, xas->xa_offset, mark); in xas_get_mark()
886 struct xa_node *node = xas->xa_node; in xas_set_mark()
915 struct xa_node *node = xas->xa_node; in xas_clear_mark()
964 static unsigned int node_get_marks(struct xa_node *node, unsigned int offset) in node_get_marks()
980 static inline void node_mark_slots(struct xa_node *node, unsigned int sibs, in node_mark_slots()
993 static void node_set_marks(struct xa_node *node, unsigned int offset, in node_set_marks()
994 struct xa_node *child, unsigned int sibs, in node_set_marks()
1012 struct xa_node *node, void *entry) in __xas_init_node_for_split()
1057 struct xa_node *node; in xas_split_alloc()
1090 struct xa_node *node; in xas_split()
1094 node = xas->xa_node; in xas_split()
1103 struct xa_node *child = xas->xa_alloc; in xas_split()
1179 struct xa_node *node; in xas_try_split()
1184 node = xas->xa_node; in xas_try_split()
1196 struct xa_node *child = xas->xa_alloc; in xas_try_split()
1277 struct xa_node *node = xas->xa_node; in xas_pause()
1282 xas->xa_node = XAS_RESTART; in xas_pause()
1292 xas->xa_node = XAS_BOUNDS; in xas_pause()
1310 if (!xas_frozen(xas->xa_node)) in __xas_prev()
1312 if (!xas->xa_node) in __xas_prev()
1314 if (xas_not_node(xas->xa_node)) in __xas_prev()
1317 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node)) in __xas_prev()
1321 xas->xa_offset = xas->xa_node->offset - 1; in __xas_prev()
1322 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_prev()
1323 if (!xas->xa_node) in __xas_prev()
1328 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_prev()
1332 xas->xa_node = xa_to_node(entry); in __xas_prev()
1349 if (!xas_frozen(xas->xa_node)) in __xas_next()
1351 if (!xas->xa_node) in __xas_next()
1353 if (xas_not_node(xas->xa_node)) in __xas_next()
1356 if (xas->xa_offset != get_offset(xas->xa_index, xas->xa_node)) in __xas_next()
1360 xas->xa_offset = xas->xa_node->offset + 1; in __xas_next()
1361 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in __xas_next()
1362 if (!xas->xa_node) in __xas_next()
1367 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in __xas_next()
1371 xas->xa_node = xa_to_node(entry); in __xas_next()
1397 if (xas_error(xas) || xas->xa_node == XAS_BOUNDS) in xas_find()
1402 if (!xas->xa_node) { in xas_find()
1405 } else if (xas->xa_node == XAS_RESTART) { in xas_find()
1407 if (entry || xas_not_node(xas->xa_node)) in xas_find()
1409 } else if (!xas->xa_node->shift && in xas_find()
1416 while (xas->xa_node && (xas->xa_index <= max)) { in xas_find()
1418 xas->xa_offset = xas->xa_node->offset + 1; in xas_find()
1419 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find()
1423 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find()
1425 xas->xa_node = xa_to_node(entry); in xas_find()
1435 if (!xas->xa_node) in xas_find()
1436 xas->xa_node = XAS_BOUNDS; in xas_find()
1473 if (!xas->xa_node) { in xas_find_marked()
1476 } else if (xas_top(xas->xa_node)) { in xas_find_marked()
1479 xas->xa_node = NULL; in xas_find_marked()
1488 xas->xa_node = xa_to_node(entry); in xas_find_marked()
1489 xas->xa_offset = xas->xa_index >> xas->xa_node->shift; in xas_find_marked()
1494 xas->xa_offset = xas->xa_node->offset + 1; in xas_find_marked()
1495 xas->xa_node = xa_parent(xas->xa, xas->xa_node); in xas_find_marked()
1496 if (!xas->xa_node) in xas_find_marked()
1503 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1522 entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset); in xas_find_marked()
1529 xas->xa_node = xa_to_node(entry); in xas_find_marked()
1538 xas->xa_node = XAS_RESTART; in xas_find_marked()
1559 if (!xas->xa_node) in xas_find_conflict()
1562 if (xas_top(xas->xa_node)) { in xas_find_conflict()
1567 struct xa_node *node = xa_to_node(curr); in xas_find_conflict()
1574 if (xas->xa_node->shift > xas->xa_shift) in xas_find_conflict()
1578 if (xas->xa_node->shift == xas->xa_shift) { in xas_find_conflict()
1582 xas->xa_offset = xas->xa_node->offset; in xas_find_conflict()
1583 xas->xa_node = xa_parent_locked(xas->xa, xas->xa_node); in xas_find_conflict()
1584 if (!xas->xa_node) in xas_find_conflict()
1588 curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset); in xas_find_conflict()
1592 xas->xa_node = xa_to_node(curr); in xas_find_conflict()
1594 curr = xa_entry_locked(xas->xa, xas->xa_node, 0); in xas_find_conflict()
1630 curr = xas->xa_node; in xas_result()
1917 if (!xas->xa_node) in xas_get_order()
1925 if (!xa_is_sibling(xa_entry(xas->xa, xas->xa_node, slot))) in xas_get_order()
1930 order += xas->xa_node->shift; in xas_get_order()
1995 if (xas.xa_node == XAS_RESTART) in __xa_alloc()
2206 struct xa_node *node = xas->xa_node; in xas_sibling()
2351 void xa_delete_node(struct xa_node *node, xa_update_node_t update) in xa_delete_node()
2359 .xa_node = xa_parent_locked(node->array, node), in xa_delete_node()
2383 xas.xa_node = NULL; in xa_destroy()
2398 void xa_dump_node(const struct xa_node *node) in xa_dump_node()
2442 struct xa_node *node = xa_to_node(entry); in xa_dump_entry()