xintrusive_list.h

[詳解]

/*
 * License: MIT license
 * Copyright (c) <2015> <MaskedW [maskedw00@gmail.com]>
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of self 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 self 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.
 */


#ifndef picox_container_xintrusive_list_h_
#define picox_container_xintrusive_list_h_


#include <picox/core/xcore.h>


#ifdef __cplusplus
extern "C" {
#endif // __cplusplus


typedef struct XIntrusiveNode
{
    struct XIntrusiveNode* next;
    struct XIntrusiveNode* prev;
} XIntrusiveNode;


typedef struct XIntrusiveList
{
    XIntrusiveNode   head;
} XIntrusiveList;


#define xnode_entry(ptr, type, member)  X_CONTAINER_OF(ptr, type, member)


static inline void
xnode_unlink(XIntrusiveNode* node)
{
   node->next->prev = node->prev;
   node->prev->next = node->next;
}


static inline void
xnode_insert_prev(XIntrusiveNode* p1, XIntrusiveNode* p2)
{
    p2->prev        = p1->prev;
    p2->next        = p1;
    p1->prev->next  = p2;
    p1->prev        = p2;
}


static inline void
xnode_insert_next(XIntrusiveNode* p1, XIntrusiveNode* p2)
{
    p2->prev        = p1;
    p2->next        = p1->next;
    p1->next->prev  = p2;
    p1->next        = p2;
}


static inline void
xnode_replace(XIntrusiveNode* p1, XIntrusiveNode* p2)
{
    p2->next       = p1->next;
    p2->next->prev = p2;
    p2->prev       = p1->prev;
    p2->prev->next = p2;
}


static inline void
xnode_splice(XIntrusiveNode* prev, XIntrusiveNode* next, XIntrusiveList* list)
{
    XIntrusiveNode* first = list->head.next;
    XIntrusiveNode* last  = list->head.prev;

    first->prev = prev;
    prev->next  = first;
    last->next  = next;
    next->prev  = last;
}


static inline void
xilist_init(XIntrusiveList* self)
{
    X_ASSERT(self);
    self->head.next = self->head.prev = &self->head;
}


static inline XIntrusiveNode*
xilist_head(XIntrusiveList* self)
{
    X_ASSERT(self);
    return &self->head;
}


static inline void
xilist_clear(XIntrusiveList* self)
{
    X_ASSERT(self);
    xilist_init(self);
}


static inline bool
xilist_empty(const XIntrusiveList* self)
{
    X_ASSERT(self);
    return self->head.next == &self->head;
}


static inline XIntrusiveNode*
xilist_end(const XIntrusiveList* self)
{
    X_ASSERT(self);
    return (XIntrusiveNode*)(&self->head);
}


static inline XIntrusiveNode*
xilist_front(const XIntrusiveList* self)
{
    X_ASSERT(self);
    return self->head.next;
}


static inline XIntrusiveNode*
xilist_pop_front(const XIntrusiveList* self)
{
    X_ASSERT(self);
    XIntrusiveNode* front = self->head.next;
    xnode_unlink(front);
    return front;
}


static inline XIntrusiveNode*
xilist_back(const XIntrusiveList* self)
{
    X_ASSERT(self);
    return self->head.prev;
}


static inline XIntrusiveNode*
xilist_pop_back(const XIntrusiveList* self)
{
    X_ASSERT(self);
    XIntrusiveNode* back = self->head.prev;
    xnode_unlink(back);
    return back;
}


#define xilist_foreach(list, ite)    \
    for (ite  = xilist_front(list);  \
         ite != xilist_end(list);    \
         ite  = ite->next)


#define xilist_rforeach(list, ite)   \
    for (ite  = xilist_back(list);   \
         ite != xilist_end(list);    \
         ite  = ite->prev)


static inline size_t
xilist_size(const XIntrusiveList* self)
{
    X_ASSERT(self);
    size_t n = 0;
    XIntrusiveNode* ite;
    xilist_foreach(self, ite)
        n++;

    return n;
}


static inline bool
xilist_is_singular(const XIntrusiveList* self)
{
    X_ASSERT(self);
    return (! xilist_empty(self)) &&  (xilist_front(self) == xilist_back(self));
}


static inline void
xilist_push_front(XIntrusiveList* self, XIntrusiveNode* node)
{
    X_ASSERT(self);
    X_ASSERT(node);
    xnode_insert_next(&self->head, node);
}


static inline void
xilist_push_back(XIntrusiveList* self, XIntrusiveNode* node)
{
    X_ASSERT(self);
    X_ASSERT(node);
    xnode_insert_prev(&self->head, node);
}


static inline void
xilist_move_front(XIntrusiveList* self, XIntrusiveNode* node)
{
    X_ASSERT(self);
    X_ASSERT(node);
    xnode_unlink(node);
    xilist_push_front(self, node);
}


static inline void
xilist_move_back(XIntrusiveList* self, XIntrusiveNode* node)
{
    X_ASSERT(self);
    X_ASSERT(node);
    xnode_unlink(node);
    xilist_push_back(self, node);
}


static inline void
xilist_splice_front(XIntrusiveList* self, XIntrusiveList* other)
{
    X_ASSERT(self);
    X_ASSERT(other);
    if (! xilist_empty(other))
    {
        xnode_splice(&self->head, self->head.next, other);
        xilist_clear(other);
    }
}


static inline void
xilist_splice_back(XIntrusiveList* self, XIntrusiveList* other)
{
    X_ASSERT(self);
    X_ASSERT(other);
    if (! xilist_empty(other))
    {
        xnode_splice(self->head.prev, &self->head, other);
        xilist_clear(other);
    }
}


static inline void
xilist_swap(XIntrusiveList* self, XIntrusiveList* other)
{
    X_ASSERT(self);
    X_ASSERT(other);

    if (self == other)
        return;

    const bool empty_self = xilist_empty(self);
    const bool empty_other = xilist_empty(other);

    X_SWAP(self->head, other->head, XIntrusiveNode);

    if (empty_other)
        xilist_init(self);
    else
        self->head.next->prev = self->head.prev->next = &(self->head);

    if (empty_self)
        xilist_init(other);
    else
        other->head.next->prev = other->head.prev->next = &(other->head);
}


static inline void
xilist_transfer_front(XIntrusiveList* self, XIntrusiveList* other, XIntrusiveNode* pos)
{
    X_ASSERT(self);
    X_ASSERT(pos);
    X_ASSERT(other);
    X_ASSERT(!xilist_empty(other));

    XIntrusiveNode* const new_first = pos->next;
    pos->next                       = self->head.next;
    self->head.next                 = other->head.next;
    self->head.next->prev           = &self->head;
    self->head.prev                 = pos;
    other->head.next                = new_first;
    new_first->prev                 = &other->head;
}


static inline void
xilist_transfer_back(XIntrusiveList* self, XIntrusiveList* other, XIntrusiveNode* pos)
{
    X_ASSERT(self);
    X_ASSERT(pos);
    X_ASSERT(other);
    X_ASSERT(!xilist_empty(other));

    XIntrusiveNode* const new_first = pos->next;
    pos->next                       = &self->head;
    pos->prev                       = self->head.prev;
    self->head.prev->next           = other->head.next;
    self->head.prev                 = pos;
    other->head.next                = new_first;
    new_first->prev                 = &other->head;
}


#ifdef __cplusplus
}
#endif // __cplusplus


#endif // picox_container_xintrusive_list_h_