Linux內(nèi)核中的通用鏈表list.h在windows下的移植實現(xiàn)
[導讀]在windows的通用開發(fā)平臺上，有MFC或者STL的支持，很少自己去編寫一個鏈表list程序?，F(xiàn)在把Linux下的list.h取出來，在Windows平臺上實現(xiàn)：我這里用的是Linux2.4版本的，
在windows的通用開發(fā)平臺上，有MFC或者STL的支持，很少自己去編寫一個鏈表list程序?，F(xiàn)在把Linux下的list.h取出來，在Windows平臺上實現(xiàn)：
我這里用的是Linux2.4版本的，2.6版本的其實都一樣，下面是修改后的list.h源文件，注意幾點：① 注釋掉了和Linux相關的字眼，如第四行、第六行等，添加了prefetch(w)兩個函數(shù)的實現(xiàn)；② 因為是在C語言下實現(xiàn)（不是C++），VC6-VC2005-VC2010編譯器均不支持C99，而這些編譯器遵循的C89規(guī)范里不支持inline關鍵字，所以關鍵字inline要去掉，直接查找替換為無即可，這一點和gcc的編譯器不同；③ C語言里，函數(shù)中所有的變量定義一定要放在函數(shù)的開始部分，一次性定義完畢，不要在函數(shù)體內(nèi)再定義變量，這一點高版本的VS2010也是如此。
#ifndef?_LINUX_LIST_H
#define?_LINUX_LIST_H
//#if?defined(__KERNEL__)?||?defined(_LVM_H_INCLUDE)
//#includevoid?prefetch(const?void?*x)?{;}?
?void?prefetchw(const?void?*x)?{;}?
/*
?*?Simple?doubly?linked?list?implementation.
?*
?*?Some?of?the?internal?functions?("__xxx")?are?useful?when
?*?manipulating?whole?lists?rather?than?single?entries,?as
?*?sometimes?we?already?know?the?next/prev?entries?and?we?can
?*?generate?better?code?by?using?them?directly?rather?than
?*?using?the?generic?single-entry?routines.
?*/
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)
#define?INIT_LIST_HEAD(ptr)?do?{?
(ptr)->next?=?(ptr);?(ptr)->prev?=?(ptr);?
}?while?(0)
/*
?*?Insert?a?new?entry?between?two?known?consecutive?entries.?
?*
?*?This?is?only?for?internal?list?manipulation?where?we?know
?*?the?prev/next?entries?already!
?*/
static??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.
?*/
static??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.
?*/
static??void?list_add_tail(struct?list_head?*new,?struct?list_head?*head)
{
__list_add(new,?head->prev,?head);
}
/*
?*?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?already!
?*/
static??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??void?list_del(struct?list_head?*entry)
{
__list_del(entry->prev,?entry->next);
entry->next?=?(void?*)?0;
entry->prev?=?(void?*)?0;
}
/**
?*?list_del_init?-?deletes?entry?from?list?and?reinitialize?it.
?*?@entry:?the?element?to?delete?from?the?list.
?*/
static??void?list_del_init(struct?list_head?*entry)
{
__list_del(entry->prev,?entry->next);
INIT_LIST_HEAD(entry);?
}
/**
?*?list_move?-?delete?from?one?list?and?add?as?another's?head
?*?@list:?the?entry?to?move
?*?@head:?the?head?that?will?precede?our?entry
?*/
static??void?list_move(struct?list_head?*list,?struct?list_head?*head)
{
????????__list_del(list->prev,?list->next);
????????list_add(list,?head);
}
/**
?*?list_move_tail?-?delete?from?one?list?and?add?as?another's?tail
?*?@list:?the?entry?to?move
?*?@head:?the?head?that?will?follow?our?entry
?*/
static??void?list_move_tail(struct?list_head?*list,
??struct?list_head?*head)
{
????????__list_del(list->prev,?list->next);
????????list_add_tail(list,?head);
}
/**
?*?list_empty?-?tests?whether?a?list?is?empty
?*?@head:?the?list?to?test.
?*/
static??int?list_empty(struct?list_head?*head)
{
return?head->next?==?head;
}
static??void?__list_splice(struct?list_head?*list,
?struct?list_head?*head)
{
struct?list_head?*first?=?list->next;
struct?list_head?*last?=?list->prev;
struct?list_head?*at?=?head->next;
first->prev?=?head;
head->next?=?first;
last->next?=?at;
at->prev?=?last;
}
/**
?*?list_splice?-?join?two?lists
?*?@list:?the?new?list?to?add.
?*?@head:?the?place?to?add?it?in?the?first?list.
?*/
static??void?list_splice(struct?list_head?*list,?struct?list_head?*head)
{
if?(!list_empty(list))
__list_splice(list,?head);
}
/**
?*?list_splice_init?-?join?two?lists?and?reinitialise?the?emptied?list.
?*?@list:?the?new?list?to?add.
?*?@head:?the?place?to?add?it?in?the?first?list.
?*
?*?The?list?at?@list?is?reinitialised
?*/
static??void?list_splice_init(struct?list_head?*list,
????struct?list_head?*head)
{
if?(!list_empty(list))?{
__list_splice(list,?head);
INIT_LIST_HEAD(list);
}
}
/**
?*?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)?
((type?*)((char?*)(ptr)-(unsigned?long)(&((type?*)0)->member)))
/**
?*?list_for_each - iterate?over?a?list
?*?@pos: the?&struct?list_head?to?use?as?a?loop?counter.
?*?@head: the?head?for?your?list.
?*/
#define?list_for_each(pos,?head)?
for?(pos?=?(head)->next,?prefetch(pos->next);?pos?!=?(head);?
???????? pos?=?pos->next,?prefetch(pos->next))
/**
?*?list_for_each_prev - iterate?over?a?list?backwards
?*?@pos: the?&struct?list_head?to?use?as?a?loop?counter.
?*?@head: the?head?for?your?list.
?*/
#define?list_for_each_prev(pos,?head)?
for?(pos?=?(head)->prev,?prefetch(pos->prev);?pos?!=?(head);?
???????? pos?=?pos->prev,?prefetch(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?counter.
?*?@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?counter.
?*?@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),
?????prefetch(pos->member.next);
?????&pos->member?!=?(head);?
?????pos?=?list_entry(pos->member.next,?typeof(*pos),?member),
?????prefetch(pos->member.next))
/**
?*?list_for_each_entry_safe?-?iterate?over?list?of?given?type?safe?against?removal?of?list?entry
?*?@pos: the?type?*?to?use?as?a?loop?counter.
?*?@n: another?type?*?to?use?as?temporary?storage
?*?@head: the?head?for?your?list.
?*?@member: the?name?of?the?list_struct?within?the?struct.
?*/
#define?list_for_each_entry_safe(pos,?n,?head,?member)
for?(pos?=?list_entry((head)->next,?typeof(*pos),?member),
n?=?list_entry(pos->member.next,?typeof(*pos),?member);
?????&pos->member?!=?(head);?
?????pos?=?n,?n?=?list_entry(n->member.next,?typeof(*n),?member))
/**
?*?list_for_each_entry_continue?-???????iterate?over?list?of?given?type
?*??????????????????????continuing?after?existing?point
?*?@pos:????????the?type?*?to?use?as?a?loop?counter.
?*?@head:???????the?head?for?your?list.
?*?@member:?????the?name?of?the?list_struct?within?the?struct.
?*/
#define?list_for_each_entry_continue(pos,?head,?member)
for?(pos?=?list_entry(pos->member.next,?typeof(*pos),?member),
?????prefetch(pos->member.next);
?????&pos->member?!=?(head);
?????pos?=?list_entry(pos->member.next,?typeof(*pos),?member),
?????prefetch(pos->member.next))
//#endif?/*?__KERNEL__?||?_LVM_H_INCLUDE?*/
#endif下面是測試程序：
#include?"stdio.h"
#include#include#include?"list.h"
//自定義的數(shù)據(jù)結構
struct?list_test_struct
{
struct?list_head list;
int?key;
int?data;
};
void?main()
{
struct?list_head?list?=?{0};??//定義鏈表（頭）?
struct?list_head?*pos?=?NULL;?
struct?list_head?*n?=?NULL;?
int?i=0;
printf("定義鏈表n");?
printf("初始化鏈表！rn");?
INIT_LIST_HEAD(&list);??//初始化鏈表（頭尾相接，形成空鏈表循環(huán)）?
//判斷鏈表是否為空?
printf("判斷鏈表是否為空：");??
if(list_empty(&list)){?
printf("空rn");?
}else{?
printf("非空rn");?
}?
//批量添加節(jié)點?
printf("批量添加節(jié)點：rn");??
for(i=0;ikey=key;?
st->data=data;?
list_add(&st->list,?&list);?
}?
//顯示列表所有節(jié)點?
printf("顯示列表所有節(jié)點：rn");???
list_for_each(pos,&list)
{?
struct?list_test_struct?*st=list_entry(pos,struct?list_test_struct,list);?
printf(?"t?node:key(%d),data(%d)rn",st->key,st->data);?
}?
//釋放所有節(jié)點資源?
printf("釋放所有節(jié)點資源！rn");?
list_for_each_safe(pos,n,&list)
{?
struct?list_test_struct?*st=list_entry(pos,struct?list_test_struct,list);?
list_del(pos);??//刪除節(jié)點，刪除節(jié)點必須在刪除節(jié)點內(nèi)存之前?
free(st);???//釋放節(jié)點內(nèi)存?
}?
}
對于復雜的宏定義，可以使用人工宏展開方式來查看：【Setting】 ->【C/C++】在底部的輸入選項中，添加“/P”再次編譯可以得到一個擴展名為i的文件，既是宏展開后的文件
下載文檔
