FreeBSD/sys/netpfil/ipfw/dn_heap.c
/*
 * remove top element from heap, or obj if obj != NULL
 */
remove top element from heap, or obj if obj != NULL
remove top element from heap or obj if obj ! = NULL
void
heap_extract(struct dn_heap *h, void *obj)
{
	int child, father, max = h->elements - 1;
	if (max < 0) {
		printf("--- %s: empty heap 0x%p\n", __FUNCTION__, h);
		return;
	}
	if (obj == NULL)
		father = 0; 
	else { 
		if (h->ofs <= 0)
			panic("%s: extract from middle not set on %p\n",
				__FUNCTION__, h);
		father = *((int *)((char *)obj + h->ofs));
		if (father < 0 || father >= h->elements) {
			panic("%s: father %d out of bound 0..%d\n",
				__FUNCTION__, father, h->elements);
		}
	}
	RESET_OFFSET(h, father);
	while ( (child = HEAP_LEFT(father)) <= max ) {
		if (child != max &&
		    DN_KEY_LT(h->p[child+1].key, h->p[child].key) )
			child++; 
		h->p[father] = h->p[child];
		SET_OFFSET(h, father);
		father = child;
	}
	h->elements--;
	if (father != max) {
		h->p[father] = h->p[max];
		heap_insert(h, father, NULL);
	}
}
void heap_extract ( struct dn_heap * h , void * obj ) { int child , father , max = h -> elements - 1 ; if ( max < 0 ) { printf ( " \n " , __FUNCTION__ , h ) ; return ; } if ( obj == NULL ) father = 0 ; else { if ( h -> ofs <= 0 ) panic ( " \n " , __FUNCTION__ , h ) ; father = * ( ( int * ) ( ( char * ) obj + h -> ofs ) ) ; if ( father < 0 || father >= h -> elements ) { panic ( " \n " , __FUNCTION__ , father , h -> elements ) ; } } RESET_OFFSET ( h , father ) ; while ( ( child = HEAP_LEFT ( father ) ) <= max ) { if ( child != max && DN_KEY_LT ( h -> p [ child + 1 ] . key , h -> p [ child ] . key ) ) child ++ ; h -> p [ father ] = h -> p [ child ] ; SET_OFFSET ( h , father ) ; father = child ; } h -> elements -- ; if ( father != max ) { h -> p [ father ] = h -> p [ max ] ; heap_insert ( h , father , NULL ) ; } }
remove top element from heap, or obj if obj != NULL
remove top element from heap or obj if obj ! = NULL
/* default: move up smallest child */ /* extract specific element, index is at offset */ /*
	 * below, father is the index of the empty element, which
	 * we replace at each step with the smallest child until we
	 * reach the bottom level.
	 */ // XXX why removing RESET_OFFSET increases runtime by 10% ? /* take right child, otherwise left */ /*
		 * Fill hole with last entry and bubble up,
		 * reusing the insert code
		 */