ghc/rts/QueueTemplate.h

   1 /* -*- mode: hugs-c; -*- */
   2 /* -----------------------------------------------------------------------------
   3  * $Id: QueueTemplate.h,v 1.3 1999/02/05 16:02:48 simonm Exp $
   4  *
   5  * (c) The GHC Team, 1998
   6  *
   7  * Template for generating queues of various types
   8  *
   9  * #define Queue##ChunkSize, Queue and Type before #including this file
  10  * to define the following:
  11  *
  12  *   typedef { ...; nat len } 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  *
  17  * Copyright (c) 1994-1998.
  18  *
  19  * $RCSfile: QueueTemplate.h,v $
  20  * $Revision: 1.3 $
  21  * $Date: 1999/02/05 16:02:48 $
  22  *
  23  * ------------------------------------------------------------------------*/
  24
  25 /* These macros are rather delicate - read a good ANSI C book carefully
  26  * before meddling.
  27  */
  28 #define mystr(x)      #x
  29 #define mycat(x,y)    x##y
  30 #define mycat2(x,y)   mycat(x,y)
  31 #define mycat3(x,y,z) mycat2(x,mycat2(y,z))
  32
  33 typedef struct mycat3(_,Queue,Chunk) {
  34     struct mycat3(_,Queue,Chunk)* next;
  35     Type                    xs[mycat2(Queue,ChunkSize)];
  36 } mycat2(Queue,Chunk);
  37
  38 static mycat2(Queue,Chunk)* mycat3(alloc,Queue,Chunk)( void )
  39 {
  40     mycat2(Queue,Chunk)* new = malloc(sizeof(mycat2(Queue,Chunk)));
  41     if (new == NULL) {
  42         barf("Can't allomycate " mystr(Queue) "Chunk");
  43     }
  44     new->next = NULL;
  45     return new;
  46 }
  47
  48 typedef struct {
  49     mycat2(Queue,Chunk)*  head;
  50     mycat2(Queue,Chunk)*  tail;
  51     nat    len;          /* position of next free instruction */
  52 } Queue;
  53
  54 static void mycat2(insert,Queue)( Queue* q, Type i )
  55 {
  56     if (q->len == 0) {
  57         mycat2(Queue,Chunk)* new = mycat3(alloc,Queue,Chunk)();
  58         new->next = NULL;
  59         q->head = new;
  60         q->tail = new;
  61     } else if (q->len % mycat2(Queue,ChunkSize) == 0) {
  62         mycat2(Queue,Chunk)* new = mycat3(alloc,Queue,Chunk)();
  63         new->next = NULL;
  64         q->tail->next = new;
  65         q->tail = new;
  66     }
  67     q->tail->xs[q->len % mycat2(Queue,ChunkSize)] = i;
  68     q->len++;
  69 }
  70
  71 static inline void mycat2(init,Queue)( Queue* q )
  72 {
  73    q->head = q->tail = NULL;
  74    q->len = 0;
  75 }
  76
  77 static void mycat2(set,Queue)( Queue* q, nat i, Type x )
  78 {
  79     mycat2(Queue,Chunk)* chunk = q->head;
  80     ASSERT(i <= q->len);
  81     /* ToDo: optimise case where i is in the last chunk in the list */
  82     for(; i >= mycat2(Queue,ChunkSize); i -= mycat2(Queue,ChunkSize)) {
  83         ASSERT(chunk);
  84         chunk = chunk->next;
  85     }
  86     ASSERT(chunk);
  87     chunk->xs[i] = x;
  88 }
  89
  90 /* evaluate a statement s once for every element in a queue q.
  91  * i and x are usually free in s
  92  * queueTy and eltTy are the types of the container and element respectively
  93  */
  94 #define mapQueue(queueTy,eltTy,q,s)                         \
  95 do {                                                        \
  96     mycat2(queueTy,Chunk)* chunk = (q).head;                \
  97     nat i = 0;                                              \
  98     eltTy x;                                                \
  99     while( i < (q).len ) {                                  \
 100         ASSERT(chunk);                                      \
 101         x = chunk->xs[i % mycat2(queueTy,ChunkSize)];       \
 102         s;                                                  \
 103         ++i;                                                \
 104         if (i % mycat2(queueTy,ChunkSize) == 0) {           \
 105             chunk = chunk->next;                            \
 106         }                                                   \
 107     }                                                       \
 108 } while (0)
 109
 110 /* --------------------------------------------------------------------------
 111  * End of Queue template
 112  * ------------------------------------------------------------------------*/