537f6cc3d8f4f97a466420abb6ba5f1f30f776fc
[charm.git] / src / conv-core / queueing.c
1 /***************************************************************************
2  * RCS INFORMATION:
3  *
4  *      $RCSfile$
5  *      $Author$        $Locker$                $State$
6  *      $Revision$      $Date$
7  *
8  ***************************************************************************
9  * DESCRIPTION:
10  *
11  * Known bug: a prio of value zero is never recognized as such.
12  * It goes in with priority slightly larger than zero.
13  *
14  * Known bug: the function CqsGetSecondPriority returns incorrect results.
15  *
16  ***************************************************************************
17  * REVISION HISTORY:
18  *
19  * $Log$
20  * Revision 1.5  1997-10-29 23:53:08  milind
21  * Fixed CthInitialize bug on uth machines.
22  *
23  * Revision 1.4  1996/04/24 22:44:16  jyelon
24  * *** empty log message ***
25  *
26  * Revision 1.3  1995/10/12 18:14:52  jyelon
27  * removed obsolete test program.
28  *
29  * Revision 1.2  1995/07/24  01:56:42  jyelon
30  * *** empty log message ***
31  *
32  * Revision 1.1  1995/07/18  19:31:34  jyelon
33  * Initial revision
34  *
35  * Revision 1.3  1995/07/12  16:29:22  jyelon
36  * *** empty log message ***
37  *
38  * Revision 1.2  1995/07/11  18:36:48  jyelon
39  * *** empty log message ***
40  *
41  * Revision 1.1  1995/07/11  18:12:11  jyelon
42  * Initial revision
43  *
44  *
45  ***************************************************************************/
46 static char ident[] = "@(#)$Header$";
47
48 #include <converse.h>
49 #define INTBITS ((unsigned int) (sizeof(int)*8))
50
51 typedef struct prio
52 {
53   unsigned short bits;
54   unsigned short ints;
55   unsigned int data[1];
56 }
57 *prio;
58
59 typedef struct deq
60 {
61   /* Note: if head==tail, circ is empty */
62   void **bgn; /* Pointer to first slot in circular buffer */
63   void **end; /* Pointer past last slot in circular buffer */
64   void **head; /* Pointer to first used slot in circular buffer */
65   void **tail; /* Pointer to next available slot in circular buffer */
66   void *space[4]; /* Enough space for the first 4 entries */
67 }
68 *deq;
69
70 typedef struct prioqelt
71 {
72   struct deq data;
73   struct prioqelt *ht_next; /* Pointer to next bucket in hash table. */
74   struct prioqelt **ht_handle; /* Pointer to pointer that points to me (!) */
75   struct prio pri;
76 }
77 *prioqelt;
78
79 #define PRIOQ_TABSIZE 1017
80 typedef struct prioq
81 {
82   int heapsize;
83   int heapnext;
84   prioqelt *heap;
85   prioqelt hashtab[PRIOQ_TABSIZE];
86 }
87 *prioq;
88
89 typedef struct Queue
90 {
91   unsigned int length;
92   unsigned int maxlen;
93   struct deq zeroprio;
94   struct prioq negprioq;
95   struct prioq posprioq;
96 }
97 *Queue;
98
99 void CqsDeqInit(d)
100 deq d;
101 {
102   d->bgn  = d->space;
103   d->end  = d->space+4;
104   d->head = d->space;
105   d->tail = d->space;
106 }
107
108 void CqsDeqExpand(d)
109 deq d;
110 {
111   int rsize = (d->end - d->head);
112   int lsize = (d->head - d->bgn);
113   int oldsize = (d->end - d->bgn);
114   int newsize = (oldsize << 1);
115   void **ovec = d->bgn;
116   void **nvec = (void **)CmiAlloc(newsize * sizeof(void *));
117   memcpy(nvec, d->head, rsize * sizeof(void *));
118   memcpy(nvec+rsize, d->bgn, lsize * sizeof(void *));
119   d->bgn = nvec;
120   d->end = nvec + newsize;
121   d->head = nvec;
122   d->tail = nvec + oldsize;
123   if (ovec != d->space) CmiFree(ovec);
124 }
125
126 void CqsDeqEnqueueFifo(d, data)
127 deq d; void *data;
128 {
129   void **tail = d->tail;
130   *tail = data;
131   tail++;
132   if (tail == d->end) tail = d->bgn;
133   d->tail = tail;
134   if (tail == d->head) CqsDeqExpand(d);
135 }
136
137 void CqsDeqEnqueueLifo(d, data)
138 deq d; void *data;
139 {
140   void **head = d->head;
141   if (head == d->bgn) head = d->end;
142   head--;
143   *head = data;
144   d->head = head;
145   if (head == d->tail) CqsDeqExpand(d);
146 }
147
148 void *CqsDeqDequeue(d)
149 deq d;
150 {
151   void **head;
152   void **tail;
153   void *data;
154   head = d->head;
155   tail = d->tail;
156   if (head == tail) return 0;
157   data = *head;
158   head++;
159   if (head == d->end) head = d->bgn;
160   d->head = head;
161   return data;
162 }
163
164 void CqsPrioqInit(pq)
165 prioq pq;
166 {
167   int i;
168   pq->heapsize = 100;
169   pq->heapnext = 1;
170   pq->heap = (prioqelt *)CmiAlloc(100 * sizeof(prioqelt));
171   for (i=0; i<PRIOQ_TABSIZE; i++) pq->hashtab[i]=0;
172 }
173
174 void CqsPrioqExpand(pq)
175 prioq pq;
176 {
177   int oldsize = pq->heapsize;
178   int newsize = oldsize * 2;
179   prioqelt *oheap = pq->heap;
180   prioqelt *nheap = (prioqelt *)CmiAlloc(newsize*sizeof(prioqelt));
181   memcpy(nheap, oheap, oldsize * sizeof(prioqelt));
182   pq->heap = nheap;
183   pq->heapsize = newsize;
184   CmiFree(oheap);
185 }
186
187 /*
188  * This routine compares priorities. It returns:
189  *
190  * 1 if prio1 > prio2
191  * ? if prio1 == prio2
192  * 0 if prio1 < prio2
193  *
194  */
195
196 int CqsPrioGT(prio1, prio2)
197 prio prio1;
198 prio prio2;
199 {
200   unsigned int ints1 = prio1->ints;
201   unsigned int ints2 = prio2->ints;
202   unsigned int *data1 = prio1->data;
203   unsigned int *data2 = prio2->data;
204   unsigned int val1;
205   unsigned int val2;
206   while (1) {
207     if (ints1==0) return 0;
208     if (ints2==0) return 1;
209     val1 = *data1++;
210     val2 = *data2++;
211     if (val1 < val2) return 0;
212     if (val1 > val2) return 1;
213     ints1--;
214     ints2--;
215   }
216 }
217
218 deq CqsPrioqGetDeq(pq, priobits, priodata)
219 prioq pq;
220 unsigned int priobits, *priodata;
221 {
222   unsigned int prioints = (priobits+INTBITS-1)/INTBITS;
223   unsigned int hashval;
224   int heappos, i, j; 
225   prioqelt *heap, pe, next;
226   prio pri;
227
228   /* Scan for priority in hash-table, and return it if present */
229   hashval = priobits;
230   for (i=0; i<prioints; i++) hashval ^= priodata[i];
231   hashval = (hashval&0x7FFFFFFF)%PRIOQ_TABSIZE;
232   for (pe=pq->hashtab[hashval]; pe; pe=pe->ht_next)
233     if (priobits == pe->pri.bits)
234       if (memcmp(priodata, pe->pri.data, sizeof(int)*prioints)==0)
235         return &(pe->data);
236   
237   /* If not present, allocate a bucket for specified priority */
238   pe = (prioqelt)CmiAlloc(sizeof(struct prioqelt)+((prioints-1)*sizeof(int)));
239   pe->pri.bits = priobits;
240   pe->pri.ints = prioints;
241   memcpy(pe->pri.data, priodata, (prioints*sizeof(int)));
242   CqsDeqInit(&(pe->data));
243   pri=&(pe->pri);
244
245   /* Insert bucket into hash-table */
246   next = pq->hashtab[hashval];
247   pe->ht_next = next;
248   pe->ht_handle = (pq->hashtab+hashval);
249   if (next) next->ht_handle = &(pe->ht_next);
250   pq->hashtab[hashval] = pe;
251   
252   /* Insert bucket into heap */
253   heappos = pq->heapnext++;
254   if (heappos == pq->heapsize) CqsPrioqExpand(pq);
255   heap = pq->heap;
256   while (heappos > 1) {
257     int parentpos = (heappos >> 1);
258     prioqelt parent = heap[parentpos];
259     if (CqsPrioGT(pri, &(parent->pri))) break;
260     heap[heappos] = parent; heappos=parentpos;
261   }
262   heap[heappos] = pe;
263   
264   return &(pe->data);
265 }
266
267 void *CqsPrioqDequeue(pq)
268 prioq pq;
269 {
270   prio pri;
271   prioqelt pe, old; void *data;
272   int heappos, heapnext;
273   prioqelt *heap = pq->heap;
274
275   if (pq->heapnext==1) return 0;
276   pe = heap[1];
277   data = CqsDeqDequeue(&(pe->data));
278   if (pe->data.head == pe->data.tail) {
279     /* Unlink prio-bucket from hash-table */
280     prioqelt next = pe->ht_next;
281     prioqelt *handle = pe->ht_handle;
282     if (next) next->ht_handle = handle;
283     *handle = next;
284     old=pe;
285     
286     /* Restore the heap */
287     heapnext = (--pq->heapnext);
288     pe = heap[heapnext];
289     pri = &(pe->pri);
290     heappos = 1;
291     while (1) {
292       int childpos1, childpos2, childpos;
293       prioqelt ch1, ch2, child;
294       childpos1 = heappos<<1;
295       if (childpos1>=heapnext) break;
296       childpos2 = childpos1+1;
297       if (childpos2>=heapnext)
298         { childpos=childpos1; child=heap[childpos1]; }
299       else {
300         ch1 = heap[childpos1];
301         ch2 = heap[childpos2];
302         if (CqsPrioGT(&(ch1->pri), &(ch2->pri)))
303              {childpos=childpos2; child=ch2;}
304         else {childpos=childpos1; child=ch1;}
305       }
306       if (CqsPrioGT(&(child->pri), pri)) break;
307       heap[heappos]=child; heappos=childpos;
308     }
309     heap[heappos]=pe;
310     
311     /* Free prio-bucket */
312     if (old->data.bgn != old->data.space) CmiFree(old->data.bgn);
313     CmiFree(old);
314   }
315   return data;
316 }
317
318 Queue CqsCreate()
319 {
320   Queue q = (Queue)CmiAlloc(sizeof(struct Queue));
321   q->length = 0;
322   q->maxlen = 0;
323   CqsDeqInit(&(q->zeroprio));
324   CqsPrioqInit(&(q->negprioq));
325   CqsPrioqInit(&(q->posprioq));
326   return q;
327 }
328
329 unsigned int CqsLength(q)
330 Queue q;
331 {
332   return q->length;
333 }
334
335 unsigned int CqsMaxLength(q)
336 Queue q;
337 {
338   return q->maxlen;
339 }
340
341 int CqsEmpty(q)
342 Queue q;
343 {
344   return (q->length == 0);
345 }
346
347 void CqsEnqueueGeneral(q, data, strategy, priobits, prioptr)
348 Queue q; void *data; unsigned int strategy, priobits, *prioptr;
349 {
350   deq d; int iprio;
351   switch (strategy) {
352   case CQS_QUEUEING_FIFO: 
353     CqsDeqEnqueueFifo(&(q->zeroprio), data); 
354     break;
355   case CQS_QUEUEING_LIFO: 
356     CqsDeqEnqueueLifo(&(q->zeroprio), data); 
357     break;
358   case CQS_QUEUEING_IFIFO:
359     iprio=prioptr[0]+(1<<(INTBITS-1));
360     if ((int)iprio<0)
361       d=CqsPrioqGetDeq(&(q->posprioq), INTBITS, &iprio);
362     else d=CqsPrioqGetDeq(&(q->negprioq), INTBITS, &iprio);
363     CqsDeqEnqueueFifo(d, data);
364     break;
365   case CQS_QUEUEING_ILIFO:
366     iprio=prioptr[0]+(1<<(INTBITS-1));
367     if ((int)iprio<0)
368       d=CqsPrioqGetDeq(&(q->posprioq), INTBITS, &iprio);
369     else d=CqsPrioqGetDeq(&(q->negprioq), INTBITS, &iprio);
370     CqsDeqEnqueueLifo(d, data);
371     break;
372   case CQS_QUEUEING_BFIFO:
373     if (priobits&&(((int)(prioptr[1]))<0))
374        d=CqsPrioqGetDeq(&(q->posprioq), priobits, prioptr);
375     else d=CqsPrioqGetDeq(&(q->negprioq), priobits, prioptr);
376     CqsDeqEnqueueFifo(d, data);
377     break;
378   case CQS_QUEUEING_BLIFO:
379     if (priobits&&(((int)(prioptr[1]))<0))
380        d=CqsPrioqGetDeq(&(q->posprioq), priobits, prioptr);
381     else d=CqsPrioqGetDeq(&(q->negprioq), priobits, prioptr);
382     CqsDeqEnqueueLifo(d, data);
383     break;
384   default:
385     CmiError("CqsEnqueueGeneral: invalid queueing strategy.\n");
386     exit(1);
387   }
388   q->length++; if (q->length>q->maxlen) q->maxlen=q->length;
389 }
390
391 void CqsEnqueueFifo(q, data)
392 Queue q; void *data;
393 {
394   CqsDeqEnqueueFifo(&(q->zeroprio), data);
395   q->length++; if (q->length>q->maxlen) q->maxlen=q->length;
396 }
397
398 void CqsEnqueueLifo(q, data)
399 Queue q; void *data;
400 {
401   CqsDeqEnqueueLifo(&(q->zeroprio), data);
402   q->length++; if (q->length>q->maxlen) q->maxlen=q->length;
403 }
404
405 void CqsEnqueue(q, data)
406 Queue q; void *data;
407 {
408   CqsDeqEnqueueFifo(&(q->zeroprio), data);
409   q->length++; if (q->length>q->maxlen) q->maxlen=q->length;
410 }
411
412 void CqsDequeue(q, resp)
413 Queue q;
414 void **resp;
415 {
416   if (q->negprioq.heapnext>1)
417     { *resp = CqsPrioqDequeue(&(q->negprioq)); q->length--; return; }
418   if (q->zeroprio.head != q->zeroprio.tail)
419     { *resp = CqsDeqDequeue(&(q->zeroprio)); q->length--; return; }
420   if (q->posprioq.heapnext>1)
421     { *resp = CqsPrioqDequeue(&(q->posprioq)); q->length--; return; }
422   *resp = 0; return;
423 }
424
425 static struct prio kprio_zero = { 0, 0, {0} };
426 static struct prio kprio_max  = { 32, 1, {((unsigned int)(-1))} };
427
428 prio CqsGetPriority(q)
429 Queue q;
430 {
431   if (q->negprioq.heapnext>1) return &(q->negprioq.heap[1]->pri);
432   if (q->zeroprio.head != q->zeroprio.tail) { return &kprio_zero; }
433   if (q->posprioq.heapnext>1) return &(q->posprioq.heap[1]->pri);
434   return &kprio_max;
435 }
436
437 prio CqsGetSecondPriority(q)
438 Queue q;
439 {
440   return CqsGetPriority(q);
441 }
442