summaryrefslogtreecommitdiffstats
path: root/lib/rbtree_test.c
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2019-09-26 13:29:42 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2019-09-26 13:29:42 -0400
commitcbafe18c71028d5e0ee1626b4776fea5d5824a78 (patch)
tree2bb7db7db4ed8df2801f7c16553c69fb27379f7f /lib/rbtree_test.c
parentf41def397161053eb0d3ed6861ef65985efbf293 (diff)
parenta22fea94992a2bc5328005e62f368413ede49c14 (diff)
Merge branch 'akpm' (patches from Andrew)
Merge more updates from Andrew Morton: - almost all of the rest of -mm - various other subsystems Subsystems affected by this patch series: memcg, misc, core-kernel, lib, checkpatch, reiserfs, fat, fork, cpumask, kexec, uaccess, kconfig, kgdb, bug, ipc, lzo, kasan, madvise, cleanups, pagemap * emailed patches from Andrew Morton <akpm@linux-foundation.org>: (77 commits) arch/sparc/include/asm/pgtable_64.h: fix build mm: treewide: clarify pgtable_page_{ctor,dtor}() naming ntfs: remove (un)?likely() from IS_ERR() conditions IB/hfi1: remove unlikely() from IS_ERR*() condition xfs: remove unlikely() from WARN_ON() condition wimax/i2400m: remove unlikely() from WARN*() condition fs: remove unlikely() from WARN_ON() condition xen/events: remove unlikely() from WARN() condition checkpatch: check for nested (un)?likely() calls hexagon: drop empty and unused free_initrd_mem mm: factor out common parts between MADV_COLD and MADV_PAGEOUT mm: introduce MADV_PAGEOUT mm: change PAGEREF_RECLAIM_CLEAN with PAGE_REFRECLAIM mm: introduce MADV_COLD mm: untag user pointers in mmap/munmap/mremap/brk vfio/type1: untag user pointers in vaddr_get_pfn tee/shm: untag user pointers in tee_shm_register media/v4l2-core: untag user pointers in videobuf_dma_contig_user_get drm/radeon: untag user pointers in radeon_gem_userptr_ioctl drm/amdgpu: untag user pointers ...
Diffstat (limited to 'lib/rbtree_test.c')
-rw-r--r--lib/rbtree_test.c37
1 files changed, 17 insertions, 20 deletions
diff --git a/lib/rbtree_test.c b/lib/rbtree_test.c
index 62b8ee92643d..41ae3c7570d3 100644
--- a/lib/rbtree_test.c
+++ b/lib/rbtree_test.c
@@ -77,26 +77,10 @@ static inline void erase_cached(struct test_node *node, struct rb_root_cached *r
77} 77}
78 78
79 79
80static inline u32 augment_recompute(struct test_node *node) 80#define NODE_VAL(node) ((node)->val)
81{
82 u32 max = node->val, child_augmented;
83 if (node->rb.rb_left) {
84 child_augmented = rb_entry(node->rb.rb_left, struct test_node,
85 rb)->augmented;
86 if (max < child_augmented)
87 max = child_augmented;
88 }
89 if (node->rb.rb_right) {
90 child_augmented = rb_entry(node->rb.rb_right, struct test_node,
91 rb)->augmented;
92 if (max < child_augmented)
93 max = child_augmented;
94 }
95 return max;
96}
97 81
98RB_DECLARE_CALLBACKS(static, augment_callbacks, struct test_node, rb, 82RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
99 u32, augmented, augment_recompute) 83 struct test_node, rb, u32, augmented, NODE_VAL)
100 84
101static void insert_augmented(struct test_node *node, 85static void insert_augmented(struct test_node *node,
102 struct rb_root_cached *root) 86 struct rb_root_cached *root)
@@ -238,7 +222,20 @@ static void check_augmented(int nr_nodes)
238 check(nr_nodes); 222 check(nr_nodes);
239 for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) { 223 for (rb = rb_first(&root.rb_root); rb; rb = rb_next(rb)) {
240 struct test_node *node = rb_entry(rb, struct test_node, rb); 224 struct test_node *node = rb_entry(rb, struct test_node, rb);
241 WARN_ON_ONCE(node->augmented != augment_recompute(node)); 225 u32 subtree, max = node->val;
226 if (node->rb.rb_left) {
227 subtree = rb_entry(node->rb.rb_left, struct test_node,
228 rb)->augmented;
229 if (max < subtree)
230 max = subtree;
231 }
232 if (node->rb.rb_right) {
233 subtree = rb_entry(node->rb.rb_right, struct test_node,
234 rb)->augmented;
235 if (max < subtree)
236 max = subtree;
237 }
238 WARN_ON_ONCE(node->augmented != max);
242 } 239 }
243} 240}
244 241