list/looplist/loop_list.c

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

#define PKT_ASSERT(x) {if(!x){printf("assert failed!\n");while(1);}}

typedef int data_type;

typedef struct list_node *list_node_t;
struct list_node
{
    list_node_t next;
    data_type data;
};

int pkt_get_loop_list_length(list_node_t l)
{
    int i = 0;
    list_node_t p = l->next;
    while (p != l)
    {
        printf("l[%d] = %d\n", i, p->data);
        p = p->next;
        i++;  
    }
    return i;
}

list_node_t pkt_creat_loop_list(void)
{
    list_node_t n;

    n = (list_node_t)malloc(sizeof(struct list_node));
    n->next = n;
    return n;
}

int pkt_insert_loop_list_head(list_node_t l, data_type data)
{
    PKT_ASSERT(l);

    list_node_t n = (list_node_t)malloc(sizeof(struct list_node));
    if (!n)
    {
        printf("malloc failed!\n");
        return -1;
    }

    n->data = data;
    n->next = l->next;
    l->next = n;

    return 0;
}

int pkt_merge_loop_list(list_node_t des, list_node_t src)
{
    PKT_ASSERT(des);
    PKT_ASSERT(src);
    if (!des->next || !src->next)
    {
        printf("is a empty list!\n");
        return -1;
    }
    list_node_t p = des;
    list_node_t q = src;

    while (p->next != des)
    {
        p = p->next;
    }

    while (q->next != src)
    {
        q = q->next;
    }

    q->next = p->next;
    p->next = src->next;
    free(src);
    return 0;
}




typedef struct dlist_node *dlist_node_t;
struct dlist_node
{
    dlist_node_t prev;
    dlist_node_t next;
    data_type data;
};

int pkt_get_loop_dlist_length(dlist_node_t l)
{
    int i = 0;
    dlist_node_t p = l->next;
    while (p != l)
    {
        printf("dl[%d] = %d\n", i, p->data);
        p = p->next;
        i++;
    }

    return i;
}

dlist_node_t pkt_creat_loop_dlist(void)
{
    dlist_node_t n;
    n = (dlist_node_t)malloc(sizeof(struct dlist_node));
    n->next = n->prev = n;
    return n;
}

int pkt_insert_loop_dlist(dlist_node_t l, data_type data)
{
    PKT_ASSERT(l);

    dlist_node_t n = (dlist_node_t)malloc(sizeof(struct dlist_node));
    if (!n)
    {
        printf("malloc failed!\n");
        return -1;
    }
    n->data = data;
    dlist_node_t p = l;

    n->next = p;
    n->prev = p->prev;
    p->prev->next = n;
    p->prev = n;
    return 0;
}

int pkt_remove_loop_dlist(dlist_node_t l, data_type data)
{
    PKT_ASSERT(l);
    dlist_node_t p = l->next;

    while (p->next != l && p->data != data)
    {
        p = p->next;
    }

    if (p->next == l)
    {
        printf("did not find the node\n");
        return -1;
    }

    p->prev->next = p->next;
    p->next->prev = p->prev;

    free(p);
    return 0;
}

dlist_node_t pkt_get_node_by_pos(dlist_node_t l, int pos)
{
    PKT_ASSERT(l);
    if (pos < 0)
    {
        printf("the pos < 0\n");
        return NULL;
    }
    dlist_node_t p = l->next;
    int i = 0;

    while (p != l && pos > i)
    {
        p = p->next;
        i++;
    }

    if (p == l)
    {
        printf("the pos is too big\n");
        return NULL;
    }

    return p;
}

int main(int argc, char **argv)
{
#if 0
    list_node_t des = pkt_creat_loop_list();
    list_node_t src = pkt_creat_loop_list();

    pkt_insert_loop_list_head(des, 9899);
    pkt_insert_loop_list_head(des, 1);
    pkt_insert_loop_list_head(des, 8);
    pkt_insert_loop_list_head(des, 9);

    pkt_insert_loop_list_head(src, 99999);
    pkt_insert_loop_list_head(src, 66666);

    pkt_get_loop_list_length(des);
    printf("======================================\n");
    pkt_get_loop_list_length(src);

    pkt_merge_loop_list(des, src);
    printf("======================================\n");
    pkt_get_loop_list_length(des);
#elif 1
    dlist_node_t dlist = pkt_creat_loop_dlist();
    pkt_insert_loop_dlist(dlist, 10);
    pkt_insert_loop_dlist(dlist, 89); 
    pkt_insert_loop_dlist(dlist, 55);
    pkt_insert_loop_dlist(dlist, 98);
    pkt_insert_loop_dlist(dlist, 23);
    pkt_insert_loop_dlist(dlist, 969);

    pkt_get_loop_dlist_length(dlist);

    printf("======================================\n");
    pkt_remove_loop_dlist(dlist, 55);
    pkt_get_loop_dlist_length(dlist);
    printf("======================================\n");
    pkt_remove_loop_dlist(dlist, 155);
    pkt_get_loop_dlist_length(dlist);

    int pos;
    while (1)
    {
        scanf("%d", &pos);
        dlist_node_t node;
        if (node = pkt_get_node_by_pos(dlist, pos))
        {
            printf("l[%d].data = %d\n", pos, node->data);
        } 
    }
#endif
    return 0;
}