[RTL]
[reactos.git] / reactos / lib / rtl / slist.c
1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS Runtime Library
4 * PURPOSE: Slist Routines
5 * FILE: lib/rtl/slist.c
6 * PROGRAMERS: Stefan Ginsberg (stefan__100__@hotmail.com)
7 * Timo Kreuzer (timo.kreuzer@reactos.org)
8 */
9
10 /* INCLUDES *****************************************************************/
11
12 #include <rtl.h>
13
14 #define NDEBUG
15 #include <debug.h>
16
17 #ifdef _WIN64
18 BOOLEAN RtlpUse16ByteSLists = -1;
19 #endif
20
21 /* FUNCTIONS ***************************************************************/
22
23 VOID
24 NTAPI
25 RtlInitializeSListHead(
26 _Out_ PSLIST_HEADER SListHead)
27 {
28 #if defined(_WIN64)
29 /* Make sure the header is 16 byte aligned */
30 if (((ULONG_PTR)SListHead & 0xf) != 0)
31 {
32 DPRINT1("Unaligned SListHead: 0x%p\n", SListHead);
33 RtlRaiseStatus(STATUS_DATATYPE_MISALIGNMENT);
34 }
35
36 /* Initialize the Region member */
37 #if defined(_IA64_)
38 /* On Itanium we store the region in the list head */
39 SListHead->Region = (ULONG_PTR)SListHead & VRN_MASK;
40 #else
41 /* On amd64 we don't need to store anything */
42 SListHead->Region = 0;
43 #endif /* _IA64_ */
44 #endif /* _WIN64 */
45
46 SListHead->Alignment = 0;
47 }
48
49 PSLIST_ENTRY
50 NTAPI
51 RtlFirstEntrySList(
52 _In_ const SLIST_HEADER *SListHead)
53 {
54 #if defined(_WIN64)
55 /* Check if the header is initialized as 16 byte header */
56 if (SListHead->Header16.HeaderType)
57 {
58 return (PVOID)(SListHead->Region & ~0xFLL);
59 }
60 else
61 {
62 union {
63 ULONG64 Region;
64 struct {
65 ULONG64 Reserved:4;
66 ULONG64 NextEntry:39;
67 ULONG64 Reserved2:21;
68 } Bits;
69 } Pointer;
70
71 #if defined(_IA64_)
72 /* On Itanium we stored the region in the list head */
73 Pointer.Region = SListHead->Region;;
74 #else
75 /* On amd64 we just use the list head itself */
76 Pointer.Region = (ULONG64)SListHead;
77 #endif
78 Pointer.Bits.NextEntry = SListHead->Header8.NextEntry;
79 return (PVOID)Pointer.Region;
80 }
81 #else
82 return SListHead->Next.Next;
83 #endif
84 }
85
86 WORD
87 NTAPI
88 RtlQueryDepthSList(
89 _In_ PSLIST_HEADER SListHead)
90 {
91 #if defined(_WIN64)
92 return (USHORT)(SListHead->Alignment & 0xffff);
93 #else
94 return SListHead->Depth;
95 #endif
96 }
97
98 PSLIST_ENTRY
99 FASTCALL
100 RtlInterlockedPushListSList(
101 _Inout_ PSLIST_HEADER SListHead,
102 _Inout_ __drv_aliasesMem PSLIST_ENTRY List,
103 _Inout_ PSLIST_ENTRY ListEnd,
104 _In_ ULONG Count)
105 {
106 #ifdef _WIN64
107 UNIMPLEMENTED;
108 DbgBreakPoint();
109 return NULL;
110 #else
111 SLIST_HEADER OldHeader, NewHeader;
112 ULONGLONG Compare;
113
114 /* Read the header */
115 OldHeader = *SListHead;
116
117 do
118 {
119 /* Link the last list entry */
120 ListEnd->Next = OldHeader.Next.Next;
121
122 /* Create a new header */
123 NewHeader = OldHeader;
124 NewHeader.Next.Next = List;
125 NewHeader.Depth += Count;
126 NewHeader.Sequence++;
127
128 /* Try to exchange atomically */
129 Compare = OldHeader.Alignment;
130 OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment,
131 NewHeader.Alignment,
132 Compare);
133 }
134 while (OldHeader.Alignment != Compare);
135
136 /* Return the old first entry */
137 return OldHeader.Next.Next;
138 #endif /* _WIN64 */
139 }
140
141
142 #if !defined(_M_IX86) && !defined(_M_AMD64)
143
144 _WARN("C based S-List functions can bugcheck, if not handled properly in kernel")
145
146 #ifdef _WIN64
147 #error "No generic S-List functions for WIN64!"
148 #endif
149
150 /* This variable must be used in kernel mode to prevent the system from
151 bugchecking on non-present kernel memory. If this variable is set to TRUE
152 an exception needs to be dispatched. */
153 BOOLEAN RtlpExpectSListFault;
154
155 PSLIST_ENTRY
156 NTAPI
157 RtlInterlockedPushEntrySList(
158 _Inout_ PSLIST_HEADER SListHead,
159 _Inout_ __drv_aliasesMem PSLIST_ENTRY SListEntry)
160 {
161 SLIST_HEADER OldHeader, NewHeader;
162 ULONGLONG Compare;
163
164 /* Read the header */
165 OldHeader = *SListHead;
166
167 do
168 {
169 /* Link the list entry */
170 SListEntry->Next = OldHeader.Next.Next;
171
172 /* Create a new header */
173 NewHeader = OldHeader;
174 NewHeader.Next.Next = SListEntry;
175 NewHeader.Depth++;
176 NewHeader.Sequence++;
177
178 /* Try to exchange atomically */
179 Compare = OldHeader.Alignment;
180 OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment,
181 NewHeader.Alignment,
182 Compare);
183 }
184 while (OldHeader.Alignment != Compare);
185
186 /* Return the old first entry */
187 return OldHeader.Next.Next;
188 }
189
190 PSLIST_ENTRY
191 NTAPI
192 RtlInterlockedPopEntrySList(
193 _Inout_ PSLIST_HEADER SListHead)
194 {
195 SLIST_HEADER OldHeader, NewHeader;
196 ULONGLONG Compare;
197
198 restart:
199
200 /* Read the header */
201 OldHeader = *SListHead;
202
203 do
204 {
205 /* Check for empty list */
206 if (OldHeader.Next.Next == NULL)
207 {
208 return NULL;
209 }
210
211 /* Create a new header */
212 NewHeader = OldHeader;
213
214 /* HACK to let the kernel know that we are doing slist-magic */
215 RtlpExpectSListFault = TRUE;
216
217 /* Wrapped in SEH, since OldHeader.Next.Next can already be freed */
218 _SEH2_TRY
219 {
220 NewHeader.Next = *OldHeader.Next.Next;
221 }
222 _SEH2_EXCEPT((SListHead->Next.Next != OldHeader.Next.Next) ?
223 EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH)
224 {
225 /* We got an exception and the list head changed.
226 Restart the whole operation. */
227 RtlpExpectSListFault = FALSE;
228 goto restart;
229 }
230 _SEH2_END;
231
232 /* We are done */
233 RtlpExpectSListFault = FALSE;
234
235 /* Adjust depth */
236 NewHeader.Depth--;
237
238 /* Try to exchange atomically */
239 Compare = OldHeader.Alignment;
240 OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)SListHead->Alignment,
241 NewHeader.Alignment,
242 Compare);
243 }
244 while (OldHeader.Alignment != Compare);
245
246 return OldHeader.Next.Next;
247 }
248
249 PSLIST_ENTRY
250 NTAPI
251 RtlInterlockedFlushSList(
252 _Inout_ PSLIST_HEADER SListHead)
253 {
254 SLIST_HEADER OldHeader, NewHeader;
255 ULONGLONG Compare;
256
257 /* Read the header */
258 OldHeader = *SListHead;
259
260 do
261 {
262 /* Check for empty list */
263 if (OldHeader.Next.Next == NULL)
264 {
265 return NULL;
266 }
267
268 /* Create a new header (keep the sequence number) */
269 NewHeader = OldHeader;
270 NewHeader.Next.Next = NULL;
271 NewHeader.Depth = 0;
272
273 /* Try to exchange atomically */
274 Compare = OldHeader.Alignment;
275 OldHeader.Alignment = InterlockedCompareExchange64((PLONGLONG)&SListHead->Alignment,
276 NewHeader.Alignment,
277 Compare);
278 }
279 while (OldHeader.Alignment != Compare);
280
281 /* Return the old first entry */
282 return OldHeader.Next.Next;
283
284 }
285
286 #ifdef _MSC_VER
287 #pragma comment(linker, "/alternatename:ExpInterlockedPopEntrySList=RtlInterlockedPopEntrySList")
288 #pragma comment(linker, "/alternatename:ExpInterlockedPushEntrySList=RtlInterlockedPushEntrySList")
289 #pragma comment(linker, "/alternatename:ExpInterlockedFlushSList=RtlInterlockedFlushSList")
290 #else
291 #pragma redefine_extname RtlInterlockedPopEntrySList ExpInterlockedPopEntrySList
292 #pragma redefine_extname RtlInterlockedPushEntrySList ExpInterlockedPushEntrySList
293 #pragma redefine_extname RtlInterlockedFlushSList ExpInterlockedFlushSList
294 #endif
295
296 #endif
297