/*
**  OSSP act - Abstract Container Types
**  Copyright (c) 1999-2003 Ralf S. Engelschall <rse@engelschall.com>
**  Copyright (c) 1999-2003 The OSSP Project <http://www.ossp.org/>
**
**  This file is part of OSSP act, an abstract container type library
**  which can be found at http://www.ossp.org/pkg/lib/act/.
**
**  Permission to use, copy, modify, and 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.
**
**  THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
**  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
**  MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
**  IN NO EVENT SHALL THE AUTHORS AND COPYRIGHT HOLDERS AND THEIR
**  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
**  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
**  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
**  USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
**  ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
**  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
**  OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
**  SUCH DAMAGE.
**
**  act_chain.h: basic chained data structures (implementation)
*/

#ifndef __ACT_CHAIN_H__
#define __ACT_CHAIN_H__

/*
 * Macro set for implementing single-linked lists.
 */

/* declaration:
 * typedef struct {
 *     ACT_LIST_ELEM(foo_t) next;
 * } foo_t;
 * ACT_LIST_HEAD(foo_t) head;
 */
#define ACT_LIST_HEAD(type)\
    struct { type *first; }
#define ACT_LIST_ELEM(type) \
    struct { type *next; }

/* initialization */
#define ACT_LIST_INITIALIZER \
    { NULL }
#define ACT_LIST_INIT(hp) \
    ACT_LIST_FIRST((hp)) = NULL
#define ACT_LIST_ELEM_INIT(ep, field) \
    ACT_LIST_NEXT((ep), field) = NULL

/* direct access */
#define ACT_LIST_FIRST(hp) \
    ((hp)->first)
#define ACT_LIST_NEXT(ep, field) \
    ((ep)->field.next)

/* empty check */
#define ACT_LIST_EMPTY(hp) \
    (ACT_LIST_FIRST((hp)) == NULL)

/* insert */
#define ACT_LIST_INSERT_HEAD(hp, ep, field) \
    do { ACT_LIST_NEXT((ep), field) = ACT_LIST_FIRST((hp)); \
         ACT_LIST_FIRST((hp)) = (ep); } while (0)
#define ACT_LIST_INSERT_AFTER(ap, ep, field) \
    do { ACT_LIST_NEXT((ep), field) = ACT_LIST_NEXT((ap), field); \
         ACT_LIST_NEXT((ap), field) = (ep); } while (0)

/* remove */
#define ACT_LIST_REMOVE_HEAD(hp, field) \
    ACT_LIST_FIRST((hp)) = \
        ACT_LIST_NEXT(ACT_LIST_FIRST((hp)), field)
#define ACT_LIST_REMOVE(hp, ep, field, type) \
    do { \
        if (ACT_LIST_FIRST((hp)) == (ep)) \
            ACT_LIST_REMOVE_HEAD((hp), field); \
        else { \
            type *cep = ACT_LIST_FIRST((hp)); \
            while (ACT_LIST_NEXT(cep, field) != (ep)) \
                cep = ACT_LIST_NEXT(cep, field); \
            ACT_LIST_NEXT(cep, field) = \
                ACT_LIST_NEXT(ACT_LIST_NEXT(cep, field), field); \
        } \
    } while (0)

/* iteration */
#define ACT_LIST_FOREACH(hp, ep, field) \
    for ((ep) = ACT_LIST_FIRST((hp)); \
         (ep) != NULL; \
         (ep) = ACT_LIST_NEXT((ep), field))

/*
 * Macro set for implementing double-linked rings.
 */

/* declaration */
#define ACT_RING_HEAD(type) \
    struct { type *next; type *prev; }
#define ACT_RING_ELEM(type) \
    struct { type *next; type *prev; }

/* initialization */
#define ACT_RING_INITIALIZER \
    { NULL, NULL }
#define ACT_RING_SENTINEL(hp, type, field) \
    (type *)((char *)(hp) - ((size_t)(&((type *)0)->field)))
#define ACT_RING_INIT(hp, type, field) \
    do { ACT_RING_FIRST((hp)) = ACT_RING_SENTINEL((hp), type, field); \
         ACT_RING_LAST((hp))  = ACT_RING_SENTINEL((hp), type, field); } while (0)
#define ACT_RING_ELEM_INIT(ep, field) \
    do { ACT_RING_NEXT((ep), field) = (ep); \
         ACT_RING_PREV((ep), field) = (ep); } while (0)

/* direct access */
#define ACT_RING_FIRST(hp) \
    ((hp)->next)
#define ACT_RING_LAST(hp) \
    ((hp)->prev)
#define ACT_RING_NEXT(ep, field) \
    ((ep)->field.next)
#define ACT_RING_PREV(ep, field) \
    ((ep)->field.prev)

/* empty check */
#define ACT_RING_EMPTY(hp, type, field) \
    (ACT_RING_FIRST((hp)) == ACT_RING_SENTINEL((hp), type, field))

/* insert */
#define ACT_RING_SPLICE_BEFORE(lep, ep1, epN, field) \
    do { \
        ACT_RING_NEXT((epN), field) = (lep); \
        ACT_RING_PREV((ep1), field) = ACT_RING_PREV((lep), field); \
        ACT_RING_NEXT(ACT_RING_PREV((lep), field), field) = (ep1); \
        ACT_RING_PREV((lep), field) = (epN); \
    } while (0)
#define ACT_RING_SPLICE_AFTER(lep, ep1, epN, field) \
    do { \
        ACT_RING_PREV((ep1), field) = (lep); \
        ACT_RING_NEXT((epN), field) = ACT_RING_NEXT((lep), field); \
        ACT_RING_PREV(ACT_RING_NEXT((lep), field), field) = (epN); \
        ACT_RING_NEXT((lep), field) = (ep1); \
    } while (0)
#define ACT_RING_SPLICE_HEAD(hp, ep1, epN, type, field) \
    ACT_RING_SPLICE_AFTER(ACT_RING_SENTINEL((hp), type, field), (ep1), (epN), field)
#define ACT_RING_SPLICE_TAIL(hp, ep1, epN, type, field) \
    ACT_RING_SPLICE_BEFORE(ACT_RING_SENTINEL((hp), type, field), (ep1), (epN), field)
#define ACT_RING_INSERT_BEFORE(lep, nep, field) \
    ACT_RING_SPLICE_BEFORE((lep), (nep), (nep), field)
#define ACT_RING_INSERT_AFTER(lep, nep, field) \
    ACT_RING_SPLICE_AFTER((lep), (nep), (nep), field)
#define ACT_RING_INSERT_HEAD(hp, nep, type, field) \
    ACT_RING_SPLICE_HEAD((hp), (nep), (nep), type, field)
#define ACT_RING_INSERT_TAIL(hp, nep, type, field) \
    ACT_RING_SPLICE_TAIL((hp), (nep), (nep), type, field)

/* remove */
#define ACT_RING_UNSPLICE(ep1, epN, field) \
    do { \
        ACT_RING_NEXT(ACT_RING_PREV((ep1), field), field) = \
            ACT_RING_NEXT((epN), field); \
        ACT_RING_PREV(ACT_RING_NEXT((epN), field), field) = \
            ACT_RING_PREV((ep1), field); \
    } while (0)
#define ACT_RING_REMOVE(ep, field) \
    ACT_RING_UNSPLICE((ep), (ep), field)

/* concatenation */
#define ACT_RING_CONCAT(h1, h2, type, field) \
    do { \
        if (!ACT_RING_EMPTY((h2), type, field)) { \
            ACT_RING_SPLICE_BEFORE(ACT_RING_SENTINEL((h1), type, field), \
                                   ACT_RING_FIRST((h2)), \
                                   ACT_RING_LAST((h2)), field); \
            ACT_RING_INIT((h2), type, field); \
        } \
    } while (0)

/* iteration */
#define ACT_RING_FOREACH(ep, hp, type, field) \
    for ((ep)  = ACT_RING_FIRST((hp)); \
         (ep) != ACT_RING_SENTINEL((hp), type, field); \
         (ep)  = ACT_RING_NEXT((ep), field))
#define ACT_RING_FOREACH_REVERSE(ep, hp, type, field) \
    for ((ep)  = ACT_RING_LAST((hp)); \
         (ep) != ACT_RING_SENTINEL((hp), type, field); \
         (ep)  = ACT_RING_PREV((ep), field))

#endif /* __ACT_CHAIN_H__*/