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

struct node {
  unsigned int size;
  void *data;
  struct node *next;
  struct node *before;
};

static struct node *rootS;

void xmallocinit(void)
{
  rootS = NULL;
}

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

void *xmalloc(unsigned int n)
{
  struct node *p;
  if (!(p = malloc(sizeof(struct node)))) {
    fprintf(stderr, "xmalloc(): cannot malloc() in xmalloc()\n");
    abort();
  }
  if (rootS == NULL) {
    rootS = p;
    p->size = n;
    p->next = p;
    p->before = p;
  } else {
    p->next = rootS->next;
    p->before = rootS;
    rootS->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 node *q;
  if (rootS == NULL) {
    fprintf(stderr, "xfree(): root is null.\n");
    abort();
  }
  flag = 0;
  q = rootS;
  for (;;) {
    if (q->data == p) {
      if (q->next == q) {
        free(q);
        flag = 1;
        rootS = NULL;
        break;
      } else {
        q->before->next = q->next;
        q->next->before = q->before;
        free(q->data);
        free(q);
        flag = 1;
        break;
      }
    }
    if (q->next == rootS)
      break;
    q = q->next;
  }
  if (flag != 1) {
    fprintf(stderr, "xfree(): cannot xfree(), no data.\n");
    abort();
  }
}

void *xrealloc(void *p, unsigned int n)
{
  int flag;
  struct node *q;
  void *r;
  if (rootS == NULL) {
    fprintf(stderr, "xrealloc(): root is null.\n");
    abort();
  }
  flag = 0;
  q = rootS;
  for (;;) {
    if (q->data == p) {
      flag = 1;
      break;
    }
    if (q->next == rootS)
      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 /* >= 2 */
char *getline(FILE *fp)
{
  static char inbuff[BUFFSIZE];
  char *outbuff_malloc, *tmpbuff;
  char *p, *q;
  int fEOL;
  if ((outbuff_malloc = xmalloc(1)) == NULL) {
    return NULL;
  }
  *outbuff_malloc = '\0';
  fEOL = 0;
  do {
    if ((q = fgets(inbuff, BUFFSIZE, fp)) == 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);
  if (q == NULL) {
    xfree(outbuff_malloc);
    return NULL;
  }
  return outbuff_malloc;
}

int main()
{
  char *p, *q;
  int sp, sq;
  int flag = 0;
  xmallocinit();
  printf("input string 1: ");
  if ((p = getline(stdin)) != NULL) {
    printf("input string 2: ");
    if ((q = getline(stdin)) != NULL) {
      sp = strlen(p);
      sq = strlen(q);
      if (sp < sq || sp == 0 || sq == 0) {
        printf("no matched.\n");
      } else {
        unsigned int i, j;
        for (i = 0; i < sp - sq + 1; i++) {
          for (j = 0; j < sq; j++) {
            if (p[i + j] != q[j])
              break;
          }
          if (j == strlen(q)) {
            printf("matched %d - %d\n", i, i + strlen(q) - 1);
            flag = 1;
          }
        }
        if (flag == 0)
          printf("no match.\n");
      }
    }
  }
  xfree(p);
  xfree(q);
  xmallocdump();
  return 0;
}
/* end */

xfree(): root is null.
input string 1: 
Disallowed system call: SYS_kill