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)
10 /* INCLUDES *****************************************************************/
18 BOOLEAN RtlpUse16ByteSLists
= -1;
21 /* FUNCTIONS ***************************************************************/
25 RtlInitializeSListHead(
26 _Out_ PSLIST_HEADER SListHead
)
29 /* Make sure the header is 16 byte aligned */
30 if (((ULONG_PTR
)SListHead
& 0xf) != 0)
32 DPRINT1("Unaligned SListHead: 0x%p\n", SListHead
);
33 RtlRaiseStatus(STATUS_DATATYPE_MISALIGNMENT
);
36 /* Initialize the Region member */
38 /* On Itanium we store the region in the list head */
39 SListHead
->Region
= (ULONG_PTR
)SListHead
& VRN_MASK
;
41 /* On amd64 we don't need to store anything */
42 SListHead
->Region
= 0;
46 SListHead
->Alignment
= 0;
52 _In_
const SLIST_HEADER
*SListHead
)
55 /* Check if the header is initialized as 16 byte header */
56 if (SListHead
->Header16
.HeaderType
)
58 return (PVOID
)(SListHead
->Region
& ~0xFLL
);
72 /* On Itanium we stored the region in the list head */
73 Pointer
.Region
= SListHead
->Region
;;
75 /* On amd64 we just use the list head itself */
76 Pointer
.Region
= (ULONG64
)SListHead
;
78 Pointer
.Bits
.NextEntry
= SListHead
->Header8
.NextEntry
;
79 return (PVOID
)Pointer
.Region
;
82 return SListHead
->Next
.Next
;
89 _In_ PSLIST_HEADER SListHead
)
92 return (USHORT
)(SListHead
->Alignment
& 0xffff);
94 return SListHead
->Depth
;
100 RtlInterlockedPushListSList(
101 _Inout_ PSLIST_HEADER SListHead
,
102 _Inout_ __drv_aliasesMem PSLIST_ENTRY List
,
103 _Inout_ PSLIST_ENTRY ListEnd
,
111 SLIST_HEADER OldHeader
, NewHeader
;
114 /* Read the header */
115 OldHeader
= *SListHead
;
119 /* Link the last list entry */
120 ListEnd
->Next
= OldHeader
.Next
.Next
;
122 /* Create a new header */
123 NewHeader
= OldHeader
;
124 NewHeader
.Next
.Next
= List
;
125 NewHeader
.Depth
+= Count
;
126 NewHeader
.Sequence
++;
128 /* Try to exchange atomically */
129 Compare
= OldHeader
.Alignment
;
130 OldHeader
.Alignment
= InterlockedCompareExchange64((PLONGLONG
)&SListHead
->Alignment
,
134 while (OldHeader
.Alignment
!= Compare
);
136 /* Return the old first entry */
137 return OldHeader
.Next
.Next
;
142 #if !defined(_M_IX86) && !defined(_M_AMD64)
144 _WARN("C based S-List functions can bugcheck, if not handled properly in kernel")
147 #error "No generic S-List functions for WIN64!"
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
;
157 RtlInterlockedPushEntrySList(
158 _Inout_ PSLIST_HEADER SListHead
,
159 _Inout_ __drv_aliasesMem PSLIST_ENTRY SListEntry
)
161 SLIST_HEADER OldHeader
, NewHeader
;
164 /* Read the header */
165 OldHeader
= *SListHead
;
169 /* Link the list entry */
170 SListEntry
->Next
= OldHeader
.Next
.Next
;
172 /* Create a new header */
173 NewHeader
= OldHeader
;
174 NewHeader
.Next
.Next
= SListEntry
;
176 NewHeader
.Sequence
++;
178 /* Try to exchange atomically */
179 Compare
= OldHeader
.Alignment
;
180 OldHeader
.Alignment
= InterlockedCompareExchange64((PLONGLONG
)&SListHead
->Alignment
,
184 while (OldHeader
.Alignment
!= Compare
);
186 /* Return the old first entry */
187 return OldHeader
.Next
.Next
;
192 RtlInterlockedPopEntrySList(
193 _Inout_ PSLIST_HEADER SListHead
)
195 SLIST_HEADER OldHeader
, NewHeader
;
200 /* Read the header */
201 OldHeader
= *SListHead
;
205 /* Check for empty list */
206 if (OldHeader
.Next
.Next
== NULL
)
211 /* Create a new header */
212 NewHeader
= OldHeader
;
214 /* HACK to let the kernel know that we are doing slist-magic */
215 RtlpExpectSListFault
= TRUE
;
217 /* Wrapped in SEH, since OldHeader.Next.Next can already be freed */
220 NewHeader
.Next
= *OldHeader
.Next
.Next
;
222 _SEH2_EXCEPT((SListHead
->Next
.Next
!= OldHeader
.Next
.Next
) ?
223 EXCEPTION_EXECUTE_HANDLER
: EXCEPTION_CONTINUE_SEARCH
)
225 /* We got an exception and the list head changed.
226 Restart the whole operation. */
227 RtlpExpectSListFault
= FALSE
;
233 RtlpExpectSListFault
= FALSE
;
238 /* Try to exchange atomically */
239 Compare
= OldHeader
.Alignment
;
240 OldHeader
.Alignment
= InterlockedCompareExchange64((PLONGLONG
)SListHead
->Alignment
,
244 while (OldHeader
.Alignment
!= Compare
);
246 return OldHeader
.Next
.Next
;
251 RtlInterlockedFlushSList(
252 _Inout_ PSLIST_HEADER SListHead
)
254 SLIST_HEADER OldHeader
, NewHeader
;
257 /* Read the header */
258 OldHeader
= *SListHead
;
262 /* Check for empty list */
263 if (OldHeader
.Next
.Next
== NULL
)
268 /* Create a new header (keep the sequence number) */
269 NewHeader
= OldHeader
;
270 NewHeader
.Next
.Next
= NULL
;
273 /* Try to exchange atomically */
274 Compare
= OldHeader
.Alignment
;
275 OldHeader
.Alignment
= InterlockedCompareExchange64((PLONGLONG
)&SListHead
->Alignment
,
279 while (OldHeader
.Alignment
!= Compare
);
281 /* Return the old first entry */
282 return OldHeader
.Next
.Next
;
287 #pragma comment(linker, "/alternatename:ExpInterlockedPopEntrySList=RtlInterlockedPopEntrySList")
288 #pragma comment(linker, "/alternatename:ExpInterlockedPushEntrySList=RtlInterlockedPushEntrySList")
289 #pragma comment(linker, "/alternatename:ExpInterlockedFlushSList=RtlInterlockedFlushSList")
291 #pragma redefine_extname RtlInterlockedPopEntrySList ExpInterlockedPopEntrySList
292 #pragma redefine_extname RtlInterlockedPushEntrySList ExpInterlockedPushEntrySList
293 #pragma redefine_extname RtlInterlockedFlushSList ExpInterlockedFlushSList