지나간 삶

#include <stdio.h>
#include <stdlib.h>

typedef struct rb_node
{
        struct rb_node *rb_parent;
        int rb_color;
#define RB_RED          0
#define RB_BLACK        1
        struct rb_node *rb_right;
        struct rb_node *rb_left;
}rb_node_t;

typedef struct rb_root
{
        struct rb_node *rb_node;
}rb_root_t;

typedef struct
{
    int age;
    struct rb_node tree;
} AGE;

#define rb_entry(ptr, type, member)              \
  ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

void rb_link_node(struct rb_node * node,
                  struct rb_node * parent,  
                  struct rb_node ** rb_link);
AGE * rb_insert_age(struct rb_root * root,
                            int age,
                            rb_node_t * node);
void in_order( rb_node_t * p );
void __rb_rotate_left(rb_node_t * node, rb_root_t * root);
void __rb_rotate_right(rb_node_t * node, rb_root_t * root);
void rb_insert_color(rb_node_t * node, rb_root_t * root);
void display(struct rb_node  *p);
void rb_erase(rb_node_t * node, rb_root_t * root);
void __rb_erase_color(rb_node_t * node, rb_node_t * parent,
                             rb_root_t * root);

void rb_delete(  int age, struct rb_root *root);
int main()
{
    struct rb_root root={0};
    int i;

    AGE a[10];

    for(i=0; i<10; i++)
    {
        a[i].age = (i+1)*10;
        rb_insert_age( &root, a[i].age , &a[i].tree );
       
    display(root.rb_node);
    getchar();
    system("cls");
    }


    display(root.rb_node);
    getchar();
    system("cls");
    rb_delete(60 , &root);

    display(root.rb_node);
    //in_order( root.rb_node );
    return 0;
}

void rb_delete(  int age, struct rb_root *root){
        struct rb_node ** p = &root->rb_node;
        struct rb_node * parent = NULL;
        AGE *temp;

        while (*p) {
                parent = *p;
                temp = rb_entry(parent, AGE, tree);
                if ( age < temp->age )
                        p = &(*p)->rb_left;
                else if (age > temp->age )
                        p = &(*p)->rb_right;
                else
                        break;
        }
        if(!*p)  return;
       
        rb_erase( *p, root );
}





void display(struct rb_node  *p)
{
    int i;
    static int x = 0;
   
    if (p)
    {
        x += 2;
        display(p->rb_right);
        for (i = 2; i < x; i++)
            printf("   ");

        if( p->rb_color == 1 )
            printf("[%2d]\n", rb_entry(p, AGE, tree)->age);
        else
            printf("<%2d>\n", rb_entry(p, AGE, tree)->age);

        display(p->rb_left);
        x -= 2;
    }
}



void rb_link_node(struct rb_node * node,
                  struct rb_node * parent,  
                  struct rb_node ** rb_link)
{
    node->rb_parent = parent;
    node->rb_color = RB_RED;
    node->rb_left = node->rb_right = NULL;
   
    *rb_link = node;
}



AGE * rb_insert_age(struct rb_root * root,
                            int age,
                            rb_node_t * node)
{
    rb_node_t ** p = &root->rb_node;
    rb_node_t * parent = NULL;
    AGE *a;
   
    while (*p)
    {
        parent = *p;
        a = rb_entry(parent, AGE, tree);
       
        if (age < a->age)
            p = &(*p)->rb_left;
        else if (age > a->age)
            p = &(*p)->rb_right;
        else
            return 0;
    }
   
    rb_link_node(node, parent, p);
    rb_insert_color(node, root);
    return NULL;
}




//  root  ->   [ 25 ]


void in_order( rb_node_t * p )
{
    if(p==0) return;

    in_order( p->rb_left );
    printf("[%d]\n",rb_entry(p, AGE, tree)->age);
    in_order( p->rb_right );
}

void __rb_rotate_left(rb_node_t * node, rb_root_t * root)
{
    rb_node_t * right = node->rb_right;
   
    if ((node->rb_right = right->rb_left))
        right->rb_left->rb_parent = node;
    right->rb_left = node;
   
    if ((right->rb_parent = node->rb_parent))
    {
        if (node == node->rb_parent->rb_left)
            node->rb_parent->rb_left = right;
        else
            node->rb_parent->rb_right = right;
    }
    else
        root->rb_node = right;
    node->rb_parent = right;
}




void rb_insert_color(rb_node_t * node, rb_root_t * root)
{
    rb_node_t * parent, * gparent;
   
    while ((parent = node->rb_parent) && parent->rb_color == RB_RED)
    {
        gparent = parent->rb_parent;
       
        if (parent == gparent->rb_left)
        {
            {
                register rb_node_t * uncle = gparent->rb_right;
                if (uncle && uncle->rb_color == RB_RED)
                {
                    uncle->rb_color = RB_BLACK;
                    parent->rb_color = RB_BLACK;
                    gparent->rb_color = RB_RED;
                    node = gparent;
                    continue;
                }
            }
           
            if (parent->rb_right == node)
            {
                register rb_node_t * tmp;
                __rb_rotate_left(parent, root);
                tmp = parent;
                parent = node;
                node = tmp;
            }
           
            parent->rb_color = RB_BLACK;
            gparent->rb_color = RB_RED;
            __rb_rotate_right(gparent, root);
        } else {
            {
                register rb_node_t * uncle = gparent->rb_left;
                if (uncle && uncle->rb_color == RB_RED)
                {
                    uncle->rb_color = RB_BLACK;
                    parent->rb_color = RB_BLACK;
                    gparent->rb_color = RB_RED;
                    node = gparent;
                    continue;
                }
            }
           
            if (parent->rb_left == node)
            {
                register rb_node_t * tmp;
                __rb_rotate_right(parent, root);
                tmp = parent;
                parent = node;
                node = tmp;
            }
           
            parent->rb_color = RB_BLACK;
            gparent->rb_color = RB_RED;
            __rb_rotate_left(gparent, root);
        }
    }
   
    root->rb_node->rb_color = RB_BLACK;
}

void __rb_rotate_right(rb_node_t * node, rb_root_t * root)
{
    rb_node_t * left = node->rb_left;
   
    if ((node->rb_left = left->rb_right))
        left->rb_right->rb_parent = node;
    left->rb_right = node;
   
    if ((left->rb_parent = node->rb_parent))
    {
        if (node == node->rb_parent->rb_right)
            node->rb_parent->rb_right = left;
        else
            node->rb_parent->rb_left = left;
    }
    else
        root->rb_node = left;
    node->rb_parent = left;
}

void __rb_erase_color(rb_node_t * node, rb_node_t * parent,
                             rb_root_t * root)
{
    rb_node_t * other;
   
    while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node)
    {
        if (parent->rb_left == node)
        {
            other = parent->rb_right;
            if (other->rb_color == RB_RED)
            {
                other->rb_color = RB_BLACK;
                parent->rb_color = RB_RED;
                __rb_rotate_left(parent, root);
                other = parent->rb_right;
            }
            if ((!other->rb_left ||
                other->rb_left->rb_color == RB_BLACK)
                && (!other->rb_right ||
                other->rb_right->rb_color == RB_BLACK))
            {
                other->rb_color = RB_RED;
                node = parent;
                parent = node->rb_parent;
            }
            else
            {
                if (!other->rb_right ||
                    other->rb_right->rb_color == RB_BLACK)
                {
                    register rb_node_t * o_left;
                    if ((o_left = other->rb_left))
                        o_left->rb_color = RB_BLACK;
                    other->rb_color = RB_RED;
                    __rb_rotate_right(other, root);
                    other = parent->rb_right;
                }
                other->rb_color = parent->rb_color;
                parent->rb_color = RB_BLACK;
                if (other->rb_right)
                    other->rb_right->rb_color = RB_BLACK;
                __rb_rotate_left(parent, root);
                node = root->rb_node;
                break;
            }
        }
        else
        {
            other = parent->rb_left;
            if (other->rb_color == RB_RED)
            {
                other->rb_color = RB_BLACK;
                parent->rb_color = RB_RED;
                __rb_rotate_right(parent, root);
                other = parent->rb_left;
            }
            if ((!other->rb_left ||
                other->rb_left->rb_color == RB_BLACK)
                && (!other->rb_right ||
                other->rb_right->rb_color == RB_BLACK))
            {
                other->rb_color = RB_RED;
                node = parent;
                parent = node->rb_parent;
            }
            else
            {
                if (!other->rb_left ||
                    other->rb_left->rb_color == RB_BLACK)
                {
                    register rb_node_t * o_right;
                    if ((o_right = other->rb_right))
                        o_right->rb_color = RB_BLACK;
                    other->rb_color = RB_RED;
                    __rb_rotate_left(other, root);
                    other = parent->rb_left;
                }
                other->rb_color = parent->rb_color;
                parent->rb_color = RB_BLACK;
                if (other->rb_left)
                    other->rb_left->rb_color = RB_BLACK;
                __rb_rotate_right(parent, root);
                node = root->rb_node;
                break;
            }
        }
    }
    if (node)
        node->rb_color = RB_BLACK;
}

void rb_erase(rb_node_t * node, rb_root_t * root)
{
    rb_node_t * child, * parent;
    int color;
   
    if (!node->rb_left)
        child = node->rb_right;
    else if (!node->rb_right)
        child = node->rb_left;
    else
    {
        rb_node_t * old = node, * left;
       
        node = node->rb_right;
        while ((left = node->rb_left))
            node = left;
        child = node->rb_right;
        parent = node->rb_parent;
        color = node->rb_color;
       
        if (child)
            child->rb_parent = parent;
        if (parent)
        {
            if (parent->rb_left == node)
                parent->rb_left = child;
            else
                parent->rb_right = child;
        }
        else
            root->rb_node = child;
       
        if (node->rb_parent == old)
            parent = node;
        node->rb_parent = old->rb_parent;
        node->rb_color = old->rb_color;
        node->rb_right = old->rb_right;
        node->rb_left = old->rb_left;
       
        if (old->rb_parent)
        {
            if (old->rb_parent->rb_left == old)
                old->rb_parent->rb_left = node;
            else
                old->rb_parent->rb_right = node;
        } else
            root->rb_node = node;
       
        old->rb_left->rb_parent = node;
        if (old->rb_right)
            old->rb_right->rb_parent = node;
        goto color;
    }
   
    parent = node->rb_parent;
    color = node->rb_color;
   
    if (child)
        child->rb_parent = parent;
    if (parent)
    {
        if (parent->rb_left == node)
            parent->rb_left = child;
        else
            parent->rb_right = child;
    }
    else
        root->rb_node = child;
   
color:
    if (color == RB_BLACK)
        __rb_erase_color(child, parent, root);
}

#include <stdio.h>
#include <time.h>
#include <windows.h>
struct task_struct
{
    int pid;
    struct task_struct *pidhash_next;
    struct task_struct **pidhash_pprev;
};

#define PIDHASH_SZ  16
#define pid_hashfn(x)   ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

struct task_struct *pidhash[PIDHASH_SZ];


void hash_pid(struct task_struct *p)
{
    struct task_struct **htable = &pidhash[pid_hashfn(p->pid)]; if((p->pidhash_next = *htable) != NULL)
        (*htable)->pidhash_pprev = &p->pidhash_next;
    *htable = p;
    p->pidhash_pprev = htable;
}

void unhash_pid(struct task_struct *p)
{
    if(p->pidhash_next)
        p->pidhash_next->pidhash_pprev = p->pidhash_pprev;
    *p->pidhash_pprev = p->pidhash_next;
}


struct task_struct *find_task_by_pid(int pid)
{
    struct task_struct *p, **htable = &pidhash[pid_hashfn(pid)];

    for(p = *htable; p && p->pid != pid; p = p->pidhash_next)
        ;

    return p;
}

void display()
{
    int i;
    struct task_struct *p;

    system("cls");                                          
    for(i =0 ; i < PIDHASH_SZ; i++ )
    {
        printf("[%2d]", i);
        for(p = pidhash[i]; p; p = p->pidhash_next)
            printf("<->[%4d]", p->pid);
        printf("\n");
    }
}

int main()
{

    int temp,i;
    struct task_struct *task;
    srand((unsigned int)time(0));
    display();
    for(i=0; i<30; i++ )
    {
        getchar();
        while( temp = rand())
        {
            if( !find_task_by_pid( temp ))
                break;
        }
        task = (struct task_struct*)malloc(sizeof(struct task_struct));
        task->pid = temp;
        hash_pid( task);
        display();
    }
}

#include <stdio.h>

struct list_head
{
    struct list_head *next;
    struct list_head *prev;
};

typedef struct
{
    int count;
    int pid;
    struct list_head list;
} TASK;

void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

#define  list_entry( temp, type, list ) \
    ((type *)( (char*)temp - (unsigned long)(&((type *)0)->list)))

#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next )

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)

int main()
{
    struct list_head *temp;
    LIST_HEAD(head);

    TASK  t1 = { 1, 1000, 0, 0 };
    TASK  t2 = { 2, 2000, 0, 0 };
    TASK *p;

    list_add ( &t1.list, &head );
    list_add ( &t2.list, &head );

    printf("[head]");
    list_for_each( temp, &head )
    {
        p = list_entry( temp, TASK, list );
        printf("->[%4d, %4d]",p->count, p->pid);
    }
    printf("\n");
    return 0;
}