AlcHeap

Files
file	AlcHeap.c
	A basic heap data structure which uses an array.

Data Structures
struct	_AlcHeapEntryCore
	Core heap entry data structure. All other heap entry data structures must have the fields of this data structure first. Typedef: AlcHeapEntryCore. More...
struct	_AlcHeap
	A general purpose heap data structure. Typedef: AlcHeap. More...

Functions
AlcHeap *	AlcHeapNew (int entSz, int entInc, void *data)
	Constructs a new heap data structure. More...
void	AlcHeapFree (AlcHeap *heap)
	Frees the given heap data structure along with it's entries. More...
void	AlcHeapEntFree (AlcHeap *heap)
	Frees the entry at the top of the heap. More...
void	AlcHeapAllEntFree (AlcHeap *heap, int reallyFree)
	Frees all the heap entries. More...
AlcErrno	AlcHeapInsertEnt (AlcHeap *heap, void *ent)
	Inserts the given entry into the queue. More...
void *	AlcHeapTop (AlcHeap *heap)
	Gets the top heap entry. More...

Detailed Description

Function Documentation

AlcHeap* AlcHeapNew	(	int	entSz,
		int	entInc,
		void *	data
	)

Constructs a new heap data structure.

Returns

New heap data structure, NULL on error.

            The following example code illustrates the use of the
            heap data structures and functions, although (for clarity
            and succinctness) without any error checking.

  typedef struct _AlcHeapEntryTest
  {
    double    priority;
    int       index; 
  } AlcHeapEntryTest;

  int             main(int argc, char *argv[])
  {
    int           idN,
                  size = 10;
    AlcHeap       *heap = NULL;
    double        *randoms = NULL;
    AlcHeapEntryTest ent;
    AlcHeapEntryTest *entP;
    AlcErrno      alcErr = ALC_ER_NONE;

    randoms = (double *)AlcMalloc(sizeof(double) * size);
    srand(0);
    for(idN = 0; idN < size; ++idN)
    {
      randoms[idN] = (double)rand() / (double )(RAND_MAX);
    }
    heap = AlcHeapNew(sizeof(AlcHeapEntryTest), (size + 1) / 2, NULL);
    for(idN = 0; idN < size; ++idN)
    {
      ent.priority = randoms[idN];
      ent.index = idN;
      AlcHeapInsertEnt(heap, &ent);
    }
    for(idN = 0; idN < size; ++idN)
    {
      entP = AlcHeapTop(heap);
      (void )printf("% 8d % 8d %1.12lf\n", idN, entP->index, entP->priority);
      AlcHeapEntFree(heap);
    }
    AlcHeapFree(heap);
    AlcFree(randoms);
  }

  entSz                   Size of the heap entries.
  entInc                  Number of entries to allocate at once
                          or zero for the default (1024).
          data                    Application specific data which
                                  is ignored by heap functions,
                                  may be NULL.

References AlcCalloc(), _AlcFreeStack::data, _AlcHeap::data, _AlcHeap::entInc, and _AlcHeap::entSz.

Referenced by AlcHeapTop(), WlzCMeshFMarNodes2D(), WlzCMeshFMarNodes3D(), and WlzThinToPoints().

void AlcHeapFree

(

AlcHeap *

heap

)

Frees the given heap data structure along with it's entries.

Parameters

heap	The heap to free.

References AlcFree(), and _AlcHeap::entries.

Referenced by AlcHeapTop(), WlzCMeshFMarNodes2D(), WlzCMeshFMarNodes3D(), and WlzThinToPoints().

void AlcHeapEntFree

(

AlcHeap *

heap

)

Frees the entry at the top of the heap.

Parameters

heap

The heap.

References _AlcHeap::nEnt, and _AlcHeap::topPriLo.

Referenced by AlcHeapTop(), WlzCMeshFMarNodes2D(), WlzCMeshFMarNodes3D(), and WlzThinToPoints().

void AlcHeapAllEntFree	(	AlcHeap *	heap,
		int	reallyFree
	)

Frees all the heap entries.

Parameters

heap	The heap.
reallyFree	If non zero the entries are really freed rather than just marked free and available for reuse.

References AlcFree(), _AlcHeap::entries, and _AlcHeap::nEnt.

Referenced by WlzCMeshFMarNodes2D(), and WlzCMeshFMarNodes3D().

AlcErrno AlcHeapInsertEnt	(	AlcHeap *	heap,
		void *	ent
	)

Inserts the given entry into the queue.

Returns

Error code.

Parameters

heap	Given heap data structure.
ent	Entry to insert.

References ALC_ER_ALLOC, ALC_ER_NONE, AlcRealloc(), _AlcHeap::entInc, _AlcHeap::entries, _AlcHeap::entSz, _AlcHeap::maxEnt, _AlcHeap::nEnt, and _AlcHeap::topPriLo.

Referenced by AlcHeapTop(), WlzCMeshFMarNodes3D(), and WlzThinToPoints().

void* AlcHeapTop

(

AlcHeap *

heap

)

Gets the top heap entry.

Returns

The entry at the top of the heap.

Parameters

heap	Given heap.

References ALC_ER_NONE, AlcFree(), AlcHeapEntFree(), AlcHeapFree(), AlcHeapInsertEnt(), AlcHeapNew(), AlcMalloc(), AlgRandSeed(), AlgRandUniform(), _AlcHeap::entries, _AlcHeap::entSz, getopt(), main(), _AlcHeap::maxEnt, _AlcHeap::nEnt, optarg, opterr, optind, and optopt.

Referenced by WlzCMeshFMarNodes2D(), WlzCMeshFMarNodes3D(), and WlzThinToPoints().