| /kernel/linux/linux-6.6/lib/ |
| D | radix-tree.c | 1 // 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 …]
|
| D | rbtree_test.c | 1 // SPDX-License-Identifier: GPL-2.0-only
14 __param(int, nnodes, 100, "Number of nodes in the rb-tree");
15 __param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
16 __param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
27 static struct rb_root_cached root = RB_ROOT_CACHED; variable
32 static void insert(struct test_node *node, struct rb_root_cached *root) in insert() argument
34 struct rb_node **new = &root->rb_root.rb_node, *parent = NULL; in insert()
35 u32 key = node->key; in insert()
39 if (key < rb_entry(parent, struct test_node, rb)->key) in insert()
40 new = &parent->rb_left; in insert()
[all …]
|
| D | rbtree.c | 1 // 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 …]
|
| /kernel/linux/linux-5.10/lib/ |
| D | radix-tree.c | 1 // SPDX-License-Identifier: GPL-2.0-or-later
24 #include <linux/radix-tree.h>
31 * Radix tree node cache.
36 * The radix tree is variable-height, so an insert operation not only has
43 * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
46 #define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
52 #define IDR_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(int) - 1)
55 #define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1)
58 * Per-cpu pool of preloaded nodes
80 return parent ? slot - parent->slots : 0; in get_slot_offset()
[all …]
|
| D | rbtree_test.c | 1 // SPDX-License-Identifier: GPL-2.0-only
14 __param(int, nnodes, 100, "Number of nodes in the rb-tree");
15 __param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
16 __param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");
27 static struct rb_root_cached root = RB_ROOT_CACHED; variable
32 static void insert(struct test_node *node, struct rb_root_cached *root) in insert() argument
34 struct rb_node **new = &root->rb_root.rb_node, *parent = NULL; in insert()
35 u32 key = node->key; in insert()
39 if (key < rb_entry(parent, struct test_node, rb)->key) in insert()
40 new = &parent->rb_left; in insert()
[all …]
|
| D | rbtree.c | 1 // 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 …]
|
| /kernel/linux/linux-6.6/scripts/gdb/linux/ |
| D | rbtree.py | 1 # SPDX-License-Identifier: GPL-2.0
13 def rb_first(root): argument
14 if root.type == rb_root_type.get_type():
15 node = root.address.cast(rb_root_type.get_type().pointer())
16 elif root.type != rb_root_type.get_type().pointer():
17 raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
19 node = root['rb_node']
20 if node == 0:
23 while node['rb_left']:
24 node = node['rb_left']
[all …]
|
| /kernel/linux/linux-5.10/scripts/gdb/linux/ |
| D | rbtree.py | 1 # SPDX-License-Identifier: GPL-2.0
13 def rb_first(root): argument
14 if root.type == rb_root_type.get_type():
15 node = root.address.cast(rb_root_type.get_type().pointer())
16 elif root.type != rb_root_type.get_type().pointer():
17 raise gdb.GdbError("Must be struct rb_root not {}".format(root.type))
19 node = root['rb_node']
20 if node == 0:
23 while node['rb_left']:
24 node = node['rb_left']
[all …]
|
| /kernel/linux/linux-5.10/include/linux/ |
| D | rbtree_latch.h | 1 /* SPDX-License-Identifier: GPL-2.0 */
3 * Latched RB-trees
7 * Since RB-trees have non-atomic modifications they're not immediately suited
8 * for RCU/lockless queries. Even though we made RB-tree lookups non-fatal for
11 * The simplest solution is a seqlock + RB-tree, this will allow lockless
17 * employing the latch technique -- see @raw_write_seqcount_latch -- to
18 * implement a latched RB-tree which does allow for unconditional lookups by
26 * Therefore, this does require a lockless RB-tree iteration to be non-fatal;
28 * condition -- not seeing partial stores -- because the latch thing isolates
41 struct rb_node node[2]; member
[all …]
|
| D | rbtree.h | 1 /* SPDX-License-Identifier: GPL-2.0-or-later */
14 See Documentation/core-api/rbtree.rst for documentation and samples.
35 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
40 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL) argument
43 #define RB_EMPTY_NODE(node) \ argument
44 ((node)->__rb_parent_color == (unsigned long)(node))
45 #define RB_CLEAR_NODE(node) \ argument
46 ((node)->__rb_parent_color = (unsigned long)(node))
59 /* Postorder iteration - always visit the parent after its children */
63 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
[all …]
|
| /kernel/linux/linux-6.6/include/linux/ |
| D | rbtree_latch.h | 1 /* SPDX-License-Identifier: GPL-2.0 */
3 * Latched RB-trees
7 * Since RB-trees have non-atomic modifications they're not immediately suited
8 * for RCU/lockless queries. Even though we made RB-tree lookups non-fatal for
11 * The simplest solution is a seqlock + RB-tree, this will allow lockless
17 * employing the latch technique -- see @raw_write_seqcount_latch -- to
18 * implement a latched RB-tree which does allow for unconditional lookups by
26 * Therefore, this does require a lockless RB-tree iteration to be non-fatal;
28 * condition -- not seeing partial stores -- because the latch thing isolates
41 struct rb_node node[2]; member
[all …]
|
| D | rbtree.h | 1 /* 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 …]
|
| D | rbtree_augmented.h | 1 /* 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 …]
|
| /kernel/linux/linux-5.10/fs/btrfs/ |
| D | delayed-inode.c | 1 // SPDX-License-Identifier: GPL-2.0
11 #include "delayed-inode.h"
12 #include "disk-io.h"
32 return -ENOMEM; in btrfs_delayed_inode_init()
43 struct btrfs_root *root, u64 inode_id) in btrfs_init_delayed_node() argument
45 delayed_node->root = root; in btrfs_init_delayed_node()
46 delayed_node->inode_id = inode_id; in btrfs_init_delayed_node()
47 refcount_set(&delayed_node->refs, 0); in btrfs_init_delayed_node()
48 delayed_node->ins_root = RB_ROOT_CACHED; in btrfs_init_delayed_node()
49 delayed_node->del_root = RB_ROOT_CACHED; in btrfs_init_delayed_node()
[all …]
|
| D | relocation.c | 1 // 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"
21 #include "inode-map.h"
23 #include "print-tree.h"
24 #include "delalloc-space.h"
25 #include "block-group.h"
40 * ------------------------------------------------------------------
[all …]
|
| /kernel/linux/linux-5.10/tools/include/linux/ |
| D | rbtree.h | 1 /* 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 …]
|
| /kernel/linux/linux-6.6/fs/btrfs/ |
| D | delayed-inode.c | 1 // 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"
37 return -ENOMEM; in btrfs_delayed_inode_init()
48 struct btrfs_root *root, u64 inode_id) in btrfs_init_delayed_node() argument
50 delayed_node->root = root; in btrfs_init_delayed_node()
51 delayed_node->inode_id = inode_id; in btrfs_init_delayed_node()
[all …]
|
| D | relocation.c | 1 // 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 …]
|
| /kernel/linux/linux-5.10/tools/lib/ |
| D | rbtree.c | 1 // 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 …]
|
| /kernel/linux/linux-6.6/tools/lib/ |
| D | rbtree.c | 1 // 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 …]
|
| /kernel/linux/linux-5.10/tools/perf/util/ |
| D | strfilter.c | 1 // 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 …]
|
| /kernel/linux/linux-6.6/tools/perf/util/ |
| D | strfilter.c | 1 // 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 …]
|
| /kernel/linux/linux-5.10/drivers/net/ethernet/mellanox/mlx5/core/ |
| D | fs_core.c | 14 * - Redistributions of source code must retain the above
18 * - Redistributions in binary form must reproduce the above
263 static void del_hw_flow_table(struct fs_node *node);
264 static void del_hw_flow_group(struct fs_node *node);
265 static void del_hw_fte(struct fs_node *node);
266 static void del_sw_flow_table(struct fs_node *node);
267 static void del_sw_flow_group(struct fs_node *node);
268 static void del_sw_fte(struct fs_node *node);
269 static void del_sw_prio(struct fs_node *node);
270 static void del_sw_ns(struct fs_node *node);
[all …]
|
| /kernel/linux/linux-6.6/drivers/net/ethernet/mellanox/mlx5/core/ |
| D | fs_core.c | 14 * - 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 …]
|
| /kernel/linux/linux-6.6/tools/include/linux/ |
| D | rbtree.h | 1 /* 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 …]
|