Home
last modified time | relevance | path

Searched +full:root +full:- +full:node (Results 1 – 25 of 857) sorted by relevance

12345678910>>...35

/linux/lib/
H A Dradix-tree.c1 // SPDX-License-Identifier: GPL-2.0-or-later
24 #include <linux/radix-tree.h>
30 #include "radix-tree.h"
33 * Radix tree node cache.
38 * The radix tree is variable-height, so an insert operation not only has
45 * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
48 #define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
54 #define IDR_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(int) - 1)
57 #define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1)
60 * Per-cpu pool of preloaded nodes
[all …]
H A Drbtree.c1 // SPDX-License-Identifier: GPL-2.0-or-later
16 * red-black trees properties: https://en.wikipedia.org/wiki/Rbtree
18 * 1) A node is either red or black
19 * 2) The root is black
21 * 4) Both children of every red node are black
22 * 5) Every simple path from root to leaves contains the same number
26 * consecutive red nodes in a path and every red node is therefore followed by
42 * These two requirements will allow lockless iteration of the tree -- not
47 * and that it will indeed complete -- does not get stuck in a loop.
61 rb->__rb_parent_color += RB_BLACK; in rb_set_black()
[all …]
H A Dbootconfig.c1 // SPDX-License-Identifier: GPL-2.0
25 /* embedded_bootconfig_data is defined in bootconfig-data.S */
31 *size = embedded_bootconfig_data_end - embedded_bootconfig_data; in xbc_get_embedded_bootconfig()
38 * Extra Boot Config (XBC) is given as tree-structured ascii text of
39 * key-value pairs on memory.
40 * xbc_parse() parses the text to build a simple tree. Each tree node is
41 * simply a key word or a value. A key node may have a next key node or/and
42 * a child node (both key and value). A value node may have a next value
43 * node (for array).
83 * xbc_get_info() - Get the information of loaded boot config
[all …]
/linux/scripts/gdb/linux/
H A Drbtree.py1 # SPDX-License-Identifier: GPL-2.0
12 def rb_inorder_for_each(root): argument
13 def inorder(node): argument
14 if node:
15 yield from inorder(node['rb_left'])
16 yield node
17 yield from inorder(node['rb_right'])
19 yield from inorder(root['rb_node'])
21 def rb_inorder_for_each_entry(root, gdbtype, member): argument
22 for node in rb_inorder_for_each(root):
[all …]
H A Dradixtree.py1 # SPDX-License-Identifier: GPL-2.0
20 def is_internal_node(node): argument
22 …return ((node.cast(long_type) & constants.LX_RADIX_TREE_ENTRY_MASK) == constants.LX_RADIX_TREE_INT…
24 def entry_to_node(node): argument
26 node_type = node.type
27 indirect_ptr = node.cast(long_type) & ~constants.LX_RADIX_TREE_INTERNAL_NODE
30 def node_maxindex(node): argument
31 return (constants.LX_RADIX_TREE_MAP_SIZE << node['shift']) - 1
33 def lookup(root, index): argument
34 if root.type == radix_tree_root_type.get_type().pointer():
[all …]
/linux/fs/btrfs/
H A Ddelayed-inode.c1 // SPDX-License-Identifier: GPL-2.0
13 #include "delayed-inode.h"
14 #include "disk-io.h"
18 #include "inode-item.h"
19 #include "space-info.h"
21 #include "file-item.h"
33 return -ENOMEM; in btrfs_delayed_inode_init()
44 atomic_set(&delayed_root->items, 0); in btrfs_init_delayed_root()
45 atomic_set(&delayed_root->items_seq, 0); in btrfs_init_delayed_root()
46 delayed_root->nodes = 0; in btrfs_init_delayed_root()
[all …]
H A Drelocation.c1 // SPDX-License-Identifier: GPL-2.0
12 #include <linux/error-injection.h>
14 #include "disk-io.h"
19 #include "async-thread.h"
20 #include "free-space-cache.h"
22 #include "print-tree.h"
23 #include "delalloc-space.h"
24 #include "block-group.h"
29 #include "inode-item.h"
30 #include "space-info.h"
[all …]
H A Dmisc.h1 /* SPDX-License-Identifier: GPL-2.0 */
14 * Enumerate bits using enum autoincrement. Define the @name as the n-th bit.
50 return n != 0 && (n & (n - 1)) == 0; in is_power_of_two_u64()
69 static inline struct rb_node *rb_simple_search(const struct rb_root *root, u64 bytenr) in rb_simple_search() argument
71 struct rb_node *node = root->rb_node; in rb_simple_search() local
74 while (node) { in rb_simple_search()
75 entry = rb_entry(node, struct rb_simple_node, rb_node); in rb_simple_search()
77 if (bytenr < entry->bytenr) in rb_simple_search()
78 node = node->rb_left; in rb_simple_search()
79 else if (bytenr > entry->bytenr) in rb_simple_search()
[all …]
H A Dordered-data.c1 // SPDX-License-Identifier: GPL-2.0
16 #include "disk-io.h"
18 #include "delalloc-space.h"
22 #include "block-group.h"
28 if (entry->file_offset + entry->num_bytes < entry->file_offset) in entry_end()
29 return (u64)-1; in entry_end()
30 return entry->file_offset + entry->num_bytes; in entry_end()
33 /* returns NULL if the insertion worked, or it returns the node it did find
36 static struct rb_node *tree_insert(struct rb_root *root, u64 file_offset, in tree_insert() argument
37 struct rb_node *node) in tree_insert() argument
[all …]
H A Dbackref.c1 // SPDX-License-Identifier: GPL-2.0
10 #include "disk-io.h"
14 #include "delayed-ref.h"
17 #include "tree-mod-log.h"
20 #include "extent-tree.h"
22 #include "tree-checker.h"
42 u64 offset = key->offset; in check_extent_in_eb()
48 if (!ctx->ignore_extent_item_pos && in check_extent_in_eb()
56 if (ctx->extent_item_pos < data_offset || in check_extent_in_eb()
57 ctx->extent_item_pos >= data_offset + data_len) in check_extent_in_eb()
[all …]
/linux/tools/lib/
H A Drbtree.c1 // SPDX-License-Identifier: GPL-2.0-or-later
16 * red-black trees properties: https://en.wikipedia.org/wiki/Rbtree
18 * 1) A node is either red or black
19 * 2) The root is black
21 * 4) Both children of every red node are black
22 * 5) Every simple path from root t
76 __rb_rotate_set_parents(struct rb_node * old,struct rb_node * new,struct rb_root * root,int color) __rb_rotate_set_parents() argument
85 __rb_insert(struct rb_node * node,struct rb_root * root,void (* augment_rotate)(struct rb_node * old,struct rb_node * new)) __rb_insert() argument
227 ____rb_erase_color(struct rb_node * parent,struct rb_root * root,void (* augment_rotate)(struct rb_node * old,struct rb_node * new)) ____rb_erase_color() argument
230 struct rb_node *node = NULL, *sibling, *tmp1, *tmp2; ____rb_erase_color() local
410 __rb_erase_color(struct rb_node * parent,struct rb_root * root,void (* augment_rotate)(struct rb_node * old,struct rb_node * new)) __rb_erase_color() argument
423 dummy_propagate(struct rb_node * node,struct rb_node * stop) dummy_propagate() argument
433 rb_insert_color(struct rb_node * node,struct rb_root * root) rb_insert_color() argument
438 rb_erase(struct rb_node * node,struct rb_root * root) rb_erase() argument
453 __rb_insert_augmented(struct rb_node * node,struct rb_root * root,void (* augment_rotate)(struct rb_node * old,struct rb_node * new)) __rb_insert_augmented() argument
462 rb_first(const struct rb_root * root) rb_first() argument
474 rb_last(const struct rb_root * root) rb_last() argument
486 rb_next(const struct rb_node * node) rb_next() argument
517 rb_prev(const struct rb_node * node) rb_prev() argument
546 rb_replace_node(struct rb_node * victim,struct rb_node * new,struct rb_root * root) rb_replace_node() argument
561 rb_left_deepest_node(const struct rb_node * node) rb_left_deepest_node() argument
573 rb_next_postorder(const struct rb_node * node) rb_next_postorder() argument
591 rb_first_postorder(const struct rb_root * root) rb_first_postorder() argument
[all...]
/linux/tools/perf/util/
H A Dstrfilter.c1 // SPDX-License-Identifier: GPL-2.0
19 static void strfilter_node__delete(struct strfilter_node *node) in strfilter_node__delete() argument
21 if (node) { in strfilter_node__delete()
22 if (node->p && !is_operator(*node->p)) in strfilter_node__delete()
23 zfree((char **)&node->p); in strfilter_node__delete()
24 strfilter_node__delete(node->l); in strfilter_node__delete()
25 strfilter_node__delete(node->r); in strfilter_node__delete()
26 free(node); in strfilter_node__delete()
33 strfilter_node__delete(filter->root); in strfilter__delete()
56 if (*(p - 1) == '\\' || (*p == '!' && *(p - 1) == '[')) { in get_token()
[all …]
/linux/include/linux/
H A Drbtree_augmented.h1 /* SPDX-License-Identifier: GPL-2.0-or-later */
20 * Please note - only struct rb_augment_callbacks and the prototypes for
24 * See Documentation/core-api/rbtree.rst for documentation and samples.
28 void (*propagate)(struct rb_node *node, struct rb_node *stop);
33 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
40 * leading to the inserted node, then call rb_link_node() as usual and
47 rb_insert_augmented(struct rb_node *node, struct rb_root *root, in rb_insert_augmented() argument
50 __rb_insert_augmented(node, root, augment->rotate); in rb_insert_augmented()
54 rb_insert_augmented_cached(struct rb_node *node, in rb_insert_augmented_cached() argument
55 struct rb_root_cached *root, bool newleft, in rb_insert_augmented_cached() argument
[all …]
H A Drbtree.h1 /* SPDX-License-Identifier: GPL-2.0-or-later */
14 See Documentation/core-api/rbtree.rst for documentation and samples.
26 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
30 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL) argument
33 #define RB_EMPTY_NODE(node) \ argument
34 ((node)->__rb_parent_color == (unsigned long)(node))
35 #define RB_CLEAR_NODE(node) \ argument
36 ((node)->__rb_parent_color = (unsigned long)(node))
49 /* Postorder iteration - always visit the parent after its children */
53 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
[all …]
/linux/tools/include/linux/
H A Drbtree.h1 /* SPDX-License-Identifier: GPL-2.0-or-later */
14 See Documentation/core-api/rbtree.rst for documentation and samples.
34 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
39 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL) argument
42 #define RB_EMPTY_NODE(node) \ argument
43 ((node)->__rb_parent_color == (unsigned long)(node))
44 #define RB_CLEAR_NODE(node) \ argument
45 ((node)->__rb_parent_color = (unsigned long)(node))
58 /* Postorder iteration - always visit the parent after its children */
62 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
[all …]
H A Drbtree_augmented.h1 /* SPDX-License-Identifier: GPL-2.0-or-later */
22 * Please note - only struct rb_augment_callbacks and the prototypes for
26 * See Documentation/core-api/rbtree.rst for documentation and samples.
30 void (*propagate)(struct rb_node *node, struct rb_node *stop);
35 extern void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
49 rb_insert_augmented(struct rb_node * node,struct rb_root * root,const struct rb_augment_callbacks * augment) rb_insert_augmented() argument
56 rb_insert_augmented_cached(struct rb_node * node,struct rb_root_cached * root,bool newleft,const struct rb_augment_callbacks * augment) rb_insert_augmented_cached() argument
57 rb_insert_augmented_cached(struct rb_node * node,struct rb_root_cached * root,bool newleft,const struct rb_augment_callbacks * augment) rb_insert_augmented_cached() argument
172 __rb_change_child(struct rb_node * old,struct rb_node * new,struct rb_node * parent,struct rb_root * root) __rb_change_child() argument
187 __rb_erase_augmented(struct rb_node * node,struct rb_root * root,const struct rb_augment_callbacks * augment) __rb_erase_augmented() argument
291 rb_erase_augmented(struct rb_node * node,struct rb_root * root,const struct rb_augment_callbacks * augment) rb_erase_augmented() argument
300 rb_erase_augmented_cached(struct rb_node * node,struct rb_root_cached * root,const struct rb_augment_callbacks * augment) rb_erase_augmented_cached() argument
[all...]
H A Dinterval_tree_generic.h1 /* SPDX-License-Identifier: GPL-2.0-or-later */
18 * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
19 * ITSTART(n): start endpoint of ITSTRUCT node n
20 * ITLAST(n): last endpoint of ITSTRUCT node n
24 * Note - before using this, please consider if generic version
38 ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, \
39 struct rb_root_cached *root) \
41 struct rb_node **link = &root->rb_root.rb_node, *rb_parent = NULL; \
42 ITTYPE start = ITSTART(node), last = ITLAST(node); \
49 if (parent->ITSUBTREE < last) \
[all …]
/linux/drivers/net/ethernet/mellanox/mlx5/core/
H A Dfs_core.c14 * - Redistributions of source code must retain the above
18 * - Redistributions in binary form must reproduce the above
353 static void del_hw_flow_table(struct fs_node *node);
354 static void del_hw_flow_group(struct fs_node *node);
355 static void del_hw_fte(struct fs_node *node);
356 static void del_sw_flow_table(struct fs_node *node);
357 static void del_sw_flow_group(struct fs_node *node);
358 static void del_sw_fte(struct fs_node *node);
359 static void del_sw_prio(struct fs_node *node);
360 static void del_sw_ns(struct fs_node *node);
[all …]
/linux/drivers/block/drbd/
H A Ddrbd_interval.c1 // SPDX-License-Identifier: GPL-2.0-only
7 * interval_end - return end of @node
10 sector_t interval_end(struct rb_node *node) in interval_end() argument
12 struct drbd_interval *this = rb_entry(node, struct drbd_interval, rb); in interval_end()
13 return this->end; in interval_end()
16 #define NODE_END(node) ((node)->sector + ((node)->size >> 9)) argument
22 * drbd_insert_interval - insert a new interval into a tree
25 drbd_insert_interval(struct rb_root *root, struct drbd_interval *this) in drbd_insert_interval() argument
27 struct rb_node **new = &root->rb_node, *parent = NULL; in drbd_insert_interval()
28 sector_t this_end = this->sector + (this->size >> 9); in drbd_insert_interval()
[all …]
/linux/mm/
H A Dinterval_tree.c1 // SPDX-License-Identifier: GPL-2.0-only
3 * mm/interval_tree.c - interval tree for mapping->i_mmap
15 return v->vm_pgoff; in vma_start_pgoff()
20 return v->vm_pgoff + vma_pages(v) - 1; in vma_last_pgoff()
27 /* Insert node immediately after prev in the interval tree */
28 void vma_interval_tree_insert_after(struct vm_area_struct *node, in vma_interval_tree_insert_after() argument
30 struct rb_root_cached *root) in vma_interval_tree_insert_after() argument
34 unsigned long last = vma_last_pgoff(node); in vma_interval_tree_insert_after()
36 VM_BUG_ON_VMA(vma_start_pgoff(node) != vma_start_pgoff(prev), node); in vma_interval_tree_insert_after()
38 if (!prev->shared.rb.rb_right) { in vma_interval_tree_insert_after()
[all …]
/linux/Documentation/core-api/
H A Drbtree.rst2 Red-black Trees (rbtree) in Linux
9 What are red-black trees, and what are they for?
10 ------------------------------------------------
12 Red-black trees are a type of self-balancing binary search tree, used for
19 Red-black trees are similar to AVL trees, but provide faster real-time bounded
26 There are a number of red-black trees in use in the kernel.
29 The high-resolution timer code uses an rbtree to organize outstanding
31 red-black tree. Virtual memory areas (VMAs) are tracked with red-black
38 Linux Weekly News article on red-black trees
41 Wikipedia entry on red-black trees
[all …]
/linux/fs/nfs/blocklayout/
H A Dextent_tree.c1 // SPDX-License-Identifier: GPL-2.0
3 * Copyright (c) 2014-2016 Christoph Hellwig.
13 ext_node(struct rb_node *node) in ext_node() argument
15 return rb_entry(node, struct pnfs_block_extent, be_node); in ext_node()
19 ext_tree_first(struct rb_root *root) in ext_tree_first() argument
21 struct rb_node *node = rb_first(root); in ext_tree_first() local
22 return node ? ext_node(node) : NULL; in ext_tree_first()
28 struct rb_node *node = rb_prev(&be->be_node); in ext_tree_prev() local
29 return node ? ext_node(node) : NULL; in ext_tree_prev()
35 struct rb_node *node = rb_next(&be->be_node); in ext_tree_next() local
[all …]
/linux/Documentation/translations/zh_CN/core-api/
H A Drbtree.rst1 .. SPDX-License-Identifier: GPL-2.0
2 .. include:: ../disclaimer-zh_CN.rst
4 :Original: Documentation/core-api/rbtree.rst
19 --------------------------
42 https://en.wikipedia.org/wiki/Red-black_tree
45 -----------------
55 --------------
60 struct rb_node node;
65 宏访问。此外，个体成员可直接用rb_entry(node, type, member)访问。
72 --------------------
[all …]
/linux/net/netfilter/
H A Dnf_conncount.c1 // SPDX-License-Identifier: GPL-2.0-only
42 struct list_head node; member
50 struct rb_node node; member
60 struct rb_root root[CONNCOUNT_SLOTS]; member
74 return conn->proto.tcp.state == TCP_CONNTRACK_TIME_WAIT || in already_closed()
75 conn->proto.tcp.state == TCP_CONNTRACK_CLOSE; in already_closed()
88 lockdep_assert_held(&list->list_lock); in conn_free()
90 list->count--; in conn_free()
91 list_del(&conn->node); in conn_free()
105 found = nf_conntrack_find_get(net, &conn->zone, &conn->tuple); in find_or_evict()
[all …]
/linux/drivers/infiniband/hw/hfi1/
H A Dmmu_rb.c1 // SPDX-License-Identifier: GPL-2.0 OR BSD-3-Clause
4 * Copyright(c) 2016 - 2017 Intel Corporation.
29 INTERVAL_TREE_DEFINE(struct mmu_rb_node, node, unsigned long, __last,
32 static unsigned long mmu_node_start(struct mmu_rb_node *node) in mmu_node_start() argument
34 return node->addr & PAGE_MASK; in mmu_node_start()
37 static unsigned long mmu_node_last(struct mmu_rb_node *node) in mmu_node_last() argument
39 return PAGE_ALIGN(node->addr + node->len) - 1; in mmu_node_last()
51 free_ptr = kzalloc(sizeof(*h) + cache_line_size() - 1, GFP_KERNEL); in hfi1_mmu_rb_register()
53 return -ENOMEM; in hfi1_mmu_rb_register()
56 h->root = RB_ROOT_CACHED; in hfi1_mmu_rb_register()
[all …]

12345678910>>...35