linkedlist.h

이 파일의 문서화 페이지로 가기

// Copyright (c) 2014, 임경현 (dlarudgus20)
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this
//   list of conditions and the following disclaimer.
//
// * Redistributions in binary form must reproduce the above copyright notice,
//   this list of conditions and the following disclaimer in the documentation
//   and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS 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 COPYRIGHT HOLDER OR 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.

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

#include <stddef.h>
#include <stdint.h>

typedef struct tagLinkedListNode
{
    struct tagLinkedListNode * volatile pNext;
    struct tagLinkedListNode * volatile pPrev;
} LinkedListNode;

typedef struct tagLinkedList
{
    LinkedListNode dummy;

    uint32_t size;
} LinkedList;

static inline void ckLinkedListInit(LinkedList *pList)
{
    // circular linked list
    pList->dummy.pNext = &pList->dummy;
    pList->dummy.pPrev = &pList->dummy;
    pList->size = 0;
}

static inline LinkedListNode *ckLinkedListHead(LinkedList *pList) { return pList->dummy.pNext; }
static inline LinkedListNode *ckLinkedListTail(LinkedList *pList) { return pList->dummy.pPrev; }

void ckLinkedListPushBack_lockfree(LinkedList *pList, LinkedListNode *pNode);
LinkedListNode *ckLinkedListPopFront_lockfree(LinkedList *pList);

static inline void ckLinkedListPushBack(LinkedList *pList, LinkedListNode *pNode)
{
    pList->size++;

    LinkedListNode *dummy = &pList->dummy;
    LinkedListNode *tail = dummy->pPrev;

    pNode->pNext = dummy;
    pNode->pPrev = tail;
    dummy->pPrev = pNode;
    tail->pNext = pNode;
}

static inline LinkedListNode *ckLinkedListPopFront(LinkedList *pList)
{
    LinkedListNode *dummy = &pList->dummy;
    LinkedListNode *ptr = dummy->pNext;
    LinkedListNode *next = ptr->pNext;

    if (ptr == dummy)
        return NULL;

    dummy->pNext = next;
    next->pPrev = dummy;

    pList->size--;
    return ptr;
}

static inline void ckLinkedListErase(LinkedList *pList, LinkedListNode *pNode)
{
    LinkedListNode *prev = pNode->pPrev;
    LinkedListNode *next = pNode->pNext;

    prev->pNext = next;
    next->pPrev = prev;
    pList->size--;
}

#endif /* LINKEDLIST_H_ */