#define PTHREAD_ONCE_INIT       {PTW32_FALSE, 0, 0, 0}

struct pthread_once_t_
{
  int             done;
  void           *lock;
  int             reserved1;
  int             reserved2;
};

struct ptw32_mcs_node_
{
  struct ptw32_mcs_node_ **lock;        /* ptr to tail of queue */
  struct ptw32_mcs_node_  *next;        /* ptr to successor in queue */
  LONG                     readyFlag;   /* set after lock is released by
                                           predecessor */
  LONG                     nextFlag;    /* set after 'next' ptr is set by
                                           successor */
};

typedef struct ptw32_mcs_node_   ptw32_mcs_node;
typedef struct ptw32_mcs_node_  *ptw32_mcs_lock;

/*
 * ptw32_mcs_flag_set -- notify another thread about an event.
 * 
 * Set event if an event handle has been stored in the flag, and
 * set flag to -1 otherwise. Note that -1 cannot be a valid hande value.
 */
static void 
ptw32_mcs_flag_set(LONG *flag)
{
  HANDLE e = (HANDLE)PTW32_INTERLOCKED_COMPARE_EXCHANGE(
						(PTW32_INTERLOCKED_LPLONG)flag,
						(PTW32_INTERLOCKED_LONG)-1,
						(PTW32_INTERLOCKED_LONG)0);
  if (0 != e)
    {
      /* another thread has already stored an event handle in the flag */
      SetEvent(e);
    }
}

/*
 * ptw32_mcs_flag_set -- wait for notification from another.
 * 
 * Store an event handle in the flag and wait on it if the flag has not been
 * set, and proceed without creating an event otherwise.
 */
static void 
ptw32_mcs_flag_wait(LONG *flag)
{
  if (0 == InterlockedExchangeAdd((LPLONG)flag, 0)) /* MBR fence */
    {
      /* the flag is not set. create event. */

      HANDLE e = CreateEvent(NULL, PTW32_FALSE, PTW32_FALSE, NULL);

      if (0 == PTW32_INTERLOCKED_COMPARE_EXCHANGE(
				       (PTW32_INTERLOCKED_LPLONG)flag,
				       (PTW32_INTERLOCKED_LONG)e,
				       (PTW32_INTERLOCKED_LONG)0))
	{
	  /* stored handle in the flag. wait on it now. */
	  WaitForSingleObject(e, INFINITE);
	}

      CloseHandle(e);
    }
}

/*
 * ptw32_mcs_lock_aquire -- acquire an MCS lock.
 * 
 * See: 
 * J. M. Mellor-Crummey and M. L. Scott.
 * Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
 * ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991.
 */
static void 
ptw32_mcs_lock_aquire(ptw32_mcs_lock  *lock, 
		      ptw32_mcs_node  *node)
{
  ptw32_mcs_node  *pred;
  
  node->lock = lock;
  node->nextFlag = 0;
  node->readyFlag = 0;
  node->next = 0; /* initially, no successor */
  
  /* queue for the lock */
  pred = (ptw32_mcs_node *)PTW32_INTERLOCKED_EXCHANGE((LPLONG)lock, 
						      (LONG)node);
  if (0 != pred)
    {
      /* the lock was not free. link behind predecessor. */
      pred->next = node;
      ptw32_mcs_flag_set(&pred->nextFlag);
      ptw32_mcs_flag_wait(&node->readyFlag);
    }
}

/*
 * ptw32_mcs_lock_aquire -- release an MCS lock.
 * 
 * See: 
 * J. M. Mellor-Crummey and M. L. Scott.
 * Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.
 * ACM Transactions on Computer Systems, 9(1):21-65, Feb. 1991.
 */
static void 
ptw32_mcs_lock_release(ptw32_mcs_node  *node)
{
  ptw32_mcs_lock *lock = node->lock;
  ptw32_mcs_node *next = (ptw32_mcs_node *)
    InterlockedExchangeAdd((LPLONG)&node->next, 0); /* MBR fence */

  if (0 == next)
    {
      /* no known successor */

      if (node == (ptw32_mcs_node *)PTW32_INTERLOCKED_COMPARE_EXCHANGE(
				       (PTW32_INTERLOCKED_LPLONG)lock,
				       (PTW32_INTERLOCKED_LONG)0,
				       (PTW32_INTERLOCKED_LONG)node))
	{
	  /* no successor, lock is free now */
	  return;
	}
  
      /* wait for successor */
      ptw32_mcs_flag_wait(&node->nextFlag);
      next = (ptw32_mcs_node *)InterlockedExchangeAdd((LPLONG)&node->next, 0);
                                                               /* MBR fence */
    }

  /* pass the lock */
  ptw32_mcs_flag_set(&next->readyFlag);
}

static void PTW32_CDECL
ptw32_once_on_init_cancel (void * arg)
{
  /* when the initting thread is cancelled we have to release the lock */
  ptw32_mcs_node *node = (ptw32_mcs_node*)arg;
  ptw32_mcs_lock_release(node);
}

int
pthread_once (pthread_once_t * once_control, void (*init_routine) (void))
{
  if (once_control == NULL || init_routine == NULL)
    {
      return EINVAL;
    }
  
  if (!InterlockedExchangeAdd((LPLONG)&once_control->done, 0)) /* MBR fence */
    {
      ptw32_mcs_node node;
      ptw32_mcs_lock_aquire(&(ptw32_mcs_lock)once_control->lock, &node);

      if (!once_control->done) 
	{

#ifdef _MSC_VER
#pragma inline_depth(0)
#endif

	  pthread_cleanup_push(ptw32_once_on_init_cancel, (void *)&node);
	  (*init_routine)();
	  pthread_cleanup_pop(0);

#ifdef _MSC_VER
#pragma inline_depth()
#endif

	  once_control->done = PTW32_TRUE;
	}

	ptw32_mcs_lock_release(&node);
    }

  return 0;

}				/* pthread_once */