chunk.c

Hausdorff Distance for Image Recognition

/*
 *
 *	$Header: /usr/u/wjr/src/ADT/RCS/chunk.c,v 1.4 1993/07/26 22:15:42 wjr Exp $
 *
 * Copyright (c) 1990, 1991, 1992, 1993 Cornell University.  All Rights
 * Reserved.
 *
 * Copyright (c) 1991, 1992 Xerox Corporation.  All Rights Reserved.
 *
 * Use, reproduction and preparation of derivative works of this software is
 * permitted.  Any copy of this software or of any derivative work must
 * include both the above copyright notices of Cornell University and Xerox
 * Corporation and this paragraph.  This software is made available AS IS, and
 * XEROX CORPORATION 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 XEROX CORPORATION IS ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGES.
 */
/*
 * Xerox may use this code without restriction.
 */

static char *rcsid = "@(#)$Header: /usr/u/wjr/src/ADT/RCS/chunk.c,v 1.4 1993/07/26 22:15:42 wjr Exp $";

/*
 *	chunk.c - Chunk manager
 *
 * A lot of programs allocate and free a lot of objects of the same type.
 * Using the general-purpose malloc/free routines for this is inefficient,
 * since they must deal with arbitrary allocations. This module is intended
 * to provide a simple, efficient method for allocating and freeing a lot
 * of objects of the same type.
 *
 * Exports:
 *	type Chunk
 *
 *	constant Chunk NULLCHUNK
 *
 *	Chunk chNew(unsigned size) - create a new area for allocating elements
 *		of size bytes
 *
 *	void *chAlloc(Chunk c) - get a new object from that chunk
 *
 *	void chFree(Chunk c, void *p) - free an object
 *
 * An object of type Chunk can be used to allocate objects of the size given
 *	when the chunk was created. Alignment is guaranteed, assuming that
 *	the size given is actually sizeof(type), where type is the type of
 *	the object being allocated.
 *
 * chNew creates a new chunk containing objects of the given size. If this
 *	is not possible, it returns NULLCHUNK.
 *
 * chAlloc allocates an object from that chunk. If this is not possible, it
 *	returns (void *)NULL.
 *
 * chFree frees the object, which must have been allocated from the given
 *	chunk.
 *
 */

#include "misc.h"
#include "chunk.h"

/* How many objects to allocate at once */
#define	QUANTUM	1000

Chunk
chNew(unsigned size)
{
    Chunk c;

    c = (Chunk)malloc(sizeof(*c));
    if (c == (Chunk)NULL) {
	return(NULLCHUNK);
	}

    /* We don't allocate any storage at all initially */
    c->freelist = (struct chunkBit *)NULL;

    /*
     * We put freelist pointers in the empty bits. We need to ensure that
     * both pointers and the things we're allocating are aligned properly,
     * and that there's enough space for either.
     *
     * If alignment rules are *really* strange, this could break: should be
     * LCM of the sizes; this will typically work though.
     */
    c->size = MAX(sizeof(struct chunkBit), size);
    if (c->size % sizeof(struct chunkBit) != 0) {
	/* Round it up */
	c->size += sizeof(struct chunkBit) -
	    (c->size % sizeof(struct chunkBit));
	}

    return(c);
    }

void *
chAlloc(Chunk c)
{
    void *p;
    char *q;
    int i;

    assert(c != NULLCHUNK);

    if (c->freelist) {
	/*
	 * If there is a free element, grab it and return.
	 * This should be the common case, and so be simple and fast.
	 */
	p = (void *)c->freelist;
	c->freelist = c->freelist->next;
	return(p);
	}
    else {
	/* Allocate a blob */
	p = malloc(c->size * QUANTUM);
	if (p == (void *)NULL) {
	    return((void *)NULL);
	    }

	/* Thread the list through it */
	for (i = 1, q = (char *)p; i < QUANTUM - 1; i++, q += c->size) {
	    ((struct chunkBit *)q)->next = (struct chunkBit *)(q + c->size);
	    }
	/* Terminate the list */
	((struct chunkBit *)q)->next = (struct chunkBit *)NULL;

	/* Point the freelist at the second element */
	c->freelist = (struct chunkBit *)(((char *)p) + c->size);
	/* and return the first */
	return(p);
	}
    }

void
chFree(Chunk c, void *p)
{
    assert(c != NULLCHUNK);
    assert(p != (void *)NULL);

    ((struct chunkBit *)p)->next = c->freelist;
    c->freelist = (struct chunkBit *)p;
    }