src/heap/heap.c File Reference

#include "heapInt.h"

Include dependency graph for heap.c:

Functions
static void HeapHeapify	ARGS ((Heap_t *heap))
Heap_t *	Heap_HeapInit (int length)
Heap_t *	Heap_HeapInitCompare (int length, int(compare)(const void , const void *))
void	Heap_HeapFree (Heap_t *heap)
int	Heap_HeapInsert (Heap_t heap, void item, long key)
int	Heap_HeapInsertCompare (Heap_t heap, void item, long key)
int	Heap_HeapExtractMin (Heap_t heap, void item, long *key)
int	Heap_HeapCount (Heap_t *heap)
Heap_t *	Heap_HeapClone (Heap_t *source)
int	Heap_HeapTest (Heap_t *heap)
int	Heap_HeapTestCompare (Heap_t *heap)
static void	HeapHeapify (Heap_t *heap)
static void	HeapHeapifyCompare (Heap_t *heap)
static int	HeapResize (Heap_t *heap)
void	Heap_HeapApplyForEachElement (Heap_t heap, int(compare)(const void *))
Variables
static char rcsid[]	UNUSED = "$Id: heap.c,v 1.18 2005/05/18 19:25:43 jinh Exp $"

Function Documentation

static int HeapResize ARGS ( (Heap_t *heap) ) [static]

AutomaticStart

void Heap_HeapApplyForEachElement	(	Heap_t *	heap,
		int()(const void )	compare
	)

Function********************************************************************

Synopsis [Apply function for each element of heap.]

Description [Apply function for each element of heap. Returns 1 if successful; 0 otherwise.]

SideEffects [ ]

SeeAlso [ ]

Definition at line 537 of file heap.c.

00538 {
00539 int i;
00540 
00541   for(i=0; i<heap->nitems; i++) {
00542     (*compare)(heap->slots[i].item);
00543   }
00544   return;
00545 }

Heap_t* Heap_HeapClone ( Heap_t * source )

Function********************************************************************

Synopsis [Clones a priority queue.]

Description []

SideEffects [None]

SeeAlso [Heap_HeapInit]

Definition at line 307 of file heap.c.

00309 {
00310   Heap_t *dest;
00311   int i;
00312   int nitems = source->nitems;
00313   HeapSlot_t *sslots = source->slots;
00314   HeapSlot_t *dslots;
00315 
00316   dest = Heap_HeapInit(source->length);
00317   if (dest == NULL) return(NULL);
00318   dest->nitems = nitems;
00319   dslots = dest->slots;
00320   for (i = 0; i < nitems; i++) {
00321     KEY(dslots, i) = KEY(sslots, i);
00322     ITEM(dslots, i) = ITEM(sslots, i);
00323   }
00324   return(dest);
00325 
00326 } /* Heap_HeapClone */

int Heap_HeapCount ( Heap_t * heap )

Function********************************************************************

Synopsis [Returns the number of items in a priority queue.]

Description []

SideEffects [None]

SeeAlso []

Definition at line 287 of file heap.c.

00289 {
00290   return(heap->nitems);
00291 
00292 } /* Heap_HeapCount */

int Heap_HeapExtractMin	(	Heap_t *	heap,
		void *	item,
		long *	key
	)

Function********************************************************************

Synopsis [Extracts the element with the minimum key from a priority queue.]

Description [Extracts the element with the minimum key from a priority queue. Returns 1 if successful; 0 otherwise.]

SideEffects [The minimum key and the associated item are returned as side effects.]

SeeAlso [Heap_HeapInsert]

Definition at line 253 of file heap.c.

00257 {
00258   HeapSlot_t *slots = heap->slots;
00259 
00260   if (heap->nitems == 0) return 0;
00261   *(void **)item = ITEM(slots, 0);
00262   *key = KEY(slots, 0);
00263   heap->nitems--;
00264   /* The next three lines are redundant if the queue is empty. */
00265   ITEM(slots, 0) = ITEM(slots, heap->nitems);
00266   KEY(slots, 0) = KEY(slots, heap->nitems);
00267   if(heap->compare) HeapHeapifyCompare(heap);
00268   else              HeapHeapify(heap);
00269 
00270   return 1;
00271 
00272 } /* Heap_HeapExtractMin */

void Heap_HeapFree ( Heap_t * heap )

Function********************************************************************

Synopsis [Frees a priority queue.]

Description []

SideEffects [None]

SeeAlso [Heap_HeapInit]

Definition at line 156 of file heap.c.

00158 {
00159   FREE(heap->slots);
00160   FREE(heap);
00161   return;
00162 
00163 } /* Heap_HeapFree */

Heap_t* Heap_HeapInit ( int length )

AutomaticEnd Function********************************************************************

Synopsis [Initializes a priority queue.]

Description [Initializes a priority queue. Returns a pointer to the heap if successful; NULL otherwise. The queue is implemented as a heap. The first element of the heap is the one with the smallest key.]

SideEffects [None]

SeeAlso [Heap_HeapFree]

Definition at line 89 of file heap.c.

00091 {
00092   Heap_t *heap;
00093 
00094   heap = ALLOC(Heap_t, 1);
00095   if (heap == NIL(Heap_t)) return NIL(Heap_t);
00096   heap->length = length;
00097   heap->nitems = 0;
00098   heap->compare = 0;
00099   heap->slots = ALLOC(HeapSlot_t, length);
00100   if (heap->slots == NIL(HeapSlot_t)) {
00101     FREE(heap);
00102     return NIL(Heap_t);
00103   }
00104   return heap;
00105 
00106 } /* Heap_HeapInit */

Heap_t* Heap_HeapInitCompare	(	int	length,
		int()(const void , const void *)	compare
	)

Function********************************************************************

Synopsis [Initializes a priority queue.]

Description [Initializes a priority queue. Returns a pointer to the heap if successful; NULL otherwise. The queue is implemented as a heap. The first element of the heap is the one with the smallest key.]

SideEffects [None]

SeeAlso [Heap_HeapFree]

Definition at line 124 of file heap.c.

00126 {
00127   Heap_t *heap;
00128 
00129   heap = ALLOC(Heap_t, 1);
00130   if (heap == NIL(Heap_t)) return NIL(Heap_t);
00131   heap->length = length;
00132   heap->nitems = 0;
00133   heap->compare = compare;
00134   heap->slots = ALLOC(HeapSlot_t, length);
00135   if (heap->slots == NIL(HeapSlot_t)) {
00136     FREE(heap);
00137     return NIL(Heap_t);
00138   }
00139   return heap;
00140 
00141 } /* Heap_HeapInitCompare */

int Heap_HeapInsert	(	Heap_t *	heap,
		void *	item,
		long	key
	)

Function********************************************************************

Synopsis [Inserts an item in a priority queue.]

Description [Inserts an item in a priority queue. Returns 1 if successful; 0 otherwise.]

SideEffects [None]

SeeAlso [Heap_HeapExtractMin]

Definition at line 179 of file heap.c.

00183 {
00184   HeapSlot_t *slots;
00185   int i = heap->nitems;
00186 
00187   if (i == heap->length && !HeapResize(heap)) return 0;
00188   slots = heap->slots;
00189   heap->nitems++;
00190   while (i > 0 && KEY(slots, PARENT(i)) > key) {
00191     ITEM(slots, i) = ITEM(slots, PARENT(i));
00192     KEY(slots, i) = KEY(slots, PARENT(i));
00193     i = PARENT(i);
00194   }
00195   ITEM(slots, i) = item;
00196   KEY(slots, i) = key;
00197   return 1;
00198 
00199 } /* Heap_HeapInsert */

int Heap_HeapInsertCompare	(	Heap_t *	heap,
		void *	item,
		long	key
	)

Function********************************************************************

Synopsis [Inserts an item in a priority queue.]

Description [Inserts an item in a priority queue. Returns 1 if successful; 0 otherwise.]

SideEffects [None]

SeeAlso [Heap_HeapExtractMin]

Definition at line 214 of file heap.c.

00218 {
00219   HeapSlot_t *slots;
00220   int i = heap->nitems;
00221 
00222   if (i == heap->length && !HeapResize(heap)) return 0;
00223   slots = heap->slots;
00224   heap->nitems++;
00225   while (i > 0 && (*(heap->compare))((char *)(long)KEY(slots, PARENT(i)), (char *)(long)key)) {
00226     ITEM(slots, i) = ITEM(slots, PARENT(i));
00227     KEY(slots, i) = KEY(slots, PARENT(i));
00228     i = PARENT(i);
00229   }
00230   ITEM(slots, i) = item;
00231   KEY(slots, i) = key;
00232   return 1;
00233 
00234 } /* Heap_HeapInsertCompare */

int Heap_HeapTest ( Heap_t * heap )

Function********************************************************************

Synopsis [Tests the heap property of a priority queue.]

Description [Tests the heap property of a priority queue. Returns 1 if successful; 0 otherwise.]

SideEffects [None]

SeeAlso []

Definition at line 342 of file heap.c.

00344 {
00345   HeapSlot_t *slots = heap->slots;
00346   int nitems = heap->nitems;
00347   int i;
00348 
00349   for (i = 1; i < nitems; i++) {
00350     if (KEY(slots,i) < KEY(slots, PARENT(i)))
00351       return 0;
00352   }
00353   return 1;
00354 
00355 } /* Heap_HeapTest */

int Heap_HeapTestCompare ( Heap_t * heap )

Function********************************************************************

Synopsis [Tests the heap property of a priority queue.]

Description [Tests the heap property of a priority queue. Returns 1 if successful; 0 otherwise.]

SideEffects [None]

SeeAlso []

Definition at line 370 of file heap.c.

00372 {
00373   HeapSlot_t *slots = heap->slots;
00374   int nitems = heap->nitems;
00375   int i;
00376 
00377   for (i = 1; i < nitems; i++) {
00378     if ((*(heap->compare))((char *)(long)KEY(slots, PARENT(i)), (char *)(long)KEY(slots,i)))
00379       return 0;
00380   }
00381   return 1;
00382 
00383 } /* Heap_HeapTest */

static void HeapHeapify ( Heap_t * heap ) [static]

Function********************************************************************

Synopsis [Maintains the heap property of a priority queue.]

Description []

SideEffects [None]

SeeAlso [Heap_HeapExtractMin]

Definition at line 410 of file heap.c.

00412 {
00413   int nitems = heap->nitems;
00414   HeapSlot_t *slots = heap->slots;
00415   int i = 0;
00416   int smallest = 0;
00417   void *item = ITEM(slots, 0);
00418   long key = KEY(slots, 0);
00419 
00420   while (1) {
00421     int left = LEFT(i);
00422     int right = RIGHT(i);
00423     int minkey;
00424     if (left < nitems && (minkey = KEY(slots, left)) < key) {
00425       smallest = left;
00426     } else {
00427       minkey = key;
00428     }
00429     if (right < nitems && KEY(slots, right) < minkey) {
00430       smallest = right;
00431     }
00432     if (smallest == i) break;
00433     KEY(slots, i) = KEY(slots, smallest);
00434     ITEM(slots, i) = ITEM(slots, smallest);
00435     i = smallest;
00436   }
00437   KEY(slots, i) = key;
00438   ITEM(slots, i) = item;
00439   return;
00440 
00441 } /* HeapHeapify */

static void HeapHeapifyCompare ( Heap_t * heap ) [static]

Function********************************************************************

Synopsis [Tests the heap property of a priority queue.]

Description [Tests the heap property of a priority queue. Returns 1 if successful; 0 otherwise.]

SideEffects [None]

SeeAlso []

Definition at line 456 of file heap.c.

00458 {
00459   int nitems = heap->nitems;
00460   HeapSlot_t *slots = heap->slots;
00461   int i = 0;
00462   int smallest = 0;
00463   void *item = ITEM(slots, 0);
00464   int key = KEY(slots, 0);
00465   int minkey;
00466 
00467 
00468   while (1) {
00469     int left = LEFT(i);
00470     int right = RIGHT(i);
00471     if (left < nitems && (*(heap->compare))((char *)(long)key, (char *)(long)(minkey = KEY(slots, left)))) {
00472       smallest = left;
00473     } else {
00474       minkey = key;
00475     }
00476     if (right < nitems && (*(heap->compare))((char *)(long)minkey, (char *)(long)KEY(slots, right))) {
00477       smallest = right;
00478     }
00479     if (smallest == i) break;
00480     KEY(slots, i) = KEY(slots, smallest);
00481     ITEM(slots, i) = ITEM(slots, smallest);
00482     i = smallest;
00483   }
00484   KEY(slots, i) = key;
00485   ITEM(slots, i) = item;
00486   return;
00487 
00488 } /* HeapHeapifyCompare */

static int HeapResize ( Heap_t * heap ) [static]

Function********************************************************************

Synopsis [Resizes a priority queue.]

Description [Resizes a priority queue by doubling the number of available slots. Returns 1 if successful; 0 otherwise.]

SideEffects [None]

SeeAlso [Heap_HeapInsert]

Definition at line 504 of file heap.c.

00506 {
00507   int oldlength = heap->length;
00508   int newlength = 2 * oldlength;
00509   HeapSlot_t *oldslots = heap->slots;
00510   HeapSlot_t *newslots = REALLOC(HeapSlot_t, oldslots, newlength);
00511   if (newslots == NIL(HeapSlot_t)) return 0;
00512   heap->length = newlength;
00513   heap->slots = newslots;
00514   if (heap->compare) {
00515     assert(Heap_HeapTestCompare(heap));
00516   }
00517   else {
00518     assert(Heap_HeapTest(heap));
00519   }
00520   return 1;
00521 
00522 } /* HeapResize */

Variable Documentation

char rcsid [] UNUSED = "$Id: heap.c,v 1.18 2005/05/18 19:25:43 jinh Exp $" [static]

CFile***********************************************************************

FileName [heap.c]

PackageName [heap]

Synopsis [Heap-based priority queue.]

Description [This file contains the functions to maintain a priority queue implemented as a heap.]

SeeAlso []

Author [Fabio Somenzi]

Copyright [This file was created at the University of Colorado at Boulder. The University of Colorado at Boulder makes no warranty about the suitability of this software for any purpose. It is presented on an AS IS basis.]

Definition at line 46 of file heap.c.

src/heap/heap.c File Reference

Functions

Variables

Function Documentation

Variable Documentation