/*-------------------------------------------------------------------
 * FILE: list.h
 *
 * $Header: /usr/local/dev/postgres/mastertree/src/lib/H/support/RCS/list.h,v 1.3 1991/03/20 18:53:28 cimarron Exp $
 *-------------------------------------------------------------------
 */

typedef int *AlignAddress;

typedef struct List {
  AlignAddress	elem;
  struct List	*next;
  struct List	*prev;
} List;

/* keep old list nodes around for reuse */
extern List *ListGarbage;

extern int ListAllocCount;

#define DELETED ((AlignAddress)(-1))
#define MARK_DELETED(curr)\
  Assert(curr->elem != DELETED);\
  MarkList(curr);\
  curr->elem = DELETED;

#define ListForEach(curr, first, last)\
    if (first) \
       for (curr = first->next; curr != last; curr = curr->next)

#define MidListForEach(curr, first, last)\
   if (first) \
      for (curr = first->next; ListElem(curr); curr = curr->next)

#define ListFirstElem(list) (list)->next->elem
#define ListLastElem(list) (list)->prev->elem

#define ListLast(list) (list)->prev
#define ListFirst(list) (list)->next

#ifdef DBG_GBG
#define LIST_ALLOC_INCR ListAllocCount++
#else
#define LIST_ALLOC_INCR 
#endif


#define ListElem(list) (list)->elem

#define ListAlloc(listTmpP)\
{\
  if (ListEmpty(ListGarbage)) {\
    *(listTmpP) = (List *)CacheAlloc((unsigned)sizeof(List));\
      LIST_ALLOC_INCR;\
  } else {\
   List *victim = ListGarbage->next;\
   *(listTmpP) = ListGarbage->next;\
    ListDeleteSimple(victim);\
  }\
}

#define ListEmpty(list) ((list == NULL) || (list->next == list))

#define ListFree(list)\
{\
   Assert(ListGarbage);\
   ListInsertElem(ListGarbage->prev,list);\
}

#define ListInsertElem(prevList,list)\
{\
  list->next = 	(prevList)->next;\
  list->prev = 	(prevList);\
  list->prev->next = list;\
  list->next->prev = list;\
}

#define ListInsert(prevList,newEl)\
{\
  List	*listTmp;\
  ListAlloc(&listTmp);\
\
  ListInsertElem(prevList,listTmp);\
  listTmp->elem = 	(AlignAddress) (newEl);\
}

#define ListPush(head, newEl)\
{\
  List	*listTmp;\
  ListAlloc(&listTmp);\
\
  Assert(listTmp != (head));\
  Assert(listTmp != (head)->next);\
  listTmp->elem = 	(AlignAddress) (newEl);\
  ListInsertElem(head,listTmp);\
  Assert(listTmp->next != listTmp);\
  Assert(listTmp->prev != listTmp);\
}

#define ListPushTail(head, newEl)\
{\
  List	*listTmp;\
  ListAlloc(&listTmp);\
\
  listTmp->elem = 	(AlignAddress) (newEl);\
  ListInsertElem(head->prev,listTmp);\
  Assert(listTmp->next != listTmp);\
  Assert(listTmp->prev != listTmp);\
}


#define ListFreeAll(head)\
{\
   List *_currl;\
\
   ListCheck(head);\
   ListGarbage->next->prev = head->prev;\
   head->prev->next = ListGarbage->next;\
   head->prev = ListGarbage;\
   ListGarbage->next = head;\
   ListCheck(ListGarbage);\
}

#define ListHead(headP)\
{\
  ListAlloc(headP);\
\
  (*(headP))->next = (*(headP))->prev = *(headP);\
  (*(headP))->elem = NULL;\
}

#define ListPop(head, newElP)\
{\
  List *listTmp;\
\
  if (ListEmpty(head)) {\
    elog(WARN,"ListPop: list argument is missing\n");\
    *newElP = NULL; /* for saber */\
  }\
  listTmp = (head)->next;\
  *(AlignAddress *)(newElP) = ListElem(listTmp);\
  ListDeleteSimple(listTmp);\
  ListFree(listTmp);\
  ListCheck(head);\
  Assert ((head)->next != listTmp);\
  Assert ((head)->prev != listTmp);\
 }

#define ListDeleteSimple(listTmp)\
{\
  Assert(((listTmp)->next != listTmp));\
  Assert(((listTmp)->prev != listTmp));\
  (listTmp)->next->prev = (listTmp)->prev;\
  (listTmp)->prev->next = (listTmp)->next;\
}

/*
 * assume this is called from within ListForEach and that listTmp is
 * not used directly after this call.  The last line of the macro sets
 * things up so that ListForEach can find the next element in the list
 * correctly.
 */
#define ListDelete(listTmp)\
{\
   List	*prevTmp = (listTmp)->prev;\
\
  ListDeleteSimple(listTmp);\
  ListFree(listTmp);\
  (listTmp) = prevTmp;\
}

#define ListMerge(first,second)\
{\
  ListMergeSimple(first,second);\
  ListFree(second);\
}

#define ListMergeSimple(first,second)\
{\
  List *oldtail = first->prev;\
\
  if (! ListEmpty(second)) {\
    oldtail->next = second->next;\
    oldtail->next->prev = oldtail;\
    first->prev = second->prev;\
    first->prev->next = first;\
  }\
}

char *ListGetString();
int *CacheAlloc();

#define ListCheck(list) \
{\
  List *_curr;\
\
  ListForEach(_curr, list, list) {\
    Assert(list && _curr->next->prev == _curr);\
    Assert(list && _curr->prev->next == _curr);\
  }\
}