[project @ 2000-01-13 14:33:57 by hwloidl]

[ghc-hetmet.git] / ghc / rts / QueueTemplate.h

diff --git a/ghc/rts/QueueTemplate.h b/ghc/rts/QueueTemplate.h
index a16d12b..b4a3513 100644 (file)
--- a/ghc/rts/QueueTemplate.h
+++ b/ghc/rts/QueueTemplate.h
@@ -1,24 +1,23 @@
-/* -*- mode: hugs-c; -*- */
+
 /* -----------------------------------------------------------------------------
- * $Id: QueueTemplate.h,v 1.3 1999/02/05 16:02:48 simonm Exp $
+ * $Id: QueueTemplate.h,v 1.5 1999/12/07 11:15:02 sewardj Exp $
  *
  * (c) The GHC Team, 1998
  *
  * Template for generating queues of various types
  *
- * #define Queue##ChunkSize, Queue and Type before #including this file
+ * #define Queue and Type before #including this file
  * to define the following:
  *
- *   typedef { ...; nat len } Queue;
+ *   typedef { Type* elems; nat used; nat size } Queue;
  *   static void insertQueue( Queue* q, Type i );
  *   static void initQueue  ( Queue* q );
  *   static void setQueue   ( Queue* q, nat i, Type x );
- *
- * Copyright (c) 1994-1998.
+ *   static void freeQueue  ( Queue* q );
  *
  * $RCSfile: QueueTemplate.h,v $
- * $Revision: 1.3 $
- * $Date: 1999/02/05 16:02:48 $
+ * $Revision: 1.5 $
+ * $Date: 1999/12/07 11:15:02 $
  *
  * ------------------------------------------------------------------------*/
 
@@ -30,81 +29,82 @@
 #define mycat2(x,y)   mycat(x,y)
 #define mycat3(x,y,z) mycat2(x,mycat2(y,z))
 
-typedef struct mycat3(_,Queue,Chunk) {
-    struct mycat3(_,Queue,Chunk)* next;
-    Type                    xs[mycat2(Queue,ChunkSize)];
-} mycat2(Queue,Chunk);
-
-static mycat2(Queue,Chunk)* mycat3(alloc,Queue,Chunk)( void )
-{
-    mycat2(Queue,Chunk)* new = malloc(sizeof(mycat2(Queue,Chunk)));
-    if (new == NULL) {
-        barf("Can't allomycate " mystr(Queue) "Chunk");
-    }
-    new->next = NULL;
-    return new;
-}
 
 typedef struct {
-    mycat2(Queue,Chunk)*  head;
-    mycat2(Queue,Chunk)*  tail;
-    nat    len;          /* position of next free instruction */
+    Type*  elems;
+    nat    len;   /* always <= size */
+    nat    size;
 } Queue;
 
-static void mycat2(insert,Queue)( Queue* q, Type i )
+
+#if MAKE_findIn
+static int mycat2(findIn,Queue)( Queue* q, Type x )
 {
-    if (q->len == 0) {
-        mycat2(Queue,Chunk)* new = mycat3(alloc,Queue,Chunk)();
-        new->next = NULL;
-        q->head = new;
-       q->tail = new;
-    } else if (q->len % mycat2(Queue,ChunkSize) == 0) {
-        mycat2(Queue,Chunk)* new = mycat3(alloc,Queue,Chunk)();
-        new->next = NULL;
-        q->tail->next = new;
-       q->tail = new;
-    }
-    q->tail->xs[q->len % mycat2(Queue,ChunkSize)] = i;
-    q->len++;
+   nat i;
+   for (i = 0; i < q->len; i++)
+      if (q->elems[i] == x) return i;
+   return -1;
 }
+#endif
 
-static inline void mycat2(init,Queue)( Queue* q )
+static void mycat2(init,Queue)( Queue* q )
 {
-   q->head = q->tail = NULL;
-   q->len = 0;
+   q->len   = 0;
+   q->size  = 8;
+   q->elems = malloc(q->size * sizeof(Type));
+   if (q->elems == NULL) {
+      barf("Out of memory: can't allocate initial " mystr(Queue) " space");
+   }
 }
  
-static void mycat2(set,Queue)( Queue* q, nat i, Type x )
+
+static void mycat2(free,Queue)( Queue* q )
 {
-    mycat2(Queue,Chunk)* chunk = q->head;
-    ASSERT(i <= q->len);
-    /* ToDo: optimise case where i is in the last chunk in the list */
-    for(; i >= mycat2(Queue,ChunkSize); i -= mycat2(Queue,ChunkSize)) {
-        ASSERT(chunk);
-        chunk = chunk->next;
-    }
-    ASSERT(chunk);
-    chunk->xs[i] = x;
+   free(q->elems);
+   q->elems = NULL;
 }
 
+
+static void mycat2(insert,Queue)( Queue* q, Type x )
+{
+   nat i;
+   if (q->len == q->size) {
+      Type* elems2 = malloc(2 * q->size * sizeof(Type));
+      if (elems2 == NULL) {
+         barf("Out of memory: can't resize " mystr(Queue) " space");
+      }
+      for (i = 0; i < q->len; i++)
+         elems2[i] = q->elems[i];
+      free(q->elems);
+      q->elems = elems2;
+      q->size *= 2;
+   }
+   q->elems[q->len] = x;
+   q->len++;
+}
+
+
+void mycat2(set,Queue)( Queue* q, nat i, Type x )
+{
+    ASSERT(i < q->len);
+    q->elems[i] = x;
+}
+
+
+
 /* evaluate a statement s once for every element in a queue q.
  * i and x are usually free in s
  * queueTy and eltTy are the types of the container and element respectively
  */
-#define mapQueue(queueTy,eltTy,q,s)                         \
-do {                                                        \
-    mycat2(queueTy,Chunk)* chunk = (q).head;               \
-    nat i = 0;                                             \
-    eltTy x;                                                \
-    while( i < (q).len ) {                                 \
-        ASSERT(chunk);                                      \
-       x = chunk->xs[i % mycat2(queueTy,ChunkSize)];       \
-       s;                                                  \
-       ++i;                                                \
-       if (i % mycat2(queueTy,ChunkSize) == 0) {           \
-           chunk = chunk->next;                            \
-       }                                                   \
-    }                                                       \
+#define mapQueue(queueTy,eltTy,q,s)     \
+do {                                    \
+    nat i = 0;                          \
+    eltTy x;                            \
+    while( i < (q).len ) {              \
+        x = q.elems[i];                 \
+        s;                              \
+        ++i;                            \
+    }                                   \
 } while (0)
 
 /* --------------------------------------------------------------------------