线程安全的高效单向链表

作为非常常用的数据结构，单项链表具有表头小，从头结点添加/删除速度快的优点.
 
常用于无限制长度的数据缓存处理。
 
比如iocp工作线程缓存输入数据，逻辑线程取缓冲数据做处理后发送到输出缓冲。这里的输入缓冲和输出缓冲就可以用单链表实现。
 
struct SList{
 
SList *next;
 
};
 
 
 
SListPush(SList* head,Slist* p){
 
p=head->next;
 
head->next=p;
 
}
 
SListPop(SList* head){
 
SList* r=p=head;
 
head=head->next;
 
return r;
 
}
 
 
 
在多线程情况下,因为每次对表头的操作不是原子操作，对表头的操作需要锁定。
 
简单做法是用CriticalSection/mutex来锁定一个表，其他表操作会等待。 考虑到slist都是短时间占用，访问次数可能很频繁。实际cpu消耗在enter/leave上面会较大。
 
 
 
更快的做法是使读写逻辑变为一个原子操作。类似__asm lock cmpexchg这样的实现。
 
原子操作会有地址对齐方面的限制,32/64位都不一样，需要各种检查，自己实现起来比较繁琐。
 
幸运的是winxp/2003之后的版本，ms提供了这么几个api操作来实现slist的原子访问。
 
 
 
InitializeSListHead     初始化链表头
 
InterlockedPushEntrySList  加节点
InterlockedFlushSList      刷新链表(清空),相当于一次把节点全部取出
 
InterlockedPopEntrySList 取节点（删除)
 
QueryDepthSList 取节点计数(16位，只能作为参考，因为取到的计数可能已经被改变了,而且有可能越界被截断）
 
另外Windows Vista /2008 还有
 
InterlockedPushListSList 往一个链表里面添加另外一个链表,  这个api只能用GetProcAddress获取地址。不知道windows sdk 7.1是否能直接连接,装了半天都下载失败。
 
 
 
 
 
需要注意的是，ListHead和ListEntry必须对齐到MEMORY_ALLOCATION_ALIGNMENT.
 
具体用法参考ms 的示例代码
 
http://msdn.microsoft.com/en-us/library/windows/desktop/ms686962(v=vs.85).aspx
 
 
 
 
 
 

补充：综合编程 , 安全编程 ,