ghc/rts/QueueTemplate.h

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