#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
/* xmalloc.h */
#if !defined(XMALLOC_H)
struct supernode {
int id;
unsigned int size;
void *data;
struct supernode *next;
struct supernode *before;
};
void xmallocdump(void);
void *xmalloc(unsigned int, int);
void xfree(void *, int);
void *xrealloc(void *, unsigned int, int);
#define XMALLOC_H
#endif
/* end */
static struct supernode *superrootS = NULL;
#define N 16
void xmallocdump(void)
{
int i;
unsigned char c;
struct supernode *p;
if (superrootS == NULL) {
fprintf(stderr, "xmallocdump(): root is NULL.\n");
} else {
p = superrootS;
fprintf(stderr, "ERROR: Memory leak occured!\n");
do {
fprintf(stderr, "Memory Leak >%p %p %p(%d):%d: ", (void *)p,(void *)p->next, (void *)p->data, p->size, p->id);
for (i = 0; i < N; i++) {
c = *(unsigned char *)((char *)(p->data) + i);
printf("%02x(%c) ", c , (isprint(c)) ? c : '.');
}
putchar('\n');
p = p->next;
} while (p != superrootS);
}
}
void *xmalloc(unsigned int n, int id)
{
unsigned int i;
struct supernode *p;
rand();
if (!(p = (struct supernode *)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();
}
for (i = 0; i < n; i++)
*(char *)((char *)(p->data) + i) = rand() & 0xff;
p->id = id;
/* printf("xmalloc():malloc id = %d(%p)\n", p->id, p->data); */
return p->data;
}
void xfree(void *p, int id)
{
unsigned int flag, i;
struct supernode *q;
/* printf("xfree():free id = %d(%p)\n", id, p); */
if (p == NULL)
return;
if (superrootS == NULL) {
fprintf(stderr, "xfree(): root is null.\n");
abort();
}
rand();
flag = 0;
q = superrootS;
for (;;) {
if (q->data == p) {
if (q->id != id) {
fprintf(stderr, "xfree(): bad ID.\n");
abort();
}
if (q->next == q) {
for (i = 0; i < q->size; i++)
*(char *)((char *)(q->data) + i) = rand() & 0xff;
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;
for (i = 0; i < q->size; i++)
*(char *)((char *)(q->data) + i) = rand() & 0xff;
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.(id = %d, %p)\n", id, p);
abort();
}
}
void *xrealloc(void *p, unsigned int n, int id)
{
int flag;
struct supernode *q;
void *r;
if (superrootS == NULL) {
fprintf(stderr, "xrealloc(): root is null.\n");
abort();
}
if (p == NULL) {
fprintf(stderr, "xrealloc(): suggest using malloc()\n");
return xmalloc(n, id);
}
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 (q->id != id) {
fprintf(stderr, "xralloc(): bad ID.\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;
}
/* end */
/*----------------------------------------------------------------------*/
#define DEBUG
#if defined(DEBUG)
/*#include "xmalloc.h" */
#else
#define xmalloc(x, y) malloc(x)
#define xfree(x, y) free(x)
#define xrealloc(x, y, z) realloc(x, y)
#define xmallocdump()
#endif
#define ID_GETLINE 1001
#define ID_NODE 1002
#define ID_STR 1004
#define ID_WORDDATA 1005
#define BUFFSIZE 3 /* >= 2 */
char *mygetline(FILE *fp) {
static char inbuff[BUFFSIZE];
char *outbuff_malloc, *tmpbuff;
char *p, *r;
int fEOL;
if ((outbuff_malloc = xmalloc(1, ID_GETLINE)) == NULL) {
return NULL;
}
*outbuff_malloc = '\0';
fEOL = 0;
do {
r = fgets(inbuff, BUFFSIZE, fp);
if (r == NULL)
break;
for (p = inbuff; *p != '\0'; p++)
;
if (*(p - 1) == '\n')
fEOL = 1;
if ((tmpbuff = xrealloc(outbuff_malloc, strlen(outbuff_malloc) + strlen(inbuff) + 1, ID_GETLINE)) == NULL) {
xfree(outbuff_malloc, ID_GETLINE);
return NULL;
}
strcat(tmpbuff, inbuff);
outbuff_malloc = tmpbuff;
} while (!fEOL);
if (strlen(outbuff_malloc) > 0) {
for (p = outbuff_malloc; *p != '\0'; p++)
;
if (*(p - 1) == '\n')
*(p - 1) = '\0';
return outbuff_malloc;
}
xfree(outbuff_malloc, ID_GETLINE);
return NULL;
}
struct node {
void *data;
int bal;
struct node *left;
struct node *right;
};
void treeRotateSingleL(struct node **p) {
struct node *p1;
p1 = (*p)->left;
(*p)->left = p1->right;
p1->right = *p;
(*p)->bal = 0;
*p = p1;
}
void treeRotateSingleR(struct node **p) {
struct node *p1;
p1 = (*p)->right;
(*p)->right = p1->left;
p1->left = *p;
(*p)->bal = 0;
*p = p1;
}
void *insertAVLTree(struct node **p, void *data, int (*cmp)(void *, void *), int *ph) {
void *rc;
struct node *p1, *p2;
if (!*p) {
if ((*p = xmalloc(sizeof(struct node), ID_NODE)) == NULL) {
fprintf(stderr, "cannot allocate enough memory(struct node), aborted\n");
exit(-1);
}
*ph = 1;
(*p)->data = data;
(*p)->bal = 0;
(*p)->left = (*p)->right = NULL;
return data;
}
if ((*cmp)(data, (*p)->data) < 0) {
if ((rc = insertAVLTree(&((*p)->left), data, cmp, ph)) != data)
return rc;
if (*ph > 0) {
if ((*p)->bal == 1) {
(*p)->bal = 0;
*ph = 0;
} else if ((*p)->bal == 0) {
(*p)->bal = -1;
} else if ((*p)->bal == -1) {
if ((*p)->left->bal == -1) {
treeRotateSingleL(p);
} else {
p1 = (*p)->left;
p2 = (p1)->right;
treeRotateSingleR(&((*p)->left));
treeRotateSingleL(p);
if (p2->bal == -1)
(*p)->bal = 1;
else
(*p)->bal = 0;
if (p2->bal == +1)
p1->bal = -1;
else
p1->bal = 0;
}
(*p)->bal = 0;
*ph = 0;
}
}
return rc;
} else if ((*cmp)(data, (*p)->data) > 0) {
if((rc = insertAVLTree(&((*p)->right), data, cmp, ph)) != data)
return rc;
if (*ph > 0) {
if ((*p)->bal == -1) {
(*p)->bal = 0;
*ph = 0;
} else if ((*p)->bal == 0) {
(*p)->bal = +1;
} else if ((*p)->bal == +1) {
if ((*p)->right->bal == +1) {
treeRotateSingleR(p);
} else { /* rotate double RL */
p1 = (*p)->right;
p2 = (p1)->left;
treeRotateSingleL(&((*p)->right));
treeRotateSingleR(p);
if (p2->bal == 1)
(*p)->bal = -1;
else
(*p)->bal = 0;
if (p2->bal == -1)
p1->bal = 1;
else
p1->bal = 0;
}
(*p)->bal = 0;
*ph = 0;
}
}
return rc;
} else {
return (*p)->data;
}
}
void *pop(struct node **root) {
struct node *p;
void *data;
if (*root == NULL) {
return NULL;
}
if ((*root)->left) {
data = pop(&((*root)->left));
return data;
}
assert((*root)->left == NULL);
p = *root;
data = p->data;
*root = p->right;
xfree(p, ID_NODE);
return data;
}
struct worddata {
char *word;
int n;
};
int isDelimiter(char c) {
return iscntrl(0xff & c) || isdigit(0xff & c) || (isprint(0xff & c) && !isalpha(0xff & c));
}
int cmp(struct worddata *s, struct worddata *t) {
return strcmp(s->word, t->word);
}
void wdregister(char *p, struct node **root) {
char *word;
struct worddata *wd, *already;
int ph;
word = xmalloc(strlen(p) + 1, ID_STR);
if (!word) {
fprintf(stderr, "cannot allocate enough memory, aborted.\n");
exit(-1);
}
strcpy(word, p);
wd = xmalloc(sizeof(struct worddata), ID_WORDDATA);
if (!wd) {
fprintf(stderr, "cannot allocate enough memory, aborted.\n");
exit(-1);
}
wd->word = word;
wd->n = 1;
if ((already = insertAVLTree(root, wd, (int (*)(void *, void *))cmp, &ph)) != wd) {
xfree(wd->word, ID_STR);
xfree(wd, ID_WORDDATA);
already->n++;
}
}
void analyze_line(char *line, struct node **root) {
char *p, *q;
for (p = line; *p;) {
for (;isDelimiter(*p) && *p; p++)
;
if (!*p)
break;
for (q = p; !isDelimiter(*q) && *q; q++)
;
if (*q) {
*q = '\0';
wdregister(p, root);
p = q + 1;
} else {
wdregister(p, root);
break;
}
}
}
int main() {
struct node *root;
struct worddata *p;
char *line;
int n;
root = NULL;
while ((line = mygetline(stdin)) != NULL) {
analyze_line(line, &root);
xfree(line, ID_GETLINE);
}
n = 0;
while ((p = pop(&root)) != NULL) {
printf("%s: %d\n", p->word, p->n);
n++;
xfree(p->word, ID_STR);
xfree(p, ID_WORDDATA);
}
printf("%d words\n", n);
xmallocdump();
return 0;
}
/* end */