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