/src/FreeRDP/winpr/libwinpr/interlocked/interlocked.c

Source
/**
 * WinPR: Windows Portable Runtime
 * Interlocked Singly-Linked Lists
 *
 * Copyright 2012 Marc-Andre Moreau <marcandre.moreau@gmail.com>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <winpr/config.h>

#include <winpr/assert.h>
#include <winpr/wlog.h>
#include <winpr/platform.h>
#include <winpr/synch.h>
#include <winpr/handle.h>

#include <winpr/interlocked.h>

/* Singly-Linked List */

#ifndef _WIN32

#include <stdio.h>
#include <stdlib.h>

VOID InitializeSListHead(WINPR_PSLIST_HEADER ListHead)
{
  WINPR_ASSERT(ListHead);
#ifdef _WIN64
  ListHead->s.Alignment = 0;
  ListHead->s.Region = 0;
  ListHead->Header8.Init = 1;
#else
  ListHead->Alignment = 0;
#endif
}

WINPR_PSLIST_ENTRY InterlockedPushEntrySList(WINPR_PSLIST_HEADER ListHead,
                                             WINPR_PSLIST_ENTRY ListEntry)
{
  WINPR_SLIST_HEADER old = WINPR_C_ARRAY_INIT;
  WINPR_SLIST_HEADER newHeader = WINPR_C_ARRAY_INIT;

  WINPR_ASSERT(ListHead);
  WINPR_ASSERT(ListEntry);
#ifdef _WIN64
  newHeader.HeaderX64.NextEntry = (((ULONG_PTR)ListEntry) >> 4);

  while (1)
  {
    old = *ListHead;

    ListEntry->Next = (PSLIST_ENTRY)(((ULONG_PTR)old.HeaderX64.NextEntry) << 4);

    newHeader.HeaderX64.Depth = old.HeaderX64.Depth + 1;
    newHeader.HeaderX64.Sequence = old.HeaderX64.Sequence + 1;

    if (InterlockedCompareExchange64((LONGLONG*)ListHead, newHeader).Alignment, old).Alignment))
    {
      InterlockedCompareExchange64(&((LONGLONG*)ListHead)[1], newHeader).Region,
                     old).Region);
      break;
    }
  }

  return (PSLIST_ENTRY)((ULONG_PTR)old.HeaderX64.NextEntry << 4);
#else
  newHeader.s.Next.Next = ListEntry;

  do
  {
    old = *ListHead;
    ListEntry->Next = old.s.Next.Next;
    newHeader.s.Depth = old.s.Depth + 1;
    newHeader.s.Sequence = old.s.Sequence + 1;
    if (old.Alignment > INT64_MAX)
      return nullptr;
    if (newHeader.Alignment > INT64_MAX)
      return nullptr;
    if (ListHead->Alignment > INT64_MAX)
      return nullptr;
  } while (InterlockedCompareExchange64((LONGLONG*)&ListHead->Alignment,
                                        (LONGLONG)newHeader.Alignment,
                                        (LONGLONG)old.Alignment) != (LONGLONG)old.Alignment);

  return old.s.Next.Next;
#endif
}

WINPR_PSLIST_ENTRY InterlockedPushListSListEx(WINPR_ATTR_UNUSED WINPR_PSLIST_HEADER ListHead,
                                              WINPR_ATTR_UNUSED WINPR_PSLIST_ENTRY List,
                                              WINPR_ATTR_UNUSED WINPR_PSLIST_ENTRY ListEnd,
                                              WINPR_ATTR_UNUSED ULONG Count)
{
  WINPR_ASSERT(ListHead);
  WINPR_ASSERT(List);
  WINPR_ASSERT(ListEnd);

  WLog_ERR("TODO", "TODO: implement");
#ifdef _WIN64

#else

#endif
  return nullptr;
}

WINPR_PSLIST_ENTRY InterlockedPopEntrySList(WINPR_PSLIST_HEADER ListHead)
{
  WINPR_SLIST_HEADER old = WINPR_C_ARRAY_INIT;
  WINPR_SLIST_HEADER newHeader = WINPR_C_ARRAY_INIT;
  WINPR_PSLIST_ENTRY entry = nullptr;

  WINPR_ASSERT(ListHead);

#ifdef _WIN64
  while (1)
  {
    old = *ListHead;

    entry = (PSLIST_ENTRY)(((ULONG_PTR)old.HeaderX64.NextEntry) << 4);

    if (!entry)
      return nullptr;

    newHeader.HeaderX64.NextEntry = ((ULONG_PTR)entry->Next) >> 4;
    newHeader.HeaderX64.Depth = old.HeaderX64.Depth - 1;
    newHeader.HeaderX64.Sequence = old.HeaderX64.Sequence - 1;

    if (InterlockedCompareExchange64((LONGLONG*)ListHead, newHeader).Alignment, old).Alignment))
    {
      InterlockedCompareExchange64(&((LONGLONG*)ListHead)[1], newHeader).Region,
                     old).Region);
      break;
    }
  }
#else
  do
  {
    old = *ListHead;

    entry = old.s.Next.Next;

    if (!entry)
      return nullptr;

    newHeader.s.Next.Next = entry->Next;
    newHeader.s.Depth = old.s.Depth - 1;
    newHeader.s.Sequence = old.s.Sequence + 1;

    if (old.Alignment > INT64_MAX)
      return nullptr;
    if (newHeader.Alignment > INT64_MAX)
      return nullptr;
    if (ListHead->Alignment > INT64_MAX)
      return nullptr;
  } while (InterlockedCompareExchange64((LONGLONG*)&ListHead->Alignment,
                                        (LONGLONG)newHeader.Alignment,
                                        (LONGLONG)old.Alignment) != (LONGLONG)old.Alignment);
#endif
  return entry;
}

WINPR_PSLIST_ENTRY InterlockedFlushSList(WINPR_PSLIST_HEADER ListHead)
{
  WINPR_SLIST_HEADER old = WINPR_C_ARRAY_INIT;
  WINPR_SLIST_HEADER newHeader = WINPR_C_ARRAY_INIT;

  WINPR_ASSERT(ListHead);
  if (!QueryDepthSList(ListHead))
    return nullptr;

#ifdef _WIN64
  newHeader).Alignment = 0;
  newHeader).Region = 0;
  newHeader.HeaderX64.HeaderType = 1;

  while (1)
  {
    old = *ListHead;
    newHeader.HeaderX64.Sequence = old.HeaderX64.Sequence + 1;

    if (InterlockedCompareExchange64((LONGLONG*)ListHead, newHeader).Alignment, old).Alignment))
    {
      InterlockedCompareExchange64(&((LONGLONG*)ListHead)[1], newHeader).Region,
                     old).Region);
      break;
    }
  }

  return (PSLIST_ENTRY)(((ULONG_PTR)old.HeaderX64.NextEntry) << 4);
#else
  newHeader.Alignment = 0;

  do
  {
    old = *ListHead;
    newHeader.s.Sequence = old.s.Sequence + 1;

    if (old.Alignment > INT64_MAX)
      return nullptr;
    if (newHeader.Alignment > INT64_MAX)
      return nullptr;
    if (ListHead->Alignment > INT64_MAX)
      return nullptr;
  } while (InterlockedCompareExchange64((LONGLONG*)&ListHead->Alignment,
                                        (LONGLONG)newHeader.Alignment,
                                        (LONGLONG)old.Alignment) != (LONGLONG)old.Alignment);

  return old.s.Next.Next;
#endif
}

USHORT QueryDepthSList(WINPR_PSLIST_HEADER ListHead)
{
  WINPR_ASSERT(ListHead);

#ifdef _WIN64
  return ListHead->HeaderX64.Depth;
#else
  return ListHead->s.Depth;
#endif
}

LONG InterlockedIncrement(LONG volatile* Addend)
{
  WINPR_ASSERT(Addend);

#if defined(__GNUC__) || defined(__clang__)
  WINPR_PRAGMA_DIAG_PUSH
  WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
  return __sync_add_and_fetch(Addend, 1);
  WINPR_PRAGMA_DIAG_POP
#else
  return 0;
#endif
}

LONG InterlockedDecrement(LONG volatile* Addend)
{
  WINPR_ASSERT(Addend);

#if defined(__GNUC__) || defined(__clang__)
  WINPR_PRAGMA_DIAG_PUSH
  WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
  return __sync_sub_and_fetch(Addend, 1);
  WINPR_PRAGMA_DIAG_POP
#else
  return 0;
#endif
}

LONG InterlockedExchange(LONG volatile* Target, LONG Value)
{
  WINPR_ASSERT(Target);

#if defined(__GNUC__) || defined(__clang__)
  WINPR_PRAGMA_DIAG_PUSH
  WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
  return __sync_val_compare_and_swap(Target, *Target, Value);
  WINPR_PRAGMA_DIAG_POP
#else
  return 0;
#endif
}

LONG InterlockedExchangeAdd(LONG volatile* Addend, LONG Value)
{
  WINPR_ASSERT(Addend);

#if defined(__GNUC__) || defined(__clang__)
  WINPR_PRAGMA_DIAG_PUSH
  WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
  return __sync_fetch_and_add(Addend, Value);
  WINPR_PRAGMA_DIAG_POP
#else
  return 0;
#endif
}

LONG InterlockedCompareExchange(LONG volatile* Destination, LONG Exchange, LONG Comperand)
{
  WINPR_ASSERT(Destination);

#if defined(__GNUC__) || defined(__clang__)
  WINPR_PRAGMA_DIAG_PUSH
  WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
  return __sync_val_compare_and_swap(Destination, Comperand, Exchange);
  WINPR_PRAGMA_DIAG_POP
#else
  return 0;
#endif
}

PVOID InterlockedCompareExchangePointer(PVOID volatile* Destination, PVOID Exchange,
                                        PVOID Comperand)
{
  WINPR_ASSERT(Destination);

#if defined(__GNUC__) || defined(__clang__)
  WINPR_PRAGMA_DIAG_PUSH
  WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
  return __sync_val_compare_and_swap(Destination, Comperand, Exchange);
  WINPR_PRAGMA_DIAG_POP
#else
  return 0;
#endif
}

#endif /* _WIN32 */

#if defined(_WIN32) && !defined(WINPR_INTERLOCKED_COMPARE_EXCHANGE64)

/* InterlockedCompareExchange64 already defined */

#elif defined(_WIN32) && defined(WINPR_INTERLOCKED_COMPARE_EXCHANGE64)

static volatile HANDLE mutex = nullptr;

BOOL static_mutex_lock(volatile HANDLE* static_mutex)
{
  if (*static_mutex == nullptr)
  {
    HANDLE handle;

    if (!(handle = CreateMutex(nullptr, FALSE, nullptr)))
      return FALSE;

    if (InterlockedCompareExchangePointer((PVOID*)static_mutex, (PVOID)handle, nullptr) !=
        nullptr)
      (void)CloseHandle(handle);
  }

  return (WaitForSingleObject(*static_mutex, INFINITE) == WAIT_OBJECT_0);
}

LONGLONG InterlockedCompareExchange64(LONGLONG volatile* Destination, LONGLONG Exchange,
                                      LONGLONG Comperand)
{
  LONGLONG previousValue = 0;
  BOOL locked = static_mutex_lock(&mutex);

  previousValue = *Destination;

  if (*Destination == Comperand)
    *Destination = Exchange;

  if (locked)
    (void)ReleaseMutex(mutex);
  else
    (void)fprintf(stderr,
                  "WARNING: InterlockedCompareExchange64 operation might have failed\n");

  return previousValue;
}

#elif (defined(ANDROID) && ANDROID) || \
    (defined(__GNUC__) && !defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_8))

#include <pthread.h>

static pthread_mutex_t mutex;

LONGLONG InterlockedCompareExchange64(LONGLONG volatile* Destination, LONGLONG Exchange,
                                      LONGLONG Comperand)
{
  LONGLONG previousValue = 0;

  pthread_mutex_lock(&mutex);

  previousValue = *Destination;

  if (*Destination == Comperand)
    *Destination = Exchange;

  pthread_mutex_unlock(&mutex);

  return previousValue;
}

#else

LONGLONG InterlockedCompareExchange64(LONGLONG volatile* Destination, LONGLONG Exchange,
                                      LONGLONG Comperand)
{
  WINPR_ASSERT(Destination);

#if defined(__GNUC__) || defined(__clang__)
  WINPR_PRAGMA_DIAG_PUSH
  WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
  return __sync_val_compare_and_swap(Destination, Comperand, Exchange);
  WINPR_PRAGMA_DIAG_POP
#else
  return 0;
#endif
}

#endif

/* Doubly-Linked List */

/**
 * Kernel-Mode Basics: Windows Linked Lists:
 * http://www.osronline.com/article.cfm?article=499
 *
 * Singly and Doubly Linked Lists:
 * http://msdn.microsoft.com/en-us/library/windows/hardware/ff563802/
 */

VOID InitializeListHead(WINPR_PLIST_ENTRY ListHead)
{
  WINPR_ASSERT(ListHead);
  ListHead->Flink = ListHead->Blink = ListHead;
}

BOOL IsListEmpty(const WINPR_LIST_ENTRY* ListHead)
{
  WINPR_ASSERT(ListHead);
  return (BOOL)(ListHead->Flink == ListHead);
}

BOOL RemoveEntryList(WINPR_PLIST_ENTRY Entry)
{
  WINPR_ASSERT(Entry);
  WINPR_PLIST_ENTRY OldFlink = Entry->Flink;
  WINPR_ASSERT(OldFlink);

  WINPR_PLIST_ENTRY OldBlink = Entry->Blink;
  WINPR_ASSERT(OldBlink);

  OldFlink->Blink = OldBlink;
  OldBlink->Flink = OldFlink;

  return (BOOL)(OldFlink == OldBlink);
}

VOID InsertHeadList(WINPR_PLIST_ENTRY ListHead, WINPR_PLIST_ENTRY Entry)
{
  WINPR_ASSERT(ListHead);
  WINPR_ASSERT(Entry);

  WINPR_PLIST_ENTRY OldFlink = ListHead->Flink;
  WINPR_ASSERT(OldFlink);

  Entry->Flink = OldFlink;
  Entry->Blink = ListHead;
  OldFlink->Blink = Entry;
  ListHead->Flink = Entry;
}

WINPR_PLIST_ENTRY RemoveHeadList(WINPR_PLIST_ENTRY ListHead)
{
  WINPR_ASSERT(ListHead);

  WINPR_PLIST_ENTRY Entry = ListHead->Flink;
  WINPR_ASSERT(Entry);

  WINPR_PLIST_ENTRY Flink = Entry->Flink;
  WINPR_ASSERT(Flink);

  ListHead->Flink = Flink;
  Flink->Blink = ListHead;

  return Entry;
}

VOID InsertTailList(WINPR_PLIST_ENTRY ListHead, WINPR_PLIST_ENTRY Entry)
{
  WINPR_ASSERT(ListHead);
  WINPR_ASSERT(Entry);

  WINPR_PLIST_ENTRY OldBlink = ListHead->Blink;
  WINPR_ASSERT(OldBlink);

  Entry->Flink = ListHead;
  Entry->Blink = OldBlink;
  OldBlink->Flink = Entry;
  ListHead->Blink = Entry;
}

WINPR_PLIST_ENTRY RemoveTailList(WINPR_PLIST_ENTRY ListHead)
{
  WINPR_ASSERT(ListHead);

  WINPR_PLIST_ENTRY Entry = ListHead->Blink;
  WINPR_ASSERT(Entry);

  WINPR_PLIST_ENTRY Blink = Entry->Blink;
  WINPR_ASSERT(Blink);

  ListHead->Blink = Blink;
  Blink->Flink = ListHead;

  return Entry;
}

VOID AppendTailList(WINPR_PLIST_ENTRY ListHead, WINPR_PLIST_ENTRY ListToAppend)
{
  WINPR_ASSERT(ListHead);
  WINPR_ASSERT(ListToAppend);

  WINPR_PLIST_ENTRY ListEnd = ListHead->Blink;

  ListHead->Blink->Flink = ListToAppend;
  ListHead->Blink = ListToAppend->Blink;
  ListToAppend->Blink->Flink = ListHead;
  ListToAppend->Blink = ListEnd;
}

VOID PushEntryList(WINPR_PSINGLE_LIST_ENTRY ListHead, WINPR_PSINGLE_LIST_ENTRY Entry)
{
  WINPR_ASSERT(ListHead);
  WINPR_ASSERT(Entry);

  Entry->Next = ListHead->Next;
  ListHead->Next = Entry;
}

WINPR_PSINGLE_LIST_ENTRY PopEntryList(WINPR_PSINGLE_LIST_ENTRY ListHead)
{
  WINPR_ASSERT(ListHead);
  WINPR_PSINGLE_LIST_ENTRY FirstEntry = ListHead->Next;

  if (FirstEntry != nullptr)
    ListHead->Next = FirstEntry->Next;

  return FirstEntry;
}

Coverage Report

Created: 2026-03-04 06:14

Line	Count	Source
1		/**
2		* WinPR: Windows Portable Runtime
3		* Interlocked Singly-Linked Lists
4		*
5		* Copyright 2012 Marc-Andre Moreau <marcandre.moreau@gmail.com>
6		*
7		* Licensed under the Apache License, Version 2.0 (the "License");
8		* you may not use this file except in compliance with the License.
9		* You may obtain a copy of the License at
10		*
11		* http://www.apache.org/licenses/LICENSE-2.0
12		*
13		* Unless required by applicable law or agreed to in writing, software
14		* distributed under the License is distributed on an "AS IS" BASIS,
15		* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16		* See the License for the specific language governing permissions and
17		* limitations under the License.
18		*/
19
20		#include <winpr/config.h>
21
22		#include <winpr/assert.h>
23		#include <winpr/wlog.h>
24		#include <winpr/platform.h>
25		#include <winpr/synch.h>
26		#include <winpr/handle.h>
27
28		#include <winpr/interlocked.h>
29
30		/* Singly-Linked List */
31
32		#ifndef _WIN32
33
34		#include <stdio.h>
35		#include <stdlib.h>
36
37		VOID InitializeSListHead(WINPR_PSLIST_HEADER ListHead)
38	0	{
39	0	WINPR_ASSERT(ListHead);
40		#ifdef _WIN64
41		ListHead->s.Alignment = 0;
42		ListHead->s.Region = 0;
43		ListHead->Header8.Init = 1;
44		#else
45	0	ListHead->Alignment = 0;
46	0	#endif
47	0	}
48
49		WINPR_PSLIST_ENTRY InterlockedPushEntrySList(WINPR_PSLIST_HEADER ListHead,
50		WINPR_PSLIST_ENTRY ListEntry)
51	0	{
52	0	WINPR_SLIST_HEADER old = WINPR_C_ARRAY_INIT;
53	0	WINPR_SLIST_HEADER newHeader = WINPR_C_ARRAY_INIT;
54
55	0	WINPR_ASSERT(ListHead);
56	0	WINPR_ASSERT(ListEntry);
57		#ifdef _WIN64
58		newHeader.HeaderX64.NextEntry = (((ULONG_PTR)ListEntry) >> 4);
59
60		while (1)
61		{
62		old = *ListHead;
63
64		ListEntry->Next = (PSLIST_ENTRY)(((ULONG_PTR)old.HeaderX64.NextEntry) << 4);
65
66		newHeader.HeaderX64.Depth = old.HeaderX64.Depth + 1;
67		newHeader.HeaderX64.Sequence = old.HeaderX64.Sequence + 1;
68
69		if (InterlockedCompareExchange64((LONGLONG*)ListHead, newHeader).Alignment, old).Alignment))
70		{
71		InterlockedCompareExchange64(&((LONGLONG*)ListHead)[1], newHeader).Region,
72		old).Region);
73		break;
74		}
75		}
76
77		return (PSLIST_ENTRY)((ULONG_PTR)old.HeaderX64.NextEntry << 4);
78		#else
79	0	newHeader.s.Next.Next = ListEntry;
80
81	0	do
82	0	{
83	0	old = *ListHead;
84	0	ListEntry->Next = old.s.Next.Next;
85	0	newHeader.s.Depth = old.s.Depth + 1;
86	0	newHeader.s.Sequence = old.s.Sequence + 1;
87	0	if (old.Alignment > INT64_MAX)
88	0	return nullptr;
89	0	if (newHeader.Alignment > INT64_MAX)
90	0	return nullptr;
91	0	if (ListHead->Alignment > INT64_MAX)
92	0	return nullptr;
93	0	} while (InterlockedCompareExchange64((LONGLONG*)&ListHead->Alignment,
94	0	(LONGLONG)newHeader.Alignment,
95	0	(LONGLONG)old.Alignment) != (LONGLONG)old.Alignment);
96
97	0	return old.s.Next.Next;
98	0	#endif
99	0	}
100
101		WINPR_PSLIST_ENTRY InterlockedPushListSListEx(WINPR_ATTR_UNUSED WINPR_PSLIST_HEADER ListHead,
102		WINPR_ATTR_UNUSED WINPR_PSLIST_ENTRY List,
103		WINPR_ATTR_UNUSED WINPR_PSLIST_ENTRY ListEnd,
104		WINPR_ATTR_UNUSED ULONG Count)
105	0	{
106	0	WINPR_ASSERT(ListHead);
107	0	WINPR_ASSERT(List);
108	0	WINPR_ASSERT(ListEnd);
109
110	0	WLog_ERR("TODO", "TODO: implement");
111		#ifdef _WIN64
112
113		#else
114
115	0	#endif
116	0	return nullptr;
117	0	}
118
119		WINPR_PSLIST_ENTRY InterlockedPopEntrySList(WINPR_PSLIST_HEADER ListHead)
120	0	{
121	0	WINPR_SLIST_HEADER old = WINPR_C_ARRAY_INIT;
122	0	WINPR_SLIST_HEADER newHeader = WINPR_C_ARRAY_INIT;
123	0	WINPR_PSLIST_ENTRY entry = nullptr;
124
125	0	WINPR_ASSERT(ListHead);
126
127		#ifdef _WIN64
128		while (1)
129		{
130		old = *ListHead;
131
132		entry = (PSLIST_ENTRY)(((ULONG_PTR)old.HeaderX64.NextEntry) << 4);
133
134		if (!entry)
135		return nullptr;
136
137		newHeader.HeaderX64.NextEntry = ((ULONG_PTR)entry->Next) >> 4;
138		newHeader.HeaderX64.Depth = old.HeaderX64.Depth - 1;
139		newHeader.HeaderX64.Sequence = old.HeaderX64.Sequence - 1;
140
141		if (InterlockedCompareExchange64((LONGLONG*)ListHead, newHeader).Alignment, old).Alignment))
142		{
143		InterlockedCompareExchange64(&((LONGLONG*)ListHead)[1], newHeader).Region,
144		old).Region);
145		break;
146		}
147		}
148		#else
149	0	do
150	0	{
151	0	old = *ListHead;
152
153	0	entry = old.s.Next.Next;
154
155	0	if (!entry)
156	0	return nullptr;
157
158	0	newHeader.s.Next.Next = entry->Next;
159	0	newHeader.s.Depth = old.s.Depth - 1;
160	0	newHeader.s.Sequence = old.s.Sequence + 1;
161
162	0	if (old.Alignment > INT64_MAX)
163	0	return nullptr;
164	0	if (newHeader.Alignment > INT64_MAX)
165	0	return nullptr;
166	0	if (ListHead->Alignment > INT64_MAX)
167	0	return nullptr;
168	0	} while (InterlockedCompareExchange64((LONGLONG*)&ListHead->Alignment,
169	0	(LONGLONG)newHeader.Alignment,
170	0	(LONGLONG)old.Alignment) != (LONGLONG)old.Alignment);
171	0	#endif
172	0	return entry;
173	0	}
174
175		WINPR_PSLIST_ENTRY InterlockedFlushSList(WINPR_PSLIST_HEADER ListHead)
176	0	{
177	0	WINPR_SLIST_HEADER old = WINPR_C_ARRAY_INIT;
178	0	WINPR_SLIST_HEADER newHeader = WINPR_C_ARRAY_INIT;
179
180	0	WINPR_ASSERT(ListHead);
181	0	if (!QueryDepthSList(ListHead))
182	0	return nullptr;
183
184		#ifdef _WIN64
185		newHeader).Alignment = 0;
186		newHeader).Region = 0;
187		newHeader.HeaderX64.HeaderType = 1;
188
189		while (1)
190		{
191		old = *ListHead;
192		newHeader.HeaderX64.Sequence = old.HeaderX64.Sequence + 1;
193
194		if (InterlockedCompareExchange64((LONGLONG*)ListHead, newHeader).Alignment, old).Alignment))
195		{
196		InterlockedCompareExchange64(&((LONGLONG*)ListHead)[1], newHeader).Region,
197		old).Region);
198		break;
199		}
200		}
201
202		return (PSLIST_ENTRY)(((ULONG_PTR)old.HeaderX64.NextEntry) << 4);
203		#else
204	0	newHeader.Alignment = 0;
205
206	0	do
207	0	{
208	0	old = *ListHead;
209	0	newHeader.s.Sequence = old.s.Sequence + 1;
210
211	0	if (old.Alignment > INT64_MAX)
212	0	return nullptr;
213	0	if (newHeader.Alignment > INT64_MAX)
214	0	return nullptr;
215	0	if (ListHead->Alignment > INT64_MAX)
216	0	return nullptr;
217	0	} while (InterlockedCompareExchange64((LONGLONG*)&ListHead->Alignment,
218	0	(LONGLONG)newHeader.Alignment,
219	0	(LONGLONG)old.Alignment) != (LONGLONG)old.Alignment);
220
221	0	return old.s.Next.Next;
222	0	#endif
223	0	}
224
225		USHORT QueryDepthSList(WINPR_PSLIST_HEADER ListHead)
226	0	{
227	0	WINPR_ASSERT(ListHead);
228
229		#ifdef _WIN64
230		return ListHead->HeaderX64.Depth;
231		#else
232	0	return ListHead->s.Depth;
233	0	#endif
234	0	}
235
236		LONG InterlockedIncrement(LONG volatile* Addend)
237	2.65M	{
238	2.65M	WINPR_ASSERT(Addend);
239
240	2.65M	#if defined(__GNUC__) \|\| defined(__clang__)
241	2.65M	WINPR_PRAGMA_DIAG_PUSH
242	2.65M	WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
243	2.65M	return __sync_add_and_fetch(Addend, 1);
244	2.65M	WINPR_PRAGMA_DIAG_POP
245		#else
246		return 0;
247		#endif
248	2.65M	}
249
250		LONG InterlockedDecrement(LONG volatile* Addend)
251	2.65M	{
252	2.65M	WINPR_ASSERT(Addend);
253
254	2.65M	#if defined(__GNUC__) \|\| defined(__clang__)
255	2.65M	WINPR_PRAGMA_DIAG_PUSH
256	2.65M	WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
257	2.65M	return __sync_sub_and_fetch(Addend, 1);
258	2.65M	WINPR_PRAGMA_DIAG_POP
259		#else
260		return 0;
261		#endif
262	2.65M	}
263
264		LONG InterlockedExchange(LONG volatile* Target, LONG Value)
265	0	{
266	0	WINPR_ASSERT(Target);
267
268	0	#if defined(__GNUC__) \|\| defined(__clang__)
269	0	WINPR_PRAGMA_DIAG_PUSH
270	0	WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
271	0	return __sync_val_compare_and_swap(Target, *Target, Value);
272	0	WINPR_PRAGMA_DIAG_POP
273		#else
274		return 0;
275		#endif
276	0	}
277
278		LONG InterlockedExchangeAdd(LONG volatile* Addend, LONG Value)
279	0	{
280	0	WINPR_ASSERT(Addend);
281
282	0	#if defined(__GNUC__) \|\| defined(__clang__)
283	0	WINPR_PRAGMA_DIAG_PUSH
284	0	WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
285	0	return __sync_fetch_and_add(Addend, Value);
286	0	WINPR_PRAGMA_DIAG_POP
287		#else
288		return 0;
289		#endif
290	0	}
291
292		LONG InterlockedCompareExchange(LONG volatile* Destination, LONG Exchange, LONG Comperand)
293	0	{
294	0	WINPR_ASSERT(Destination);
295
296	0	#if defined(__GNUC__) \|\| defined(__clang__)
297	0	WINPR_PRAGMA_DIAG_PUSH
298	0	WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
299	0	return __sync_val_compare_and_swap(Destination, Comperand, Exchange);
300	0	WINPR_PRAGMA_DIAG_POP
301		#else
302		return 0;
303		#endif
304	0	}
305
306		PVOID InterlockedCompareExchangePointer(PVOID volatile* Destination, PVOID Exchange,
307		PVOID Comperand)
308	6	{
309	6	WINPR_ASSERT(Destination);
310
311	6	#if defined(__GNUC__) \|\| defined(__clang__)
312	6	WINPR_PRAGMA_DIAG_PUSH
313	6	WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
314	6	return __sync_val_compare_and_swap(Destination, Comperand, Exchange);
315	6	WINPR_PRAGMA_DIAG_POP
316		#else
317		return 0;
318		#endif
319	6	}
320
321		#endif /* _WIN32 */
322
323		#if defined(_WIN32) && !defined(WINPR_INTERLOCKED_COMPARE_EXCHANGE64)
324
325		/* InterlockedCompareExchange64 already defined */
326
327		#elif defined(_WIN32) && defined(WINPR_INTERLOCKED_COMPARE_EXCHANGE64)
328
329		static volatile HANDLE mutex = nullptr;
330
331		BOOL static_mutex_lock(volatile HANDLE* static_mutex)
332		{
333		if (*static_mutex == nullptr)
334		{
335		HANDLE handle;
336
337		if (!(handle = CreateMutex(nullptr, FALSE, nullptr)))
338		return FALSE;
339
340		if (InterlockedCompareExchangePointer((PVOID*)static_mutex, (PVOID)handle, nullptr) !=
341		nullptr)
342		(void)CloseHandle(handle);
343		}
344
345		return (WaitForSingleObject(*static_mutex, INFINITE) == WAIT_OBJECT_0);
346		}
347
348		LONGLONG InterlockedCompareExchange64(LONGLONG volatile* Destination, LONGLONG Exchange,
349		LONGLONG Comperand)
350		{
351		LONGLONG previousValue = 0;
352		BOOL locked = static_mutex_lock(&mutex);
353
354		previousValue = *Destination;
355
356		if (*Destination == Comperand)
357		*Destination = Exchange;
358
359		if (locked)
360		(void)ReleaseMutex(mutex);
361		else
362		(void)fprintf(stderr,
363		"WARNING: InterlockedCompareExchange64 operation might have failed\n");
364
365		return previousValue;
366		}
367
368		#elif (defined(ANDROID) && ANDROID) \|\| \
369		(defined(__GNUC__) && !defined(__GCC_HAVE_SYNC_COMPARE_AND_SWAP_8))
370
371		#include <pthread.h>
372
373		static pthread_mutex_t mutex;
374
375		LONGLONG InterlockedCompareExchange64(LONGLONG volatile* Destination, LONGLONG Exchange,
376		LONGLONG Comperand)
377		{
378		LONGLONG previousValue = 0;
379
380		pthread_mutex_lock(&mutex);
381
382		previousValue = *Destination;
383
384		if (*Destination == Comperand)
385		*Destination = Exchange;
386
387		pthread_mutex_unlock(&mutex);
388
389		return previousValue;
390		}
391
392		#else
393
394		LONGLONG InterlockedCompareExchange64(LONGLONG volatile* Destination, LONGLONG Exchange,
395		LONGLONG Comperand)
396	0	{
397	0	WINPR_ASSERT(Destination);
398
399	0	#if defined(__GNUC__) \|\| defined(__clang__)
400	0	WINPR_PRAGMA_DIAG_PUSH
401	0	WINPR_PRAGMA_DIAG_IGNORED_ATOMIC_SEQ_CST
402	0	return __sync_val_compare_and_swap(Destination, Comperand, Exchange);
403	0	WINPR_PRAGMA_DIAG_POP
404		#else
405		return 0;
406		#endif
407	0	}
408
409		#endif
410
411		/* Doubly-Linked List */
412
413		/**
414		* Kernel-Mode Basics: Windows Linked Lists:
415		* http://www.osronline.com/article.cfm?article=499
416		*
417		* Singly and Doubly Linked Lists:
418		* http://msdn.microsoft.com/en-us/library/windows/hardware/ff563802/
419		*/
420
421		VOID InitializeListHead(WINPR_PLIST_ENTRY ListHead)
422	0	{
423	0	WINPR_ASSERT(ListHead);
424	0	ListHead->Flink = ListHead->Blink = ListHead;
425	0	}
426
427		BOOL IsListEmpty(const WINPR_LIST_ENTRY* ListHead)
428	0	{
429	0	WINPR_ASSERT(ListHead);
430	0	return (BOOL)(ListHead->Flink == ListHead);
431	0	}
432
433		BOOL RemoveEntryList(WINPR_PLIST_ENTRY Entry)
434	0	{
435	0	WINPR_ASSERT(Entry);
436	0	WINPR_PLIST_ENTRY OldFlink = Entry->Flink;
437	0	WINPR_ASSERT(OldFlink);
438
439	0	WINPR_PLIST_ENTRY OldBlink = Entry->Blink;
440	0	WINPR_ASSERT(OldBlink);
441
442	0	OldFlink->Blink = OldBlink;
443	0	OldBlink->Flink = OldFlink;
444
445	0	return (BOOL)(OldFlink == OldBlink);
446	0	}
447
448		VOID InsertHeadList(WINPR_PLIST_ENTRY ListHead, WINPR_PLIST_ENTRY Entry)
449	0	{
450	0	WINPR_ASSERT(ListHead);
451	0	WINPR_ASSERT(Entry);
452
453	0	WINPR_PLIST_ENTRY OldFlink = ListHead->Flink;
454	0	WINPR_ASSERT(OldFlink);
455
456	0	Entry->Flink = OldFlink;
457	0	Entry->Blink = ListHead;
458	0	OldFlink->Blink = Entry;
459	0	ListHead->Flink = Entry;
460	0	}
461
462		WINPR_PLIST_ENTRY RemoveHeadList(WINPR_PLIST_ENTRY ListHead)
463	0	{
464	0	WINPR_ASSERT(ListHead);
465
466	0	WINPR_PLIST_ENTRY Entry = ListHead->Flink;
467	0	WINPR_ASSERT(Entry);
468
469	0	WINPR_PLIST_ENTRY Flink = Entry->Flink;
470	0	WINPR_ASSERT(Flink);
471
472	0	ListHead->Flink = Flink;
473	0	Flink->Blink = ListHead;
474
475	0	return Entry;
476	0	}
477
478		VOID InsertTailList(WINPR_PLIST_ENTRY ListHead, WINPR_PLIST_ENTRY Entry)
479	0	{
480	0	WINPR_ASSERT(ListHead);
481	0	WINPR_ASSERT(Entry);
482
483	0	WINPR_PLIST_ENTRY OldBlink = ListHead->Blink;
484	0	WINPR_ASSERT(OldBlink);
485
486	0	Entry->Flink = ListHead;
487	0	Entry->Blink = OldBlink;
488	0	OldBlink->Flink = Entry;
489	0	ListHead->Blink = Entry;
490	0	}
491
492		WINPR_PLIST_ENTRY RemoveTailList(WINPR_PLIST_ENTRY ListHead)
493	0	{
494	0	WINPR_ASSERT(ListHead);
495
496	0	WINPR_PLIST_ENTRY Entry = ListHead->Blink;
497	0	WINPR_ASSERT(Entry);
498
499	0	WINPR_PLIST_ENTRY Blink = Entry->Blink;
500	0	WINPR_ASSERT(Blink);
501
502	0	ListHead->Blink = Blink;
503	0	Blink->Flink = ListHead;
504
505	0	return Entry;
506	0	}
507
508		VOID AppendTailList(WINPR_PLIST_ENTRY ListHead, WINPR_PLIST_ENTRY ListToAppend)
509	0	{
510	0	WINPR_ASSERT(ListHead);
511	0	WINPR_ASSERT(ListToAppend);
512
513	0	WINPR_PLIST_ENTRY ListEnd = ListHead->Blink;
514
515	0	ListHead->Blink->Flink = ListToAppend;
516	0	ListHead->Blink = ListToAppend->Blink;
517	0	ListToAppend->Blink->Flink = ListHead;
518	0	ListToAppend->Blink = ListEnd;
519	0	}
520
521		VOID PushEntryList(WINPR_PSINGLE_LIST_ENTRY ListHead, WINPR_PSINGLE_LIST_ENTRY Entry)
522	0	{
523	0	WINPR_ASSERT(ListHead);
524	0	WINPR_ASSERT(Entry);
525
526	0	Entry->Next = ListHead->Next;
527	0	ListHead->Next = Entry;
528	0	}
529
530		WINPR_PSINGLE_LIST_ENTRY PopEntryList(WINPR_PSINGLE_LIST_ENTRY ListHead)
531	0	{
532	0	WINPR_ASSERT(ListHead);
533	0	WINPR_PSINGLE_LIST_ENTRY FirstEntry = ListHead->Next;
534
535	0	if (FirstEntry != nullptr)
536	0	ListHead->Next = FirstEntry->Next;
537
538	0	return FirstEntry;
539	0	}