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