transhash.c

Hausdorff Distance for Image Recognition

/*
 *
 * $Header: /usr/u/wjr/vision/r-h/RCS/transhash.c,v 1.5 1993/11/04 21:11:14 wjr Exp $
 *
 * Copyright (c) 1992, 1993 Cornell University.  All Rights Reserved.  
 *  
 * Use, reproduction, preparation of derivative works, and distribution
 * of this software is permitted.  Any copy of this software or of any
 * derivative work must include both the above copyright notice of
 * Cornell University and this paragraph.  Any distribution of this
 * software or derivative works must comply with all applicable United
 * States export control laws.  This software is made available AS IS,
 * and CORNELL UNIVERSITY DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED,
 * INCLUDING WITHOUT LIMITATION THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE, AND NOTWITHSTANDING ANY OTHER
 * PROVISION CONTAINED HEREIN, ANY LIABILITY FOR DAMAGES RESULTING FROM
 * THE SOFTWARE OR ITS USE IS EXPRESSLY DISCLAIMED, WHETHER ARISING IN
 * CONTRACT, TORT (INCLUDING NEGLIGENCE) OR STRICT LIABILITY, EVEN IF
 * CORNELL UNIVERSITY IS ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
 */

static char rcsid[] = "@(#)$Header: /usr/u/wjr/vision/r-h/RCS/transhash.c,v 1.5 1993/11/04 21:11:14 wjr Exp $";

#include "list.h"
#include "misc.h"
#include "transhash.h"

/*
 * What's a TransHash, anyway? Well, it's a place to record some
 * basic information about a bunch of transformations, each of which consists
 * of two integers, referred to as x, y, each of which is
 * known to have bounded range, and whose values are spaced apart by known
 * steps (i.e. x can take on values, lowX, lowX + stepX, ..., highX-1, and
 * similarly for y). We want to know, for each value, whether or not
 * it is in the hash table. We also want cheap addition and deletion.
 * Actually, highX-lowX need not be conguent to zero mod stepX, and as long
 * as you don't try to feed it two entries which are within stepX of each
 * other, it will do fine.
 *
 * The TransHash structure contains a number of Lists, used as buckets.
 * Each List contains all the entries added so far which hash to that
 * bucket. The hashing function is simple: just add up the four values
 * (correcting for the step size and the ranges). It remains to be seen how
 * well this works...
 *
 * What do the routines do? Well, thNew() does what you'd expect: gives
 * you a new, empty, hash table. If it can't, it gives you (TransHash *)NULL.
 * thFree() gets rid of your old, unfashionable, hash table.
 * thAdd() makes a mark that this point is in the table, and returns TRUE;
 * it returns FALSE if it can't. Adding the same point more than once is
 * an error.
 * thRem() removes a point. If it isn't in the table, you get an assertion
 * failure.
 * thIsIn tells you if a point is in the table.
 * thGetLowest gives you the lowest-sum point in the table (point with
 * smallest x+y, with a possible error of stepX+stepY). If the table
 * is empty, it gives you FALSE, otherwise TRUE.
 *
 * You can tell it to store a void * pointer along with an entry when you
 * initially thAdd() it; use thGet() to get it back.
 *
 */

/*
 * Internally, the hash function just adds the two components, and also
 * separates out some of the lower-order bits; entries which add up to
 * the same value are grouped based on the low bits of the two values.
 */

/* How many low bits to pull out as additional hash bits */
#define	LOWBITS	2

/* The mask to get these */
#define	LOWMASK	((1 << LOWBITS) - 1)

/* With 2 components, pulling out LOWBITS gets us this many groups */
#define	NHASHGROUPS	(1 << (2 * LOWBITS))

static int hash(TransHash *th, int x, int y);

/* This is the structure we hang off the ListNodes */
typedef struct {
    int x, y;
    void *userdata;
    } TransHashEntry;

TransHash *
thNew(int lowX, int highX, int stepX,
      int lowY, int highY, int stepY)
{
    TransHash *newth;
    int nlist;
    int i;

    assert(lowX < highX);
    assert(lowY < highY);

    newth = (TransHash *)malloc(sizeof(*newth));
    if (newth == (TransHash *)NULL) {
	return((TransHash *)NULL);
	}

    /*
     * How many entries can there be in the hash table?
     * Well, feed in the highest values possible (highX - 1, highY - 1 etc),
     * shift by the space we're saving for the low-order bits (NHASHGROUPS),
     * and add then the highest values for the low-order bits possible (i.e. up
     * to an additional NHASHGROUPS - 1); this gives us the highest
     * possible hash value. Since they start at zero, add one.
     */
    nlist = ((highX - 1 - lowX) / stepX + (highY - 1 - lowY) / stepY) *
	NHASHGROUPS + NHASHGROUPS;

    newth->listarr = (List *)malloc((unsigned)nlist * sizeof(List));
    if (newth->listarr == (List *)NULL) {
	free((void *)newth);
	return((TransHash *)NULL);
	}

    newth->lowX = lowX;
    newth->highX = highX;
    newth->stepX = stepX;

    newth->lowY = lowY;
    newth->highY = highY;
    newth->stepY = stepY;

    newth->nlist = nlist;

    for (i = 0; i < nlist; i++) {
	newth->listarr[i] = NULLLIST;
	}

    newth->lowbucket = nlist;

    return(newth);
    }


void 
thFree(TransHash *th)
{
    int i;
    List l;
    ListNode ln;
    TransHashEntry *the;
#ifdef INSTRUMENT
    int ntot = 0;
    int nmax = 0;
    int nli = 0;
#endif

    assert(th != (TransHash *)NULL);
    assert(th->listarr != (List *)NULL);

    /* Free all the Lists and the stuff hung on them */
    for (i = 0; i < th->nlist; i++) {
	if (th->listarr[i] != NULLLIST) {
	    l = th->listarr[i];
#ifdef INSTRUMENT
	    nli++;
	    nmax = MAX(nmax, liLen(l));
	    ntot += liLen(l);
#endif
	    foreach (ln, l) {
		the = (TransHashEntry *)liGet(ln);
		assert(the != (TransHashEntry *)NULL);
		free((void *)the);
		}
	    liFree(l);
	    }
	}
#ifdef INSTRUMENT
    DEBUG( "freed with %d/%d lists, max %d, mean %f\n",
	  nli, th->nlist, nmax, ntot / (double)nli);
#endif
    free((void *)th->listarr);
    free((void *)th);
    }

boolean 
thAdd(TransHash *th, int x, int y, void *userdata)
{
    int bucket;
    List l;
    ListNode ln;
    TransHashEntry *the;
    
    assert(th != (TransHash *)NULL);
    assert(!thIsIn(th, x, y));

    the = (TransHashEntry *)malloc(sizeof(TransHashEntry));
    if (the == (TransHashEntry *)NULL) {
	return(FALSE);
	}

    the->x = x;
    the->y = y;
    the->userdata = userdata;

    bucket = hash(th, x, y);

    l = th->listarr[bucket];
    if (l == NULLLIST) {
	/* First hit on this bucket */
	l = liNew();
	if (l == NULLLIST) {
	    free((void *)the);
	    return(FALSE);
	    }
	th->listarr[bucket] = l;
	}

    /* Add to the collision chain */
    ln = liAdd(l, (void *)the);
    if (ln == NULLLISTNODE) {
	/* Don't free l - th now owns it */
	free((void *)the);
	return(FALSE);
	}

    /* Make sure we keep track of the lowest bucket */
    th->lowbucket = MIN(th->lowbucket, bucket);

    return(TRUE);
    }

void 
thRem(TransHash *th, int x, int y)
{
    int bucket;
    List l;
    ListNode ln;
    TransHashEntry *the;
    
    assert(th != (TransHash *)NULL);
    assert(thIsIn(th, x, y));

    bucket = hash(th, x, y);

    l = th->listarr[bucket];
    assert(l != NULLLIST);

    foreach (ln, l) {
	the = (TransHashEntry *)liGet(ln);
	assert(the != (TransHashEntry *)NULL);

	if ((the->x == x) && (the->y == y)) {
	    /* Found it. */
	    liRem(ln);
	    free((void *)the);
	    break;
	    }
	}
    }

boolean
thIsIn(TransHash *th, int x, int y)
{
    int bucket;
    List l;
    ListNode ln;
    TransHashEntry *the;
    
    assert(th != (TransHash *)NULL);

    bucket = hash(th, x, y);

    l = th->listarr[bucket];
    if (l == NULLLIST) {
	/* No bucket chain - can't be there. */
	return(FALSE);
	}

    foreach (ln, l) {
	the = (TransHashEntry *)liGet(ln);
	assert(the != (TransHashEntry *)NULL);

	if ((the->x == x) && (the->y == y)) {
	    /* Found it. */
	    return(TRUE);
	    }
	}

    return(FALSE);
    }

boolean
thGetLowest(TransHash *th, int *x, int *y)
{
    int i;
    List l;
    ListNode ln;
    TransHashEntry *the;

    assert(th != (TransHash *)NULL);
    assert(x != (int *)NULL);
    assert(y != (int *)NULL);

    for (i = th->lowbucket; i < th->nlist; i++) {
	if (th->listarr[i] != NULLLIST) {
	    l = th->listarr[i];
	    ln = liFirst(l);
	    if (ln != NULLLISTNODE) {
		/* Found one */
		the = (TransHashEntry *)liGet(ln);
		assert(the != (TransHashEntry *)NULL);
		*x = the->x;
		*y = the->y;

		/* This is the lowest non-empty bucket */
		th->lowbucket = i;
		return(TRUE);
		}
	    }
		
	}

    return(FALSE);
    }

void *
thGet(TransHash *th, int x, int y)
{
    int bucket;
    List l;
    ListNode ln;
    TransHashEntry *the;
    
    assert(th != (TransHash *)NULL);
    assert(thIsIn(th, x, y));

    bucket = hash(th, x, y);

    l = th->listarr[bucket];
    assert(l != NULLLIST);

    foreach (ln, l) {
	the = (TransHashEntry *)liGet(ln);
	assert(the != (TransHashEntry *)NULL);

	if ((the->x == x) && (the->y == y)) {
	    /* Found it. */
	    return(the->userdata);
	    }
	}

    panic("thIsIn says it's there...");
    }

/*
 * Given a point, find out which bucket it hashes to.
 */
static int
hash(TransHash *th, int x, int y)
{
    int bucket;
    int hashx, hashy;

    assert(th != (TransHash *)NULL);
    assert(th->lowX <= x);
    assert(x < th->highX);
    assert(th->lowY <= y);
    assert(y < th->highY);

    hashx = (x - th->lowX) / th->stepX;
    hashy = (y - th->lowY) / th->stepY;
    bucket = (((hashx + hashy) << (2 * LOWBITS)) |
	      ((hashx & LOWMASK) << (LOWBITS)) |
	      ((hashy & LOWMASK)));
	    
    assert(bucket < th->nlist);

    return(bucket);
    }