#include
#include
#include
struct tnode {
char *string;
int count;
struct tnode *left, *right;
};
/* total nr. of nodes */
static int tnodecount = 0;
struct tnode *addtree(struct tnode *, char *);
void freetree(struct tnode *);
void freetarr(struct tnode **);
char *strdup(const char *s);
int tree_to_array(struct tnode **, struct tnode *);
int cmpr(const void *x, const void *y);
int main(void) {
FILE *fp = stdin;
struct tnode *root = {0};
struct tnode **tnarray = {0};
char line[1024];
char *start = NULL;
char *end = NULL;
char *filename = NULL;
int i = 0;
/* get unresponsibly wild with pointers */
while(fgets(line, 1024, fp) != NULL) {
if((start = strchr(line, '"')) == NULL)
continue;
start++;
for(end = start; *end; end++) {
if(*end == '"')
break;
}
*end = '\0';
if((filename = strchr(start, ' ')) == NULL)
continue;
filename += 2;
end = strrchr(filename, ' ');
*end = '\0';
/* grow a tree for world peace */
root = addtree(root, filename);
}
/* allocate mem for ptr array */
tnarray = malloc(tnodecount * sizeof(*tnarray));
/* read btree into array */
tree_to_array(tnarray, root);
/* qsort the array */
qsort(tnarray, tnodecount, sizeof(*tnarray), cmpr);
/* print the result */
for(i = 0; i < tnodecount; i++)
printf("%4d %s\n", tnarray[i]->count, tnarray[i]->string);
/* clean up mess, mom's proud.. */
freetree(root);
freetarr(tnarray);
fclose(fp);
return 0;
}
struct tnode *addtree(struct tnode *p, char *w) {
int cond;
if(p == NULL) {
p = (struct tnode *)malloc(sizeof(struct tnode));
p->string = strdup(w);
p->count = 1;
p->left = p->right = NULL;
tnodecount++;
} else if((cond = strcmp(w, p->string)) == 0)
p->count++;
else if(cond < 0)
p->left = addtree(p->left, w);
else
p->right = addtree(p->right, w);
return p;
}
void freetree(struct tnode *p) {
if(p != NULL) {
freetree(p->left);
freetree(p->right);
free(p->string);
free(p);
}
}
void freetarr(struct tnode **p) {
int i = 0;
if(p != NULL)
for(i = 0; i < tnodecount; i++)
free(p);
}
char *strdup(const char *s) {
char *result = malloc(strlen(s) + 1);
if(result == NULL)
return NULL;
strcpy(result, s);
return result;
}
int tree_to_array(struct tnode **array, struct tnode *tree) {
static struct tnode **write = NULL;
if(tree == NULL)
return -1;
if(array != NULL)
write = array;
if(tree != NULL) {
*write = tree, write++;
if(tree->left != NULL)
tree_to_array(NULL, tree->left);
if(tree->right != NULL)
tree_to_array(NULL, tree->right);
}
return 0;
}
int cmpr(const void *x, const void *y) {
struct tnode * const *a = x;
struct tnode * const *b = y;
int retval = 0;
if(a == NULL || b == NULL)
return -2;
if((*a)->count > (*b)->count)
retval = -1;
else if((*a)->count < (*b)->count)
retval = 1;
else
retval = 0;
return retval;
}