/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 …]
|
/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 …]
|
H A D | bfind.c | 15 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument 19 fd->tree = tree; in hfs_find_init() 21 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init() 25 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init() 27 tree->cnid, __builtin_return_address(0)); in hfs_find_init() 28 switch (tree->cnid) { in hfs_find_init() 30 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX); in hfs_find_init() 33 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX); in hfs_find_init() 36 mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX); in hfs_find_init() 49 fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit() [all …]
|
/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 …]
|
H A D | bfind.c | 15 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument 19 fd->tree = tree; in hfs_find_init() 21 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init() 25 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init() 27 tree->cnid, __builtin_return_address(0)); in hfs_find_init() 28 mutex_lock_nested(&tree->tree_lock, in hfs_find_init() 29 hfsplus_btree_lock_class(tree)); in hfs_find_init() 38 fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit() 39 mutex_unlock(&fd->tree->tree_lock); in hfs_find_exit() 40 fd->tree = NULL; in hfs_find_exit() [all …]
|
/linux/fs/btrfs/ |
H A D | extent-io-tree.c | 8 #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() 56 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument 57 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end)) 59 struct extent_io_tree *tree, in __btrfs_debug_check_extent_io_range() argument 65 if (tree->owner != IO_TREE_INODE_IO) in __btrfs_debug_check_extent_io_range() 68 inode = extent_io_tree_to_inode_const(tree); in __btrfs_debug_check_extent_io_range() 85 * The only tree allowed to set the inode is IO_TREE_INODE_IO. 87 static bool is_inode_io_tree(const struct extent_io_tree *tree) in is_inode_io_tree() argument 89 return tree->owner == IO_TREE_INODE_IO; in is_inode_io_tree() [all …]
|
H A D | extent-io-tree.h | 74 * Redefined bits above which are used only in the device allocation tree, 101 * The fs_info is needed for trace points, a tree attached to an inode 112 /* Who owns this io tree, should be one of IO_TREE_* */ 133 struct btrfs_inode *extent_io_tree_to_inode(struct extent_io_tree *tree); 134 const struct btrfs_inode *extent_io_tree_to_inode_const(const struct extent_io_tree *tree); 135 const struct btrfs_fs_info *extent_io_tree_to_fs_info(const struct extent_io_tree *tree); 138 struct extent_io_tree *tree, unsigned int owner); 139 void extent_io_tree_release(struct extent_io_tree *tree); 140 int __lock_extent(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, 142 bool __try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, [all …]
|
H A D | extent_map.c | 31 * Initialize the extent tree @tree. Should be called for each new inode or 34 void extent_map_tree_init(struct extent_map_tree *tree) in extent_map_tree_init() argument 36 tree->root = RB_ROOT; in extent_map_tree_init() 37 INIT_LIST_HEAD(&tree->modified_extents); in extent_map_tree_init() 38 rwlock_init(&tree->lock); in extent_map_tree_init() 136 * Search through the tree for an extent_map with a given offset. If it can't 259 * removed from the tree and likely freed. Note that @merged is one of @prev/@next 349 * We can't modify an extent map that is in the tree and that is being in try_merge_map() 352 * the tree and 1 for this task (which is unpinning the extent map or in try_merge_map() 409 * -ENOENT when the extent is not found in the tree [all …]
|
/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 in alloc_tree() 111 get_tree(struct audit_tree * tree) get_tree() argument 116 put_tree(struct audit_tree * tree) put_tree() argument 123 audit_tree_path(struct audit_tree * tree) audit_tree_path() argument 261 audit_tree_match(struct audit_chunk * chunk,struct audit_tree * tree) audit_tree_match() argument 397 create_chunk(struct inode * inode,struct audit_tree * tree) create_chunk() argument 458 tag_chunk(struct inode * inode,struct audit_tree * tree) tag_chunk() argument 542 kill_rules(struct audit_context * context,struct audit_tree * tree) kill_rules() argument 609 trim_marked(struct audit_tree * tree) trim_marked() argument 649 struct audit_tree *tree; audit_remove_tree_rule() local 684 struct audit_tree *tree; audit_trim_trees() local 740 audit_put_tree(struct audit_tree * tree) audit_put_tree() argument 802 struct audit_tree *seed = rule->tree, *tree; audit_add_tree_rule() local 897 struct audit_tree *tree; audit_tag_tree() local 934 struct audit_tree *tree; audit_tag_tree() local [all...] |
/linux/drivers/gpu/drm/xe/ |
H A D | xe_range_fence.c | 24 struct xe_range_fence_tree *tree = rfence->tree; in xe_range_fence_signal_notify() local 26 llist_add(&rfence->link, &tree->list); in xe_range_fence_signal_notify() 29 static bool __xe_range_fence_tree_cleanup(struct xe_range_fence_tree *tree) in __xe_range_fence_tree_cleanup() argument 31 struct llist_node *node = llist_del_all(&tree->list); in __xe_range_fence_tree_cleanup() 35 xe_range_fence_tree_remove(rfence, &tree->root); in __xe_range_fence_tree_cleanup() 45 * @tree: range fence tree to insert intoi 54 int xe_range_fence_insert(struct xe_range_fence_tree *tree, in xe_range_fence_insert() argument 61 __xe_range_fence_tree_cleanup(tree); in xe_range_fence_insert() 69 rfence->tree = tree; in xe_range_fence_insert() 78 xe_range_fence_tree_insert(rfence, &tree->root); in xe_range_fence_insert() [all …]
|
H A D | xe_range_fence.h | 24 /** @rb: RB tree node inserted into interval tree */ 26 /** @start: start address of range fence is interval tree */ 28 /** @last: last address (inclusive) of range fence is interval tree */ 30 /** @__subtree_last: interval tree internal usage */ 36 /** @tree: interval tree which range fence belongs to */ 37 struct xe_range_fence_tree *tree; member 39 * @cb: callback when fence signals to remove range fence free from interval tree 48 /** struct xe_range_fence_tree - interval tree to store range fences */ 50 /** @root: interval tree root */ 59 xe_range_fence_tree_first(struct xe_range_fence_tree *tree, u64 start, [all …]
|
/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 …]
|
/linux/include/linux/ |
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 …]
|
/linux/tools/include/linux/ |
H A D | rbtree.h | 52 /* Find logical next and previous nodes in a tree */ 95 * rb_erase() may rebalance the tree, causing us to miss some nodes. 172 * rb_add_cached() - insert @node into the leftmost cached tree @tree 174 * @tree: leftmost cached tree to insert @node into 178 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree, in rb_add_cached() argument 181 struct rb_node **link = &tree->rb_root.rb_node; in rb_add_cached() 196 rb_insert_color_cached(node, tree, leftmost); in rb_add_cached() 200 * rb_add() - insert @node into @tree 202 * @tree: tree to insert @node into 206 rb_add(struct rb_node *node, struct rb_root *tree, in rb_add() argument [all …]
|
/linux/rust/kernel/ |
H A D | rbtree.rs | 17 /// A red-black tree with owned nodes. 23 /// In the example below we do several operations on a tree. We note that insertions may fail if 29 /// // Create a new tree. 30 /// let mut tree = RBTree::new(); 33 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; 34 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?; 35 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; 39 /// assert_eq!(tree.get(&10), Some(&100)); 40 /// assert_eq!(tree.get(&20), Some(&200)); 41 /// assert_eq!(tree.get(&30), Some(&300)); [all …]
|
/linux/sound/hda/ |
H A D | hdac_sysfs.c | 79 * Widget tree sysfs 81 * This is a tree showing the attributes of each widget. It appears like 322 struct hdac_widget_tree *tree = codec->widgets; in widget_tree_free() local 325 if (!tree) in widget_tree_free() 327 free_widget_node(tree->afg, &widget_afg_group); in widget_tree_free() 328 if (tree->nodes) { in widget_tree_free() 329 for (p = tree->nodes; *p; p++) in widget_tree_free() 331 kfree(tree->nodes); in widget_tree_free() 333 kobject_put(tree->root); in widget_tree_free() 334 kfree(tree); in widget_tree_free() [all …]
|
/linux/lib/zlib_deflate/ |
H A D | deftree.c | 13 * Each code tree is stored in a compressed form which is itself 84 /* The static literal tree. Since the bit lengths are imposed, there is no 86 * The codes 286 and 287 are needed to build a canonical tree (see zlib_tr_init 91 /* The static distance tree. (Actually a trivial tree since all codes use 111 const ct_data *static_tree; /* static tree or NULL */ 114 int elems; /* max number of elements in the tree */ 133 static void pqdownheap (deflate_state *s, ct_data *tree, int k); 135 static void gen_codes (ct_data *tree, int max_code, ush *bl_count); 137 static void scan_tree (deflate_state *s, ct_data *tree, int max_code); 138 static void send_tree (deflate_state *s, ct_data *tree, int max_code); [all …]
|
/linux/net/sched/ |
H A D | ematch.c | 162 static inline struct tcf_ematch *tcf_em_get_match(struct tcf_ematch_tree *tree, in tcf_em_get_match() argument 165 return &tree->matches[index]; in tcf_em_get_match() 290 * tcf_em_tree_validate - validate ematch config TLV and build ematch tree 293 * @nla: ematch tree configuration TLV 294 * @tree: destination ematch tree variable to store the resulting 295 * ematch tree. 298 * ematch tree in @tree. The resulting tree must later be copied into 300 * provide the ematch tree variable of the private classifier data directly, 306 struct tcf_ematch_tree *tree) in tcf_em_tree_validate() argument 314 memset(tree, 0, sizeof(*tree)); in tcf_em_tree_validate() [all …]
|
/linux/scripts/dtc/libfdt/ |
H A D | fdt_overlay.c | 3 * libfdt - Flat Device Tree manipulation 16 * @fdto: pointer to the device tree overlay blob 89 * @fdt: Base device tree blob 90 * @node: Device tree overlay blob 124 * @fdto: Device tree overlay blob 131 * phandles to not conflict with the overlays of the base device tree. 162 * @fdto: Device tree overlay blob 168 * phandles to not conflict with the overlays of the base device tree. 184 * @fdto: Device tree overlay blob 190 * pointing to a node within the device tree overlay by adding a [all …]
|
H A D | libfdt.h | 5 * libfdt - Flat Device Tree manipulation 28 * tree, but its buffer did not have sufficient space to 29 * contain the expanded tree. Use fdt_open_into() to move the 30 * device tree to a buffer with more space. */ 48 * tree created by the sequential-write functions, which is 51 /* Error codes: codes for bad device tree blobs */ 57 /* FDT_ERR_BADMAGIC: Given "device tree" appears not to be a 58 * device tree at all - it is missing the flattened device 59 * tree magic number. */ 61 /* FDT_ERR_BADVERSION: Given device tree has a version which [all …]
|