Windows 原子Interlocked单向链式栈

雨点打透心脏的1/2处 2022-08-20 14:13 117阅读 0赞

SLists使用了无锁算法来保证原子同步，以提升系统性能，避免了诸如优先级挂和互锁的问题。

注意：所有的链表项必须对齐到MEMORY\_ALLOCATION\_ALIGNMENT。否则会出现奇葩的错误。

（PS：看英文MSDN的API解释，我感觉这是从前插又从前取，是个栈的样子。）

InitializeSListHead，创建一个空栈

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **void** WINAPI InitializeSListHead( 
2.   \_\_inout PSLIST\_HEADER ListHead//SLIST\_HEADER类型的链头，供系统使用。
3.  );

InterlockedFlushSList ， 清空栈（感觉这个返回值没什么用的样子，难道可以先全部得到，然后根据链表中元素数量再一个一个地用？求解释。）

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  PSLIST\_ENTRY WINAPI InterlockedFlushSList( 
2.   \_\_inout PSLIST\_HEADER ListHead//创建空栈时用的那个链头
3.  );

InterlockedPushEntrySList ， 在头添加 （区别于从尾部添加），返回值为之前的第一项，如果之前为空链，则返回NULL。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  PSLIST\_ENTRY WINAPI InterlockedPushEntrySList( 
2.   \_\_inout PSLIST\_HEADER ListHead,//创建空栈时用的那个链头
3.   \_\_inout PSLIST\_ENTRY ListEntry//插入项
4.  );

InterlockedPopEntrySList ， 在头取出 （区别于从尾部取出），返回值就是取的那个项的指针，如果之前为空链，则返回NULL。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  PSLIST\_ENTRY WINAPI InterlockedPopEntrySList( 
2.   \_\_inout PSLIST\_HEADER ListHead 
3.  );

QueryDepthSList ， 返回元素的数量 。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **USHORT** WINAPI QueryDepthSList( 
2.   \_\_in PSLIST\_HEADER ListHead 
3.  );

微软的MSDN上有个例子，我复制了下来，链接： [http://msdn.microsoft.com/en-us/library/windows/desktop/ms686962][http_msdn.microsoft.com_en-us_library_windows_desktop_ms686962] 。代码如下。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  \#include <windows.h>
2.  \#include <malloc.h>
3.  \#include <stdio.h>
4.  
5.  // Structure to be used for a list item; the first member is the 
6.  // SLIST\_ENTRY structure, and additional members are used for data.
7.  // Here, the data is simply a signature for testing purposes. 
8.  
9.  
10. **typedef****struct** \_PROGRAM\_ITEM \{ 
11.  SLIST\_ENTRY ItemEntry; 
12. **ULONG** Signature; 
13. \} PROGRAM\_ITEM, \*PPROGRAM\_ITEM; 
14. 
15. **int** main( ) 
16. \{ 
17. **ULONG** Count; 
18.  PSLIST\_ENTRY pFirstEntry, pListEntry; 
19.  PSLIST\_HEADER pListHead; 
20.  PPROGRAM\_ITEM pProgramItem; 
21. 
22. // Initialize the list header to a MEMORY\_ALLOCATION\_ALIGNMENT boundary.
23.  pListHead = (PSLIST\_HEADER)\_aligned\_malloc(**sizeof**(SLIST\_HEADER), 
24.  MEMORY\_ALLOCATION\_ALIGNMENT); 
25. **if**( NULL == pListHead ) 
26.  \{ 
27.  printf("Memory allocation failed.\\n"); 
28. **return** \-1; 
29.  \} 
30.  InitializeSListHead(pListHead); 
31. 
32. // Insert 10 items into the list.
33. **for**( Count = 1; Count <= 10; Count += 1 ) 
34.  \{ 
35.  pProgramItem = (PPROGRAM\_ITEM)\_aligned\_malloc(**sizeof**(PROGRAM\_ITEM), 
36.  MEMORY\_ALLOCATION\_ALIGNMENT); 
37. **if**( NULL == pProgramItem ) 
38.  \{ 
39.  printf("Memory allocation failed.\\n"); 
40. **return** \-1; 
41.  \} 
42.  pProgramItem->Signature = Count; 
43.  pFirstEntry = InterlockedPushEntrySList(pListHead, 
44.  &(pProgramItem->ItemEntry)); 
45.  \} 
46. 
47. // Remove 10 items from the list and display the signature.
48. **for**( Count = 10; Count >= 1; Count -= 1 ) 
49.  \{ 
50.  pListEntry = InterlockedPopEntrySList(pListHead); 
51. 
52. **if**( NULL == pListEntry ) 
53.  \{ 
54.  printf("List is empty.\\n"); 
55. **return** \-1; 
56.  \} 
57. 
58.  pProgramItem = (PPROGRAM\_ITEM)pListEntry; 
59.  printf("Signature is %d\\n", pProgramItem->Signature); 
60. 
61. // This example assumes that the SLIST\_ENTRY structure is the 
62. // first member of the structure. If your structure does not 
63. // follow this convention, you must compute the starting address 
64. // of the structure before calling the free function.
65. 
66.  \_aligned\_free(pListEntry); 
67.  \} 
68. 
69. // Flush the list and verify that the items are gone.
70.  pListEntry = InterlockedFlushSList(pListHead); 
71.  pFirstEntry = InterlockedPopEntrySList(pListHead); 
72. **if** (pFirstEntry != NULL) 
73.  \{ 
74.  printf("Error: List is not empty.\\n"); 
75. **return** \-1; 
76.  \} 
77. 
78.  \_aligned\_free(pListHead); 
79. 
80. **return** 1; 
81. \}

这里略微解释下吧！

微软自己定义的那个结构体PROGRAM\_ITEM的第一项是SLIST\_ENTRY类型的变量。

往InterlockedPushEntrySList和InterlockedPopEntrySList传递时传递的是自定义结构体的第一项。

结构体的地址和它的第一项的地址是同一个。

[view plain]: http://blog.csdn.net/wlsgzl/article/details/17021551#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/87960
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/87960/fork
[http_msdn.microsoft.com_en-us_library_windows_desktop_ms686962]: http://msdn.microsoft.com/en-us/library/windows/desktop/ms686962

发表评论取消回复

表情：

评论列表（有 0 条评论，117人围观）

还没有评论，来说两句吧...

相关阅读

相关栈—链式结构

、定义将链表的头部作为栈顶，尾部作为栈底，可带头结点，也可不带头结点特点： \*先进后出 \*存储单元逻辑上连续但地址不一定连续 \*链栈的入栈、出栈...

╰+哭是因爲堅強的太久メ/ 2024年04月17日 17:48/ 0 赞/ 71 阅读

相关顺序栈-链式栈的实现

/ 顺序栈的实现 / include<iostream> using namespace std; const in

「爱情、让人受尽委屈。」/ 2024年04月06日 13:57/ 0 赞/ 85 阅读

相关 javascript 链式栈

function Stack() { this.top = null; this.size = 0; } Stack.pr

男娘i/ 2024年02月17日 15:16/ 0 赞/ 76 阅读

相关 Interlocked原子访问系列函数

所谓原子访问，指的是一个线程在访问某个资源的同时能够保证没有其他线程会在同一时刻访问同一资源。Interlocked系列函数提供了这样的操作。所有这些函数会以原子方式来操控一个

灰太狼/ 2022年08月20日 14:13/ 0 赞/ 118 阅读

相关 Windows 原子Interlocked单向链式栈

SLists使用了无锁算法来保证原子同步，以提升系统性能，避免了诸如优先级挂和互锁的问题。注意：所有的链表项必须对齐到MEMORY\_ALLOCATION\_ALIGNME

雨点打透心脏的1/2处/ 2022年08月20日 14:13/ 0 赞/ 118 阅读

相关链式栈

2016年7月23日15:39:13 为什么需要链式栈? 这是因为,顺序栈的使用需要事先指定存贮空间的大小,如果静态分配的存贮空

╰+哭是因爲堅強的太久メ/ 2022年07月16日 13:29/ 0 赞/ 251 阅读

相关链式栈

链式栈 // //Description:链式栈 // include <iostream> include <malloc.h>

偏执的太偏执、/ 2022年06月18日 01:56/ 0 赞/ 182 阅读

相关栈的链式存储

栈的链式存储链式存储，也就相当于一个链表，只不过写的API满足栈的要求：先进后出代码实例 stack.h ifndef __STACK_H

淩亂°似流年/ 2022年04月16日 03:15/ 0 赞/ 258 阅读

相关栈-链式栈-C语言实现

include<stdio.h> //栈完成 include<malloc.h> include<stdlib.h> include<stdbo

心已赠人/ 2022年04月02日 06:19/ 0 赞/ 318 阅读

相关链式队列/链式栈

Java实现链式队列 / @auther: 巨未 @DATE: 2019/1/5 0005 20:49 @Descriptio

- 日理万妓/ 2021年09月23日 07:02/ 0 赞/ 392 阅读