ghc/rts/QueueTemplate.h

   1
   2 /* -----------------------------------------------------------------------------
   3  * $Id: QueueTemplate.h,v 1.6 2000/04/14 15:08:14 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.6 $
  20  * $Date: 2000/04/14 15:08:14 $
  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 #if MAKE_findIn
  41 static int mycat2(findIn,Queue)( Queue* q, Type x )
  42 {
  43    nat i;
  44    for (i = 0; i < q->len; i++)
  45       if (q->elems[i] == x) return i;
  46    return -1;
  47 }
  48 #endif
  49
  50 static void mycat2(init,Queue)( Queue* q )
  51 {
  52    q->len   = 0;
  53    q->size  = 8;
  54    q->elems = malloc(q->size * sizeof(Type));
  55    if (q->elems == NULL) {
  56       barf("Out of memory: can't allocate initial " mystr(Queue) " space");
  57    }
  58 }
  59
  60
  61 static void mycat2(free,Queue)( Queue* q )
  62 {
  63    free(q->elems);
  64    q->elems = NULL;
  65 }
  66
  67
  68 static void mycat2(insert,Queue)( Queue* q, Type x )
  69 {
  70    nat i;
  71    if (q->len == q->size) {
  72       Type* elems2 = malloc(2 * q->size * sizeof(Type));
  73       if (elems2 == NULL) {
  74          barf("Out of memory: can't resize " mystr(Queue) " space");
  75       }
  76       for (i = 0; i < q->len; i++)
  77          elems2[i] = q->elems[i];
  78       free(q->elems);
  79       q->elems = elems2;
  80       q->size *= 2;
  81    }
  82    q->elems[q->len] = x;
  83    q->len++;
  84 }
  85
  86
  87 static void mycat2(set,Queue)( Queue* q, nat i, Type x )
  88 {
  89     ASSERT(i < q->len);
  90     q->elems[i] = x;
  91 }
  92
  93
  94
  95 /* evaluate a statement s once for every element in a queue q.
  96  * i and x are usually free in s
  97  * queueTy and eltTy are the types of the container and element respectively
  98  */
  99 #define mapQueue(queueTy,eltTy,q,s)     \
 100 do {                                    \
 101     nat i = 0;                          \
 102     eltTy x;                            \
 103     while( i < (q).len ) {              \
 104         x = q.elems[i];                 \
 105         s;                              \
 106         ++i;                            \
 107     }                                   \
 108 } while (0)
 109
 110 /* --------------------------------------------------------------------------
 111  * End of Queue template
 112  * ------------------------------------------------------------------------*/