[sgt/library] / bheap.c

/*
 * Generic reusable binary-heap maintenance code.
 * 
 * This file is copyright 2005 Simon Tatham.
 * 
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT.  IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include <stdlib.h>
#include <string.h>
#include "bheap.h"

#ifdef TESTMODE
int coverage;			       /* bit flags for various if clauses */
int checked_coverage;
#define COVERAGE(x) ( coverage |= (1 << (x)) )
#else
#define COVERAGE(x) ( (void)0 )
#endif

struct bheap {
    int nelts, maxelts;
    int eltsize;
    int direction;
    bheap_cmpfn_t compare;
    void *compare_ctx;
    char *elts;
};

/*
 * Our array is zero-based. Therefore the children of 0 are 1 and
 * 2; the children of 1 are 3 and 4; of 2 are 5 and 6, and so on.
 * In other words, the children of node n are 2n+1 and 2n+2, and
 * the parent of node n is floor((n-1)/2).
 */
#define PARENT(n) ( ((n)-1)/2 )
#define LCHILD(n) ( 2*(n)+1 )
#define RCHILD(n) ( 2*(n)+2 )

/*
 * This macro calls the compare function, and returns TRUE if the
 * two elements are the wrong way up and should be swapped.
 * 
 * It doesn't _have_ to be called on a parent and child, but its
 * return value assumes that. So you could call it on any two
 * elements x,y and it would return TRUE if y ought to be the
 * parent of x.
 */
#define MISORDERED(bh,parent,child) \
    ( (bh)->direction * \
	  (bh)->compare((bh)->compare_ctx, \
			    (bh)->elts + (parent) * (bh)->eltsize, \
			    (bh)->elts + (child) * (bh)->eltsize) > 0 )

/*
 * This macro swaps two elements of the heap.
 */
#define SWAP(bh,x,y) do { \
    memcpy((bh)->elts + (bh)->maxelts * (bh)->eltsize, \
	   (bh)->elts + (x) * (bh)->eltsize, (bh)->eltsize); \
    memcpy((bh)->elts + (x) * (bh)->eltsize, \
	   (bh)->elts + (y) * (bh)->eltsize, (bh)->eltsize); \
    memcpy((bh)->elts + (y) * (bh)->eltsize, \
	   (bh)->elts + (bh)->maxelts * (bh)->eltsize, (bh)->eltsize); \
} while (0)

bheap *bheap_new(int maxelts, int eltsize, int direction,
		 bheap_cmpfn_t compare, void *compare_ctx)
{
    bheap *bh = malloc(sizeof(bheap));
    if (!bh)
	return NULL;

    /*
     * Allocate one extra element of space, to use for swapping
     * things.
     */
    bh->elts = malloc(maxelts * (eltsize+1));
    if (!bh->elts)
	return NULL;

    bh->nelts = 0;
    bh->maxelts = maxelts;
    bh->eltsize = eltsize;
    bh->direction = direction;
    bh->compare = compare;
    bh->compare_ctx = compare_ctx;

    return bh;
}

void *bheap_add(bheap *bh, void *elt)
{
    int i;

    if (bh->nelts >= bh->maxelts) {
	COVERAGE(0);
	return NULL;
    }

    COVERAGE(1);
    /*
     * Add the element to the end of the array.
     */
    memcpy(bh->elts + bh->nelts * bh->eltsize, elt, bh->eltsize);
    bh->nelts++;

    /*
     * Now swap it with its parent repeatedly to preserve the heap
     * property.
     */
    i = bh->nelts-1;

    if (i == 0)
	COVERAGE(2);

    while (i > 0) {
	int p = PARENT(i);

	COVERAGE(3);

	if (MISORDERED(bh, p, i)) {
	    COVERAGE(4);
	    SWAP(bh, p, i);
	    i = p;
	} else {
	    COVERAGE(5);
	    break;		       /* we're done */
	}
    }

    return elt;
}

void *bheap_topmost(bheap *bh, void *elt)
{
    if (bh->nelts <= 0) {
	COVERAGE(6);
	return NULL;
    }

    COVERAGE(7);
    memcpy(elt, bh->elts, bh->eltsize);
    return elt;
}

void *bheap_remove(bheap *bh, void *elt)
{
    if (bh->nelts <= 0) {
	COVERAGE(8);
	return NULL;
    }

    if (elt)
	memcpy(elt, bh->elts, bh->eltsize);

    bh->nelts--;

    if (bh->nelts > 0) {
	int i;

	COVERAGE(8);
	/*
	 * Move the highest-index element of the heap into the top
	 * position.
	 */
	SWAP(bh, bh->nelts, 0);

	/*
	 * Now repeatedly move it down the heap by swapping it with
	 * the more suitable of its children.
	 */
	i = 0;
	while (1) {
	    int lc, rc;

	    lc = LCHILD(i);
	    rc = RCHILD(i);

	    COVERAGE(9);

	    if (lc >= bh->nelts) {
		COVERAGE(10);
		break;		       /* we've hit bottom */
	    }

	    if (rc >= bh->nelts) {
		/*
		 * Special case: there is only one child to check.
		 */
		COVERAGE(11);
		if (MISORDERED(bh, i, lc)) {
		    COVERAGE(12);
		    SWAP(bh, i, lc);
		} else {
		    COVERAGE(13);
		}
		/* _Now_ we've hit bottom. */
		break;
	    } else {
		COVERAGE(14);
		/*
		 * The common case: there are two children and we
		 * must check them both.
		 */
		if (MISORDERED(bh, i, lc) || MISORDERED(bh, i, rc)) {
		    COVERAGE(15);
		    /*
		     * Pick the more appropriate child to swap with
		     * (i.e. the one which would want to be the
		     * parent if one were above the other - as one
		     * is about to be).
		     */
		    if (MISORDERED(bh, lc, rc)) {
			COVERAGE(16);
			SWAP(bh, i, rc);
			i = rc;
		    } else {
			COVERAGE(17);
			SWAP(bh, i, lc);
			i = lc;
		    }
		} else {
		    /* This element is in the right place; we're done. */
		    COVERAGE(18);
		    break;
		}
	    }
	}
    } else {
	COVERAGE(19);
    }

    return elt;
}

int bheap_count(bheap *bh)
{
    return bh->nelts;
}

void bheap_free(bheap *bh)
{
    if (bh) {
	if (bh->elts)
	    free(bh->elts);
	free(bh);
    }
}

#ifdef TESTMODE

#include <stdio.h>

/* we _really_ need assertions enabled, for this test */
#undef NDEBUG
#include <assert.h>

#define MAX 8

#define CHECK_COVERAGE(c, statement) do { \
    coverage &= ~ (1 << (c)); \
    statement; \
    assert(coverage & (1 << (c))); \
    checked_coverage |= (1 << (c)); \
} while (0)

int intcmp_ctx;
int array[MAX];
int n;

bheap *bh;

int intcmp(void *vctx, const void *av, const void *bv)
{
    const int *a = (const int *)av;
    const int *b = (const int *)bv;
    int *ctx = (int *)vctx;

    assert(ctx == &intcmp_ctx);

    if (*a < *b)
	return -1;
    else if (*a > *b)
	return +1;
    return 0;
}

void add(int x)
{
    int *ret = bheap_add(bh, &x);

    if (n >= MAX) {
	assert(ret == NULL);
    } else {
	assert(ret == &x);

	array[n++] = x;
    }

    assert(bheap_count(bh) == n);
}

void rem(int x)
{
    int out1, *ret1, out2, *ret2;

    ret1 = bheap_topmost(bh, &out1);
    ret2 = bheap_remove(bh, &out2);

    if (n == 0) {
	assert(x < 0);		       /* test the tests! */
	assert(ret1 == NULL);
	assert(ret2 == NULL);
    } else {
	int i;

	assert(x >= 0);		       /* test the tests! */
	assert(ret1 == &out1);
	assert(ret2 == &out2);
	assert(out1 == out2);
	assert(out1 == x);

	/* Now find x in _our_ array and remove it. */
	for (i = 0; i < n; i++) {
	    assert(array[i] >= x);
	    if (array[i] == x) {
		int tmp;

		tmp = array[n-1];
		array[n-1] = array[i];
		array[i] = tmp;

		break;
	    }
	}
	assert(i < n);		       /* we expect to have found it */
	n--;
    }

    assert(bheap_count(bh) == n);
}

int main(void)
{
    coverage = checked_coverage = 0;

    bh = bheap_new(MAX, sizeof(int), +1, intcmp, &intcmp_ctx);

    /*
     * Various sets of adds and removes which test all the code
     * paths marked with COVERAGE() statements.
     */
    CHECK_COVERAGE(2, add(4));
    CHECK_COVERAGE(3, add(7));
    CHECK_COVERAGE(4, add(2));
    CHECK_COVERAGE(1, add(6));
    add(3);
    add(1);
    CHECK_COVERAGE(5, add(8));
    add(5);
    CHECK_COVERAGE(0, add(9));	       /* check the full-heap case */

    CHECK_COVERAGE(7, rem(1));
    CHECK_COVERAGE(8, rem(2));
    CHECK_COVERAGE(9, rem(3));
    CHECK_COVERAGE(14, rem(4));
    rem(5);
    rem(6);
    rem(7);
    CHECK_COVERAGE(19, rem(8));
    CHECK_COVERAGE(6, rem(-1));	       /* and check the empty-heap case */
    CHECK_COVERAGE(8, rem(-1));	       /* and check the empty-heap case */

    add(1);
    add(2);
    add(3);
    CHECK_COVERAGE(12, rem(1));
    rem(2);
    rem(3);

    add(1);
    add(3);
    add(2);
    CHECK_COVERAGE(13, rem(1));
    rem(2);
    rem(3);

    add(1);
    add(2);
    add(3);
    add(4);
    CHECK_COVERAGE(17, rem(1));
    rem(2);
    rem(3);
    rem(4);

    add(1);
    add(3);
    add(2); 
    add(4);
    CHECK_COVERAGE(16, rem(1));
    rem(2);
    rem(3);
    rem(4);

    add(1);
    add(2);
    add(3);
    add(5);
    add(6);
    add(7);
    add(4);
    CHECK_COVERAGE(18, rem(1));
    CHECK_COVERAGE(15, rem(2));
    rem(3);
    CHECK_COVERAGE(10, rem(4));
    CHECK_COVERAGE(11, rem(5));
    rem(6);
    rem(7);

    /*
     * See what happens with compare equality.
     */
    add(3);
    add(3);
    add(3);
    add(3);
    add(3);
    add(3);
    add(3);
    add(3);
    rem(3);
    rem(3);
    rem(3);
    rem(3);
    rem(3);
    rem(3);
    rem(3);
    rem(3);

    add(5);
    add(4);
    add(7);
    add(4);
    add(1);
    add(4);
    add(3);
    rem(1);
    rem(3);
    rem(4);
    rem(4);
    rem(4);
    rem(5);
    rem(7);

    /*
     * Interleave some adds and removes, turning the heap into a
     * real priority queue rather than a glorified sorter.
     * 
     * We add the digits of pi in order, and keep the heap size
     * capped at 5 by extracting one before adding the next.
     * 
     * Python code that generates this test sequence:

python -c '
list=[]
for c in "314159265358979323846264338327950288":
    c = int(c)
    if len(list) >= 5:
        list.sort()
        d = list[0]
        del list[0]
        print ("    rem(%d); /"+"* %s *"+"/") % (d, repr(list))
    list.append(c)
    list.sort()
    print ("    add(%d); /"+"* %s *"+"/") % (c, repr(list))
while len(list) > 0:
    list.sort()
    d = list[0]
    del list[0]
    print ("    rem(%d); /"+"* %s *"+"/") % (d, repr(list))
print "    rem(-1);"
'

     */
    add(3); /* [3] */
    add(1); /* [1, 3] */
    add(4); /* [1, 3, 4] */
    add(1); /* [1, 1, 3, 4] */
    add(5); /* [1, 1, 3, 4, 5] */
    rem(1); /* [1, 3, 4, 5] */
    add(9); /* [1, 3, 4, 5, 9] */
    rem(1); /* [3, 4, 5, 9] */
    add(2); /* [2, 3, 4, 5, 9] */
    rem(2); /* [3, 4, 5, 9] */
    add(6); /* [3, 4, 5, 6, 9] */
    rem(3); /* [4, 5, 6, 9] */
    add(5); /* [4, 5, 5, 6, 9] */
    rem(4); /* [5, 5, 6, 9] */
    add(3); /* [3, 5, 5, 6, 9] */
    rem(3); /* [5, 5, 6, 9] */
    add(5); /* [5, 5, 5, 6, 9] */
    rem(5); /* [5, 5, 6, 9] */
    add(8); /* [5, 5, 6, 8, 9] */
    rem(5); /* [5, 6, 8, 9] */
    add(9); /* [5, 6, 8, 9, 9] */
    rem(5); /* [6, 8, 9, 9] */
    add(7); /* [6, 7, 8, 9, 9] */
    rem(6); /* [7, 8, 9, 9] */
    add(9); /* [7, 8, 9, 9, 9] */
    rem(7); /* [8, 9, 9, 9] */
    add(3); /* [3, 8, 9, 9, 9] */
    rem(3); /* [8, 9, 9, 9] */
    add(2); /* [2, 8, 9, 9, 9] */
    rem(2); /* [8, 9, 9, 9] */
    add(3); /* [3, 8, 9, 9, 9] */
    rem(3); /* [8, 9, 9, 9] */
    add(8); /* [8, 8, 9, 9, 9] */
    rem(8); /* [8, 9, 9, 9] */
    add(4); /* [4, 8, 9, 9, 9] */
    rem(4); /* [8, 9, 9, 9] */
    add(6); /* [6, 8, 9, 9, 9] */
    rem(6); /* [8, 9, 9, 9] */
    add(2); /* [2, 8, 9, 9, 9] */
    rem(2); /* [8, 9, 9, 9] */
    add(6); /* [6, 8, 9, 9, 9] */
    rem(6); /* [8, 9, 9, 9] */
    add(4); /* [4, 8, 9, 9, 9] */
    rem(4); /* [8, 9, 9, 9] */
    add(3); /* [3, 8, 9, 9, 9] */
    rem(3); /* [8, 9, 9, 9] */
    add(3); /* [3, 8, 9, 9, 9] */
    rem(3); /* [8, 9, 9, 9] */
    add(8); /* [8, 8, 9, 9, 9] */
    rem(8); /* [8, 9, 9, 9] */
    add(3); /* [3, 8, 9, 9, 9] */
    rem(3); /* [8, 9, 9, 9] */
    add(2); /* [2, 8, 9, 9, 9] */
    rem(2); /* [8, 9, 9, 9] */
    add(7); /* [7, 8, 9, 9, 9] */
    rem(7); /* [8, 9, 9, 9] */
    add(9); /* [8, 9, 9, 9, 9] */
    rem(8); /* [9, 9, 9, 9] */
    add(5); /* [5, 9, 9, 9, 9] */
    rem(5); /* [9, 9, 9, 9] */
    add(0); /* [0, 9, 9, 9, 9] */
    rem(0); /* [9, 9, 9, 9] */
    add(2); /* [2, 9, 9, 9, 9] */
    rem(2); /* [9, 9, 9, 9] */
    add(8); /* [8, 9, 9, 9, 9] */
    rem(8); /* [9, 9, 9, 9] */
    add(8); /* [8, 9, 9, 9, 9] */
    rem(8); /* [9, 9, 9, 9] */
    rem(9); /* [9, 9, 9] */
    rem(9); /* [9, 9] */
    rem(9); /* [9] */
    rem(9); /* [] */
    rem(-1);

    bheap_free(bh);

    {
	int i;

	for (i = 0; i < 20; i++) {
	    if (!(coverage & (1 << i)))
		printf("coverage is missing %d\n", i);
	    else if (!(checked_coverage & (1 << i)))
		printf("checked_coverage is missing %d\n", i);
	}
    }

    printf("finished testing, no assertions failed\n");

    return 0;
}

#endif
Commit	Line	Data
80aaeada	1	/*
80aaeada	2	* Generic reusable binary-heap maintenance code.
749cebc3	3	*
	4	* This file is copyright 2005 Simon Tatham.
	5	*
	6	* Permission is hereby granted, free of charge, to any person
	7	* obtaining a copy of this software and associated documentation
	8	* files (the "Software"), to deal in the Software without
	9	* restriction, including without limitation the rights to use,
	10	* copy, modify, merge, publish, distribute, sublicense, and/or
	11	* sell copies of the Software, and to permit persons to whom the
	12	* Software is furnished to do so, subject to the following
	13	* conditions:
	14	*
	15	* The above copyright notice and this permission notice shall be
	16	* included in all copies or substantial portions of the Software.
	17	*
	18	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
	19	* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
	20	* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
	21	* NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
	22	* ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
	23	* CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
	24	* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
	25	* SOFTWARE.
80aaeada	26	*/
	27
	28	#include <stdlib.h>
	29	#include <string.h>
	30	#include "bheap.h"
	31
	32	#ifdef TESTMODE
	33	int coverage; /* bit flags for various if clauses */
	34	int checked_coverage;
	35	#define COVERAGE(x) ( coverage \|= (1 << (x)) )
	36	#else
	37	#define COVERAGE(x) ( (void)0 )
	38	#endif
	39
	40	struct bheap {
	41	int nelts, maxelts;
	42	int eltsize;
	43	int direction;
	44	bheap_cmpfn_t compare;
	45	void *compare_ctx;
	46	char *elts;
	47	};
	48
	49	/*
	50	* Our array is zero-based. Therefore the children of 0 are 1 and
	51	* 2; the children of 1 are 3 and 4; of 2 are 5 and 6, and so on.
	52	* In other words, the children of node n are 2n+1 and 2n+2, and
	53	* the parent of node n is floor((n-1)/2).
	54	*/
	55	#define PARENT(n) ( ((n)-1)/2 )
	56	#define LCHILD(n) ( 2*(n)+1 )
	57	#define RCHILD(n) ( 2*(n)+2 )
	58
	59	/*
	60	* This macro calls the compare function, and returns TRUE if the
	61	* two elements are the wrong way up and should be swapped.
	62	*
	63	* It doesn't _have_ to be called on a parent and child, but its
	64	* return value assumes that. So you could call it on any two
	65	* elements x,y and it would return TRUE if y ought to be the
	66	* parent of x.
	67	*/
	68	#define MISORDERED(bh,parent,child) \
	69	( (bh)->direction * \
	70	(bh)->compare((bh)->compare_ctx, \
	71	(bh)->elts + (parent) * (bh)->eltsize, \
	72	(bh)->elts + (child) * (bh)->eltsize) > 0 )
	73
	74	/*
	75	* This macro swaps two elements of the heap.
	76	*/
	77	#define SWAP(bh,x,y) do { \
	78	memcpy((bh)->elts + (bh)->maxelts * (bh)->eltsize, \
	79	(bh)->elts + (x) * (bh)->eltsize, (bh)->eltsize); \
	80	memcpy((bh)->elts + (x) * (bh)->eltsize, \
	81	(bh)->elts + (y) * (bh)->eltsize, (bh)->eltsize); \
	82	memcpy((bh)->elts + (y) * (bh)->eltsize, \
	83	(bh)->elts + (bh)->maxelts * (bh)->eltsize, (bh)->eltsize); \
	84	} while (0)
	85
	86	bheap *bheap_new(int maxelts, int eltsize, int direction,
	87	bheap_cmpfn_t compare, void *compare_ctx)
	88	{
	89	bheap *bh = malloc(sizeof(bheap));
90	if (!bh)
91	return NULL;
92
93	/*
94	* Allocate one extra element of space, to use for swapping
95	* things.
96	*/
97	bh->elts = malloc(maxelts * (eltsize+1));
98	if (!bh->elts)
99	return NULL;
100
101	bh->nelts = 0;
102	bh->maxelts = maxelts;
103	bh->eltsize = eltsize;
104	bh->direction = direction;
105	bh->compare = compare;
106	bh->compare_ctx = compare_ctx;
107
108	return bh;
109	}
110
111	void bheap_add(bheap bh, void *elt)
112	{
113	int i;
114
115	if (bh->nelts >= bh->maxelts) {
116	COVERAGE(0);
117	return NULL;
118	}
119
120	COVERAGE(1);
121	/*
122	* Add the element to the end of the array.
123	*/
124	memcpy(bh->elts + bh->nelts * bh->eltsize, elt, bh->eltsize);
125	bh->nelts++;
126
127	/*
128	* Now swap it with its parent repeatedly to preserve the heap
129	* property.
130	*/
131	i = bh->nelts-1;
132
133	if (i == 0)
134	COVERAGE(2);
135
136	while (i > 0) {
137	int p = PARENT(i);
138
139	COVERAGE(3);
140
141	if (MISORDERED(bh, p, i)) {
142	COVERAGE(4);
143	SWAP(bh, p, i);
144	i = p;
145	} else {
146	COVERAGE(5);
147	break; /* we're done */
148	}
149	}
150
151	return elt;
152	}
153
154	void bheap_topmost(bheap bh, void *elt)
155	{
156	if (bh->nelts <= 0) {
157	COVERAGE(6);
158	return NULL;
159	}
160
161	COVERAGE(7);
162	memcpy(elt, bh->elts, bh->eltsize);
163	return elt;
164	}
165
166	void bheap_remove(bheap bh, void *elt)
167	{
168	if (bh->nelts <= 0) {
169	COVERAGE(8);
170	return NULL;
171	}
172
173	if (elt)
174	memcpy(elt, bh->elts, bh->eltsize);
175
176	bh->nelts--;
177
178	if (bh->nelts > 0) {
179	int i;
180
181	COVERAGE(8);
182	/*
183	* Move the highest-index element of the heap into the top
184	* position.
185	*/
186	SWAP(bh, bh->nelts, 0);
187
188	/*
189	* Now repeatedly move it down the heap by swapping it with
190	* the more suitable of its children.
191	*/
192	i = 0;
193	while (1) {
194	int lc, rc;
195
196	lc = LCHILD(i);
197	rc = RCHILD(i);
198
199	COVERAGE(9);
200
201	if (lc >= bh->nelts) {
202	COVERAGE(10);
203	break; /* we've hit bottom */
204	}
205
206	if (rc >= bh->nelts) {
207	/*
208	* Special case: there is only one child to check.
209	*/
210	COVERAGE(11);
211	if (MISORDERED(bh, i, lc)) {
212	COVERAGE(12);
213	SWAP(bh, i, lc);
214	} else {
215	COVERAGE(13);
216	}
217	/* _Now_ we've hit bottom. */
218	break;
219	} else {
220	COVERAGE(14);
221	/*
222	* The common case: there are two children and we
223	* must check them both.
224	*/
225	if (MISORDERED(bh, i, lc) \|\| MISORDERED(bh, i, rc)) {
226	COVERAGE(15);
227	/*
228	* Pick the more appropriate child to swap with
229	* (i.e. the one which would want to be the
230	* parent if one were above the other - as one
231	* is about to be).
232	*/
233	if (MISORDERED(bh, lc, rc)) {
234	COVERAGE(16);
235	SWAP(bh, i, rc);
236	i = rc;
237	} else {
238	COVERAGE(17);
239	SWAP(bh, i, lc);
240	i = lc;
241	}
242	} else {
243	/* This element is in the right place; we're done. */
244	COVERAGE(18);
245	break;
246	}
247	}
248	}
249	} else {
250	COVERAGE(19);
251	}
252
253	return elt;
254	}
255
256	int bheap_count(bheap *bh)
257	{
258	return bh->nelts;
259	}
260
261	void bheap_free(bheap *bh)
262	{
263	if (bh) {
264	if (bh->elts)
265	free(bh->elts);
266	free(bh);
267	}
268	}
269
270	#ifdef TESTMODE
271
272	#include <stdio.h>
273
274	/* we _really_ need assertions enabled, for this test */
275	#undef NDEBUG
276	#include <assert.h>
277
278	#define MAX 8
279
280	#define CHECK_COVERAGE(c, statement) do { \
281	coverage &= ~ (1 << (c)); \
282	statement; \
283	assert(coverage & (1 << (c))); \
284	checked_coverage \|= (1 << (c)); \
285	} while (0)
286
287	int intcmp_ctx;
288	int array[MAX];
289	int n;
290
291	bheap *bh;
292
293	int intcmp(void vctx, const void av, const void *bv)
294	{
295	const int a = (const int )av;
296	const int b = (const int )bv;
297	int ctx = (int )vctx;
298
299	assert(ctx == &intcmp_ctx);
300
301	if (a < b)
302	return -1;
303	else if (a > b)
304	return +1;
305	return 0;
306	}
307
308	void add(int x)
309	{
310	int *ret = bheap_add(bh, &x);
311
312	if (n >= MAX) {
313	assert(ret == NULL);
314	} else {
315	assert(ret == &x);
316
317	array[n++] = x;
318	}
319
320	assert(bheap_count(bh) == n);
321	}
322
323	void rem(int x)
324	{
325	int out1, ret1, out2, ret2;
326
327	ret1 = bheap_topmost(bh, &out1);
328	ret2 = bheap_remove(bh, &out2);
329
330	if (n == 0) {
331	assert(x < 0); /* test the tests! */
332	assert(ret1 == NULL);
333	assert(ret2 == NULL);
334	} else {
335	int i;
336
337	assert(x >= 0); /* test the tests! */
338	assert(ret1 == &out1);
339	assert(ret2 == &out2);
340	assert(out1 == out2);
341	assert(out1 == x);
342
343	/* Now find x in _our_ array and remove it. */
344	for (i = 0; i < n; i++) {
345	assert(array[i] >= x);
346	if (array[i] == x) {
347	int tmp;
348
349	tmp = array[n-1];
350	array[n-1] = array[i];
351	array[i] = tmp;
352
353	break;
354	}
355	}
356	assert(i < n); /* we expect to have found it */
357	n--;
358	}
359
360	assert(bheap_count(bh) == n);
361	}
362
363	int main(void)
364	{
365	coverage = checked_coverage = 0;
366
367	bh = bheap_new(MAX, sizeof(int), +1, intcmp, &intcmp_ctx);
368
369	/*
370	* Various sets of adds and removes which test all the code
371	* paths marked with COVERAGE() statements.
372	*/
373	CHECK_COVERAGE(2, add(4));
374	CHECK_COVERAGE(3, add(7));
375	CHECK_COVERAGE(4, add(2));
376	CHECK_COVERAGE(1, add(6));
377	add(3);
378	add(1);
379	CHECK_COVERAGE(5, add(8));
380	add(5);
381	CHECK_COVERAGE(0, add(9)); /* check the full-heap case */
382
383	CHECK_COVERAGE(7, rem(1));
384	CHECK_COVERAGE(8, rem(2));
385	CHECK_COVERAGE(9, rem(3));
386	CHECK_COVERAGE(14, rem(4));
387	rem(5);
388	rem(6);
389	rem(7);
390	CHECK_COVERAGE(19, rem(8));
391	CHECK_COVERAGE(6, rem(-1)); /* and check the empty-heap case */
392	CHECK_COVERAGE(8, rem(-1)); /* and check the empty-heap case */
393
394	add(1);
395	add(2);
396	add(3);
397	CHECK_COVERAGE(12, rem(1));
398	rem(2);
399	rem(3);
400
401	add(1);
402	add(3);
403	add(2);
404	CHECK_COVERAGE(13, rem(1));
405	rem(2);
406	rem(3);
407
408	add(1);
409	add(2);
410	add(3);
411	add(4);
412	CHECK_COVERAGE(17, rem(1));
413	rem(2);
414	rem(3);
415	rem(4);
416
417	add(1);
418	add(3);
419	add(2);
420	add(4);
421	CHECK_COVERAGE(16, rem(1));
422	rem(2);
423	rem(3);
424	rem(4);
425
426	add(1);
427	add(2);
428	add(3);
429	add(5);
430	add(6);
431	add(7);
432	add(4);
433	CHECK_COVERAGE(18, rem(1));
434	CHECK_COVERAGE(15, rem(2));
435	rem(3);
436	CHECK_COVERAGE(10, rem(4));
437	CHECK_COVERAGE(11, rem(5));
438	rem(6);
439	rem(7);
440
441	/*
442	* See what happens with compare equality.
443	*/
444	add(3);
445	add(3);
446	add(3);
447	add(3);
448	add(3);
449	add(3);
450	add(3);
451	add(3);
452	rem(3);
453	rem(3);
454	rem(3);
455	rem(3);
456	rem(3);
457	rem(3);
458	rem(3);
459	rem(3);
460
461	add(5);
462	add(4);
463	add(7);
464	add(4);
465	add(1);
466	add(4);
467	add(3);
468	rem(1);
469	rem(3);
470	rem(4);
471	rem(4);
472	rem(4);
473	rem(5);
474	rem(7);
475
476	/*
477	* Interleave some adds and removes, turning the heap into a
478	* real priority queue rather than a glorified sorter.
479	*
480	* We add the digits of pi in order, and keep the heap size
481	* capped at 5 by extracting one before adding the next.
482	*
483	* Python code that generates this test sequence:
484
485	python -c '
486	list=[]
487	for c in "314159265358979323846264338327950288":
488	c = int(c)
489	if len(list) >= 5:
490	list.sort()
491	d = list[0]
492	del list[0]
493	print (" rem(%d); /"+"* %s *"+"/") % (d, repr(list))
494	list.append(c)
495	list.sort()
496	print (" add(%d); /"+"* %s *"+"/") % (c, repr(list))
497	while len(list) > 0:
498	list.sort()
499	d = list[0]
500	del list[0]
501	print (" rem(%d); /"+"* %s *"+"/") % (d, repr(list))
502	print " rem(-1);"
503	'
504
505	*/
506	add(3); /* [3] */
507	add(1); /* [1, 3] */
508	add(4); /* [1, 3, 4] */
509	add(1); /* [1, 1, 3, 4] */
510	add(5); /* [1, 1, 3, 4, 5] */
511	rem(1); /* [1, 3, 4, 5] */
512	add(9); /* [1, 3, 4, 5, 9] */
513	rem(1); /* [3, 4, 5, 9] */
514	add(2); /* [2, 3, 4, 5, 9] */
515	rem(2); /* [3, 4, 5, 9] */
516	add(6); /* [3, 4, 5, 6, 9] */
517	rem(3); /* [4, 5, 6, 9] */
518	add(5); /* [4, 5, 5, 6, 9] */
519	rem(4); /* [5, 5, 6, 9] */
520	add(3); /* [3, 5, 5, 6, 9] */
521	rem(3); /* [5, 5, 6, 9] */
522	add(5); /* [5, 5, 5, 6, 9] */
523	rem(5); /* [5, 5, 6, 9] */
524	add(8); /* [5, 5, 6, 8, 9] */
525	rem(5); /* [5, 6, 8, 9] */
526	add(9); /* [5, 6, 8, 9, 9] */
527	rem(5); /* [6, 8, 9, 9] */
528	add(7); /* [6, 7, 8, 9, 9] */
529	rem(6); /* [7, 8, 9, 9] */
530	add(9); /* [7, 8, 9, 9, 9] */
531	rem(7); /* [8, 9, 9, 9] */
532	add(3); /* [3, 8, 9, 9, 9] */
533	rem(3); /* [8, 9, 9, 9] */
534	add(2); /* [2, 8, 9, 9, 9] */
535	rem(2); /* [8, 9, 9, 9] */
536	add(3); /* [3, 8, 9, 9, 9] */
537	rem(3); /* [8, 9, 9, 9] */
538	add(8); /* [8, 8, 9, 9, 9] */
539	rem(8); /* [8, 9, 9, 9] */
540	add(4); /* [4, 8, 9, 9, 9] */
541	rem(4); /* [8, 9, 9, 9] */
542	add(6); /* [6, 8, 9, 9, 9] */
543	rem(6); /* [8, 9, 9, 9] */
544	add(2); /* [2, 8, 9, 9, 9] */
545	rem(2); /* [8, 9, 9, 9] */
546	add(6); /* [6, 8, 9, 9, 9] */
547	rem(6); /* [8, 9, 9, 9] */
548	add(4); /* [4, 8, 9, 9, 9] */
549	rem(4); /* [8, 9, 9, 9] */
550	add(3); /* [3, 8, 9, 9, 9] */
551	rem(3); /* [8, 9, 9, 9] */
552	add(3); /* [3, 8, 9, 9, 9] */
553	rem(3); /* [8, 9, 9, 9] */
554	add(8); /* [8, 8, 9, 9, 9] */
555	rem(8); /* [8, 9, 9, 9] */
556	add(3); /* [3, 8, 9, 9, 9] */
557	rem(3); /* [8, 9, 9, 9] */
558	add(2); /* [2, 8, 9, 9, 9] */
559	rem(2); /* [8, 9, 9, 9] */
560	add(7); /* [7, 8, 9, 9, 9] */
561	rem(7); /* [8, 9, 9, 9] */
562	add(9); /* [8, 9, 9, 9, 9] */
563	rem(8); /* [9, 9, 9, 9] */
564	add(5); /* [5, 9, 9, 9, 9] */
565	rem(5); /* [9, 9, 9, 9] */
566	add(0); /* [0, 9, 9, 9, 9] */
567	rem(0); /* [9, 9, 9, 9] */
568	add(2); /* [2, 9, 9, 9, 9] */
569	rem(2); /* [9, 9, 9, 9] */
570	add(8); /* [8, 9, 9, 9, 9] */
571	rem(8); /* [9, 9, 9, 9] */
572	add(8); /* [8, 9, 9, 9, 9] */
573	rem(8); /* [9, 9, 9, 9] */
574	rem(9); /* [9, 9, 9] */
575	rem(9); /* [9, 9] */
576	rem(9); /* [9] */
577	rem(9); /* [] */
578	rem(-1);
579
580	bheap_free(bh);
581
582	{
583	int i;
584
585	for (i = 0; i < 20; i++) {
586	if (!(coverage & (1 << i)))
587	printf("coverage is missing %d\n", i);
588	else if (!(checked_coverage & (1 << i)))
589	printf("checked_coverage is missing %d\n", i);
590	}
591	}
592
593	printf("finished testing, no assertions failed\n");
594
595	return 0;
596	}
597
598	#endif