AlcCPQ

Files
file	AlcCPQueue.c
	An \(O(1)\) priority queue based on algorithms from: Brown R, 1988. Calendar Queues: A Fast {O}(1)Priority Queue Implementation for the Simulation Event Set Problem. Communications of the ACM 31(10), 1220-1227. The priority queue has an \(O(1)\) time for insertion unlinking and holding of queue items with a favorable constant when compared to tree based priority queue data structures such as splay trees. Results presented by Brown show that this data structure outperforms tree based implementations and that simple ordered linked lists with \(O(n)\) operations outperform both calendar queues and tree based queues when there are less than ten items in the queue.

Data Structures
struct	_AlcCPQQueue
	An \(O(1)\) priority queue based on the Calendar Priority Queue data structure. Typedef: AlcCPQQueue. More...
struct	_AlcCPQItem
	An item in a calendar priority queue. Typedef: AlcCPQItem. More...

Functions
AlcCPQQueue *	AlcCPQQueueNew (AlcErrno *dstErr)
	Creates a new priority queue. More...
AlcCPQItem *	AlcCPQItemNew (AlcCPQQueue *q, float priority, void *entry, AlcErrno *dstErr)
	Creates a new priority queue item. More...
AlcErrno	AlcCPQQueueFree (AlcCPQQueue *q)
	Frees a priority queue. Queue item entries are not freed. More...
void	AlcCPQItemFree (AlcCPQQueue *q, AlcCPQItem *item)
	Frees a priority queue item by putting it onto the freeItem list. The queue items entries are not freed. More...
AlcErrno	AlcCPQEntryInsert (AlcCPQQueue *q, float priority, void *entry)
	Inserts an entry into the priority queue. This function calls AlcCPQItemNew() followed by AlcCPQItemInsert(). More...
AlcErrno	AlcCPQItemInsert (AlcCPQQueue *q, AlcCPQItem *item)
	Inserts an item into the priority queue. More...
AlcCPQItem *	AlcCPQItemUnlink (AlcCPQQueue *q)
	Unlinks and returns the item with the highest priority from the given priority queue. More...

Detailed Description

Function Documentation

AlcCPQQueue* AlcCPQQueueNew

(

AlcErrno *

dstErr

)

Creates a new priority queue.

Returns

New priority queue.

Parameters

dstErr

Destination error pointer may be NULL.

References ALC_ER_ALLOC, ALC_ER_NONE, AlcCalloc(), AlcCPQQueueFree(), _AlcCPQQueue::bucketBase, _AlcCPQQueue::bucketMin, _AlcCPQQueue::buckets, _AlcCPQQueue::bucketWidth, _AlcCPQQueue::itemBlockSz, _AlcCPQQueue::lastIdx, _AlcCPQQueue::lastPriority, _AlcCPQQueue::maxBucket, _AlcCPQQueue::nBucket, _AlcCPQQueue::nItem, _AlcCPQQueue::nItemDecThr, _AlcCPQQueue::nItemIncThr, and _AlcCPQQueue::resizable.

Referenced by AlcCPQItemUnlink(), WlzLBTBalanceDomain2D(), WlzLBTBalanceDomain3D(), and WlzMatchICPCtr().

AlcCPQItem* AlcCPQItemNew	(	AlcCPQQueue *	q,
		float	priority,
		void *	entry,
		AlcErrno *	dstErr
	)

Creates a new priority queue item.

Returns

New priority queue item.

Parameters

q	Given queue.
priority	Priority for the item.
entry	Entry for the item.
dstErr	Destination error pointer may be NULL.

References ALC_ER_NONE, ALC_ER_PARAM, _AlcCPQItem::entry, _AlcCPQQueue::freeItem, _AlcCPQItem::next, _AlcCPQItem::prev, and _AlcCPQItem::priority.

Referenced by AlcCPQEntryInsert().

AlcErrno AlcCPQQueueFree

(

AlcCPQQueue *

q

)

Frees a priority queue. Queue item entries are not freed.

Returns

Alc error code.

Parameters

q	Given queue to free.

References ALC_ER_NONE, AlcBlockStackFree(), AlcFree(), _AlcCPQQueue::buckets, and _AlcCPQQueue::freeStack.

Referenced by AlcCPQItemUnlink(), AlcCPQQueueNew(), WlzLBTBalanceDomain2D(), and WlzLBTBalanceDomain3D().

void AlcCPQItemFree	(	AlcCPQQueue *	q,
		AlcCPQItem *	item
	)

Frees a priority queue item by putting it onto the freeItem list. The queue items entries are not freed.

Returns

Alc error code.

Parameters

q	The queue.
item	Given item to free.

References _AlcCPQQueue::freeItem, _AlcCPQItem::next, and _AlcCPQItem::prev.

Referenced by AlcCPQItemUnlink(), WlzLBTClassifyNodeFace3D(), and WlzMatchICPCtr().

AlcErrno AlcCPQEntryInsert	(	AlcCPQQueue *	q,
		float	priority,
		void *	entry
	)

Inserts an entry into the priority queue. This function calls AlcCPQItemNew() followed by AlcCPQItemInsert().

Returns

Alc error code.

Parameters

q	The queue.
priority	Priority of entry.
entry	Given entry.

References ALC_ER_NONE, AlcCPQItemInsert(), and AlcCPQItemNew().

Referenced by AlcCPQItemUnlink(), WlzLBTClassifyNodeFace3D(), and WlzMatchICPCtr().

AlcErrno AlcCPQItemInsert	(	AlcCPQQueue *	q,
		AlcCPQItem *	item
	)

Inserts an item into the priority queue.

Returns

Alc error code.

Parameters

q	The queue.
item	Given item to insert.

References ALC_ER_NONE, _AlcCPQQueue::bucketMin, _AlcCPQQueue::bucketWidth, _AlcCPQQueue::lastIdx, _AlcCPQQueue::lastPriority, _AlcCPQQueue::nBucket, _AlcCPQQueue::nItem, _AlcCPQQueue::nItemIncThr, _AlcCPQItem::priority, and _AlcCPQQueue::resizable.

Referenced by AlcCPQEntryInsert(), AlcCPQItemUnlink(), and WlzMatchICPCtr().

AlcCPQItem* AlcCPQItemUnlink

(

AlcCPQQueue *

q

)

Unlinks and returns the item with the highest priority from the given priority queue.

Returns

The highest priority item or NULL if the queue is empty.

Parameters

q	Given queue.

References ALC_ER_ALLOC, ALC_ER_NONE, AlcBlockStackNew(), AlcCPQEntryInsert(), AlcCPQItemFree(), AlcCPQItemInsert(), AlcCPQQueueFree(), AlcCPQQueueNew(), AlcMalloc(), AlcRealloc(), _AlcCPQQueue::bucketBase, _AlcCPQQueue::bucketMin, _AlcCPQQueue::buckets, _AlcCPQQueue::bucketWidth, _AlcBlockStack::elements, _AlcCPQQueue::freeItem, _AlcCPQQueue::freeStack, _AlcCPQQueue::itemBlockSz, _AlcCPQQueue::lastIdx, _AlcCPQQueue::lastPriority, main(), _AlcCPQQueue::maxBucket, _AlcBlockStack::maxElm, _AlcCPQQueue::nBucket, _AlcCPQItem::next, _AlcCPQQueue::nItem, _AlcCPQQueue::nItemDecThr, _AlcCPQQueue::nItemIncThr, _AlcCPQItem::prev, _AlcCPQItem::priority, and _AlcCPQQueue::resizable.

Referenced by WlzLBTClassifyNodeFace3D(), and WlzMatchICPCtr().