Prioritized Queue: Major Cleanup
authorPhil Miller <mille121@illinois.edu>
Tue, 29 Sep 2009 22:12:57 +0000 (22:12 +0000)
committerPhil Miller <mille121@illinois.edu>
Tue, 29 Sep 2009 22:12:57 +0000 (22:12 +0000)
- Remove several functions not used outside the implementation from
  the interface header.
- Move comments on function interfaces from implementation to header.
- Stop using archaic style function argument type declarations.
- Reflow comments and remove excess whitespace.

src/conv-core/queueing.c
src/conv-core/queueing.h
tests/charm++/queue/pgm.C

index 656698c266504cddc097056c90a8868a1c82cfff..c4dd609bae493f3a033ef79962914fce67a4fccd 100644 (file)
@@ -20,8 +20,8 @@
     negative priorities. The positive and negative priorty queues are actually heaps.
 
 
-    The charm++ messages are only scheduled after the \ref ConverseScheduler "converse message queues"
-    have been emptied:
+    The charm++ messages are only scheduled after the \ref
+    ConverseScheduler "converse message queues" have been emptied:
 
     - CsdScheduleForever() is the commonly used Converse scheduler loop
        - CsdNextMessage()
@@ -43,8 +43,7 @@ int schedAdaptMemThresholdMB;
 
 
 /** Initialize a deq */
-static void CqsDeqInit(d)
-deq d;
+static void CqsDeqInit(deq d)
 {
   d->bgn  = d->space;
   d->end  = d->space+4;
@@ -53,8 +52,7 @@ deq d;
 }
 
 /** Double the size of a deq */
-static void CqsDeqExpand(d)
-deq d;
+static void CqsDeqExpand(deq d)
 {
   int rsize = (d->end - d->head);
   int lsize = (d->head - d->bgn);
@@ -72,8 +70,7 @@ deq d;
 }
 
 /** Insert a data pointer at the tail of a deq */
-void CqsDeqEnqueueFifo(d, data)
-deq d; void *data;
+void CqsDeqEnqueueFifo(deq d, void *data)
 {
   void **tail = d->tail;
   *tail = data;
@@ -84,8 +81,7 @@ deq d; void *data;
 }
 
 /** Insert a data pointer at the head of a deq */
-void CqsDeqEnqueueLifo(d, data)
-deq d; void *data;
+void CqsDeqEnqueueLifo(deq d, void *data)
 {
   void **head = d->head;
   if (head == d->bgn) head = d->end;
@@ -96,8 +92,7 @@ deq d; void *data;
 }
 
 /** Remove a data pointer from the head of a deq */
-void *CqsDeqDequeue(d)
-deq d;
+void *CqsDeqDequeue(deq d)
 {
   void **head;
   void **tail;
@@ -113,8 +108,7 @@ deq d;
 }
 
 /** Initialize a Priority Queue */
-static void CqsPrioqInit(pq)
-prioq pq;
+static void CqsPrioqInit(prioq pq)
 {
   int i;
   pq->heapsize = 100;
@@ -340,8 +334,7 @@ deq CqsPrioqGetDeq(prioq pq, unsigned int priobits, unsigned int *priodata)
 }
 
 /** Dequeue an entry */
-void *CqsPrioqDequeue(pq)
-prioq pq;
+void *CqsPrioqDequeue(prioq pq)
 {
   prio pri;
   prioqelt pe, old; void *data;
@@ -537,7 +530,6 @@ prioq pq;
   return data;
 }
 
-/** Initialize a Queue and its three internal queues (for positive, negative, and zero priorities) */
 Queue CqsCreate(void)
 {
   Queue q = (Queue)CmiAlloc(sizeof(struct Queue_struct));
@@ -552,7 +544,6 @@ Queue CqsCreate(void)
   return q;
 }
 
-/** Delete a Queue */
 void CqsDelete(Queue q)
 {
   CmiFree(q->negprioq.heap);
@@ -575,10 +566,6 @@ int CqsEmpty(Queue q)
   return (q->length == 0);
 }
 
-
-/** Enqueue something (usually an envelope*) into the queue in 
-    a manner consistent with the specified strategy and priority.
-*/
 void CqsEnqueueGeneral(Queue q, void *data, int strategy, 
            int priobits,unsigned int *prioptr)
 {
@@ -673,7 +660,6 @@ void CqsEnqueue(Queue q, void *data)
   q->length++; if (q->length>q->maxlen) q->maxlen=q->length;
 }
 
-/** Retrieve the highest priority message (one with most negative priority) */
 void CqsDequeue(Queue q, void **resp)
 {
 #ifdef ADAPT_SCHED_MEM
@@ -697,9 +683,8 @@ void CqsDequeue(Queue q, void **resp)
 
 static struct prio_struct kprio_zero = { 0, 0, {0} };
 static struct prio_struct kprio_max  = { 32, 1, {((unsigned int)(-1))} };
-/** Get the priority of the highest priority message in q */
-prio CqsGetPriority(q)
-Queue q;
+
+prio CqsGetPriority(Queue q)
 {
   if (q->negprioq.heapnext>1) return &(q->negprioq.heap[1]->pri);
   if (q->zeroprio.head != q->zeroprio.tail) { return &kprio_zero; }
@@ -795,12 +780,6 @@ void** CqsEnumeratePrioq(prioq q, int *num){
   return result;
 }
 
-/** Produce an array containing all the entries in a Queue
-    @return a newly allocated array filled with copies of the (void*) elements in the Queue. 
-    @param [in] q a Queue
-    @param [out] resp an array of pointer entries found in the Queue,
-    with as many entries as the Queue's length
-*/
 void CqsEnumerateQueue(Queue q, void ***resp){
   void **result;
   int num;
@@ -831,13 +810,14 @@ void CqsEnumerateQueue(Queue q, void ***resp){
   CmiFree(result);
 }
 
+/**
+   Remove first occurence of a specified entry from the deq  by
+   setting the entry to NULL.
 
+   The size of the deq will not change, it will now just contain an
+   entry for a NULL pointer.
 
-
-/** Remove first occurence of a specified entry from the deq  by setting the entry to NULL.
-    The size of the deq will not change, it will now just contain an entry for a NULL pointer.
-
-    @return number of entries that were replaced with NULL
+   @return number of entries that were replaced with NULL
 */
 int CqsRemoveSpecificDeq(deq q, const void *msgPtr){
   void **head, **tail;
@@ -858,12 +838,14 @@ int CqsRemoveSpecificDeq(deq q, const void *msgPtr){
   return 0;
 }
 
+/**
+   Remove first occurence of a specified entry from the prioq by
+   setting the entry to NULL.
 
+   The size of the prioq will not change, it will now just contain an
+   entry for a NULL pointer.
 
-/** Remove first occurence of a specified entry from the prioq by setting the entry to NULL.
-    The size of the prioq will not change, it will now just contain an entry for a NULL pointer.
-
-    @return number of entries that were replaced with NULL
+   @return number of entries that were replaced with NULL
 */
 int CqsRemoveSpecificPrioq(prioq q, const void *msgPtr){
   void **head, **tail;
@@ -889,11 +871,6 @@ int CqsRemoveSpecificPrioq(prioq q, const void *msgPtr){
   return 0;
 }
 
-
-
-/** Remove an occurence of a specified entry from the Queue by setting its entry to NULL. 
-    The size of the Queue will not change, it will now just contain an entry for a NULL pointer.
-*/
 void CqsRemoveSpecific(Queue q, const void *msgPtr){
   if( CqsRemoveSpecificPrioq(&(q->negprioq), msgPtr) == 0 )
     if( CqsRemoveSpecificDeq(&(q->zeroprio), msgPtr) == 0 )  
@@ -902,16 +879,9 @@ void CqsRemoveSpecific(Queue q, const void *msgPtr){
       }  
 }
 
-
 #ifdef ADAPT_SCHED_MEM
 int numMemCriticalEntries=0;
 int *memCriticalEntries=NULL;
 #endif
 
-
-
-
-
-
-
 /** @} */
index 49803f33401a358a661f9e4edbcdb05b3c114f9e..c8f745be03939cecc5b66d834499f1a5a311eb52 100644 (file)
@@ -44,7 +44,10 @@ typedef struct prio_struct
 }
 *prio;
 
-/** A double ended queue of void* pointers stored in a circular buffer, with internal space for 4 entries */
+/**
+   A double ended queue of void* pointers stored in a circular buffer,
+   with internal space for 4 entries
+*/
 typedef struct deq_struct
 {
   /* Note: if head==tail, circ is empty */
@@ -57,7 +60,11 @@ typedef struct deq_struct
 *deq;
 
 #ifndef FASTQ
-/** An bucket in a priority queue which contains a deque(storing the void* pointers) and references to other buckets in the hash table. */
+/**
+   A bucket in a priority queue which contains a deque(storing the
+   void* pointers) and references to other buckets in the hash
+   table.
+*/
 typedef struct prioqelt_struct
 {
   struct deq_struct data;
@@ -87,7 +94,11 @@ typedef struct prioqelt_struct
 /*#endif */
 
 /*#ifndef FASTQ*/
-/** A priority queue, implemented as a heap of prioqelt_struct buckets (each bucket represents a single priority value and contains a deque of void* pointers) */
+/**
+   A priority queue, implemented as a heap of prioqelt_struct buckets
+   (each bucket represents a single priority value and contains a
+   deque of void* pointers)
+*/
 typedef struct prioq_struct
 {
   int heapsize; 
@@ -111,8 +122,12 @@ typedef struct prioq1_struct
 */
 
 /*#ifndef FASTQ*/
-/** A set of 3 queues: a positive priority prioq_struct, a negative priority prioq_struct, and a zero priority deq_struct.
-    If the user modifies the queue, NULL entries may be present, and hence NULL values will be returned by CqsDequeue().
+/**
+   A set of 3 queues: a positive priority prioq_struct, a negative
+   priority prioq_struct, and a zero priority deq_struct.
+   
+   If the user modifies the queue, NULL entries may be present, and
+   hence NULL values will be returned by CqsDequeue().
 */
 typedef struct Queue_struct
 {
@@ -136,28 +151,63 @@ typedef struct Queue1_struct
 #endif
 */
 
+/**
+    Initialize a Queue and its three internal queues (for positive,
+    negative, and zero priorities)
+*/
 Queue CqsCreate(void);
+
+/** Delete a Queue */
 void CqsDelete(Queue);
+
+/** Enqueue with priority 0 */
 void CqsEnqueue(Queue, void *msg);
+
+/** Enqueue behind other elements of priority 0 */
 void CqsEnqueueFifo(Queue, void *msg);
+
+/** Enqueue ahead of other elements of priority 0 */
 void CqsEnqueueLifo(Queue, void *msg);
+
+/**
+    Enqueue something (usually an envelope*) into the queue in a
+    manner consistent with the specified strategy and priority.
+*/
 void CqsEnqueueGeneral(Queue, void *msg,int strategy, 
               int priobits, unsigned int *prioPtr);
 
+/**
+    Produce an array containing all the entries in a Queue
+    @return a newly allocated array filled with copies of the (void*)
+    elements in the Queue.
+    @param [in] q a Queue
+    @param [out] resp an array of pointer entries found in the Queue,
+    with as many entries as the Queue's length
+*/
 void CqsEnumerateQueue(Queue q, void ***resp);
+
+/**
+   Retrieve the highest priority message (one with most negative
+   priority)
+*/
 void CqsDequeue(Queue, void **msgPtr);
 
 unsigned int CqsLength(Queue);
-unsigned int CqsMaxLength(Queue);
 int CqsEmpty(Queue);
 int CqsPrioGT(prio, prio);
-prio CqsGetPriority(Queue);
 
-deq CqsPrioqGetDeq(prioq pq, unsigned int priobits, unsigned int *priodata);
-void *CqsPrioqDequeue(prioq pq);
-void CqsDeqEnqueueFifo(deq d, void *data);
+/** Get the priority of the highest priority message in q */
+prio CqsGetPriority(Queue);
 
 void CqsIncreasePriorityForEntryMethod(Queue q, const int entrymethod);
+
+/**
+    Remove an occurence of a specified entry from the Queue by setting
+    its entry to NULL.
+
+    The size of the Queue will not change, it will now just contain an
+    entry for a NULL pointer.
+*/
 void CqsRemoveSpecific(Queue, const void *msgPtr);
 
 #ifdef ADAPT_SCHED_MEM
index 3c0f1d1808cdc0e303711954774403fe7456ea23..be467801d533308fcb7460c5a506c2ffe0635f35 100644 (file)
@@ -24,7 +24,6 @@ bool test_empty()
 {
   Queue q = CqsCreate();
   bool result = (0 == CqsLength(q)) && (1 == CqsEmpty(q));
-  result &= CqsMaxLength(q) >= 0;
   CqsDelete(q);
   return result;
 }
@@ -40,7 +39,6 @@ bool test_one()
   CqsEnqueue(q, p);
   bool result = (1 == CqsLength(q)) && (0 == CqsEmpty(q));
   void *r;
-  result &= CqsMaxLength(q) >= 1;
   CqsDequeue(q, &r);
   result &= (r == p) 
     && (0 == CqsLength(q)) 
@@ -58,7 +56,6 @@ bool test_two()
   CqsEnqueue(q, i);
   CqsEnqueue(q, j);
   bool result = (2 == CqsLength(q));
-  result &= CqsMaxLength(q) >= 2;
   CqsDequeue(q, &r);
   CqsDequeue(q, &s);
   result &= (r == i && s == j) || (r == j && s == i);