-/* -*- mode: hugs-c; -*- */
-/* --------------------------------------------------------------------------
+
+/* -----------------------------------------------------------------------------
+ * $Id: QueueTemplate.h,v 1.6 2000/04/14 15:08:14 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.2 $
- * $Date: 1998/12/02 13:28:37 $
+ * $Revision: 1.6 $
+ * $Date: 2000/04/14 15:08:14 $
*
* ------------------------------------------------------------------------*/
#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(free,Queue)( Queue* q )
+{
+ 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++;
+}
+
+
static void mycat2(set,Queue)( Queue* q, nat i, Type x )
{
- 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;
+ 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)
/* --------------------------------------------------------------------------