wendt@arizona.edu (Alan Lee Wendt) (11/20/88)
recent.c reads a file and throws out all but the last occurrence of each line, leaving the remainder of the lines in order. It is a useful filter for history lists and directory stacks, because it shortens the list without changing its meaning. Also, if you feed a page trace through it, "recent < pagetrace | tail -n", will give you n most-recently used pages (which an lru replacement algorithm would leave resident). BUGS: It should really have a "-f" option to throw out all but the first, then it would look like "uniq" except not require sorting. Max of 5000 lines of input (enough for history and directories but not for page traces). #include <stdio.h> #define NBUCKETS 569 struct Hnode { struct Hnode *ptr; int number; char *txt; } *Buckets[NBUCKETS]; struct Hnode *install(s) register char *s; { register char *p1, *p2; register unsigned h; register int *p, *q, n; register struct Hnode *hnode; char *strcpy(), *sbrk(); static unsigned mask[] = { ~0, 0 }; q = (p = (int *) s) + (n = strlen(s))/sizeof(int); h = *q & *((unsigned *)((char *)mask + (sizeof(int) - n%sizeof(int)))); while ( p < q ) h ^= *p++; h %= NBUCKETS; /* for each entry on the chain */ for (hnode = Buckets[h]; hnode; hnode = hnode->ptr) { for (p1 = s, p2 = hnode->txt; *p1++ == *p2++;) if (p1[-1] == 0) { hnode->number++; /* count occurrences */ return hnode; } } /* not found, add another entry */ hnode = (struct Hnode *)sbrk((unsigned)sizeof(struct Hnode) + n + 1); hnode->txt = (char *)hnode + sizeof(struct Hnode); strcpy(hnode->txt, s); hnode->ptr = Buckets[h]; /* link at head */ hnode->number = 1; Buckets[h] = hnode; return hnode; } main() { char bf[10000]; struct Hnode *vec[5000]; int vsize = 0, i; while (fgets(bf, sizeof(bf), stdin) && vsize < 5000) vec[vsize++] = install(bf); for (i = 0; i < vsize; i++) { if (--vec[i]->number == 0) fputs(vec[i]->txt, stdout); } }