linux/lib/rbtree_test.c

// SPDX-License-Identifier: GPL-2.0-only
#include <linux/module.h>
#include <linux/moduleparam.h>
#include <linux/rbtree_augmented.h>
#include <linux/random.h>
#include <linux/slab.h>
#include <asm/timex.h>

#define __param(type, name, init, msg) …

__param(int, nnodes, 100, "Number of nodes in the rb-tree");
__param(int, perf_loops, 1000, "Number of iterations modifying the rb-tree");
__param(int, check_loops, 100, "Number of iterations modifying and verifying the rb-tree");

struct test_node { … };

static struct rb_root_cached root = …;
static struct test_node *nodes = …;

static struct rnd_state rnd;

static void insert(struct test_node *node, struct rb_root_cached *root)
{ … }

static void insert_cached(struct test_node *node, struct rb_root_cached *root)
{ … }

static inline void erase(struct test_node *node, struct rb_root_cached *root)
{ … }

static inline void erase_cached(struct test_node *node, struct rb_root_cached *root)
{ … }


#define NODE_VAL(node) …

RB_DECLARE_CALLBACKS_MAX(static, augment_callbacks,
			 struct test_node, rb, u32, augmented, NODE_VAL)

static void insert_augmented(struct test_node *node,
			     struct rb_root_cached *root)
{ … }

static void insert_augmented_cached(struct test_node *node,
				    struct rb_root_cached *root)
{ … }


static void erase_augmented(struct test_node *node, struct rb_root_cached *root)
{ … }

static void erase_augmented_cached(struct test_node *node,
				   struct rb_root_cached *root)
{ … }

static void init(void)
{ … }

static bool is_red(struct rb_node *rb)
{ … }

static int black_path_count(struct rb_node *rb)
{ … }

static void check_postorder_foreach(int nr_nodes)
{ … }

static void check_postorder(int nr_nodes)
{ … }

static void check(int nr_nodes)
{ … }

static void check_augmented(int nr_nodes)
{ … }

static int __init rbtree_test_init(void)
{ … }

static void __exit rbtree_test_exit(void)
{ … }

module_init(…) …
module_exit(…)

MODULE_LICENSE(…) …;
MODULE_AUTHOR(…) …;
MODULE_DESCRIPTION(…) …;