1e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott/* 2e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Copyright (c) 1997-1999 3e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Silicon Graphics Computer Systems, Inc. 4e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 5e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Copyright (c) 1999 6e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Boris Fomitchev 7e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 8e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * This material is provided "as is", with absolutely no warranty expressed 9e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * or implied. Any use is at your own risk. 10e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 11e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Permission to use or copy this software for any purpose is hereby granted 12e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * without fee, provided the above notices are retained on all copies. 13e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Permission to modify the code and to distribute modified code is granted, 14e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * provided the above notices are retained, and a notice that the code was 15e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * modified is included with the above copyright notice. 16e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 17e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 18e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 19e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#ifndef _STLP_LOCK_FREE_SLIST_H 20e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#define _STLP_LOCK_FREE_SLIST_H 21e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 22e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined(_STLP_PTHREADS) 23e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# include <pthread.h> 24e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 25e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (__GNUC__) && defined (__i386__) 26e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 27e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# define _STLP_HAS_ATOMIC_FREELIST 28e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott/** 29e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Class that implements a non-blocking and thread-safe freelist. 30e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * It is used for the lock-free node allocation engine. 31e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 32e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * @author felixw@inin.com 33e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 34e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottclass _STLP_atomic_freelist { 35e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottpublic: 36e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott /** 37e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Type representing items of the freelist 38e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 39e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott struct item { 40e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott item* _M_next; 41e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott }; 42e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 43e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_atomic_freelist() { 44e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Statically assert layout of member is as expected by assembly code 45e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STATIC_ASSERT(sizeof(_M) == 8) 46e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M._M_data._M_top = 0; 47e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M._M_data._M_sequence = 0; 48e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 49e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 50e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott /** 51e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Atomically pushes the specified item onto the freelist. 52e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 53e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * @param __item [in] Item to add to the front of the list 54e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 55e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void push(item* __item) { 56e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // NOTE: GCC uses ebx as the PIC register for globals in shared libraries. 57e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // The GCC version I'm using (3.4.1) won't temporarily spill it if it's 58e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // used as input, output, or clobber. Instead, it complains with a 59e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // "can't find a register in class `BREG' while reloading `asm'" error. 60e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // This is probably a compiler bug, but as the cmpxchg8b instruction 61e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // requires ebx, I work around this here by using ecx for the '__item' 62e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // input and spilling ebx into edi. This also precludes us from using 63e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // a "m" operand for the cmpxchg8b argument (GCC might think it can make 64e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // it relative to ebx). Instead, we're using esi for the address of _M_data. 65e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // 66e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott int __tmp1; // These dummy variables are used to tell GCC that the eax, ecx, 67e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott int __tmp2; // and edx registers will not have the same value as their input. 68e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott int __tmp3; // The optimizer will remove them as their values are not used. 69e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __asm__ __volatile__ 70e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott (" movl %%ebx, %%edi\n\t" 71e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " movl %%ecx, %%ebx\n\t" 72e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "L1_%=: movl %%eax, (%%ebx)\n\t" // __item._M_next = _M._M_data._M_top 73e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " leal 1(%%edx),%%ecx\n\t" // new sequence = _M._M_data._M_sequence + 1 74e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "lock; cmpxchg8b (%%esi)\n\t" 75e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " jne L1_%=\n\t" // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top) 76e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " movl %%edi, %%ebx" 77e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott :"=a" (__tmp1), "=d" (__tmp2), "=c" (__tmp3) 78e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "c" (__item), "S" (&_M._M_data) 79e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott :"edi", "memory", "cc"); 80e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 81e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 82e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott /** 83e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Atomically removes the topmost item from the freelist and returns a 84e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * pointer to it. Returns NULL if the list is empty. 85e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 86e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * @return Item that was removed from front of list; NULL if list empty 87e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 88e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott item* pop() { 89e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott item* __result; 90e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott int __tmp; 91e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __asm__ __volatile__ 92e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott (" movl %%ebx, %%edi\n\t" 93e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "L1_%=: testl %%eax, %%eax\n\t" // _M_top == NULL? 94e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " je L2_%=\n\t" // If yes, we're done 95e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " movl (%%eax), %%ebx\n\t" // new top = _M._M_data._M_top->_M_next 96e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " leal 1(%%edx),%%ecx\n\t" // new sequence = _M._M_data._M_sequence + 1 97e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "lock; cmpxchg8b (%%esi)\n\t" 98e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " jne L1_%=\n\t" // We failed, retry! (edx:eax now contain most recent _M_sequence:_M_top) 99e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "L2_%=: movl %%edi, %%ebx" 100e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott :"=a" (__result), "=d" (__tmp) 101e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data) 102e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott :"edi", "ecx", "memory", "cc"); 103e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return __result; 104e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 105e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 106e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott /** 107e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Atomically detaches all items from the list and returns a pointer to the 108e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * topmost item. The items are still chained and may be traversed safely as 109e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * they're now "owned" by the calling thread. 110e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 111e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * @return Pointer to topmost item in the list; NULL if list empty 112e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 113e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott item* clear() { 114e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott item* __result; 115e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott int __tmp; 116e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __asm__ __volatile__ 117e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott (" movl %%ebx, %%edi\n\t" 118e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "L1_%=: testl %%eax, %%eax\n\t" // _M_top == NULL? 119e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " je L2_%=\n\t" // If yes, we're done 120e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " xorl %%ebx, %%ebx\n\t" // We're attempting to set _M_top to NULL 121e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " leal 1(%%edx),%%ecx\n\t" // new sequence = _M._M_data._M_sequence + 1 122e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "lock; cmpxchg8b (%%esi)\n\t" 123e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott " jne L1_%=\n\t" // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top) 124e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott "L2_%=: movl %%edi, %%ebx" 125e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott :"=a" (__result), "=d" (__tmp) 126e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data) 127e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott :"edi", "ecx", "memory", "cc"); 128e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return __result; 129e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 130e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 131e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottprivate: 132e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott union { 133e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott long long _M_align; 134e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott struct { 135e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott item* _M_top; // Topmost element in the freelist 136e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott unsigned int _M_sequence; // Sequence counter to prevent "ABA problem" 137e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } _M_data; 138e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } _M; 139e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 140e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_atomic_freelist(const _STLP_atomic_freelist&); 141e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_atomic_freelist& operator=(const _STLP_atomic_freelist&); 142e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott}; 143e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 144e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif /* if defined(__GNUC__) && defined(__i386__) */ 145e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 146e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#elif defined (_STLP_WIN32THREADS) 147e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 148e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if !defined (_WIN64) 149e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# define _STLP_USE_ASM_IMPLEMENTATION 150e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 151e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 152e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// Here are the compiler/platform requirements for the thread safe and 153e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// lock free singly linked list implementation: 154e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_USE_ASM_IMPLEMENTATION) 155e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// For the asm version: 156e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_MSVC) && defined (_M_IX86) && (_M_IX86 >= 500) 157e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# define _STLP_HAS_ATOMIC_FREELIST 158e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 159e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# else 160e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// For the API based version: 161e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_NEW_PLATFORM_SDK) && (!defined (WINVER) || (WINVER >= 0x0501)) && \ 162e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott (!defined (_WIN32_WINNT) || (_WIN32_WINNT >= 0x0501)) 163e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# define _STLP_HAS_ATOMIC_FREELIST 164e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 165e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 166e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 167e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_HAS_ATOMIC_FREELIST) 168e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_USE_ASM_IMPLEMENTATION) 169e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL) 170e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# pragma warning (push) 171e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# pragma warning (disable : 4035) //function has no return value 172e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 173e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 174e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott/** 175e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Class that implements a non-blocking and thread-safe freelist. 176e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * It is used for the lock-free node allocation engine. 177e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 178e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * @author felixw@inin.com 179e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 180e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottclass _STLP_atomic_freelist { 181e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottpublic: 182e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott /** 183e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Type representing items of the freelist 184e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 185e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_USE_ASM_IMPLEMENTATION) 186e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott struct item { 187e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott item* _M_next; 188e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott }; 189e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# else 190e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott typedef SLIST_ENTRY item; 191e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 192e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 193e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_atomic_freelist() { 194e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott // Statically assert layout of member is as expected by assembly code 195e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_USE_ASM_IMPLEMENTATION) 196e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STATIC_ASSERT((sizeof(item) == sizeof(item*)) && (sizeof(_M) == 8)) 197e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M._M_data._M_top = 0; 198e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _M._M_data._M_sequence = 0; 199e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# else 200e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott InitializeSListHead(&_M_head); 201e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 202e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 203e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 204e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott /** 205e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Atomically pushes the specified item onto the freelist. 206e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 207e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * @param __item [in] Item to add to the front of the list 208e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 209e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott void push(item* __item) { 210e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_USE_ASM_IMPLEMENTATION) 211e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __asm 212e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 213e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov esi, this 214e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov ebx, __item 215e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov eax, [esi] // _M._M_data._M_top 216e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov edx, [esi+4] // _M._M_data._M_sequence 217e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott L1: mov [ebx], eax // __item._M_next = _M._M_data._M_top 218e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1 219e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott lock cmpxchg8b qword ptr [esi] 220e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top) 221e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 222e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# else 223e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott InterlockedPushEntrySList(&_M_head, __item); 224e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 225e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 226e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 227e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott /** 228e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Atomically removes the topmost item from the freelist and returns a 229e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * pointer to it. Returns NULL if the list is empty. 230e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 231e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * @return Item that was removed from front of list; NULL if list empty 232e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 233e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott item* pop() { 234e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_USE_ASM_IMPLEMENTATION) 235e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __asm 236e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 237e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov esi, this 238e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov eax, [esi] // _M._M_data._M_top 239e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov edx, [esi+4] // _M._M_data._M_sequence 240e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott L1: test eax, eax // _M_top == NULL? 241e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott je L2 // Yes, we're done 242e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov ebx, [eax] // new top = _M._M_data._M_top->_M_next 243e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1 244e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott lock cmpxchg8b qword ptr [esi] 245e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top) 246e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott L2: 247e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 248e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# else 249e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return InterlockedPopEntrySList(&_M_head); 250e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 251e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 252e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 253e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott /** 254e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * Atomically detaches all items from the list and returns pointer to the 255e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * topmost. The items are still chained and may be traversed safely as 256e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * they're now "owned" by the calling thread. 257e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * 258e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott * @return Pointer to topmost item in the list; NULL if list empty 259e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott */ 260e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott item* clear() { 261e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_USE_ASM_IMPLEMENTATION) 262e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __asm 263e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott { 264e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov esi, this 265e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov eax, [esi] // _M._M_data._M_top 266e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott mov edx, [esi+4] // _M._M_data._M_sequence 267e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott L1: test eax, eax // _M_top == NULL? 268e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott je L2 // Yes, we're done 269e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott xor ebx,ebx // We're attempting to set _M._M_data._M_top to NULL 270e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1 271e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott lock cmpxchg8b qword ptr [esi] 272e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top) 273e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott L2: 274e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 275e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# else 276e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return InterlockedFlushSList(&_M_head); 277e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 278e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 279e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 280e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottprivate: 281e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_USE_ASM_IMPLEMENTATION) 282e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott union { 283e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __int64 _M_align; 284e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott struct { 285e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott item* _M_top; // Topmost element in the freelist 286e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott unsigned int _M_sequence; // Sequence counter to prevent "ABA problem" 287e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } _M_data; 288e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } _M; 289e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# else 290e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott SLIST_HEADER _M_head; 291e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 292e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 293e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_atomic_freelist(const _STLP_atomic_freelist&); 294e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_atomic_freelist& operator = (const _STLP_atomic_freelist&); 295e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott}; 296e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 297e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_USE_ASM_IMPLEMENTATION) 298e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL) 299e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# pragma warning (pop) 300e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 301e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 302e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 303e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif /* _STLP_HAS_ATOMIC_FREELIST */ 304e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 305e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 306e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 307e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif /* _STLP_LOCK_FREE_SLIST_H */ 308