Woolz Image Processing  Version 1.8.3
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

AlcCPQQueueAlcCPQQueueNew (AlcErrno *dstErr)
 Creates a new priority queue. More...
 
AlcCPQItemAlcCPQItemNew (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...
 
AlcCPQItemAlcCPQItemUnlink (AlcCPQQueue *q)
 Unlinks and returns the item with the highest priority from the given priority queue. More...
 

Detailed Description

Function Documentation

◆ AlcCPQQueueNew()

◆ AlcCPQItemNew()

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

Creates a new priority queue item.

Returns
New priority queue item.
Parameters
qGiven queue.
priorityPriority for the item.
entryEntry for the item.
dstErrDestination error pointer may be NULL.

References ALC_ER_NONE, ALC_ER_PARAM, and _AlcCPQQueue::freeItem.

Referenced by AlcCPQEntryInsert().

◆ AlcCPQQueueFree()

AlcErrno AlcCPQQueueFree ( AlcCPQQueue q)

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

Returns
Alc error code.
Parameters
qGiven queue to free.

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

Referenced by AlcCPQQueueNew().

◆ AlcCPQItemFree()

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
qThe queue.
itemGiven item to free.

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

◆ AlcCPQEntryInsert()

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
qThe queue.
priorityPriority of entry.
entryGiven entry.

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

◆ AlcCPQItemInsert()

AlcErrno AlcCPQItemInsert ( AlcCPQQueue q,
AlcCPQItem item 
)

Inserts an item into the priority queue.

Returns
Alc error code.
Parameters
qThe queue.
itemGiven item to insert.

References ALC_ER_NONE, _AlcCPQQueue::nItem, _AlcCPQQueue::nItemIncThr, _AlcCPQItem::priority, and _AlcCPQQueue::resizable.

Referenced by AlcCPQEntryInsert().

◆ AlcCPQItemUnlink()

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
qGiven queue.

References _AlcCPQQueue::bucketBase, _AlcCPQQueue::bucketMin, _AlcCPQQueue::buckets, _AlcCPQQueue::bucketWidth, _AlcCPQQueue::lastIdx, _AlcCPQQueue::nBucket, _AlcCPQQueue::nItem, and _AlcCPQItem::priority.