仿照内核链表实现了一个通用链表库

W.Z.T

在系统编程的时候经常要用到双向链表， 以前使用的都是内核头文件list.h中的链表库。但是太大了， 于是仔细分析了下内核链表的实现， 仿照它写了个简单的链表库， 基本的功能都有了。 如有需要， 以后在加。 大家看看有什么问题没。

#ifndef LIST_H
#define LIST_H

#include <stddef.h>

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


#define INIT_LIST_HEAD(name_ptr)        do {    (name_ptr)->next = (name_ptr); \
                                                (name_ptr)->prev = (name_ptr); \
                                        }while (0)

#define OFFSET(type, member)            (char *)&(((type *)0x0)->member)
#define container_of(ptr, type, member) ({                                      \
                        (type *)((char * )ptr - OFFSET(type, member)); });

#define list_for_each(pos, head)        for (pos = head->next; pos != head; pos = pos->next)
#define list_for_each_prev(pos, head)   for (pos = head->prev; pos != head; pos = pos->prev)
#define list_entry(ptr, type, member)   container_of(ptr, type, member)

static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
        head->prev->next = new;
        new->prev = head->prev;
        new->next = head;
        head->prev = new;
}

static inline void list_add_tail1(struct list_head *new, struct list_head *head)
{
        new->next = head;
        new->prev = head->prev;
        head->prev->next = new;
        head->prev = new;
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
        new->next = head->next;
        new->prev = head;
        head->next->prev = new;
        head->next = new;
}

static inline void list_del(struct list_head *p)
{
        p->prev->next = p->next;
        p->next->prev = p->prev;
}

#endif

测试程序：

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

#include "list.h"

struct test {
        char data[1024];
        struct list_head list;
};

struct list_head f_list_head;

void usage(char *pro)
{
        fprintf(stderr, "usage: %s <file>\n", pro);

        exit(0);
}

int create_list(FILE *fp, struct list_head *list_head)
{
        char buff[1024];
        struct test *new = NULL;

        while (fgets(buff, 1024, fp) != NULL) {
                new = (struct test *)malloc(sizeof(struct test));
                if (!new) {
                        fprintf(stderr, "Malloc failed.\n");
                        continue;
                }

                strcpy(new->data, buff);
                list_add_tail(&(new->list), list_head);
        }

        fclose(fp);
        }

void del_str(struct list_head *list_head)
{
        struct test *p = NULL;
        struct list_head *s = NULL;

        list_for_each(s, list_head) {
                p = list_entry(s, struct test, list);
                if (p) {
                        if (!strcmp(p->data, "int main(int argc, char **argv)\n"))
                                list_del(s);
                }
        }
}

void print_list(struct list_head *list_head)
{
        struct test *p = NULL;
        struct list_head *s = NULL;

        list_for_each(s, list_head) {
                p = list_entry(s, struct test, list);
                if (p)
                        fprintf(stderr, "%s", p->data);
        }
}

int main(int argc, char **argv)
{
        FILE *fp;

        if (argc == 1)
                usage(argv[0]);

        INIT_LIST_HEAD(&f_list_head);
        fp = fopen(argv[1], "r");
        if (!fp) {
                fprintf(stderr, "Open %s failed.\n", argv[1]);
                exit(0);
        }
        fprintf(stderr, "Open %s ok.\n", argv[1]);

        if (create_list(fp, &f_list_head))
                fprintf(stderr, "done.\n");
        del_str(&f_list_head);
        print_list(&f_list_head);

        return 0;
}

wangdan1600

1. 我想在任意节点之前/后添加一个节点
2. 我想从任意一个节点开始遍历(向前或者向后)，不一定要把链表遍历完，可能在遍历过程中添加、删除、替换某个/些节点
3. 要是实现线程安全，该怎么做才好

Godbach

2楼的问题提的很好

wangdan1600

前天经理让实现一个通用的双链表库。所以才想到了这些问题，正在琢磨着该如何做才好。
内核中的List.h是很精巧，可不能就照搬吧。

Godbach

原帖由 wangdan1600 于 2009-7-3 11:40 发表
前天经理让实现一个通用的双链表库。所以才想到了这些问题，正在琢磨着该如何做才好。
内核中的List.h是很精巧，可不能就照搬吧。

LS的进展的怎么样了？

wangdan1600

/** * db_list.h : public header for application */ #ifndef DB_LIST_H #define DB_LIST_H /** * type defines */ typedef enum {     FALSE,     TRUE } bool_t; typedef enum {     DBL_NORMAL,            /* normal operation */     DBL_EMEM,                 /* malloc error */     DBL_ZERO_INFO,        /* sizeof(Info) is zero */     DBL_NULL_LIST,         /* list is NULL */     DBL_NOT_FOUND,      /* record not found */     DBL_EOPEN,                /* can not open file */     DBL_EWRITE,              /* file write error */     DBL_EREAD,                /* file read error */     DBL_NOT_MODIFIED,        /* unmodified list */     DBL_NULL_FUNCTION        /* NULL function pointer */ } return_t; typedef enum {     DBL_ORIGIN_DEFAULT,        /* use current origin setting */     DBL_HEAD,                            /* set origin to head pointer */     DBL_CURRENT,                     /* set origin to current pointer */     DBL_TAIL,                              /* set origin to tail pointer */ } search_origin; typedef enum {     DBL_DIRECTION_DEFAULT,    /* use current directino setting */     DBL_DOWN,            /* set direction to down */     DBL_UP                /* set direction to up */ } search_direction; typedef enum {     DBL_INSERT_DEFAULT,        /* use current pointerition for insert */     DBL_BEFORE,            /* insert new node before current node */     DBL_AFTER            /* insert new node after current node */ } insert_direction; /** * Basic structures */ typedef struct node {     void        *info;     struct node    *next;     struct node    *prev; } node_t; typedef struct list {     node_t            *head;     node_t            *tail;     node_t            *current;     node_t            *saved;     size_t            info_size;     uint64_t        list_size;     uint64_t        current_index;     uint64_t        save_index;     bool_t            modified;     search_origin        srch_ori;     search_direction    srch_dir; } list_t typedef    struct    search_mode {     search_origin        srch_ori;     search_direction    srch_dir; } srch_mode_t; /** * Prototypes */ /* Initialization routines */ list_t    *create_list(list_t **list); return_t init_list(list_t *list, size_t info_size); void     destroy_list(list_t **list); /* Status and state routines */ bool_t    is_empty(list_t *list); bool_t    is_full(list_t *list); uint64_t get_current_index(list_t *list); uint64_t get_record_counter(list_t *list); srch_mode_t get_srch_mode(list_t *list, srch_mode_t *mode); return_t set_srch_mode(list_t *list, search_origin origin,     search_direction direct); /* Pointer manipulation routines */ return_t current_pointer_to_head(list_t *list); return_t current_pointer_to_tail(list_t *list); return_t increment_current_pointer(list_t *list); return_t decrement_current_pointer(list_t *list); return_t save_current_pointer(list_t *list); return_t restore_current_pointer(list_t *list); /* List update routines */ return_t add_node(list_t *list, void *info,     int (*func)(void *, void *)); return_t insert_record(list_t *list, void *info, insert_direction direct); return_t swap_record(list_t *list, insert_direction direct); return_t update_current_record(list_t *list, void *record); return_t del_current_node(list_t *list); return_t remove_list(list_t *list); /* List search routines */ return_t find_record(list_t, void *record, void *match,     int (*func)(void *, void *)); return_t find_nth_record(list_t *list, void *record, uint64_t nRec); return_t get_current_record(list_t *list, void *record); return_t get_next_record(list_t *list Info *record); return_t get_prev_record(list_t *list,Info *record); /* Input/Output routines */ return_t import_list(list_t *list, const char *path,     int (*func)(void *, void *)); return_t export_list(list_t *list, const char *path); #endif    /* DB_LIST_H */

[ 本帖最后由 wangdan1600 于 2009-7-4 09:11 编辑 ]

connet

看看　glib 中各种链表的实现简洁高效