澳门新葡亰网址下载C语言实现一个简单的单向链表list

by admin on 2020年1月20日

用C语言实现一个简单实用的单向链表list,具有一定的实际意义。尤其我们不想使用STL里面的list<…>类的时候。我实现
的这个list,结点存储任何调用者分配的任意类型的数据(void*)。这个list适用于一些简单的场合,消耗极少的资源。 

 

转自:

头文件:

Makefile

操作系统:ubuntu10.04

/*
 * list.h
 *        Generic sequential linked list node structure — can hold any type data.
 *        cheungmine 
 *      Sep. 22, 2007.  All rights reserved.
 */
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

CC=gcc


main:main.o


clean:
    $(RM) *.o main

.PHONY:clean

前言:
   
在通信过程中,无法知道将会接收到的数据的长度,因此开一个固定大小的缓冲区并不合适,开大了,很可能大多数通信都只是几十个自己而已;开小了,又无法处理大数据。因此最好的方法就是创建内存池,根据实际情况,分配合适大小的内存空间。

#include “unistd.h”

 

一,思路
澳门新葡亰网址下载 1

typedef struct _listnode_t
{
    struct _listnode_t    *next;
    union{
        void*            data;
        struct _list_t    *list;
        const char        *str;
        long            key;
    };
}listnode_t;

main.c

    通过双向链表,管理所有的内存池。

typedef struct _list_t
{
    size_t        size;    /* count of nodes */
    listnode_t    *head;
    listnode_t  *tail;
}list_t, *list_p;

#include "list.h"
#include <stdio.h>


typedef struct 
{
    unsigned long gp;  // (group<<3)|(pnum&0x7)
    unsigned long on;  // on or off
    unsigned long delay;
    unsigned long count;
    struct  list_head p;
}GPIO_NODE;

int main(int argc, const char *argv[])
{

    GPIO_NODE *a1;
    GPIO_NODE *a2;
    GPIO_NODE *a3;
    GPIO_NODE *a4;
    struct list_head *q = NULL;
    struct list_head *q1 = NULL;
    GPIO_NODE *a5;

    LIST_HEAD(gpio_list);

    a1 = (GPIO_NODE *)malloc(sizeof(GPIO_NODE));
    a2 = (GPIO_NODE *)malloc(sizeof(GPIO_NODE));
    a3 = (GPIO_NODE *)malloc(sizeof(GPIO_NODE));
    a4 = (GPIO_NODE *)malloc(sizeof(GPIO_NODE));

    a1->gp = 1;
    a1->on = 1;
    a1->delay = 1;
    a1->count = 1;

    a2->gp = 2;
    a2->on = 2;
    a2->delay = 2;
    a2->count = 2;

    a3->gp = 3;
    a3->on = 3;
    a3->delay = 3;
    a3->count = 3;


    a4->gp = 4;
    a4->on = 4;
    a4->delay = 4;
    a4->count = 4;

    list_add_tail(&(a1->p), &gpio_list);
    list_add_tail(&(a2->p), &gpio_list);
    list_add_tail(&(a3->p), &gpio_list);
    list_add_tail(&(a4->p), &gpio_list);

    list_for_each_safe(q, q1, &gpio_list) {
        a5 = list_entry(q, GPIO_NODE, p); 
        if(a5->gp > 3)
        {
            printf("a5->gp = %dn", a5->gp);
            printf("a5->on = %dn", a5->on);
            printf("a5->delay = %dn", a5->delay);
            printf("a5->count = %dn", a5->count);

            if (!list_empty(&gpio_list))
            {
                list_del(q);
                printf("free node %dn", a5->gp);
                free(a5);
            }
        }
    }

    list_for_each_safe(q, q1, &gpio_list)
    {
        a5 = list_entry(q, GPIO_NODE, p);

        printf("a5->gp = %dn", a5->gp);
        printf("a5->on = %dn", a5->on);
        printf("a5->delay = %dn", a5->delay);
        printf("a5->count = %dn", a5->count);

        if (!list_empty(&gpio_list))
        {
            list_del(q);
            printf("free node %dn", a5->gp);
            free(a5);
        }
    }


    return 0;
}

二,实现
    1,内存池的相关信息结构体

/* A prototype of callbacked function called by list_destroy(), NULL for no use. */
typedef void(*pfcb_list_node_free)(listnode_t* node);    

 

点击(此处)折叠或打开

/* An example of free node data function implemented by callee:
void my_list_node_free(listnode_t *node)
{
    free(node->data);
}
*/

list.h

  1. struct pool_head {

  2.     void                 **free_list;    

  3.     struct list_head     list;            /* list of
    all known pools */

  4.     int32_t                used;            /* how many
    chunks are currently in use */

  5.     int32_t                allocated;        /* how many
    chunks have been allocated */

  6.     int32_t                limit;            /* hard limit
    on the number of chunks */

  7.     int32_t                minavail;        /* how many
    chunks are expected to be used */

  8.     int32_t                size;            /* chunk size
    */

  9.     int32_t                flags;            /*
    MEM_F_* */

  10.     int32_t                users;            /* number of
    pools sharing this zone */

  11.     int8_t                name[12];        /* name of
    the pool */

  12. };

/* Appends a node to a list */
extern void 
list_append_node(list_t *in_list, listnode_t *in_node);

    2,具体实现
        a,头文件(pools.h)

/* Removes the first node from a list and returns it */
extern listnode_t* 
list_remove_head(list_t *in_list);

 

点击(此处)折叠或打开

/* Removes all nodes but for list itself */
extern void
list_remove_all(list_t *in_list, pfcb_list_node_free pfunc /* NULL for no use or a key node */);

参考:

  1. #ifndef __POOLS_H__

  2. #define __POOLS_H__

  3. #ifdef __cplusplus
  4. extern “C” {

  5. #endif

  6. /*
    Define to prevent recursive
    inclusion

  7. ————————————-*/

  8. #include “types.h”

  9. #include “list.h”

  10. #define MEM_F_SHARED    0x1                /*
    标示对应的池允许共用 */

  11. /*
    每个池的相关信息 */

  12. struct pool_head {

  13.     void                 **free_list;    

  14.     struct list_head     list;            /* list of
    all known pools */

  15.     int32_t                used;            /* how many
    chunks are currently in use */

  16.     int32_t                allocated;        /* how many
    chunks have been allocated */

  17.     int32_t                limit;            /* hard limit
    on the number of chunks */

  18.     int32_t                minavail;        /* how many
    chunks are expected to be used */

  19.     int32_t                size;            /* chunk size
    */

  20.     int32_t                flags;            /*
    MEM_F_* */

  21.     int32_t                users;            /* number of
    pools sharing this zone */

  22.     int8_t                name[12];        /* name of
    the pool */

  23. };

  24. /*
    池创建 */

  25. /* Try
    to find an existing shared pool with
    the same characteristics and

  26.  * returns it, otherwise creates this one. NULL is returned if
    no memory

  27.  * is
    available for a new creation.

  28.  */

  29. extern     struct pool_head *    pool_create(char *name,
    uint32_t size, uint32_t flags);

  30. /*
    池销毁 */

  31. /*

  32.  * This function destroys a pool by freeing it
    completely, unless it’s still

  33.  * in
    use. This should be called only under
    extreme circumstances. It always

  34.  * returns NULL if the
    resulting pool is empty, easing
    the clearing of the old

  35.  * pointer, otherwise it returns the pool.

  36.  * .

  37.  */

  38. extern    void*                pool_destroy(struct pool_head *pool);

  39. /*
    把池中的空闲的元素都给释放掉 */

  40. /*

  41.  * This function frees whatever can be freed in pool <pool>.

  42.  */

  43. extern     void                 pool_clear(struct pool_head *pool);

  44. /*
    把池中非必要的元素给释放掉 */

  45. /*

  46.  * This function frees whatever can be freed in all pools,
    but respecting

  47.  * the minimum thresholds imposed by
    owners. It takes care of avoiding

  48.  * recursion because it may be called
    from a signal handler.

  49.  */

  50. extern    void                 pool_flush_nonessential(void);

  51. /*
    动态分配一个 pool 元素大小的内存空间 */

  52. /*
    Allocate a new entry for pool <pool>, and return it for immediate use.

  53.  * NULL
    is returned if no memory is available for a new creation.

  54.  */

  55. extern    void *                pool_refill_alloc(struct pool_head *pool);

  56. /*

  57.  * Returns a pointer to type <type>
    taken from the

  58.  * pool <pool_type> or
    dynamically allocated. In the

  59.  * first case, <pool_type> is
    updated to point to the

  60.  * next
    element in the list.

  61.  */

  62. #define pool_alloc(pool)

  63. ({

  64.         void *__p;

  65.         if ((__p = (pool)->free_list) == NULL)            

  66.                 __p =
    pool_refill_alloc(pool);

  67.         else {

  68.                 (pool)->free_list = *(void **)(pool)->free_list;

  69.         (pool)->used++;                    

  70.         }

  71.         __p;

  72. })

  73. /*

  74.  * Puts a memory area back to the corresponding pool.

  75.  * Items are chained directly through
    a pointer that

  76.  * is
    written in the beginning of the memory
    area, so

  77.  * there’s no need for
    any carrier cell. This implies

  78.  * that each memory area is at least as big as one

  79.  * pointer. Just like with the libc’s free(), nothing

  80.  * is
    done if <ptr>
    is NULL.

  81.  */

  82. #define pool_free(pool, ptr)

  83. ({

  84.         if ((ptr) != NULL) {

  85.                 *(void **)(ptr) = (void *)(pool)->free_list;    

  86.                 (pool)->free_list = (void *)(ptr);    

  87.                 (pool)->used–;                

  88.         }

  89. })

  90. #ifdef __cplusplus

  91. }

  92. #endif

  93. #endif

/* Returns a copy of a list_t from heap */
extern list_t* 
澳门新葡亰网址下载,list_copy(list_t in_list);

Linux内核链表的核心思想是:在用户自定义的结构A中声明list_head类型的成员p,这样每个结构类型为A的变量a中,都拥有同样的成员p,如下:

        b,c文件(pools.c)

/* Concatenates two lists into first list. NOT freeing the second */
extern void 
list_concat(list_t *first, list_t *second);

struct A{

点击(此处)折叠或打开

/* Allocates a new listnode_t from heap. NO memory allocated for input node_data */
extern listnode_t* 
list_node_create(void* node_data);

int property;

  1. #include “pools.h”

  2. #include “standard.h”

  3. /*
    管理所有池的链表头 */

  4. static struct list_head        pools = LIST_HEAD_INIT(pools);

  5. /*
    池创建 */

  6. /* Try
    to find an existing shared pool with
    the same characteristics and

  7.  * returns it, otherwise creates this one. NULL is returned if
    no memory

  8.  * is
    available for a new creation.

  9.  */

  10. struct pool_head *    pool_create(char *name,
    uint32_t size, uint32_t flags)

  11. {

  12.     struct pool_head *pool;

  13.     struct pool_head *entry;

  14.     struct list_head *start;

  15.     uint32_t         align;

  16.     /*
    We need to store at least a (void *) in the
    chunks. Since we know

  17.      * that the malloc() function will never return such a small
    size,

  18.      * let’s round the size up to something slightly bigger, in order
    to

  19.      * ease merging of entries. Note that the rounding is a power of two.

  20.      */

  21.     align = 16;

  22.     size = (size + align

    • 1)
      & -align;
  23.     start = &pools;

  24.     pool = NULL;

  25.     list_for_each_entry(entry, &pools, list) {

  26.         if (entry->size == size) {

  27.             /* either we can share this place and we take it, or

  28.              * we look for a sharable one or for the
    next position

  29.              * before which we will
    insert a new one.

  30.              */

  31.             if (flags &
    entry->flags &
    MEM_F_SHARED) {

  32.                 /* we can share this one */

  33.                 pool = entry;

  34.                 break;

  35.             }

  36.         }

  37.         else if (entry->size
    > size) {

  38.             /* insert before this one */

  39.             start = &entry->list;

  40.             break;

  41.         }

  42.     }

  43.     if (!pool) {

  44.         pool = calloc(1,
    sizeof(*pool));

  45.         if (!pool)

  46.             return NULL;

  47.         if (name)

  48.             strlcpy(pool->name, (int8_t*)name, sizeof(pool->name));

  49.         pool->size =
    size;

  50.         pool->flags =
    flags;

  51.         list_add_tail(&pool->list,start);

  52.     }

  53.     pool->users++;

  54.     return pool;

  55. }

  56. /*
    池销毁 */

  57. void*                pool_destroy(struct pool_head *pool)

  58. {

  59.     if (pool)

  60.     {

  61.         pool_clear(pool);            //
    请看池中的空闲的元素

  62.         if (pool->used)

  63.             return pool;

  64.         pool->users–;

  65.         if (!pool->users)

  66.         {

  67.             list_del(&pool->list);    // 从 pools 链表中删除

  68.             free(pool);                // 把 pool
    结构体占用的内存给释放了

  69.         }

  70.     }

  71.     return NULL;

  72. }

  73. /*
    把池中的空闲的元素都给释放掉 */

  74. /*

  75.  * This function frees whatever can be freed in pool <pool>.

  76.  */

  77. void                 pool_clear(struct pool_head *pool)

  78. {

  79.     void *temp, *next;

  80.     if (!pool)

  81.         return;

  82.     next = pool->free_list;

  83.     while (next) {

  84.         temp = next;

  85.         next = *(void **)temp;

  86.         pool->allocated–;

  87.         free(temp);

  88.     }

  89.     pool->free_list = next;

  90.     /*

    here, we should have pool->allocate

    pool->used */

  91. }

  92. /*
    把池中非必要的元素给释放掉 */

  93. /*

  94.  * This function frees whatever can be freed in all pools,
    but respecting

  95.  * the minimum thresholds imposed by
    owners. It takes care of avoiding

  96.  * recursion because it may be
    called from a signal handler.

  97.  */

  98. void                 pool_flush_nonessential(void)

  99. {

  100.     static int recurse;

  101.     struct pool_head *entry;

  102.     if (recurse++)

  103.         goto out;

  104.     list_for_each_entry(entry, &pools, list) {

  105.         void *temp, *next;

  106.         //qfprintf(stderr, “Flushing pool %sn”, entry->name);

  107.         next = entry->free_list;

  108.         while (next &&

  109.          entry->allocated > entry->minavail
    &&

  110.          entry->allocated > entry->used) {

  111.             temp = next;

  112.             next = *(void **)temp;

  113.             entry->allocated–;

  114.             free(temp);

  115.         }

  116.         entry->free_list = next;

  117.     }

  118.  out:

  119.     recurse–;

  120. }

  121. /*
    动态分配一个 pool 元素大小的内存空间 */

  122. /*
    Allocate a new entry for pool <pool>, and return it for immediate use.

  123.  * NULL is
    returned if no memory is available for a new creation. A call

  124.  * to
    the garbage collector is performed
    before returning NULL.

  125.  */

  126. void *pool_refill_alloc(struct pool_head *pool)

  127. {

  128.     void *ret;

  129.     if (pool->limit && (pool->allocated >=
    pool->limit))

  130.         return NULL;

  131.     ret = calloc(1, pool->size);

  132.     if (!ret) {

  133.         pool_flush_nonessential();

  134.         ret = calloc(1, pool->size);

  135.         if (!ret)

  136.             return NULL;

  137.     }

  138.     pool->allocated++;

  139.     pool->used++;

  140.     return ret;

  141. }

  142. /*
    销毁所有的池 */

  143. int32_t                dump_pools(void)

  144. {

  145.     int32_t        ret =
    OPER_OK;

  146.     return ret;

  147. }

/* Allocates a new listnode_t with a key node type */
extern listnode_t* 
list_key_create(long node_key);

struct list_head
p;

        c,辅助文件(standard.c)

/* Allocates a empty list_t from heap */
extern list_t* 
list_create();

}

点击(此处)折叠或打开

/* Frees in_list’s all nodes and destroys in_list from heap.
 * the callee is responsible for freeing node data.
 * the node freed-function(pfunc) is called by list_destroy.
 */
extern void 
list_destroy(list_t *in_list, pfcb_list_node_free pfunc /* NULL for no use or a key node */);

其中,list_head结构类型定义如下:

  1. /*

  2.  * copies at most <size-1> chars
    from <src> to <dst>. Last
    char is always

  3.  * set
    to 0,
    unless <size> is 0. The number of chars copied is returned

  4.  * (excluding the terminating zero).

  5.  * This code has been optimized for size and
    speed : on x86,
    it’s 45 bytes

  6.  * long, uses only registers, and consumes
    only 4 cycles per char.

  7.  */

  8. int32_t    strlcpy(int8_t*dst, const int8_t*src,
    int32_t size)

  9. {

  10.     int8_t *orig = dst;

  11.     if (size)

  12.     {

  13.         while (–size && (*dst = *src))

  14.         {

  15.             src++; dst++;

  16.         }

  17.         *dst = 0;

  18.     }

  19.     return dst – orig;

  20. }

/* Gets count of nodes in the list */
extern size_t 
list_size(const list_t* in_list);

struct list_head
{

        d,辅助文件(types.h)

/* Gets node by index 0-based. 0 is head */
extern listnode_t* 
list_node_at(const list_t* in_list, int index);

struct list_head
*next,*prev;

点击(此处)折叠或打开

#endif  /* LIST_H_INCLUDED */

};

  1. #ifndef __TYPES_H__

  2. #define __TYPES_H__

  3. #ifdef __cplusplus
  4. extern “C” {

  5. #endif

  6. /*
    Define to prevent recursive
    inclusion

  7. ————————————-*/

  8. #include <stdio.h>
        //
    标准输入输出定义

  9. #include <stdlib.h>
        //
    标准函数库定义

  10. #include <string.h>             // memset

  11. #include <unistd.h>
        //
    Unix标准函数定义,read,write…

  12. #include <sys/types.h>

  13. #include <sys/stat.h>

  14. #include <fcntl.h> //
    文件控制定义

  15. #include <termios.h>
        //
    POSIX中断控制定义

  16. #include <errno.h>
        //
    错误号定义

  17. #include <pthread.h>        //
    pthread_t,pthread_create…

  18. #include “error.h”

  19. #include “debug.h”

  20. /*
    类型定义 */

  21. typedef signed        char        int8_t;

  22. typedef unsigned     char         uint8_t;

  23. typedef signed        short         int16_t;

  24. typedef unsigned     short         uint16_t;

  25. typedef signed        int            int32_t;

  26. typedef unsigned     int
            uint32_t;

  27. typedef signed        long long     int64_t;

  28. typedef unsigned long long         uint64_t;

  29. #define    BUFFER_SIZE                256

  30. /*
    1,COM,串口相关*/

  31. #define    COM_TYPE_UPPER_DEVICE    1

  32. #define    COM_TYPE_LOWER_DEVICE    2
  33. #define    COM_BUFFER_SIZE            (BUFFER_SIZE)

  34. /*
    2,pools,池相关 */

  35. /*
    3,命令相关*/

  36. #define    CMD_DATA_LEN_MAX        (BUFFER_SIZE)

  37. #ifdef __cplusplus

  38. }

  39. #endif

  40. #endif

实现文件:

list_head拥有两个指针成员,其类型都为list_head,分别为前驱指针prev和后驱指针next。

三,实例
    1,头文件(command.h)

/*
 * list.c
 *        Generic linked list implementation.
 *        cheungmine 
 *      Sep. 22, 2007.  All rights reserved.
 */

假设:

点击(此处)折叠或打开

#include “list.h”

(1)多个结构类型为A的变量a1…an,其list_head结构类型的成员为p1…pn

  1. #ifndef __COMMAND_H__

  2. #define __COMMAND_H__

  3. #ifdef __cplusplus
  4. extern “C” {

  5. #endif

  6. /*
    Define to prevent recursive
    inclusion

  7. ————————————-*/

  8. #include “types.h”

  9. /*
    接收到的命令的来源等 */

  10. typedef    struct _cmd

  11. {

  12.     int32_t        fd;

  13.     pthread_t    id;

  14.     void*        data;

  15. }cmd_t;

  16. //
    创建内存池

  17. extern    int32_t        cmd_pool_create(void);

  18. //
    释放内存池

  19. extern    int32_t        cmd_pool_destroy(void);

  20. //
    申请命令内存块,用以保存命令数据

  21. extern    int32_t        cmd_alloc(cmd_t    **param);

  22. //
    释放命令内存块

  23. extern    int32_t        cmd_free(cmd_t    *param);

  24. #ifdef DEBUG_POOL

  25. extern    void            cmd_pool_info(void);

  26. #endif

  27. #ifdef __cplusplus
  28. }

  29. #endif

  30. #endif

/* Appends a node to a list */
void 
list_append_node(list_t *in_list, listnode_t *node)
{
    node->next = NULL;

(2)一个list_head结构类型的变量head,代表头节点

    2,c文件(command.c)

    if (in_list->head)
    {
        in_list->tail->next = node;
        in_list->tail = node;
    }
    else
        in_list->head = in_list->tail = node;

使:

点击(此处)折叠或打开

    in_list->size++;
}

(1)head.next= p1 ; head.prev =
pn

  1. #include “command.h”

  2. #include “pools.h”

  3. static    struct    pool_head        *cmd_head_pool = NULL;

  4. static    struct    pool_head        *cmd_data_pool = NULL;

  5. //
    创建内存池

  6. int32_t        cmd_pool_create(void)

  7. {

  8.     int32_t        ret =
    OPER_OK;

  9.     

  10.     if (cmd_head_pool == NULL)

  11.     {

  12.         if((cmd_head_pool = pool_create(“cmd_head”,
    sizeof(cmd_t),
    MEM_F_SHARED)) == NULL)

  13.         {

  14.             ret = -POOL_CREATE_ERROR;

  15.         }

  16.         else

  17.         {

  18.             if (cmd_data_pool == NULL)

  19.                 if((cmd_data_pool = pool_create(“cmd_data”,
    CMD_DATA_LEN_MAX,
    MEM_F_SHARED)) == NULL)

  20.                 {

  21.                     cmd_pool_destroy();        

  22.                     ret = -POOL_CREATE_ERROR;

  23.                 }

  24.         }

  25.     }

  26. #ifdef DEBUG_POOL

  27.     cmd_pool_info();

  28. #endif

  29.     return ret;

  30. }

  31. #ifdef DEBUG_POOL

  32. void        cmd_pool_info(void)

  33. {

  34.     struct    pool_head        *entry =
    cmd_head_pool;

  35.     printf(“pool %s (%d bytes) : %d allocated (%u
    bytes), %d usedn”,entry->name, entry->size,
    entry->allocated,entry->size *
    entry->allocated,
    entry->used);

  36.     entry = cmd_data_pool;

  37.     printf(“pool %s (%d bytes) : %d allocated (%u
    bytes), %d usedn”,entry->name, entry->size,
    entry->allocated,entry->size *
    entry->allocated,
    entry->used);

  38. }

  39. #endif

  40. //
    释放内存池

  41. int32_t        cmd_pool_destroy(void)

  42. {

  43.     int32_t    ret = OPER_OK;

  44. #ifdef DEBUG_POOL

  45.     cmd_pool_info();

  46. #endif

  47.     if(cmd_head_pool != NULL)

  48.     {

  49.         if(NULL !=
    pool_destroy(cmd_head_pool))

  50.         {

  51.             ret = -POOL_DESTROY_ERROR;

  52.         }

  53.         else

  54.         {

  55.             if(cmd_data_pool != NULL)

  56.                 if(NULL !=
    pool_destroy(cmd_data_pool))

  57.                     ret = -POOL_DESTROY_ERROR;

  58.         }

  59.     }

  60.     return ret;

  61. }

  62. //
    申请命令内存块,用以保存命令数据

  63. int32_t        cmd_alloc(cmd_t    **param)

  64. {

  65.     int32_t        ret =
    OPER_OK;

  66.     if((*param =
    (cmd_t*)pool_alloc(cmd_head_pool)) == NULL)

  67.     {

  68.         ret = -CMD_POOL_ALLOC_ERROR;

  69.     }

  70.     else

  71.     {

  72.         memset(*param,0,sizeof(cmd_t));

  73.         

  74.         if(((*param)->data =
    pool_alloc(cmd_data_pool)) == NULL)

  75.         {

  76.             cmd_free(*param);

  77.             ret = -CMD_POOL_ALLOC_ERROR;

  78.         }

  79.     }

  80. #ifdef DEBUG_POOL

  81.     cmd_pool_info();

  82. #endif

  83.     
  84.     return ret;

  85. }

  86. //
    释放命令内存块

  87. int32_t        cmd_free(cmd_t    *param)

  88. {

  89.     if(param->data != NULL)

  90.     {

  91.         pool_free(cmd_data_pool,param->data);

  92.         param->data =
    NULL;

  93.     }

  94.     

  95.     if(param != NULL)

  96.     {

  97.         pool_free(cmd_head_pool,param);

  98.         param = NULL;

  99.     }

  100.     

  101. #ifdef DEBUG_POOL

  102.     cmd_pool_info();

  103. #endif

  104.     return OPER_OK;

  105. }

/* Removes the first node from a list and returns it */
listnode_t* 
list_remove_head(list_t *in_list)
{
    listnode_t    *node = NULL;
    if (in_list->head)
    {
        node = in_list->head;
        in_list->head = in_list->head->next;
        if (in_list->head == NULL)
            in_list->tail = NULL;
        node->next = NULL;

(2)p1.prev = head,p1.next = p2;

        c,辅助文件(test.c)

        in_list->size–;        
    }
    assert(in_list->size >= 0);
    return node;
}

(3)p2.prev= p1 , p2.next =
p3;

点击(此处)折叠或打开

/* Removes all nodes but for list itself */
void
list_remove_all(list_t *in_list, pfcb_list_node_free pf)
{
    listnode_t    *node;
    while((node = list_remove_head(in_list))){
        if (pf) (*pf)(node);
        free(node);
    }
    assert (in_list->size==0);
}

  1. /*

  2.  * cmd pool begin

  3.  */

  4. static    void    cmd_pool_oper(void)

  5. {

  6.     int32_t        ret =
    OPER_OK;

  7.     printf(“command pool test!n”);

  8.     if((ret = cmd_pool_create()) != OPER_OK)

  9.     {

  10.         printf(“Create command pool fail!n”);

  11.     }

  12.     else

  13.     {

  14.         cmd_t*    cmd_buf[5];

  15.         int32_t    i = 0;

  16.         int32_t    count = 0;

  17.         

  18.         printf(“Create command pool success!!!n”);

  19.         memset(cmd_buf,0,sizeof(cmd_buf));

  20.         for(i = 0; i <
    5; i++)

  21.         {

  22.             printf(”    alloc n”);

  23.             if(cmd_alloc(&cmd_buf[i]) != OPER_OK)

  24.             {

  25.                 printf(“Alloc buffer fail : %dn”,i);

  26.                 count = i;

  27.                 break;

  28.             }

  29.             cmd_buf[i]->fd    =
    i+1;

  30.             strcpy((char*)cmd_buf[i]->data,”hello”);

  31.         }

  32.         printf(“Alloc complete success!n”);

  33. //        if(i >= 5)    count =
    i;

  34.         

  35.         for(i = 0 ; i <
    5; i++)

  36.         {

  37.             printf(“command %d fd : %d,data : %sn”,(i+1),cmd_buf[i]->fd,(char*)cmd_buf[i]->data);

  38.             cmd_free(cmd_buf[i]);

  39.         }

  40.         if((ret = cmd_pool_destroy()) != OPER_OK)

  41.             printf(“command pool destroy fail, still in
    usen”);

  42.         else

  43.             printf(“command pool destroy success!n”);

  44.     }

  45.     

  46. }

  47. void    test_cmd_pool()

  48. {

  49.     cmd_pool_oper();

  50. }

  51. /*

  52.  * cmd pool end

  53.  */

/* Returns a copy of a list_t from heap */
list_t* 
list_copy(list_t list)
{
    list_t    *newlist = (list_t*)malloc (sizeof(list_t));
    *newlist = list;
    return newlist;
}

(n)pn.prev= pn-1 , pn.next =
head

        d,测试结果
        澳门新葡亰网址下载 2

/* Concatenates two lists into first list */
void 
list_concat(list_t *first, list_t *second)
{
    if (first->head)
    {
        if (second->head)
        {
            first->tail->next = second->head;
            first->tail = second->tail;
        }
    }
    else
        *first = *second;
    second->head = second->tail = NULL;

以上,则构成了一个循环链表。

四,参考文件
1,《haproxy-1.5》源码
2,linux下双向链表的实现

    first->size += second->size;
}

因p是嵌入到a中的,p与a的地址偏移量可知,又因为head的地址可知,所以每个结构类型为A的链表节点a1…an的地址也是可以计算出的,从而可实现链表的遍历,在此基础上,则可以实现链表的各种操作。

/* Allocates a new listnode_t from heap */
listnode_t* 
list_node_create(void* data)
{
    listnode_t    *node = (listnode_t*)malloc (sizeof(listnode_t));
    node->next = NULL;
    node->data = data;
    return node;
}

下面是从linux内核中移植出来的简单链表,list.h和list.c:

listnode_t* 
list_key_create(long key)
{
    listnode_t    *node = (listnode_t*)malloc (sizeof(listnode_t));
    node->next = NULL;
    node->key = key;
    return node;
}

list.h:

/* Allocates a empty list_t from heap */
list_t* 
list_create()
{
    list_t    *list = (list_t*)malloc (sizeof(list_t));
    list->size = 0;
    list->head = list->tail = NULL;
    return list;
}

[cpp] view
plaincopy

/* Frees a empty list_t from heap */
void 
list_destroy(list_t *in_list, pfcb_list_node_free  pf)
{
    list_remove_all(in_list, pf);    
    free(in_list);
}

  1. #ifndef _INIT_LIST_H_  
  2. #define _INIT_LIST_H_  
  3.   
  4. #ifndef offsetof  
  5. /* Offset of member MEMBER in a struct of type TYPE. */  
  6. #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)  
  7. #endif  
  8.   
  9. struct listnode  
  10. {  
  11.     struct listnode *next;  
  12.     struct listnode *prev;  
  13. };  
  14.   
  15. #define node_to_item(node, container, member)   
  16.     (container *) (((char*) (node)) – offsetof(container, member))  
  17.   
  18. #define list_declare(name)   
  19.     struct listnode name = {   
  20.         .next = &name,   
  21.         .prev = &name,   
  22.     }  
  23.   
  24. #define list_for_each(node, list)   
  25.     for (node = (list)->next; node != (list); node = node->next)  
  26.   
  27. #define list_for_each_reverse(node, list)   
  28.     for (node = (list)->prev; node != (list); node = node->prev)  
  29.   
  30. void list_init(struct listnode *list);  
  31. void list_add_tail(struct listnode *list, struct listnode *item);  
  32. void list_remove(struct listnode *item);  
  33.   
  34. #define list_empty(list) ((list) == (list)->next)  
  35. #define list_head(list) ((list)->next)  
  36. #define list_tail(list) ((list)->prev)  
  37.   
  38. #endif  

/* Gets count of nodes in the list */
size_t 
list_size(const list_t* in_list)
{
    return in_list->size;
}

list.c:

/* Gets node by index 0-based. 0 is head */
listnode_t* 
list_node_at(const list_t* in_list, int index)
{
    int  i=0;
    listnode_t    *node = in_list->head;

[cpp] view
plaincopy

    assert(index >=0 && index < (int)in_list->size);

  1. #include “list.h”  
  2.   
  3. void list_init(struct listnode *node)  
  4. {  
  5.     node->next = node;  
  6.     node->prev = node;  
  7. }  
  8.   
  9. void list_add_tail(struct listnode *head, struct listnode *item)  
  10. {  
  11.     item->next = head;  
  12.     item->prev = head->prev;  
  13.     head->prev->next = item;  
  14.     head->prev = item;  
  15. }  
  16.   
  17. void list_remove(struct listnode *item)  
  18. {  
  19.     item->next->prev = item->prev;  
  20.     item->prev->next = item->next;  
  21. }  

    while (i < index)
    {
        node = node->next;
        i++;
    }

测试代码list_test.c:

    return node;
}

[cpp] view
plaincopy

公共头文件:

  1. #include<stdio.h>  
  2. #include<stdlib.h>  
  3. #include “list.h”  
  4.   
  5. #define STUDENT_FREE_MEMORY  
  6.   
  7. //声明链表节点  
  8. typedef struct {  
  9.     int id;  
  10.     char *name;  
  11.     struct listnode _list;  
  12. }student;  
  13.   
  14. //遍历函数指针  
  15. typedef void (*student_foreach_fun)(student *stu,void *data);  
  16.   
  17.   
  18. //声明链表  
  19. static list_declare(student_list);  
  20.   
  21. //添加节点  
  22. int student_add(struct listnode *list,student *stu)  
  23. {  
  24.     list_init(&stu->_list);  
  25.     list_add_tail(list,&stu->_list);   
  26. }  
  27.   
  28. //删除节点,释放节点空间  
  29. int student_del(struct listnode *list,int id)  
  30. {  
  31.     struct listnode *node;  
  32.     student *stu;  
  33.     list_for_each(node,list){  
  34.         stu = node_to_item(node,student,_list);  
  35.         if(id == stu->id){  
  36.             printf(“list_del, id:%d,name:%sn”,stu->id,stu->name);  
  37.             list_remove(node);  
  38. #ifdef STUDENT_FREE_MEMORY    
  39.             //释放节点空间  
  40.             free(stu);  
  41.             stu = NULL;  
  42. #endif  
  43.             return 1;  
  44.               
  45.         }  
  46.           
  47.     }  
  48.   
  49.     return 0;  
  50. }  
  51.   
  52. //节点遍历  
  53. void student_foreach(struct listnode *list,student_foreach_fun fun,void *data)  
  54. {  
  55.     struct listnode *node;  
  56.     student *stu;  
  57.     list_for_each(node,list){  
  58.         stu = node_to_item(node,student,_list);  
  59.         fun(stu,data);  
  60.     }  
  61.   
  62. }  
  63.   
  64. //打印节点信息  
  65. void student_print(student *stu,void *data)  
  66. {  
  67.     printf(“id:%d,name:%sn”,stu->id,stu->name);  
  68. }  
  69.   
  70. int main()  
  71. {  
  72.     int i,len;  
  73.     student *stu;  
  74.     char *stu_name[]={“tonny”,”andy”,”michael”,”leslie”,”john”};  
  75.       
  76.       
  77.     len = sizeof(stu_name)/sizeof(stu_name[0]);  
  78.     //添加节点  
  79.     for(i=0;i<len;i++){  
  80.         stu = calloc(1,sizeof(student));  
  81.         stu->id = i + 1;  
  82.         stu->name = stu_name[i];  
  83.   
  84.         student_add(&student_list,stu);  
  85.     }  
  86.   
  87.     //打印所有节点  
  88.     student_foreach(&student_list,student_print,(void *)0);  
  89.       
  90.     //删除节点  
  91.     student_del(&student_list,1);  
  92.     student_foreach(&student_list,student_print,(void *)0);  
  93.   
  94.     //删除节点  
  95.     student_del(&student_list,5);  
  96.     student_foreach(&student_list,student_print,(void *)0);  
  97.       
  98.     return 0;  
  99.       
  100.   
  101. }  

/* unistd.h 
   2008-09-15 Last created by cheungmine.
   All rights reserved by cheungmine.
*/
#ifndef UNISTD_H__
#define UNISTD_H__

Makefile:

/* Standard C header files included */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

[cpp] view
plaincopy

/*============================================================================*/

  1. TARGET=list_test  
  2. SRC=list_test.c list.c  
  3. #SRC=$(wildcard *.c)  
  4. OBJ=$(SRC:.c=.o)  
  5. CFLAGS=-g -Wall -o  
  6.   
  7. $(TARGET):$(SRC)  
  8.     gcc $(SRC) $(CFLAGS) $(TARGET)  
  9. clean:  
  10.     rm $(OBJ) $(TARGET)   

typedef unsigned char uchar, byte, BYTE;

typedef unsigned short uint16, word_t, ushort;

typedef unsigned __int32 uint, uint32, dword_t, size_t;

typedef unsigned long    ulong;

typedef __int16 int16;
typedef __int32 int32;
typedef __int64 int64, longlong;

typedef    long    lresult;

typedef unsigned __int64 uint64, qword_t, ulonglong;

#ifndef BOOL
    typedef int     BOOL;
    #define TRUE  1
    #define FALSE 0
#endif

#ifndef RESULT
    #define RESULT        lresult
    #define _SUCCESS    0
    #define _ERROR        -1
#endif

#ifndef IN
#define IN
#endif

#ifndef OUT
#define OUT
#endif

#ifndef INOUT
#define INOUT
#endif

#ifndef OPTIONAL
#define OPTIONAL
#endif

#define SIZE_BYTE    1
#define SIZE_ACHAR    1
#define SIZE_WCHAR    2
#define SIZE_SHORT    2
#define SIZE_INT    4
#define SIZE_LONG    4
#define SIZE_FLT    4
#define SIZE_DBL    8
#define SIZE_WORD    2
#define SIZE_DWORD    4
#define SIZE_QWORD    8
#define SIZE_LINT    8
#define SIZE_INT64    8
#define SIZE_UUID    16

/*============================================================================*/
#endif    /*UNISTD_H__*/

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图