#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/* #define DEBUG*/
#if defined(DEBUG)
#include "qzmalloc.h"
#else
#define qzmallocdump()
#define qzmalloc(a, b) malloc(a)
#define qzfree(a, b) free(a)
#endif


#define ID_NODE 1001
#define ID_DATA 1002

/*=========================================================================*/
/* 双方向リスト*/
struct node {
  void *data;
  struct node *next;
  struct node *before;
};
/*=========================================================================*/

int add_node(struct node **root, void *data) {
  struct node *new_node;
  if (root == 0)
    return 0;
  if (*root == 0) {
    if ((new_node = qzmalloc(sizeof(struct node), ID_NODE)) != 0) {
      new_node->next = new_node->before = new_node;
      *root = new_node;
      new_node->data = data;
      return 1;
    } else {
      return 0;
    }
  } else {
    if ((new_node = qzmalloc(sizeof(struct node), ID_NODE)) != 0) {
      (*root)->before->next = new_node;
      new_node->before = (*root)->before;
      (*root)->before = new_node;
      new_node->next = *root;
      (*root) = new_node;
      new_node->data = data;
      return 1;
    } else
      return 0;
  }
}

void dump(struct node *root, void (*dump_data)(void *)) {
  if (root == 0) {
    printf("<null>\n");
    return;
  }
  if (root != 0) {
    struct node *p = root;
    do {
      if (p->data) (*dump_data)(p->data);      
      assert(p->next->before == p);
      assert(p->before->next == p);
      p = p->next;
    } while (p != root);
  }
  putchar('\n');
}

void release(struct node **root, void(*release_data)(void *)) {
  if (*root == 0)
    return;
  struct node *p = *root, *q;
  do {
    if (p->data != 0) {
      release_data(p->data);
      p->data = 0;
    }
    p->next->before = 0;
    p->before = 0;
    q = p;
    p = p->next;
    q->next = 0;
    qzfree(q, ID_NODE);
  } while (p != *root);
  *root = 0;
}


struct node *search(struct node *root, int (*cmp_data)(void *, void *), void *data) {
  if (root == 0)
    return 0;
  struct node *p = root;
  do {
    if ((*cmp_data)(p->data, data) == 1)
      return p;
    p = p->next;
  } while (p != root);
  return 0;
}

/*=========================================================================*/
/* リンクリストの要素数にかかわらず、O(1) でノードを削除する */
void delete(struct node **root, struct node *del_node, void (*release_data)(void *)) {
  if (root == 0)
    return;
  if (*root != del_node) {
    del_node->before->next = del_node->next;
    del_node->next->before = del_node->before;
    del_node->next = del_node->before = 0;
    release_data(del_node->data);
    del_node->data = 0;
    qzfree(del_node, ID_NODE);
    del_node = 0;
  } else {
    assert(del_node == *root);
    del_node = del_node->next;
    (*root)->before->next = (*root)->next;
    (*root)->next->before = (*root)->before;
    (*root)->next = (*root)->before = 0;
    release_data((*root)->data);
    (*root)->data = 0;
    qzfree(*root, ID_NODE);
    if (del_node == *root) {
      *root = 0;
    } else {
      *root = del_node;
    }
  }
}
/*=========================================================================*/
int add_node_data(struct node **root, int data) {
  int *data_pack;
  if ((data_pack = qzmalloc(sizeof(struct node), ID_DATA)) != 0) {
  } else {
    
    fprintf(stderr, "Cannnot allocate data-area.\n");
    return 0;
  }
  *data_pack = data;
  if (add_node(root, data_pack) == 0) {
    fprintf(stderr, "Cannnot allocate node.\n");
    qzfree(data_pack, ID_DATA);
    return 0;
  }
  return 1;
}

void dump_data(int *data_pack) { printf("<%d>", *data_pack); fflush(stdout); }
void release_data(int *data_pack) { qzfree(data_pack, ID_DATA); }
int cmp_data(int *a, int *b) { return (a == 0) ? 0 : (b == 0) ? 0 : (*a == *b) ? 1 : 0; }

int main() {
  struct node *root = 0;
  int data_set[] = {31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62, -1};
/*  int data_set[] = {62, -1}; */
  for (int i = 0; data_set[i] > 0; i++) {
    printf("add data: %d\n", data_set[i]);
    add_node_data(&root, data_set[i]);
  }
  dump(root, (void (*)(void *))dump_data);

  /*-----------------------------------------------------*/
  /* 削除するノードを探す。この部分は O(N) なのは当然である. */

  struct node *node;
  int target = 62;
  if ((node = search(root, (int (*)(void *, void *))cmp_data, &target)) != 0) {
    printf("found & deleting! : %d\n", *(int *)node->data);
  } else {
    printf("not found..\n");
  }

  /*-----------------------------------------------------*/
  /* リンクリストの要素数にかかわらず、O(1) でノードを削除する */
  delete(&root, node, (void (*)(void *))release_data);

  /*-----------------------------------------------------*/
  dump(root, (void (*)(void *))dump_data);
  
  release(&root, (void (*)(void *))release_data);
  qzmallocdump();
  return 0;
}
/* end */