| /openbmc/linux/tools/testing/radix-tree/ |
| H A D | tag_check.c | 8 #include <linux/radix-tree.h>
14 __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag) in __simple_checks() argument
19 item_check_absent(tree, index); in __simple_checks()
20 assert(item_tag_get(tree, index, tag) == 0); in __simple_checks()
22 item_insert(tree, index); in __simple_checks()
23 assert(item_tag_get(tree, index, tag) == 0); in __simple_checks()
24 item_tag_set(tree, index, tag); in __simple_checks()
25 ret = item_tag_get(tree, index, tag); in __simple_checks()
27 ret = tag_tagged_items(tree, first, ~0UL, 10, tag, !tag); in __simple_checks()
29 ret = item_tag_get(tree, index, !tag); in __simple_checks()
[all …]
|
| H A D | main.c | 10 #include <linux/radix-tree.h>
18 RADIX_TREE(tree, GFP_KERNEL); in __gang_check()
23 item_insert(&tree, middle + idx); in __gang_check()
25 item_check_absent(&tree, middle - down - 1); in __gang_check()
27 item_check_present(&tree, middle + idx); in __gang_check()
28 item_check_absent(&tree, middle + up); in __gang_check()
31 item_gang_check_present(&tree, middle - down, up + down, in __gang_check()
33 item_full_scan(&tree, middle - down, down + up, chunk); in __gang_check()
35 item_kill_tree(&tree); in __gang_check()
81 RADIX_TREE(tree, GFP_KERNEL); in add_and_check()
[all …]
|
| /openbmc/linux/fs/hfs/ |
| H A D | btree.c | 18 /* Get a reference to a B*Tree and do some initial checks */
21 struct hfs_btree *tree; in hfs_btree_open() local
27 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
28 if (!tree) in hfs_btree_open()
31 mutex_init(&tree->tree_lock); in hfs_btree_open()
32 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
34 tree->sb = sb; in hfs_btree_open()
35 tree->cnid = id; in hfs_btree_open()
36 tree->keycmp = keycmp; in hfs_btree_open()
38 tree->inode = iget_locked(sb, id); in hfs_btree_open()
[all …]
|
| H A D | brec.c | 16 static int hfs_btree_inc_height(struct hfs_btree *tree);
24 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
39 !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { in hfs_brec_keylen()
40 if (node->tree->attributes & HFS_TREE_BIGKEYS) in hfs_brec_keylen()
41 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
43 retval = node->tree->max_key_len + 1; in hfs_brec_keylen()
45 recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (node->tree->attributes & HFS_TREE_BIGKEYS) { in hfs_brec_keylen()
50 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
56 if (retval > node->tree->max_key_len + 1) { in hfs_brec_keylen()
[all …]
|
| H A D | bnode.c | 30 if (pagenum >= node->tree->pages_per_bnode) in hfs_bnode_read()
60 struct hfs_btree *tree; in hfs_bnode_read_key() local
63 tree = node->tree; in hfs_bnode_read_key()
65 tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_read_key()
68 key_len = tree->max_key_len + 1; in hfs_bnode_read_key()
154 off = node->tree->node_size - 2; in hfs_bnode_dump()
161 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
164 tmp = node->tree->max_key_len + 1; in hfs_bnode_dump()
181 struct hfs_btree *tree; in hfs_bnode_unlink() local
185 tree = node->tree; in hfs_bnode_unlink()
[all …]
|
| /openbmc/u-boot/test/py/tests/ |
| H A D | test_bind.py | 31 tree = u_boot_console.run_command('dm tree')
32 assert in_tree(tree, 'bind-test', 'simple_bus', 'generic_simple_bus', 0, True)
33 assert in_tree(tree, 'bind-test-child1', 'phy', 'phy_sandbox', 1, False)
34 assert in_tree(tree, 'bind-test-child2', 'simple_bus', 'generic_simple_bus', 1, True)
39 tree = u_boot_console.run_command('dm tree')
40 assert in_tree(tree, 'bind-test', 'simple_bus', 'generic_simple_bus', 0, True)
41 assert 'bind-test-child1' not in tree
42 assert in_tree(tree, 'bind-test-child2', 'simple_bus', 'generic_simple_bus', 1, True)
47 tree = u_boot_console.run_command('dm tree')
48 assert in_tree(tree, 'bind-test', 'simple_bus', 'generic_simple_bus', 0, True)
[all …]
|
| /openbmc/linux/fs/hfsplus/ |
| H A D | btree.c | 42 * Catalog B-tree Header
47 * Attributes B-tree Header
132 /* Get a reference to a B*Tree and do some initial checks */
135 struct hfs_btree *tree; in hfs_btree_open() local
142 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
143 if (!tree) in hfs_btree_open()
146 mutex_init(&tree->tree_lock); in hfs_btree_open()
147 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
148 tree->sb = sb; in hfs_btree_open()
149 tree->cnid = id; in hfs_btree_open()
[all …]
|
| H A D | brec.c | 25 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
40 !(node->tree->attributes & HFS_TREE_VARIDXKEYS) && in hfs_brec_keylen()
41 (node->tree->cnid != HFSPLUS_ATTR_CNID)) { in hfs_brec_keylen()
42 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
45 node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (recoff > node->tree->node_size - 2) { in hfs_brec_keylen()
54 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
65 struct hfs_btree *tree; in hfs_brec_insert() local
72 tree = fd->tree; in hfs_brec_insert()
74 if (!tree->root) in hfs_brec_insert()
[all …]
|
| H A D | bnode.c | 59 struct hfs_btree *tree; in hfs_bnode_read_key() local
62 tree = node->tree; in hfs_bnode_read_key()
64 tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_read_key()
65 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_read_key()
68 key_len = tree->max_key_len + 2; in hfs_bnode_read_key()
303 off = node->tree->node_size - 2; in hfs_bnode_dump()
310 if (node->tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_dump()
311 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_dump()
314 tmp = node->tree->max_key_len + 2; in hfs_bnode_dump()
330 struct hfs_btree *tree; in hfs_bnode_unlink() local
[all …]
|
| /openbmc/qemu/tests/unit/ |
| H A D | test-qtree.c | 6 * https://gitlab.gnome.org/GNOME/glib/-/blob/main/glib/tests/tree.c
94 QTree *tree; in test_tree_search() local
99 tree = q_tree_new_with_data(my_compare_with_data, GINT_TO_POINTER(123)); in test_tree_search()
102 q_tree_insert(tree, &chars[i], &chars[i]); in test_tree_search()
105 q_tree_foreach(tree, my_traverse, NULL); in test_tree_search()
107 g_assert(q_tree_nnodes(tree) == strlen(chars)); in test_tree_search()
108 g_assert(q_tree_height(tree) == 6); in test_tree_search()
111 q_tree_foreach(tree, check_order, &p); in test_tree_search()
114 removed = q_tree_remove(tree, &chars[i + 10]); in test_tree_search()
119 removed = q_tree_remove(tree, &c); in test_tree_search()
[all …]
|
| /openbmc/qemu/include/qemu/ |
| H A D | qtree.h | 34 * used by the tree implementation. Until Glib 2.75.3, GTree uses Glib's
65 QTree *q_tree_ref(QTree *tree);
66 void q_tree_unref(QTree *tree);
67 void q_tree_destroy(QTree *tree);
68 void q_tree_insert(QTree *tree,
71 void q_tree_replace(QTree *tree,
74 gboolean q_tree_remove(QTree *tree,
76 gboolean q_tree_steal(QTree *tree,
78 gpointer q_tree_lookup(QTree *tree,
80 gboolean q_tree_lookup_extended(QTree *tree,
[all …]
|
| H A D | iova-tree.h | 2 * An very simplified iova tree implementation based on GTree.
15 * Currently the iova tree will only allow to keep ranges
18 * tree. It can save a lot of memory when the ranges are split but
22 * protections. Callers of the iova tree should be responsible
46 * Create a new iova tree.
48 * Returns: the tree pointer when succeeded, or NULL if error.
55 * @tree: the iova tree to insert
58 * Insert an iova range to the tree. If there is overlapped
63 int iova_tree_insert(IOVATree *tree, const DMAMap *map);
68 * @tree: the iova tree to remove range from
[all …]
|
| /openbmc/qemu/util/ |
| H A D | qtree.c | 73 * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be
99 static QTreeNode *q_tree_insert_internal(QTree *tree,
103 static gboolean q_tree_remove_internal(QTree *tree,
107 static QTreeNode *q_tree_find_node(QTree *tree,
199 QTree *tree; in q_tree_new_full() local
203 tree = g_new(QTree, 1); in q_tree_new_full()
204 tree->root = NULL; in q_tree_new_full()
205 tree->key_compare = key_compare_func; in q_tree_new_full()
206 tree->key_destroy_func = key_destroy_func; in q_tree_new_full()
207 tree->value_destroy_func = value_destroy_func; in q_tree_new_full()
[all …]
|
| H A D | iova-tree.c | 2 * IOVA tree implementation based on GTree.
13 #include "qemu/iova-tree.h"
16 GTree *tree; member
49 * @next: The next mapping in the tree. Can be NULL to signal the last one
79 iova_tree->tree = g_tree_new_full(iova_tree_compare, NULL, g_free, NULL); in iova_tree_new()
84 const DMAMap *iova_tree_find(const IOVATree *tree, const DMAMap *map) in iova_tree_find() argument
86 return g_tree_lookup(tree->tree, map); in iova_tree_find()
108 const DMAMap *iova_tree_find_iova(const IOVATree *tree, const DMAMap *map) in iova_tree_find_iova() argument
114 g_tree_foreach(tree->tree, iova_tree_find_address_iterator, &args); in iova_tree_find_iova()
124 int iova_tree_insert(IOVATree *tree, const DMAMap *map) in iova_tree_insert() argument
[all …]
|
| /openbmc/linux/fs/btrfs/ |
| H A D | extent-io-tree.c | 7 #include "extent-io-tree.h"
46 pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n", in btrfs_extent_state_leak_debug_check()
55 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
56 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
58 struct extent_io_tree *tree, in __btrfs_debug_check_extent_io_range() argument
61 struct btrfs_inode *inode = tree->inode; in __btrfs_debug_check_extent_io_range()
84 * the tree lock and get the inode lock when setting delalloc. These two things
97 struct extent_io_tree *tree, unsigned int owner) in extent_io_tree_init() argument
99 tree->fs_info = fs_info; in extent_io_tree_init()
100 tree->state = RB_ROOT; in extent_io_tree_init()
[all …]
|
| H A D | extent-io-tree.h | 64 * Redefined bits above which are used only in the device allocation tree,
91 /* Inode associated with this tree, or NULL. */
94 /* Who owns this io tree, should be one of IO_TREE_* */
116 struct extent_io_tree *tree, unsigned int owner);
117 void extent_io_tree_release(struct extent_io_tree *tree);
119 int lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
122 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
128 u64 count_range_bits(struct extent_io_tree *tree,
134 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
136 int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
[all …]
|
| /openbmc/linux/kernel/ |
| H A D | audit_tree.c | 61 * the same tree.
68 * tree.chunks anchors chunk.owners[].list hash_lock
69 * tree.rules anchors rule.rlist audit_filter_mutex
70 * chunk.trees anchors tree.same_root hash_lock
74 * tree is refcounted; one reference for "some rules on rules_list refer to
95 struct audit_tree *tree; in alloc_tree() local
97 tree = kmalloc(struct_size(tree, pathname, strlen(s) + 1), GFP_KERNEL); in alloc_tree()
98 if (tree) { in alloc_tree()
99 refcount_set(&tree->count, 1); in alloc_tree()
100 tree->goner = 0; in alloc_tree()
[all …]
|
| /openbmc/linux/Documentation/core-api/ |
| H A D | maple_tree.rst | 5 Maple Tree
13 The Maple Tree is a B-Tree data type which is optimized for storing
14 non-overlapping ranges, including ranges of size 1. The tree was designed to
17 entry in a cache-efficient manner. The tree can also be put into an RCU-safe
22 The Maple Tree maintains a small memory footprint and was designed to use
24 use the normal API. An :ref:`maple-tree-advanced-api` exists for more complex
25 scenarios. The most important usage of the Maple Tree is the tracking of the
28 The Maple Tree can store values between ``0`` and ``ULONG_MAX``. The Maple
29 Tree reserves values with the bottom two bits set to '10' which are below 4096
34 :ref:`maple-tree-advanced-api`, but are blocked by the normal API.
[all …]
|
| /openbmc/qemu/hw/virtio/ |
| H A D | vhost-iova-tree.c | 2 * vhost software live migration iova tree
11 #include "qemu/iova-tree.h"
12 #include "vhost-iova-tree.h"
34 * Create a new IOVA tree
36 * Returns the new IOVA tree
40 VhostIOVATree *tree = g_new(VhostIOVATree, 1); in vhost_iova_tree_new() local
43 tree->iova_first = MAX(iova_first, iova_min_addr); in vhost_iova_tree_new()
44 tree->iova_last = iova_last; in vhost_iova_tree_new()
46 tree->iova_taddr_map = iova_tree_new(); in vhost_iova_tree_new()
47 return tree; in vhost_iova_tree_new()
[all …]
|
| /openbmc/u-boot/dts/ |
| H A D | Kconfig | 2 # Device Tree Control
22 menu "Device Tree Control"
26 bool "Run-time configuration via Device Tree"
30 via a flattened device tree.
33 bool "Board-specific manipulation of Device Tree"
36 U-Boot's device tree (e.g. to delete device from it). This option
37 make the Device Tree writeable and provides a board-specific
39 enables the board initialization to modifiy the Device Tree. The
43 bool "Enable run-time configuration via Device Tree in SPL"
46 Some boards use device tree in U-Boot but only have 4KB of SRAM
[all …]
|
| /openbmc/u-boot/doc/driver-model/ |
| H A D | livetree.txt | 1 Driver Model with Live Device Tree
8 Traditionally U-Boot has used a 'flat' device tree. This means that it
9 reads directly from the device tree binary structure. It is called a flat
10 device tree because nodes are listed one after the other, with the
13 This document describes U-Boot's support for a 'live' device tree, meaning
14 that the tree is loaded into a hierarchical data structure within U-Boot.
20 The flat device tree has several advantages:
22 - it is the format produced by the device tree compiler, so no translation
30 However the flat device tree does have some limitations. Adding new
32 The overall tree has a fixed maximum size so sometimes the tree must be
[all …]
|
| H A D | fdt-fixup.txt | 1 Pre-relocation device tree manipulation
32 device tree overlay mechanism: There exists one "base" device tree, which
35 boards is then detected, and the corresponding device tree overlays are applied
42 In the U-Boot boot loader, support for device tree overlays has recently been
43 integrated, and is used on some boards to alter the device tree that is later
44 passed to Linux. But since U-Boot's driver model, which is device tree-based as
46 device tree starts cropping up in U-Boot itself as well.
48 An additional problem with the device tree in U-Boot is that it is read-only,
49 and the current mechanisms don't allow easy manipulation of the device tree
51 tree (at least after the relocation) would greatly simplify the solution of
[all …]
|
| /openbmc/linux/include/linux/ |
| H A D | maple_tree.h | 5 * Maple Tree - An RCU-safe adaptive tree for storing ranges
17 * Allocated nodes are mutable until they have been inserted into the tree,
19 * from the tree and an RCU grace period has passed.
25 * Nodes in the tree point to their parent unless bit 0 is set.
45 * is a pointer to the tree itself. No more bits are available in this pointer
49 * parent pointer is 256B aligned like all other tree nodes. When storing a 32
56 * type is done by examining the immutable tree flag for the MAPLE_ALLOC_RANGE
96 * In regular B-Tree terms, pivots are called keys. The term pivot is used to
97 * indicate that the tree is specifying ranges, Pivots may appear in the
99 * specific position of a B-tree. Pivot values are inclusive of the slot with
[all …]
|
| H A D | rbtree.h | 43 /* Find logical next and previous nodes in a tree */
97 * rb_erase() may rebalance the tree, causing us to miss some nodes.
157 * rb_add_cached() - insert @node into the leftmost cached tree @tree
159 * @tree: leftmost cached tree to insert @node into
165 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree, in rb_add_cached() argument
168 struct rb_node **link = &tree->rb_root.rb_node; in rb_add_cached()
183 rb_insert_color_cached(node, tree, leftmost); in rb_add_cached()
189 * rb_add() - insert @node into @tree
191 * @tree: tree to insert @node into
195 rb_add(struct rb_node *node, struct rb_root *tree, in rb_add() argument
[all …]
|
| /openbmc/qemu/hw/hyperv/ |
| H A D | hv-balloon-page_range_tree.c | 37 static GTreeNode *page_range_tree_insert_new(PageRangeTree tree, in page_range_tree_insert_new() argument
48 return g_tree_insert_node(tree.t, key, range); in page_range_tree_insert_new()
51 void hvb_page_range_tree_insert(PageRangeTree tree, in hvb_page_range_tree_insert() argument
65 node = g_tree_upper_bound(tree.t, &start); in hvb_page_range_tree_insert()
69 node = g_tree_node_last(tree.t); in hvb_page_range_tree_insert()
82 * !node case: the tree is empty or the very first node in the tree in hvb_page_range_tree_insert()
84 * the other case: there is a gap in the tree between the new range in hvb_page_range_tree_insert()
86 * anyway, let's just insert the new range into the tree. in hvb_page_range_tree_insert()
88 node = page_range_tree_insert_new(tree, start, count); in hvb_page_range_tree_insert()
94 * the previous range in the tree either partially covers the new in hvb_page_range_tree_insert()
[all …]
|