ghc/rts/QueueTemplate.h

   1
   2 /* -----------------------------------------------------------------------------
   3  * $Id: QueueTemplate.h,v 1.4 1999/04/27 10:07:19 sewardj Exp $
   4  *
   5  * (c) The GHC Team, 1998
   6  *
   7  * Template for generating queues of various types
   8  *
   9  * #define Queue and Type before #including this file
  10  * to define the following:
  11  *
  12  *   typedef { Type* elems; nat used; nat size } Queue;
  13  *   static void insertQueue( Queue* q, Type i );
  14  *   static void initQueue  ( Queue* q );
  15  *   static void setQueue   ( Queue* q, nat i, Type x );
  16  *   static void freeQueue  ( Queue* q );
  17  *
  18  * $RCSfile: QueueTemplate.h,v $
  19  * $Revision: 1.4 $
  20  * $Date: 1999/04/27 10:07:19 $
  21  *
  22  * ------------------------------------------------------------------------*/
  23
  24 /* These macros are rather delicate - read a good ANSI C book carefully
  25  * before meddling.
  26  */
  27 #define mystr(x)      #x
  28 #define mycat(x,y)    x##y
  29 #define mycat2(x,y)   mycat(x,y)
  30 #define mycat3(x,y,z) mycat2(x,mycat2(y,z))
  31
  32
  33 typedef struct {
  34     Type*  elems;
  35     nat    len;   /* always <= size */
  36     nat    size;
  37 } Queue;
  38
  39
  40 static void mycat2(init,Queue)( Queue* q )
  41 {
  42    q->len   = 0;
  43    q->size  = 8;
  44    q->elems = malloc(q->size * sizeof(Type));
  45    if (q->elems == NULL) {
  46       barf("Out of memory: can't allocate initial " mystr(Queue) " space");
  47    }
  48 }
  49
  50
  51 static void mycat2(free,Queue)( Queue* q )
  52 {
  53    free(q->elems);
  54    q->elems = NULL;
  55 }
  56
  57
  58 static void mycat2(insert,Queue)( Queue* q, Type x )
  59 {
  60    nat i;
  61    if (q->len == q->size) {
  62       Type* elems2 = malloc(2 * q->size * sizeof(Type));
  63       if (elems2 == NULL) {
  64          barf("Out of memory: can't resize " mystr(Queue) " space");
  65       }
  66       for (i = 0; i < q->len; i++)
  67          elems2[i] = q->elems[i];
  68       free(q->elems);
  69       q->elems = elems2;
  70       q->size *= 2;
  71    }
  72    q->elems[q->len] = x;
  73    q->len++;
  74 }
  75
  76
  77 void mycat2(set,Queue)( Queue* q, nat i, Type x )
  78 {
  79     ASSERT(i < q->len);
  80     q->elems[i] = x;
  81 }
  82
  83
  84
  85 /* evaluate a statement s once for every element in a queue q.
  86  * i and x are usually free in s
  87  * queueTy and eltTy are the types of the container and element respectively
  88  */
  89 #define mapQueue(queueTy,eltTy,q,s)     \
  90 do {                                    \
  91     nat i = 0;                          \
  92     eltTy x;                            \
  93     while( i < (q).len ) {              \
  94         x = q.elems[i];                 \
  95         s;                              \
  96         ++i;                            \
  97     }                                   \
  98 } while (0)
  99
 100 /* --------------------------------------------------------------------------
 101  * End of Queue template
 102  * ------------------------------------------------------------------------*/