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