Lines Matching defs:nodes
13 * pivots. In the case of dense nodes, the pivots are implied by the position
23 * The following illustrates the layout of a range64 nodes slots and pivots.
39 * Internal (non-leaf) nodes contain pointers to other nodes.
40 * Leaf nodes contain entries.
71 * * MA_STATE_PREALLOC - Preallocated nodes, WARN_ON allocation
145 struct ma_topiary *free; /* nodes to be freed */
163 static inline int mt_alloc_bulk(gfp_t gfp, size_t size, void **nodes)
165 return kmem_cache_alloc_bulk(maple_node_cache, gfp, size, nodes);
168 static inline void mt_free_bulk(size_t size, void __rcu **nodes)
170 kmem_cache_free_bulk(maple_node_cache, size, (void **)nodes);
385 * Excluding root, the parent pointer is 256B aligned like all other tree nodes.
393 * 0x?00 = 16 bit nodes
394 * 0x010 = 32 bit nodes
395 * 0x110 = 64 bit nodes
577 * mas_allocated() - Get the number of nodes allocated in a maple state.
581 * allocated node or to the number of requested nodes to allocate. If bit 0 is
582 * set, then the alloc contains the number of requested nodes. If there is an
583 * allocated node, then the total allocated nodes is in that node.
585 * Return: The total number of nodes allocated
966 * ma_set_meta_gap() - Set the largest gap location in a nodes metadata
981 * mat_add() - Add a @dead_enode to the ma_topiary of a list of dead nodes.
982 * @mat - the ma_topiary, a linked list of dead nodes.
1005 * mas_mat_destroy() - Free all nodes and subtrees in a dead list.
1007 * @mat - the ma_topiary linked list of dead nodes to free.
1241 * mas_alloc_nodes() - Allocate nodes into a maple state
1333 * mas_node_count() - Check if enough nodes are allocated and request more if
1334 * there is not enough nodes.
1336 * @count: The number of nodes needed
1350 * mas_node_count() - Check if enough nodes are allocated and request more if
1351 * there is not enough nodes.
1353 * @count: The number of nodes needed
1386 /* Tree with nodes */
1673 * mas_update_gap() - Update a nodes gaps and propagate up if necessary.
1699 * mas_adopt_children() - Set the parent pointer of all nodes in @parent to
1901 * that overwrites the end and beginning of two full nodes. The result is a set
1902 * of entries that cannot be stored in 2 nodes. Sometimes, these two nodes can
1903 * also be located in different parent nodes which are also full. This can
2233 * Uses mas_slot_locked() and does not need to worry about dead nodes.
2293 * mast_spanning_rebalance() - Rebalance nodes with nearest neighbour favouring
2294 * the node to the right. Checking the nodes to the right then the left at each
2389 * mas_mab_to_node() - Set up right and middle nodes
2501 * mast_set_split_parents() - Helper function to set three nodes parents. Slot
2539 * @mas: The maple state for pushing nodes
2564 * the dead subtrees and topiary the nodes that are no longer of use.
2571 * of the old entries as they may have more nodes below replaced. Nodes within
2619 /* Collect the old nodes that need to be discarded */
2687 * mast_cp_to_nodes() - Copy data out to nodes.
2846 * mas_spanning_rebalance() - Rebalance across two nodes which may not be peers.
2855 * nodes that will remain active by using orig_l_mas->index and orig_l_mas->last
2893 * right, or rebalancing against left or right nodes is employed to avoid
2895 * the tree is created, there may be a mix of new and old nodes. The old nodes
2946 /* rebalancing from other nodes may require another loop. */
2987 * Rebalance two nodes into a single node or two new nodes that are sufficient.
3201 * @skip: The number of entries to skip for new nodes insertion.
3242 * nodes.
3370 * and right nodes after a split.
3402 * or "pushing right" and is similar to the B* tree, except the nodes left or
3622 * Uses mas_slot_locked() and does not need to worry about dead nodes.
3815 * and new nodes where necessary, then place the sub-tree in the actual tree.
3836 * A store operation that spans multiple nodes is called a spanning
3841 * The data in the two nodes are combined into a single node, two nodes,
3842 * or possibly three nodes (see the 3-way split above). A ``NULL``
4698 * Restarts on dead nodes.
4736 /* dense nodes. */
5467 * mas_preallocate() - Preallocate enough nodes for a store operation
5498 /* Exact fit, no nodes needed. */
5505 /* Slot store, does not require additional nodes */
5550 * the right if necessary. Frees any allocated nodes associated with this maple
5600 * This will attempt to pre-allocate enough nodes to store the expected number
5603 * to ensure any unused nodes are freed.
5621 * of nodes during the operation.
5638 /* Internal nodes */
5640 /* Add working room for split (2 nodes) + new parents */
5683 *entry = mas_walk(mas); /* Retries on dead nodes handled by mas_walk */
5721 /* Retries on dead nodes handled by mas_next_slot */
5744 /* Retries on dead nodes handled by mas_next_slot */
5834 * searchable nodes.
5857 * searchable nodes.
6003 /* Retries on dead nodes handled by mas_next_slot */
6027 /* Retries on dead nodes handled by mas_next_slot */
6128 /* Retries on dead nodes handled by mas_prev_slot */
6154 /* Retries on dead nodes handled by mas_prev_slot */
6480 * __mt_destroy() - Walk and free all nodes of a locked maple tree.