操作系统:ubuntu10.04
前言:
在开发中,经常需要使用到链表,因此参考linux内核的链表的实现。
一,源码
-
#ifndef __LIST_H__
-
#define __LIST_H__
-
-
#ifdef __cplusplus
-
extern "C" {
-
#endif
-
-
/* Define to prevent recursive inclusion
-
-------------------------------------*/
-
#include "types.h"
-
-
-
struct list_head { struct list_head *next, *prev;};
-
-
-
#define LIST_HEAD_INIT(name) {&(name), &(name)}
-
-
#define LIST_HEAD(name) \
-
struct list_head name = LIST_HEAD_INIT(name)
-
-
static inline void INIT_LIST_HEAD(struct list_head *list)
-
{
-
list->next = list;
-
list->prev = list;
-
}
-
-
-
/*
-
* Insert a new entry between two known consecutive entries.
-
*
-
* This is only for internal list manipulation where we know
-
* the prev/next entries
-
*/
-
/* prev <=> new <=> next */
-
static inline 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;
-
}
-
-
-
-
/**
-
* list_add - add a new entry
-
* @new: new entry to be added
-
* @head: list head to add it after
-
*
-
* Insert a new entry after the specified head.
-
* This is good for implementing stacks.
-
*/
-
/* head <=> lastest <=> ... <=> third <=> second <=> first */
-
static inline void list_add(struct list_head *new,
-
struct list_head *head)
-
{
-
__list_add(new,head,head->next);
-
}
-
-
-
-
/**
-
* list_add_tail - add a new entry
-
* @new: new entry to be added
-
* @head: list head to add it before
-
*
-
* Insert a new entry before the specified head.
-
* This is useful for implementing queues.
-
*/
-
/* first <=> second <=> third <=> ... <=> lastest <=> head */
-
static inline void list_add_tail(struct list_head *new,
-
struct list_head *head)
-
{
-
__list_add(new,head->prev,head);
-
}
-
-
-
-
-
#define LIST_POISON1 ((void *) 0x00100100)
-
#define LIST_POISON2 ((void *) 0x00200200)
-
-
-
/*
-
* Delete a list entry by making the prev/next entries
-
* point to each other.
-
*
-
* This is only for internal list manipulation where we know
-
* the prev/next entries
-
*/
-
static inline void __list_del(struct list_head *prev,
-
struct list_head *next)
-
{
-
next->prev = prev;
-
prev->next = next;
-
}
-
-
-
/**
-
* list_del - deletes entry from list.
-
* @entry: the element to delete from the list.
-
* Note: list_empty() on entry does not return true after this, the entry is
-
* in an undefined state.
-
*/
-
static inline void list_del(struct list_head *entry)
-
{
-
-
__list_del(entry->prev,entry->next);
-
entry->next = LIST_POISON1;
-
entry->prev = LIST_POISON2;
-
}
-
-
-
-
-
/**
-
* list_is_last - tests whether @list is the last entry in list @head
-
* @list: the entry to test
-
* @head: the head of the list
-
*/
-
static inline int list_is_last(const struct list_head *list,
-
const struct list_head *head)
-
{
-
return (list->next == head);
-
}
-
-
-
-
/**
-
* list_empty - tests whether a list is empty
-
* @head: the list to test.
-
*/
-
static inline int list_empty(const struct list_head *head)
-
{
-
return (head->next == head);
-
}
-
-
-
/**
-
* container_of - cast a member of a structure out to the containing structure
-
* @ptr: the pointer to the member.
-
* @type: the type of the container struct this is embedded in.
-
* @member: the name of the member within the struct.
-
*
-
*/
-
#define offsetof(TYPE,MEMBER) ((size_t)&((TYPE*)0)->MEMBER)
-
#define container_of(ptr,type,member) ({ \
-
const typeof(((type *)0)->member) *__mptr = (ptr);\
-
(type*)((char *)__mptr - offsetof(type,member));})
-
-
-
/**
-
* list_entry - get the struct for this entry
-
* @ptr: the &struct list_head pointer.
-
* @type: the type of the struct this is embedded in.
-
* @member: the name of the list_struct within the struct.
-
*/
-
#define list_entry(ptr, type, member) \
-
container_of(ptr,type,member)
-
-
-
/**
-
* list_first_entry - get the first element from a list
-
* @ptr: the list head to take the element from.
-
* @type: the type of the struct this is embedded in.
-
* @member: the name of the list_struct within the struct.
-
*
-
* Note, that list is expected to be not empty.
-
*/
-
#define list_first_entry(ptr, type, member) \
-
list_entry((ptr)->next, type, member)
-
-
-
-
-
/**
-
* list_for_each - iterate over a list
-
* @pos: the &struct list_head to use as a loop cursor.
-
* @head: the head for your list.
-
*
-
* This variant differs from list_for_each() in that it's the
-
* simplest possible list iteration code, no prefetching is done.
-
* Use this for code that knows the list to be very short (empty
-
* or 1 entry) most of the time.
-
*/
-
#define list_for_each(pos,head) \
-
for(pos = (head)->next; pos != (head); pos = pos->next)
-
-
-
-
/**
-
* list_for_each_prev - iterate over a list backwards
-
* @pos: the &struct list_head to use as a loop cursor.
-
* @head: the head for your list.
-
*/
-
#define list_for_each_prev(pos, head) \
-
for(pos = (head)->prev; pos != (head); pos = pos->prev)
-
-
-
-
/**
-
* list_for_each_safe - iterate over a list safe against removal of list entry
-
* @pos: the &struct list_head to use as a loop cursor.
-
* @n: another &struct list_head to use as temporary storage
-
* @head: the head for your list.
-
*/
-
#define list_for_each_safe(pos, n, head) \
-
for (pos = (head)->next, n = pos->next; pos != (head); \
-
pos = n, n = pos->next)
-
-
-
-
-
/**
-
* list_for_each_entry - iterate over list of given type
-
* @pos: the type * to use as a loop cursor.
-
* @head: the head for your list.
-
* @member: the name of the list_struct within the struct.
-
*/
-
#define list_for_each_entry(pos, head, member) \
-
for (pos = list_entry((head)->next, typeof(*pos), member); \
-
&pos->member != (head); \
-
pos = list_entry(pos->member.next, typeof(*pos), member))
-
-
-
-
-
#ifdef __cplusplus
-
}
-
#endif
-
-
#endif
二,测试
1,测试代码
-
/*
-
* list begin
-
*/
-
-
typedef struct _test_list
-
{
-
char name[20];
-
int age;
-
struct list_head list;
-
}test_list_t;
-
-
struct list_head t_list = LIST_HEAD_INIT(t_list);
-
-
static void _item_init(char * name,int age)
-
{
-
test_list_t *item = (test_list_t*)malloc(sizeof(test_list_t));
-
-
strcpy(item->name,name);
-
item->age = age;
-
-
list_add(&item->list,&t_list);
-
}
-
-
static void _item_destroy()
-
{
-
test_list_t *entry = NULL;
-
struct list_head *temp = NULL;
-
struct list_head *item = NULL;
-
-
printf("destroy\n");
-
list_for_each_safe(item,temp,&t_list)
-
{
-
entry = list_entry(item, struct _test_list, list);
-
list_del(item);
-
printf("next : %p\t prev : %p\n",entry->list.next,entry->list.prev);
-
printf("name : %s\t age : %d\n",entry->name,entry->age);
-
free(entry);
-
printf("delete\n");
-
entry = NULL;
-
}
-
}
-
-
static void _item_display()
-
{
-
test_list_t *entry = NULL;
-
-
printf("display\n");
-
list_for_each_entry(entry, &t_list, list)
-
{
-
printf("name : %s\t age : %d\n",entry->name,entry->age);
-
}
-
}
-
-
static void list_oper(void)
-
{
-
_item_init("wo",10);
-
_item_init("shi",20);
-
_item_init("zhong",30);
-
_item_init("guo",40);
-
_item_init("ren",50);
-
-
_item_display();
-
-
_item_destroy();
-
-
}
-
-
void test_list()
-
{
-
list_oper();
-
}
-
-
/*
-
* list end
-
*/
2,测试结果
3,注意事项
a,在删除时,要注意指针问题。
建议使用
list_for_each_safe,而不是
list_for_each_entry。
阅读(1950) | 评论(0) | 转发(0) |