#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct supernode {
  unsigned int size;
  void *data;
  struct supernode *next;
  struct supernode *before;
};
static struct supernode *superrootS = NULL;

void xmallocdump(void)
{
  struct supernode *p;
  if (superrootS == NULL) {
/*    fprintf(stderr, "xmallocdump(): root is NULL.\n");*/
  } else {
    p = superrootS;
    do {
      fprintf(stderr, ">%p %p %p(%d):%s\n", p, p->next, p->data, p->size, p->data);
      p = p->next;
    } while (p != superrootS);
  }
}

void *xmalloc(unsigned int n)
{
  struct supernode *p;
  if (!(p = malloc(sizeof(struct supernode)))) {
    fprintf(stderr, "xmalloc(): cannot malloc() in xmalloc()\n");
    abort();
  }
  if (superrootS == NULL) {
    superrootS = p;
    p->size = n;
    p->next = p;
    p->before = p;
  } else {
    p->size = n;
    p->next = superrootS->next;
    p->before = superrootS;
    superrootS->next = p;
    p->next->before = p;
  }
  if (!(p->data = malloc(n))) {
    fprintf(stderr, "xmalloc(): cannot malloc() in malloc()\n");
    abort();
  }
  return p->data;
}

void xfree(void *p)
{
  int flag;
  struct supernode *q;
  if (p == NULL)
    return;
  if (superrootS == NULL) {
    fprintf(stderr, "xfree(): root is null.\n");
    abort();
  }
  flag = 0;
  q = superrootS;
  for (;;) {
    if (q->data == p) {
      if (q->next == q) {
        free(q->data);
        free(q);
        flag = 1;
        superrootS = NULL;
        break;
      } else {
        q->before->next = q->next;
        q->next->before = q->before;
        if (q == superrootS)
          superrootS = q->next;
        free(q->data);
        free(q);
        flag = 1;
        break;
      }
    }
    if (q->next == superrootS)
      break;
    q = q->next;
  }
  if (flag != 1) {
    fprintf(stderr, "xfree(): cannot xfree(), no data.(%p)\n", p);
    abort();
  }
}

void *xrealloc(void *p, unsigned int n)
{
  int flag;
  struct supernode *q;
  void *r;
  if (superrootS == NULL) {
    fprintf(stderr, "xrealloc(): root is null.\n");
    abort();
  }
  flag = 0;
  q = superrootS;
  for (;;) {
    if (q->data == p) {
      flag = 1;
      break;
    }
    if (q->next == superrootS)
      break;
    q = q->next;
  } 
  if (flag != 1) {
    fprintf(stderr, "xrealloc(): no data.\n");
    abort();
  }
  if (n < q->size) {
    q->size = n;
    return p;
  } else {
    r = malloc(n);
    memcpy(r, q->data, q->size);
    free(q->data);
    q->data = r;
    q->size = n;
  }
  return r;
}

#define BUFFSIZE 3
char *getline(FILE *fp)
{
  static char inbuff[BUFFSIZE];
  char *outbuff_malloc, *tmpbuff;
  char *p;
  int fEOL;

  if ((outbuff_malloc = xmalloc(1)) == NULL)
    return NULL;
  *outbuff_malloc = '\0';
  fEOL = 0;
  do {
    if (fgets(inbuff, BUFFSIZE, fp) == NULL) {
      if (strlen(outbuff_malloc) == 0) {
        xfree(outbuff_malloc);
        outbuff_malloc = NULL;
      }
      break;
    }
    for (p = inbuff; *p != '\0'; p++)
      ;
    if (*(p - 1) == '\n') {
      *(p - 1) = '\0';
      fEOL = 1;
    }
    if ((tmpbuff = xrealloc(outbuff_malloc, strlen(outbuff_malloc) + strlen(inbuff) + 1)) == NULL) {
      xfree(outbuff_malloc);
      return NULL;
    }
    strcat(tmpbuff, inbuff);
    outbuff_malloc = tmpbuff;
  } while (!fEOL);
  return outbuff_malloc;
}

struct data {
  char *name;
  char *tel;
  struct data *left;
  struct data *right;
};

struct list {
  struct data *node;
  struct list *next;
};

struct data *add_data(struct data *root, char *name, char *tel) {
  struct data *node;
  if (root == NULL) {
    if ((node = xmalloc(sizeof(struct data))) == NULL)
      return NULL;
    if ((node->name = xmalloc(strlen(name) + 1)) == NULL) {
      xfree(node);
      return NULL;
    }
    if ((node->tel = xmalloc(strlen(tel) + 1)) == NULL) {
      xfree(name);
      xfree(node);
      return NULL;
    }
    strcpy(node->name, name);
    strcpy(node->tel, tel);
    node->left = node->right = NULL;
    return node;
  }
  if (strcmp(root->name, name) < 0) {
    root->left = add_data(root->left, name, tel);
    return root;
  }  else if (strcmp(root->name, name) > 0) {
    root->right = add_data(root->right, name, tel);
    return root;
  } else {
    return NULL;
  }
}

void writefile(struct data *root, FILE *fp) {
  if (root != NULL) {
    fprintf(fp, "%s %s\n", root->name, root->tel);
    xfree(root->name);
    xfree(root->tel);
    writefile(root->left, fp);
    if (!root->left) xfree(root->left);
    writefile(root->right, fp);
    if (!root->right) xfree(root->right);    
    xfree(root);
  }
}

struct data *add_abb(struct data *root, FILE *fp, int sw) {
  char *p;
  while ((p = getline(fp)) != NULL) {
    char *q;
    if (sw > 0)
      printf("%s\n", p);
    if (strlen(p) > 0) {
      for (q = p; !isdigit(*q) && *q != '\0'; q++)
        ;
      *(q - 1) = '\0';
      if((root = add_data(root, p, q)) == NULL) {
        fprintf(stderr, "memory full, aborted\n");
        exit(-1);
      }
    }
    xfree(p);
  }
  return root;
}

struct data *add_command(struct data *root) {
  printf("input(quit for ^D): ");
  return add_abb(root, stdin, 0);
}

struct list *add_list(struct list *listroot, struct data *node) {
  struct list *newlist;
  if (listroot == NULL) {
    if ((newlist = xmalloc(sizeof(struct list))) != NULL) {
      newlist->node = node;
      newlist->next = NULL;
    }
    return newlist;
  } else {
    listroot->next = add_list(listroot->next, node);
    return listroot;
  }
}

void vomit_list(struct list *listroot, int n) {
  if (listroot != NULL) {
    printf("%d: %s %s\n", n, listroot->node->name, listroot->node->tel);
    vomit_list(listroot->next, n + 1);
  }
}

void release_list(struct list *listroot) {
  struct list *p;
  if (listroot != NULL) {
    p = listroot->next;
    xfree(listroot);
    release_list(p);
  }
}

struct list *search_data(struct data *node, char *word, struct list *listroot) {
  if (node == NULL)
    return listroot;
  if (strstr(node->name, word) != NULL)
    listroot = add_list(listroot, node);
  listroot = search_data(node->left, word, listroot);
  listroot = search_data(node->right, word, listroot);
  return listroot;
}

struct data *vector_list(struct list *listnode, int n) {
  if (listnode == NULL)
    return NULL;
  if (n <= 1)
    return listnode->node;
  return vector_list(listnode->next, n - 1);
}

struct data *delete_data(struct data *root, struct data *delnode) {
  return root;
}

struct data *delete_command(struct data *root) {
  struct data *delnode;
  char *p, *q;
  int n;
  struct list *listroot = NULL;
  printf("input: ");
  if ((p = getline(stdin)) != NULL) {
    if (strlen(p) > 0) {
      listroot = search_data(root, p, listroot);
      vomit_list(listroot, 1);
      printf("which data to delete? :");
      if (strlen(q = getline(stdin)) > 0) {
        n = atof(q);
        xfree(q);
        delnode = vector_list(listroot, n);
        if (delnode == NULL) {
          printf("index is out of range.\n");
        } else {
          printf("delete: %s %s\n", delnode->name, delnode->tel);
        }
        root = delete_data(root, delnode);
      }
      release_list(listroot);
    }
    xfree(p);
  }
  return root;
}
  
void search_command(struct data *root) {
  char *p;
  struct list *listroot = NULL;
  printf("input: ");
  if ((p = getline(stdin)) != NULL) {
    if (strlen(p) > 0) {
      listroot = search_data(root, p, listroot);
      vomit_list(listroot, 1);
      release_list(listroot);
    }
    xfree(p);
  }
}

int main(int argc, char *argv[]) {
  struct data *root = NULL;
  char c;
  FILE *fp;
  if (argc != 2) {
    fprintf(stderr, "usage: %s <data-file>\n", argv[0]);
    exit(-1);
  }
  if ((fp = fopen(argv[1], "rt")) != NULL) {
    root = add_abb(root, fp, 1);
    fclose(fp);
  }    
  do {
    char *p;
    printf("command (\'a\'dd, \'d\'elete, \'s\'earch, \'q\'uit): ");
    p = getline(stdin);
    c = *p;
    switch (c) {
    case 'a':
      root = add_command(root);
      break;
    case 'd':
      root = delete_command(root);
      break;
    case 's':
      search_command(root);
      break;
    case 'q':
      break;
    default:
      break;
    }
    xfree(p);
  } while (c != 'q');
  if ((fp = fopen(argv[1], "wt")) != NULL) {
    writefile(root, fp);
    fclose(fp);
  }
  xmallocdump();
  return 0;
}
/* end */

usage: /t <data-file>

Exited: ExitFailure 255