/* -------------------------------------------------------------------------
 *
 * dllist.h
 *		simple doubly linked list primitives
 *		the elements of the list are void* so the lists can contain anything
 *		Dlelem can only be in one list at a time
 *
 *
 *	 Here's a small example of how to use Dllists:
 *
 *	 Dllist *lst;
 *	 Dlelem *elt;
 *	 void	*in_stuff;	  -- stuff to stick in the list
 *	 void	*out_stuff
 *
 *	 lst = DLNewList();				   -- make a new dllist
 *	 DLAddHead(lst, DLNewElem(in_stuff)); -- add a new element to the list
 *											 with in_stuff as the value
 *	  ...
 *	 elt = DLGetHead(lst);			   -- retrieve the head element
 *	 out_stuff = (void*)DLE_VAL(elt);  -- get the stuff out
 *	 DLRemove(elt);					   -- removes the element from its list
 *	 DLFreeElem(elt);				   -- free the element since we don't
 *										  use it anymore
 *
 *
 * It is also possible to use Dllist objects that are embedded in larger
 * structures instead of being separately malloc'd.  To do this, use
 * DLInitElem() to initialize a Dllist field within a larger object.
 * Don't forget to DLRemove() each field from its list (if any) before
 * freeing the larger object!
 *
 *
 * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/lib/dllist.h
 *
 * -------------------------------------------------------------------------
 */

#ifndef DLLIST_H
#define DLLIST_H

struct Dllist;
struct Dlelem;

typedef struct Dlelem {
    struct Dlelem* dle_next; /* next element */
    struct Dlelem* dle_prev; /* previous element */
    void* dle_val;           /* value of the element */
    struct Dllist* dle_list; /* what list this element is in */
} Dlelem;

typedef struct Dllist {
	Dlelem	   *dll_head;
	Dlelem	   *dll_tail;
    uint64      dll_len;
} Dllist;

class DllistWithLock : public BaseObject {
public:
    DllistWithLock();
    ~DllistWithLock();
    void Remove(Dlelem* e)
    {
        (void)RemoveConfirm(e);
    }
    bool RemoveConfirm(Dlelem* e);
    void AddHead(Dlelem* e);
    void AddTail(Dlelem* e);
    Dlelem* RemoveHead();
    Dlelem* RemoveHeadNoLock();
    Dlelem* RemoveTail();
    bool IsEmpty();
    Dlelem* GetHead();
    void GetLock();
    void ReleaseLock();

    inline uint64 GetLength()
    {
        return m_list.dll_len;
    }

private:
    slock_t m_lock;
    Dllist m_list;
};

extern Dllist* DLNewList(void);       /* allocate and initialize a list header */
extern void DLInitList(Dllist* list); /* init a header alloced by caller */
extern void DLFreeList(Dllist* list); /* free up a list and all the nodes in
                                       * it */
extern void DLListConcat(Dllist* a, Dllist* b);
extern Dlelem* DLNewElem(void* val);
extern void DLInitElem(Dlelem* e, void* val);
extern void DLFreeElem(Dlelem* e);
extern void DLRemove(Dlelem* e); /* removes node from list */
extern void DLAddHead(Dllist* list, Dlelem* node);
extern void DLAddTail(Dllist* list, Dlelem* node);
extern Dlelem* DLRemHead(Dllist* list); /* remove and return the head */
extern Dlelem* DLRemTail(Dllist* list);
extern void DLMoveToFront(Dlelem* e); /* move node to front of its list */
extern uint64 DLListLength(Dllist* list);

/* These are macros for speed */
#define DLGetHead(list) ((list)->dll_head)
#define DLGetTail(list) ((list)->dll_tail)
#define DLIsNIL(list) ((list)->dll_head == NULL)
#define DLGetSucc(elem) ((elem)->dle_next)
#define DLGetPred(elem) ((elem)->dle_prev)
#define DLGetListHdr(elem) ((elem)->dle_list)

#define DLE_VAL(elem) ((elem)->dle_val)

#endif /* DLLIST_H */