linux-imx

#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)      \

    static type name = init;        \

    module_param(name, type, 0444);     \

    MODULE_PARM_DESC(name, 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 {

    u32 key;

    struct rb_node rb;

​

    /* following fields used for testing augmented rbtree functionality */

    u32 val;

    u32 augmented;

};

​

static struct rb_root_cached root = RB_ROOT_CACHED;

static struct test_node *nodes = NULL;

​

static struct rnd_state rnd;

​

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

{

    struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;

    u32 key = node->key;

​

    while (*new) {

        parent = *new;

        if (key < rb_entry(parent, struct test_node, rb)->key)

            new = &parent->rb_left;

        else

            new = &parent->rb_right;

    }

​

    rb_link_node(&node->rb, parent, new);

    rb_insert_color(&node->rb, &root->rb_root);

}

​

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

{

    struct rb_node **new = &root->rb_root.rb_node, *parent = NULL;

    u32 key = node->key;

    bool leftmost = true;

​

    while (*new) {

        parent = *new;

        if (key < rb_entry(parent, struct test_node, rb)->key)

            new = &parent->rb_left;

        else {

            new = &parent->rb_right;

            leftmost = false;

        }

    }

​