// Queue implemented by circularly-linked list.
//
// Adapted from libuv.
//
// Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl>
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
// ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
// ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
// OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

#ifndef QUEUE_H_
#define QUEUE_H_

#include <stddef.h>

typedef void *QUEUE[2];   // QUEUE[0] -> next, QUEUE[1] -> prev

#define QUEUE_DATA(ptr, type, field)                                           \
  ((type *) ((char *) (ptr) - offsetof(type, field)))

#define QUEUE_FOREACH(q, h)                                                  \
  for ((q) = (*(h))[0]; (q) != (h); (q) = (*(q))[0])

static inline int QUEUE_EMPTY(const QUEUE * const q)
{
  return q == (*q)[0];    // q == q->next
}

static inline QUEUE* QUEUE_HEAD(const QUEUE * const q)
{
  return (*q)[0];   // q->next
}

static inline QUEUE* QUEUE_TAIL(const QUEUE * const q)
{
  return (*q)[1];   // q->prev
}

static inline void QUEUE_INIT(QUEUE * const q)
{
  // QUEUE_NEXT(q) = (q)
  (*q)[0] = (q);    // q->next = q
  // QUEUE_PREV(q) = (q)
  (*q)[1] = (q);    // q->prev = q
}


// +----+---+   +------+-+------+
// |tail|0:h|<->|1:tail|h|0:head|
// +----+---+   +------+-+------+
// +----+-----+   +--------+-+--------+   +---+------+
// |n_tail|0:n|<->|1:n_tail|n|0:n_head|<->|1:n|n_head|
// +----+-----+   +---------+-+-------+   +---+------+
//                          ||
//                         \||/
//                          \/
// +----+--------+   +------+------+   +------+---+   +--------+-+
// |tail|0:n_head|<->|1:tail|n_head|...|n_tail|0:h|<->|1:n_tail|h|
// +----+--------+   +------+------+   +------+---+   +--------+-+
//
static inline void QUEUE_ADD(QUEUE * const h, QUEUE * const n)
{
  // QUEUE_PREV_NEXT(h) = QUEUE_NEXT(n)
  (*(QUEUE *)(*h)[1])[0] = (*n)[0];   // h->prev->next(=tail->next) = n->next(=n_head)
  // QUEUE_NEXT_PREV(n) = QUEUE_PREV(h)
  (*(QUEUE *)(*n)[0])[1] = (*h)[1];   // n->next->prev(=n_head->prev) = h->prev(=tail)
  // QUEUE_PREV(h) = QUEUE_PREV(n)
  (*h)[1] = (*n)[1];                  // h->prev = n->prev(=n_tail)
  // QUEUE_PREV_NEXT(h) = (h)
  (*(QUEUE *)(*h)[1])[0] = (h);       // h->prev->next(=n_tail->next) = h
}


//     +----+---+   +------+-+------+   +---+---+   +-----+-+
// +-->|tail|0:h|<->|1:tail|h|0:head|...|q-1|0:q|<->|1:q-1|q|--+
// |   +----+---+   +------+-+------+   +---+---+   +-----+-+  |
// +-----------------------------------------------------------+
// +---+-+---+
// |1:n|n|0:n|
// +---+-+---+
//     ||
//    \||/
//     \/
// +----+---+   +------+-+---+   +---+-+
// |tail|0:n|<->|1:tail|n|0:q|<->|1:n|q|...
// +----+---+   +------+-+---+   +---+-+
// +---+---+   +-----+-+
// |q-1|0:h|<->|1:q-1|h|...
// +---+---+   +-----+-+
//
static inline void QUEUE_SPLIT(QUEUE * const h, QUEUE * const q, QUEUE * const n)
{
  // QUEUE_PREV(n) = QUEUE_PREV(h)
  (*n)[1] = (*h)[1];              // n->prev = h->prev(=tail)
  // QUEUE_PREV_NETX(n) = (n)
  (*(QUEUE *)(*n)[1])[0] = (n);   // n->prev->next(=tail->next) = n
  // QUEUE_NEXT(n) = (q)
  (*n)[0] = (q);                  // n->next = q
  // QUEUE_PREV(h) = QUEUE_PREV(q)
  (*h)[1] = (*q)[1];              // h->prev = q->prev(=(q - 1))
  // QUEUE_PREV_NEXT(h) = (h)
  (*(QUEUE *)(*h)[1])[0] = (h);   // h->prev->next(=(q - 1)->next) = h
  // QUEUE_PREV(q) = (n)
  (*q)[1] = (n);                  // q->prev = n
}


//     +----+---+   +------+-+------+   +---+----+
// +-->|tail|0:h|<->|1:tail|h|0:head|<->|1:h|head|--+
// |   +----+---+   +------+-+------+   +---+----+  |
// +------------------------------------------------+
//
// +---+-+---+
// |1:n|n|0:n|
// +---+-+---+
//     ||
//    \||/
//     \/
// +---+-+---+
// |1:h|h|0:h|
// +---+-+---+
//
//     +----+---+   +------+-+------+   +---+----+
// +-->|tail|0:n|<->|1:tail|n|0:head|<->|1:n|head|--+
// |   +----+---+   +------+-+------+   +---+----+  |
// +------------------------------------------------+
//
static inline void QUEUE_MOVE(QUEUE * const h, QUEUE * const n)
{
  if (QUEUE_EMPTY(h)) {
    QUEUE_INIT(n);
  } else {
    QUEUE* q = QUEUE_HEAD(h);
    QUEUE_SPLIT(h, q, n);
  }
}


// +------+--------+   +---+----+
// |1:tail|h|0:head|<->|1:h|head|
// +------+--------+   +---+----+
// +---+-+---+
// |1:q|q|0:q|
// +---+-+---+
//     ||
//    \||/
//     \/
// +------+-+---+   +---+-+------+   +---+----+
// |1:tail|h|0:q|<->|1:h|q|0:head|<->|1:q|head|
// +------+-+---+   +---+-+------+   +---+----+
//
static inline void QUEUE_INSERT_HEAD(QUEUE * const h, QUEUE * const q)
{
  // QUEUE_NEXT(q) = QUEUE_NEXT(h)
  (*q)[0] = (*h)[0];              // q->next = h->next(=head)
  // QUEUE_PREV(q) = (h)
  (*q)[1] = (h);                  // q->prev = h
  // QUEUE_NEXT_PREV(q) = (q)
  (*(QUEUE *)(*q)[0])[1] = (q);   // q->prev->next(=head->prev) = q
  // QUEUE_NEXT(h) = (q)
  (*h)[0] = (q);                  // h->next = q
}


// +----+---+   +------+--------+
// |tail|0:h|<->|1:tail|h|0:head|
// +----+---+   +------+--------+
// +---+-+---+
// |1:q|q|0:q|
// +---+-+---+
//     ||
//    \||/
//     \/
// +----+---+   +------+-+---+   +---+-+------+
// |tail|0:q|<->|1:tail|q|0:h|<->|1:q|h|0:head|
// +----+---+   +------+-+---+   +---+-+------+
//
static inline void QUEUE_INSERT_TAIL(QUEUE * const h, QUEUE * const q)
{
  // QUEUE_NEXT(q) = (h)
  (*q)[0] = (h);                  // q->next = h
  // QUEUE_PREV(q) = QUEUE_PREV(h)
  (*q)[1] = (*h)[1];              // q->prev = h->prev(=tail)
  // QUEUE_PREV_NEXT(q) = (q)
  (*(QUEUE *)(*q)[1])[0] = (q);   // q->prev->next(=tail->next) = q
  // QUEUE_PREV(h) = (q);
  (*h)[1] = (q);                  // h->prev = q
}


// +----+---+   +------+-+------+   +---+----+
// |prev|0:q|<->|1:prev|q|0:next|<->|1:q|next|
// +----+---+   +------+-+------+   +---+----+
//                     ||
//                    \||/
//                     \/
// +----+---+--+   +------+----+
// |prev|0:next|<->|1:prev|next|
// +----+------+   +------+----+
//
static inline void QUEUE_REMOVE(QUEUE * const q)
{
  // QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q)
   (*(QUEUE *)(*q)[1])[0] = (*q)[0];    // q->prev->next = q->next
  // QUEUE_NEXT_PREV(q) = QUEUE_PREV(q)
   (*(QUEUE *)(*q)[0])[1] = (*q)[1];    // q->next->prev = q->prev
}

#endif /* QUEUE_H_ */