/*

Routines for (Fairly) General Linked Lists

 */

#define LLSetData(cell,type,value) { type *_x; _x = (type *) malloc(sizeof(type)); *_x = value; if ((*cell).data != NULL) free((*cell).data); (*cell).data = (void *) _x; }
#define LLGetData(cell,type) (*((type *) (*cell).data))
#define LLInsertDataAtEnd(list,type,value) { LLCell _C = LLNewCell(); LLSetData(_C,type,value); LLInsertAtEnd(list,_C); }
#define LLfirst(list) ((*list).first)
#define LLlast(list) ((*list).last)
#define LLlength(list) ((*list).length)
#define LLnext(cell) ((*cell).next)
#define LLprev(cell) ((*cell).prev)
#define LLdata(cell) ((*cell).data)

typedef struct LLcellstruct *LLCell;
typedef struct LListstruct *LList;

struct LLcellstruct {
  LLCell next;
  LLCell prev;
  void *data;
};

struct LListstruct {
  LLCell first;
  LLCell last;
  long length;
};

LLCell LLNewCell() {
  LLCell C = (LLCell) malloc(sizeof(struct LLcellstruct));
  (*C).next = NULL;
  (*C).prev = NULL;
  (*C).data = NULL;
  return C;
}

LList LLNewList() {
  LList L = (LList) malloc(sizeof(struct LListstruct));
  (*L).first = NULL;
  (*L).last = NULL;
  (*L).length = 0;
  return L;
}

void LLInsertAtEnd(LList L, LLCell C) {
  if ((*L).last == NULL) {
    (*L).first = C;
    (*L).last = C;
    (*L).length = 1;
  } else {
    LLCell Last = (*L).last;
    (*Last).next = C;
    (*C).prev = Last;
    (*L).last = C;
    (*L).length++;
  }
}

void LLInsertAfter(LList L, LLCell Present, LLCell C) {
  LLCell AfterPresent = (*Present).next;
  (*Present).next = C;
  (*C).prev = Present;
  (*C).next = AfterPresent;
  if (AfterPresent != NULL) {
    (*AfterPresent).prev = C;
  } else {
    (*L).last = C;
  }
  (*L).length++;
}

void LLKillCell(LList L, LLCell C) {
  LLCell Before = (*C).prev, After = (*C).next;
  if ((Before == NULL) && (After == NULL)) {
    (*L).first = NULL;
    (*L).last = NULL;
  } else if ((Before == NULL) && (After != NULL)) {
    (*L).first = After;
    (*After).prev = NULL;
  } else if ((Before != NULL) && (After == NULL)) {
    (*Before).next = NULL;
    (*L).last = Before;
  } else {
    (*Before).next = After;
    (*After).prev = Before;
  }
  (*L).length--;
  free((*C).data);
  free(C);
}

void LLKillList(LList L) {
  while ((*L).first != NULL) LLKillCell(L,(*L).first);
  if ((*L).length != 0) error("bug behind LLKillList");
  free(L);
}