recent; a sort of sideways uniq

[Alan Lee Wendt]

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);
	}
    }