/*
 * Copyright (c) 2005 Hewlett-Packard Development Company, L.P.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/*
 * The implementation of the routines described here is covered by the GPL.
 * This header file is covered by the above license.
 */

/* Almost lock-free LIFO linked lists (linked stacks).  */
#ifndef AO_STACK_H
#define AO_STACK_H

#include "atomic_ops.h"

#ifndef AO_HAVE_double_t
  /* Can happen if we are using CAS emulation, since we do not want to  */
  /* force that here, in case other atomic_ops clients do not want it.  */
# include "atomic_ops/sysdeps/standard_ao_double_t.h"
#endif

#ifdef __cplusplus
  extern "C" {
#endif

#ifdef AO_USE_ALMOST_LOCK_FREE
  /* Use the almost-non-blocking implementation regardless of the       */
  /* compare-and-swap availability.                                     */
#elif defined(AO_HAVE_compare_double_and_swap_double) \
      && !defined(AO_FAT_POINTER) && !defined(AO_STACK_USE_CPTR)
# define AO_STACK_IS_LOCK_FREE
#elif !defined(AO_HAVE_compare_and_swap)
  /* If we have no compare-and-swap operation at all, we assume that we */
  /* will actually be emulating it.                                     */
# define AO_STACK_IS_LOCK_FREE
#else
# define AO_USE_ALMOST_LOCK_FREE
  /* If we do have a real compare-and-swap operation, it is cheaper to  */
  /* use the version-based implementation.                              */
#endif

/*
 * These are not guaranteed to be completely lock-free.
 * List insertion may spin under extremely unlikely conditions.
 * It cannot deadlock due to recursive reentry unless AO_list_remove
 * is called while at least AO_BL_SIZE activations of
 * AO_list_remove are currently active in the same thread, i.e.
 * we must have at least AO_BL_SIZE recursive signal handler
 * invocations.
 *
 * All operations take an AO_list_aux argument.  It is safe to
 * share a single AO_list_aux structure among all lists, but that
 * may increase contention.  Any given list must always be accessed
 * with the same AO_list_aux structure.
 *
 * We make some machine-dependent assumptions:
 *   - we have a compare-and-swap operation;
 *   - at least AO_N_BITS low order bits in pointers are
 *     zero and normally unused.
 *
 * We do use a fully lock-free implementation if double-width
 * compare-and-swap operations are available.
 */

/* AO_stack_aux should be treated as opaque.  It is fully defined       */
/* here, so it can be allocated, and also to facilitate debugging.      */
/* Note: changing the value of AO_BL_SIZE leads to the ABI change.      */
#ifndef AO_BL_SIZE
# define AO_BL_SIZE 2
#endif

/* The number of low order pointer bits we can use for a small          */
/* version number.                                                      */
#if defined(AO_FAT_POINTER) && defined(__LP64__)
# define AO_N_BITS 4
#elif defined(__LP64__) || defined(_LP64) || defined(_WIN64) \
      || defined(AO_FAT_POINTER)
# define AO_N_BITS 3
#else
# define AO_N_BITS 2
#endif

#define AO_BIT_MASK ((1 << AO_N_BITS) - 1)

#if AO_BL_SIZE > (1 << AO_N_BITS)
# error AO_BL_SIZE too big
#endif

#ifndef AO_STACK_ATTR_ALLIGNED
  /* Enforce proper alignment of AO_stack_t.AO_pa to avoid the          */
  /* structure value to cross the CPU cache line boundary.              */
  /* A workaround for almost-lock-free push/pop test failures           */
  /* on aarch64, at least.                                              */
# if AO_BL_SIZE == 1
    /* AO_vp is double-pointer aligned, no extra align of AO_pa is needed.  */
#   define AO_STACK_ATTR_ALLIGNED /* empty */
# elif AO_GNUC_PREREQ(3, 1)
#   define AO_STACK_LOG_BL_SZP1 (AO_BL_SIZE > 7 ? 4 : AO_BL_SIZE > 3 ? 3 : 2)
#   define AO_STACK_ATTR_ALLIGNED \
        __attribute__((__aligned__(sizeof(void*) << AO_STACK_LOG_BL_SZP1)))
# elif defined(_MSC_VER) && _MSC_VER >= 1400 /* Visual Studio 2005+ */
    /* MS compiler accepts only a literal number in align, not expression.  */
    /* AO_STACK_ALLIGN_N is 1 << (AO_N_BITS + AO_STACK_LOG_BL_SZP1).        */
#   if AO_N_BITS > 2 && AO_BL_SIZE > 7
#     define AO_STACK_ALLIGN_N 128
#   elif (AO_N_BITS > 2 && AO_BL_SIZE > 3) || AO_BL_SIZE > 7
#     define AO_STACK_ALLIGN_N 64
#   elif AO_N_BITS > 2 || AO_BL_SIZE > 3
#     define AO_STACK_ALLIGN_N 32
#   else
#     define AO_STACK_ALLIGN_N 16
#   endif
#   define AO_STACK_ATTR_ALLIGNED __declspec(align(AO_STACK_ALLIGN_N))
# else
#   define AO_STACK_ATTR_ALLIGNED /* TODO: alignment is not enforced */
# endif
#endif /* !AO_STACK_ATTR_ALLIGNED */

#if defined(__e2k__) && defined(AO_FAT_POINTER) || defined(AO_STACK_USE_CPTR)
  /* A workaround because the platform does not allow conversion from   */
  /* a numeric type (128-bit one) to a pointer.                         */
  typedef char *AO_internal_ptr_t;
# ifndef AO_STACK_USE_CPTR
#   define AO_STACK_USE_CPTR
# endif
#else
  typedef AO_uintptr_t AO_internal_ptr_t;
#endif

typedef struct AO__stack_aux {
  AO_internal_ptr_t volatile AO_stack_bl[AO_BL_SIZE];
} AO_stack_aux;

struct AO__stack_ptr_aux {
  AO_internal_ptr_t volatile AO_ptr;
  AO_stack_aux AO_aux;
};

/* The AO stack type.  Should be treated as opaque.                     */
/* Note: AO_stack_t variables are not intended to be local ones,        */
/* otherwise it is the client responsibility to ensure they have        */
/* double-word alignment.                                               */
typedef union AO__stack {
  AO_STACK_ATTR_ALLIGNED struct AO__stack_ptr_aux AO_pa;
  volatile AO_double_t AO_vp;
} AO_stack_t;

/* The static initializer of the AO stack type. */
#define AO_STACK_INITIALIZER { /* .AO_pa= */ { 0, { {0} } } }

#ifdef AO_USE_ALMOST_LOCK_FREE
  /* The following two routines should not normally be used directly.   */
  /* We make them visible here for the rare cases in which it makes     */
  /* sense to share the AO_stack_aux between stacks.                    */

  AO_API void AO_stack_push_explicit_aux_release(
                                        volatile AO_uintptr_t * /* list */,
                                        AO_uintptr_t * /* new_element */,
                                        AO_stack_aux *);

  AO_API AO_uintptr_t *AO_stack_pop_explicit_aux_acquire(
                                        volatile AO_uintptr_t * /* list */,
                                        AO_stack_aux *);
#endif /* AO_USE_ALMOST_LOCK_FREE */

#ifndef AO_REAL_PTR_AS_MACRO
  /* The stack implementation knows only about the location of  */
  /* link fields in nodes, and nothing about the rest of the    */
  /* stack elements.  Link fields hold an AO_uintptr_t, which   */
  /* is not necessarily a real pointer.  This converts the      */
  /* AO_uintptr_t value to a real AO_uintptr_t* which is either */
  /* NULL, or points at the link field in the next node.        */
# define AO_REAL_NEXT_PTR(x) AO_stack_next_ptr_d(&(x))

  /* Convert an AO_stack_t to a pointer to the link field in    */
  /* the first element.                                         */
# define AO_REAL_HEAD_PTR(x) AO_stack_head_ptr(&(x))

#elif defined(AO_USE_ALMOST_LOCK_FREE)
# ifdef AO_STACK_USE_CPTR
#   define AO_REAL_NEXT_PTR(x) \
        ((AO_uintptr_t *)AO_real_next_ptr_i(*(const AO_internal_ptr_t *)&(x)))
    /* Implemented as an inline function because the argument is used twice. */
    AO_INLINE AO_internal_ptr_t
    AO_real_next_ptr_i(AO_internal_ptr_t next)
    {
      return next - ((unsigned)(AO_uintptr_t)next & AO_BIT_MASK);
    }
# else
#   define AO_REAL_NEXT_PTR(x) \
            (AO_uintptr_t *)((x) & ~(AO_uintptr_t)AO_BIT_MASK)
# endif
# define AO_REAL_HEAD_PTR(x) \
            AO_REAL_NEXT_PTR(*(volatile AO_uintptr_t *)&(&(x))->AO_pa.AO_ptr)
#else
# define AO_REAL_NEXT_PTR(x) ((AO_t *)*(&(x)))
# define AO_REAL_HEAD_PTR(x) (AO_t *)((&(x))->AO_vp.AO_val2 /* ptr */)
#endif /* AO_REAL_PTR_AS_MACRO && !AO_USE_ALMOST_LOCK_FREE */

AO_API void AO_stack_push_release(AO_stack_t *,
                                  AO_uintptr_t * /* new_element */);
#define AO_HAVE_stack_push_release

#define AO_stack_push(l, e) AO_stack_push_release(l, e)
#define AO_HAVE_stack_push

AO_API AO_uintptr_t *AO_stack_pop_acquire(AO_stack_t *);
#define AO_HAVE_stack_pop_acquire

#define AO_stack_pop(l) AO_stack_pop_acquire(l)
#define AO_HAVE_stack_pop

AO_API void AO_stack_init(AO_stack_t *);
AO_API int AO_stack_is_lock_free(void);

/* These primitives should not be used directly.        */
AO_API AO_uintptr_t *AO_stack_head_ptr(const AO_stack_t *);
AO_API AO_uintptr_t *AO_stack_next_ptr(AO_uintptr_t); /* deprecated */
AO_API AO_uintptr_t *AO_stack_next_ptr_d(const AO_uintptr_t * /* pnext */);

#ifdef __cplusplus
  } /* extern "C" */
#endif

#endif /* !AO_STACK_H */