#include<linux/module.h>
#include<linux/rbtree.h>
#include<linux/slab.h>

struct my_struct
{
    int data;
    struct rb_node node;
};

static struct rb_root root = RB_ROOT;

static struct my_struct *search_node(struct rb_root *root, int number)
{
    struct rb_node *node = root->rb_node;

    while(node) {
        struct my_struct *current_data = rb_entry(node, struct my_struct, node);

        if(number<current_data->data)
            node = node->rb_left;
        else if(number>current_data->data)
            node = node->rb_right;
        else
            return current_data;
        }
    return NULL;
}

static bool insert_node(struct rb_root *root, struct my_struct *node)
{
    struct rb_node **new_node = &(root->rb_node), *parent = NULL;

    while(*new_node) {
        struct my_struct *this = rb_entry(*new_node, struct my_struct, node);

        parent = *new_node;
        if(node->data<this->data)
            new_node = &((*new_node)->rb_left);
        else if(node->data>this->data)
    new_node = &((*new_node)->rb_right);
        else return false;
        }

    rb_link_node(&node->node,parent,new_node);
    rb_insert_color(&node->node,root);
    return true;
}

static int __init rbtreemod_init(void)
{
    int i;
    struct my_struct *node = NULL;

    for(i=10;i<25;i++) {
        node = (struct my_struct *)kmalloc(sizeof(struct my_struct), GFP_KERNEL);
        if(!IS_ERR(node)) {
            node->data = i;
            if(!insert_node(&root,node))
                pr_alert("Blad wstawienia wartosci do wezla!\n");

        } else
            pr_alert("Blad alokacji pamieci dla wezla: %ld\n",PTR_ERR(node));
    }
    struct rb_node *node2;
    struct rb_node *copyNode;
    pr_alert("Niemalejaco:");
    for(node2 = rb_first(&root); node2;node2 = rb_next(node2)){
        if (rb_entry(node2,struct my_struct, node)->data == 10){
            copyNode = node2;
            pr_alert("Zapisano wezel z wartoscia: 10!");
        }

       pr_notice("Wartosc wezla: %d\n",rb_entry(node2, struct my_struct, node)->data);
}
    pr_alert("Nierosnaco: ");
    for(node2 = rb_last(&root); node2;node2 = rb_prev(node2)){
        if (rb_entry(node2,struct my_struct,node)->data == 10){
            rb_replace_node(node2,copyNode,&root);
            pr_alert("Zamiana wezla z wartoscia: 10 z zapisanym wezlem!");
        }
        pr_notice("Wartosc wezla: %d\n",rb_entry(node2, struct my_struct, node)->data);
    }
    pr_alert("Normalny: ");
    for(i=10;i<25;i++) {
        node = search_node(&root,i);
        if(node)
            pr_notice("Wartosc wezla: %d\n",node->data);
        else
            pr_alert("Blad odczytu wezla!\n");
    }

    return 0;
}

static void __exit rbtreemod_exit(void)
{
    int i;
    struct my_struct *node = NULL;

    for(i=10;i<25;i++) {
        node = search_node(&root,i);
        if(node) {
            rb_erase(&node->node, &root);
            kfree(node);
        } else
            pr_alert("Blad pozyskania wezla z drzewa czerwono-czarnego!\n");
    }
}

module_init(rbtreemod_init);
module_exit(rbtreemod_exit);