#include <stdio.h>
#include <stdlib.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;
};
/*=========================================================================*/

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

void dump(struct node *root, void (*dump_data)(void *)) {
  while (root != 0) {
    if (root->data) (*dump_data)(root->data);
    root = root->next;
  }
  putchar('\n');
}

void release(struct node **root, void(*release_data)(void *)) {
  if (root == 0)
    return;
  while (*root != 0) {
    struct node *node;
    if ((*root)->data != 0) {
      release_data((*root)->data);
      (*root)->data = 0;
    }
    node = *root;
    *root = (*root)->next;
    qzfree(node, ID_NODE);
    node = 0; /* may be no need, but... */
  }
}

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

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

/*=========================================================================*/
/* リンクリストの要素数にかかわらず、O(1) でノードを削除する */
void delete(struct node **del_node, void (*release_data)(void *)) {
  if (del_node != 0) {
    struct node *target_node;
    target_node = *del_node;
    *del_node = (*del_node)->next;
    release_data(target_node->data);
    target_node->data = 0;
    qzfree(target_node, ID_NODE);
    target_node = 0;/* may be no need, but... */
  }
}
/*=========================================================================*/

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};
  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);

  struct node *node;
  int target = 97;
  if ((node = search(root, (int (*)(void *, void *))cmp_data, &target)) != 0) {
    printf("found! : %d\n", *(int *)node->data);
  } else {
    printf("not found..\n");
  }
  /*-----------------------------------------------------*/
  /* 削除するノードを探す。この部分は O(N) なのは当然である. */
  struct node **pnode;
  if ((pnode = search_for_delete(&root, (int (*)(void *, void *))cmp_data, &target)) != 0) {
    printf("deleting! : %d\n", *(int *)(*pnode)->data);  
  }
  /*-----------------------------------------------------*/
  /* リンクリストの要素数にかかわらず、O(1) でノードを削除する */
  delete(pnode, (void (*)(void *))release_data);
  /*-----------------------------------------------------*/
  
  dump(root, (void (*)(void *))dump_data);
  
  release(&root, (void (*)(void *))release_data);
  qzmallocdump();
  return 0;
}
/* end */