codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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 */
Private
[
?
]
Run code
Submit