/*

 * Portions Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.

 *

 * 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) 

#       if (_M_IX86 >= 500)

#         define _STLP_HAS_ATOMIC_FREELIST

#       endif

#    endif

#  else

// For the API based version:

#    if defined (_STLP_NEW_PLATFORM_SDK) && (!defined (WINVER) || (WINVER >= 0x0501)) && \

                                            (!defined (_WIN32_WINDOWS) || (_WIN32_WINDOWS >= 0x0501))

#      define _STLP_HAS_ATOMIC_FREELIST

#    endif

#  endif

#  if defined (_STLP_HAS_ATOMIC_FREELIST)

#    if !defined (_STLP_USE_ASM_IMPLEMENTATION)

#      include <windows.h>

#    else

#      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 */