src/lock_free_slist.h - platform/external/stlport - Git at Google

 /*
  * Copyright (c) 1997-1999
  * Silicon Graphics Computer Systems, Inc.
  *
  * Copyright (c) 1999
  * Boris Fomitchev
  *
  * This material is provided "as is", with absolutely no warranty expressed
  * or implied. Any use is at your own risk.
  *
  * Permission to use or copy this software for any purpose is hereby granted
  * without fee, provided the above notices are retained on all copies.
  * Permission to modify the code and to distribute modified code is granted,
  * provided the above notices are retained, and a notice that the code was
  * modified is included with the above copyright notice.
  *
  */

 #ifndef _STLP_LOCK_FREE_SLIST_H
 #define _STLP_LOCK_FREE_SLIST_H

 #if defined(_STLP_PTHREADS)
 #  include <pthread.h>

 #  if defined (__GNUC__) && defined (__i386__)

 #    define _STLP_HAS_ATOMIC_FREELIST
 /**
  * Class that implements a non-blocking and thread-safe freelist.
  * It is used for the lock-free node allocation engine.
  *
  * @author felixw@inin.com
  */
 class _STLP_atomic_freelist {
 public:
   /**
    * Type representing items of the freelist
    */
   struct item {
     item* _M_next;
   };

   _STLP_atomic_freelist() {
     // Statically assert layout of member is as expected by assembly code
     _STLP_STATIC_ASSERT(sizeof(_M) == 8)
     _M._M_data._M_top       = 0;
     _M._M_data._M_sequence  = 0;
   }

   /**
    * Atomically pushes the specified item onto the freelist.
    *
    * @param __item [in] Item to add to the front of the list
    */
   void push(item* __item) {
     // NOTE: GCC uses ebx as the PIC register for globals in shared libraries.
     //       The GCC version I'm using (3.4.1) won't temporarily spill it if it's
     //       used as input, output, or clobber.  Instead, it complains with a
     //       "can't find a register in class `BREG' while reloading `asm'" error.
     //       This is probably a compiler bug, but as the cmpxchg8b instruction
     //       requires ebx, I work around this here by using ecx for the '__item'
     //       input and spilling ebx into edi.  This also precludes us from using
     //       a "m" operand for the cmpxchg8b argument (GCC might think it can make
     //       it relative to ebx).  Instead, we're using esi for the address of _M_data.
     //
     int __tmp1;     // These dummy variables are used to tell GCC that the eax, ecx,
     int __tmp2;     // and edx registers will not have the same value as their input.
     int __tmp3;     // The optimizer will remove them as their values are not used.
     __asm__ __volatile__
       ("       movl       %%ebx, %%edi\n\t"
        "       movl       %%ecx, %%ebx\n\t"
        "L1_%=: movl       %%eax, (%%ebx)\n\t"     // __item._M_next = _M._M_data._M_top
        "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
        "lock;  cmpxchg8b  (%%esi)\n\t"
        "       jne        L1_%=\n\t"              // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
        "       movl       %%edi, %%ebx"
       :"=a" (__tmp1), "=d" (__tmp2), "=c" (__tmp3)
       :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "c" (__item), "S" (&_M._M_data)
       :"edi", "memory", "cc");
   }

   /**
    * Atomically removes the topmost item from the freelist and returns a
    * pointer to it.  Returns NULL if the list is empty.
    *
    * @return Item that was removed from front of list; NULL if list empty
    */
   item* pop() {
     item*   __result;
     int     __tmp;
     __asm__ __volatile__
       ("       movl       %%ebx, %%edi\n\t"
        "L1_%=: testl      %%eax, %%eax\n\t"       // _M_top == NULL?
        "       je         L2_%=\n\t"              // If yes, we're done
        "       movl       (%%eax), %%ebx\n\t"     // new top = _M._M_data._M_top->_M_next
        "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
        "lock;  cmpxchg8b  (%%esi)\n\t"
        "       jne        L1_%=\n\t"              // We failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
        "L2_%=: movl       %%edi, %%ebx"
       :"=a" (__result), "=d" (__tmp)
       :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
       :"edi", "ecx", "memory", "cc");
     return __result;
   }

   /**
    * Atomically detaches all items from the list and returns a pointer to the
    * topmost item.  The items are still chained and may be traversed safely as
    * they're now "owned" by the calling thread.
    *
    * @return Pointer to topmost item in the list; NULL if list empty
    */
   item* clear() {
     item*   __result;
     int     __tmp;
     __asm__ __volatile__
       ("       movl       %%ebx, %%edi\n\t"
        "L1_%=: testl      %%eax, %%eax\n\t"       // _M_top == NULL?
        "       je         L2_%=\n\t"              // If yes, we're done
        "       xorl       %%ebx, %%ebx\n\t"       // We're attempting to set _M_top to NULL
        "       leal       1(%%edx),%%ecx\n\t"     // new sequence = _M._M_data._M_sequence + 1
        "lock;  cmpxchg8b  (%%esi)\n\t"
        "       jne        L1_%=\n\t"              // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
        "L2_%=: movl       %%edi, %%ebx"
       :"=a" (__result), "=d" (__tmp)
       :"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
       :"edi", "ecx", "memory", "cc");
     return __result;
   }

 private:
     union {
       long long   _M_align;
       struct {
         item*           _M_top;         // Topmost element in the freelist
         unsigned int    _M_sequence;    // Sequence counter to prevent "ABA problem"
       } _M_data;
     } _M;

   _STLP_atomic_freelist(const _STLP_atomic_freelist&);
   _STLP_atomic_freelist& operator=(const _STLP_atomic_freelist&);
 };

 #  endif /* if defined(__GNUC__) && defined(__i386__) */

 #elif defined (_STLP_WIN32THREADS)

 #  if !defined (_WIN64)
 #    define _STLP_USE_ASM_IMPLEMENTATION
 #  endif

 // Here are the compiler/platform requirements for the thread safe and
 // lock free singly linked list implementation:
 #  if defined (_STLP_USE_ASM_IMPLEMENTATION)
 // For the asm version:
 #    if defined (_STLP_MSVC) && defined (_M_IX86) && (_M_IX86 >= 500)
 #      define _STLP_HAS_ATOMIC_FREELIST
 #    endif
 #  else
 // For the API based version:
 #    if defined (_STLP_NEW_PLATFORM_SDK) && (!defined (WINVER) || (WINVER >= 0x0501)) && \
                                             (!defined (_WIN32_WINNT) || (_WIN32_WINNT >= 0x0501))
 #      define _STLP_HAS_ATOMIC_FREELIST
 #    endif
 #  endif

 #  if defined (_STLP_HAS_ATOMIC_FREELIST)
 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
 #      if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL)
 #        pragma warning (push)
 #        pragma warning (disable : 4035) //function has no return value
 #      endif
 #    endif
 /**
  * Class that implements a non-blocking and thread-safe freelist.
  * It is used for the lock-free node allocation engine.
  *
  * @author felixw@inin.com
  */
 class _STLP_atomic_freelist {
 public:
   /**
    * Type representing items of the freelist
    */
 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
   struct item {
       item*   _M_next;
   };
 #    else
   typedef SLIST_ENTRY item;
 #    endif

   _STLP_atomic_freelist() {
     // Statically assert layout of member is as expected by assembly code
 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
     _STLP_STATIC_ASSERT((sizeof(item) == sizeof(item*)) && (sizeof(_M) == 8))
     _M._M_data._M_top       = 0;
     _M._M_data._M_sequence  = 0;
 #    else
     InitializeSListHead(&_M_head);
 #    endif
   }

   /**
    * Atomically pushes the specified item onto the freelist.
    *
    * @param __item [in] Item to add to the front of the list
    */
   void push(item* __item) {
 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
     __asm
     {
         mov             esi, this
         mov             ebx, __item
         mov             eax, [esi]              // _M._M_data._M_top
         mov             edx, [esi+4]            // _M._M_data._M_sequence
     L1: mov             [ebx], eax              // __item._M_next = _M._M_data._M_top
         lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
         lock cmpxchg8b  qword ptr [esi]
         jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
     }
 #    else
     InterlockedPushEntrySList(&_M_head, __item);
 #    endif
   }

   /**
    * Atomically removes the topmost item from the freelist and returns a
    * pointer to it.  Returns NULL if the list is empty.
    *
    * @return Item that was removed from front of list; NULL if list empty
    */
   item* pop() {
 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
     __asm
     {
         mov             esi, this
         mov             eax, [esi]              // _M._M_data._M_top
         mov             edx, [esi+4]            // _M._M_data._M_sequence
     L1: test            eax, eax                // _M_top == NULL?
         je              L2                      // Yes, we're done
         mov             ebx, [eax]              // new top = _M._M_data._M_top->_M_next
         lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
         lock cmpxchg8b  qword ptr [esi]
         jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
     L2:
     }
 #    else
     return InterlockedPopEntrySList(&_M_head);
 #    endif
   }

   /**
    * Atomically detaches all items from the list and returns pointer to the
    * topmost.  The items are still chained and may be traversed safely as
    * they're now "owned" by the calling thread.
    *
    * @return Pointer to topmost item in the list; NULL if list empty
    */
   item* clear() {
 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
     __asm
     {
         mov             esi, this
         mov             eax, [esi]              // _M._M_data._M_top
         mov             edx, [esi+4]            // _M._M_data._M_sequence
     L1: test            eax, eax                // _M_top == NULL?
         je              L2                      // Yes, we're done
         xor             ebx,ebx                 // We're attempting to set _M._M_data._M_top to NULL
         lea             ecx, [edx+1]            // new sequence = _M._M_data._M_sequence + 1
         lock cmpxchg8b  qword ptr [esi]
         jne             L1                      // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
     L2:
     }
 #    else
     return InterlockedFlushSList(&_M_head);
 #    endif
   }

 private:
 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
   union {
     __int64     _M_align;
     struct {
       item*           _M_top;         // Topmost element in the freelist
       unsigned int    _M_sequence;    // Sequence counter to prevent "ABA problem"
     } _M_data;
   } _M;
 #    else
   SLIST_HEADER _M_head;
 #    endif

   _STLP_atomic_freelist(const _STLP_atomic_freelist&);
   _STLP_atomic_freelist& operator = (const _STLP_atomic_freelist&);
 };

 #    if defined (_STLP_USE_ASM_IMPLEMENTATION)
 #      if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) || defined (__ICL)
 #        pragma warning (pop)
 #      endif
 #    endif

 #  endif /* _STLP_HAS_ATOMIC_FREELIST */

 #endif

 #endif /* _STLP_LOCK_FREE_SLIST_H */
	/*
	* Copyright (c) 1997-1999
	* Silicon Graphics Computer Systems, Inc.
	*
	* Copyright (c) 1999
	* Boris Fomitchev
	*
	* This material is provided "as is", with absolutely no warranty expressed
	* or implied. Any use is at your own risk.
	*
	* Permission to use or copy this software for any purpose is hereby granted
	* without fee, provided the above notices are retained on all copies.
	* Permission to modify the code and to distribute modified code is granted,
	* provided the above notices are retained, and a notice that the code was
	* modified is included with the above copyright notice.
	*
	*/

	#ifndef _STLP_LOCK_FREE_SLIST_H
	#define _STLP_LOCK_FREE_SLIST_H

	#if defined(_STLP_PTHREADS)
	# include <pthread.h>

	# if defined (__GNUC__) && defined (__i386__)

	# define _STLP_HAS_ATOMIC_FREELIST
	/**
	* Class that implements a non-blocking and thread-safe freelist.
	* It is used for the lock-free node allocation engine.
	*
	* @author felixw@inin.com
	*/
	class _STLP_atomic_freelist {
	public:
	/**
	* Type representing items of the freelist
	*/
	struct item {
	item* _M_next;
	};

	_STLP_atomic_freelist() {
	// Statically assert layout of member is as expected by assembly code
	_STLP_STATIC_ASSERT(sizeof(_M) == 8)
	_M._M_data._M_top = 0;
	_M._M_data._M_sequence = 0;
	}

	/**
	* Atomically pushes the specified item onto the freelist.
	*
	* @param __item [in] Item to add to the front of the list
	*/
	void push(item* __item) {
	// NOTE: GCC uses ebx as the PIC register for globals in shared libraries.
	// The GCC version I'm using (3.4.1) won't temporarily spill it if it's
	// used as input, output, or clobber. Instead, it complains with a
	// "can't find a register in class `BREG' while reloading `asm'" error.
	// This is probably a compiler bug, but as the cmpxchg8b instruction
	// requires ebx, I work around this here by using ecx for the '__item'
	// input and spilling ebx into edi. This also precludes us from using
	// a "m" operand for the cmpxchg8b argument (GCC might think it can make
	// it relative to ebx). Instead, we're using esi for the address of _M_data.
	//
	int __tmp1; // These dummy variables are used to tell GCC that the eax, ecx,
	int __tmp2; // and edx registers will not have the same value as their input.
	int __tmp3; // The optimizer will remove them as their values are not used.
	__asm__ __volatile__
	(" movl %%ebx, %%edi\n\t"
	" movl %%ecx, %%ebx\n\t"
	"L1_%=: movl %%eax, (%%ebx)\n\t" // __item._M_next = _M._M_data._M_top
	" leal 1(%%edx),%%ecx\n\t" // new sequence = _M._M_data._M_sequence + 1
	"lock; cmpxchg8b (%%esi)\n\t"
	" jne L1_%=\n\t" // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
	" movl %%edi, %%ebx"
	:"=a" (__tmp1), "=d" (__tmp2), "=c" (__tmp3)
	:"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "c" (__item), "S" (&_M._M_data)
	:"edi", "memory", "cc");
	}

	/**
	* Atomically removes the topmost item from the freelist and returns a
	* pointer to it. Returns NULL if the list is empty.
	*
	* @return Item that was removed from front of list; NULL if list empty
	*/
	item* pop() {
	item* __result;
	int __tmp;
	__asm__ __volatile__
	(" movl %%ebx, %%edi\n\t"
	"L1_%=: testl %%eax, %%eax\n\t" // _M_top == NULL?
	" je L2_%=\n\t" // If yes, we're done
	" movl (%%eax), %%ebx\n\t" // new top = _M._M_data._M_top->_M_next
	" leal 1(%%edx),%%ecx\n\t" // new sequence = _M._M_data._M_sequence + 1
	"lock; cmpxchg8b (%%esi)\n\t"
	" jne L1_%=\n\t" // We failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
	"L2_%=: movl %%edi, %%ebx"
	:"=a" (__result), "=d" (__tmp)
	:"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
	:"edi", "ecx", "memory", "cc");
	return __result;
	}

	/**
	* Atomically detaches all items from the list and returns a pointer to the
	* topmost item. The items are still chained and may be traversed safely as
	* they're now "owned" by the calling thread.
	*
	* @return Pointer to topmost item in the list; NULL if list empty
	*/
	item* clear() {
	item* __result;
	int __tmp;
	__asm__ __volatile__
	(" movl %%ebx, %%edi\n\t"
	"L1_%=: testl %%eax, %%eax\n\t" // _M_top == NULL?
	" je L2_%=\n\t" // If yes, we're done
	" xorl %%ebx, %%ebx\n\t" // We're attempting to set _M_top to NULL
	" leal 1(%%edx),%%ecx\n\t" // new sequence = _M._M_data._M_sequence + 1
	"lock; cmpxchg8b (%%esi)\n\t"
	" jne L1_%=\n\t" // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
	"L2_%=: movl %%edi, %%ebx"
	:"=a" (__result), "=d" (__tmp)
	:"a" (_M._M_data._M_top), "d" (_M._M_data._M_sequence), "S" (&_M._M_data)
	:"edi", "ecx", "memory", "cc");
	return __result;
	}

	private:
	union {
	long long _M_align;
	struct {
	item* _M_top; // Topmost element in the freelist
	unsigned int _M_sequence; // Sequence counter to prevent "ABA problem"
	} _M_data;
	} _M;

	_STLP_atomic_freelist(const _STLP_atomic_freelist&);
	_STLP_atomic_freelist& operator=(const _STLP_atomic_freelist&);
	};

	# endif /* if defined(__GNUC__) && defined(__i386__) */

	#elif defined (_STLP_WIN32THREADS)

	# if !defined (_WIN64)
	# define _STLP_USE_ASM_IMPLEMENTATION
	# endif

	// Here are the compiler/platform requirements for the thread safe and
	// lock free singly linked list implementation:
	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
	// For the asm version:
	# if defined (_STLP_MSVC) && defined (_M_IX86) && (_M_IX86 >= 500)
	# define _STLP_HAS_ATOMIC_FREELIST
	# endif
	# else
	// For the API based version:
	# if defined (_STLP_NEW_PLATFORM_SDK) && (!defined (WINVER) \|\| (WINVER >= 0x0501)) && \
	(!defined (_WIN32_WINNT) \|\| (_WIN32_WINNT >= 0x0501))
	# define _STLP_HAS_ATOMIC_FREELIST
	# endif
	# endif

	# if defined (_STLP_HAS_ATOMIC_FREELIST)
	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
	# if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) \|\| defined (__ICL)
	# pragma warning (push)
	# pragma warning (disable : 4035) //function has no return value
	# endif
	# endif
	/**
	* Class that implements a non-blocking and thread-safe freelist.
	* It is used for the lock-free node allocation engine.
	*
	* @author felixw@inin.com
	*/
	class _STLP_atomic_freelist {
	public:
	/**
	* Type representing items of the freelist
	*/
	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
	struct item {
	item* _M_next;
	};
	# else
	typedef SLIST_ENTRY item;
	# endif

	_STLP_atomic_freelist() {
	// Statically assert layout of member is as expected by assembly code
	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
	_STLP_STATIC_ASSERT((sizeof(item) == sizeof(item*)) && (sizeof(_M) == 8))
	_M._M_data._M_top = 0;
	_M._M_data._M_sequence = 0;
	# else
	InitializeSListHead(&_M_head);
	# endif
	}

	/**
	* Atomically pushes the specified item onto the freelist.
	*
	* @param __item [in] Item to add to the front of the list
	*/
	void push(item* __item) {
	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
	__asm
	{
	mov esi, this
	mov ebx, __item
	mov eax, [esi] // _M._M_data._M_top
	mov edx, [esi+4] // _M._M_data._M_sequence
	L1: mov [ebx], eax // __item._M_next = _M._M_data._M_top
	lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1
	lock cmpxchg8b qword ptr [esi]
	jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
	}
	# else
	InterlockedPushEntrySList(&_M_head, __item);
	# endif
	}

	/**
	* Atomically removes the topmost item from the freelist and returns a
	* pointer to it. Returns NULL if the list is empty.
	*
	* @return Item that was removed from front of list; NULL if list empty
	*/
	item* pop() {
	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
	__asm
	{
	mov esi, this
	mov eax, [esi] // _M._M_data._M_top
	mov edx, [esi+4] // _M._M_data._M_sequence
	L1: test eax, eax // _M_top == NULL?
	je L2 // Yes, we're done
	mov ebx, [eax] // new top = _M._M_data._M_top->_M_next
	lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1
	lock cmpxchg8b qword ptr [esi]
	jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
	L2:
	}
	# else
	return InterlockedPopEntrySList(&_M_head);
	# endif
	}

	/**
	* Atomically detaches all items from the list and returns pointer to the
	* topmost. The items are still chained and may be traversed safely as
	* they're now "owned" by the calling thread.
	*
	* @return Pointer to topmost item in the list; NULL if list empty
	*/
	item* clear() {
	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
	__asm
	{
	mov esi, this
	mov eax, [esi] // _M._M_data._M_top
	mov edx, [esi+4] // _M._M_data._M_sequence
	L1: test eax, eax // _M_top == NULL?
	je L2 // Yes, we're done
	xor ebx,ebx // We're attempting to set _M._M_data._M_top to NULL
	lea ecx, [edx+1] // new sequence = _M._M_data._M_sequence + 1
	lock cmpxchg8b qword ptr [esi]
	jne L1 // Failed, retry! (edx:eax now contain most recent _M_sequence:_M_top)
	L2:
	}
	# else
	return InterlockedFlushSList(&_M_head);
	# endif
	}

	private:
	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
	union {
	__int64 _M_align;
	struct {
	item* _M_top; // Topmost element in the freelist
	unsigned int _M_sequence; // Sequence counter to prevent "ABA problem"
	} _M_data;
	} _M;
	# else
	SLIST_HEADER _M_head;
	# endif

	_STLP_atomic_freelist(const _STLP_atomic_freelist&);
	_STLP_atomic_freelist& operator = (const _STLP_atomic_freelist&);
	};

	# if defined (_STLP_USE_ASM_IMPLEMENTATION)
	# if defined (_STLP_MSVC) && (_STLP_MSVC < 1300) \|\| defined (__ICL)
	# pragma warning (pop)
	# endif
	# endif

	# endif /* _STLP_HAS_ATOMIC_FREELIST */

	#endif

	#endif /* _STLP_LOCK_FREE_SLIST_H */