3 files changed, 169 insertions, 120 deletions

diff --git a/mps/code/abq.c b/mps/code/abq.c
index e29a9786599..c327a721a54 100644
--- a/mps/code/abq.c
+++ b/mps/code/abq.c
@@ -1,18 +1,15 @@
-/* abq.c: AVAILABLE BLOCK QUEUE
+/* abq.c: QUEUE IMPLEMENTATION
  *
  * $Id$
  * Copyright (c) 2001 Ravenbrook Limited.  See end of file for license.
  *
- * .readership: Any MPS developer
+ * .purpose: A fixed-length FIFO queue.
  *
- * .purpose: A FIFO queue substrate for <code/poolmv2.c>
- *
- * .design: See <design/poolmvt/>
+ * .design: <design/abq/>
  */
 
 #include "meter.h"
 #include "abq.h"
-#include "cbs.h"
 #include "mpm.h"
 
 SRCID(abq, "$Id$");
@@ -20,37 +17,39 @@ SRCID(abq, "$Id$");
 
 /* Private prototypes */
 
-static Size ABQQueueSize(Count elements);
+static Size ABQQueueSize(Count elements, Size elementSize);
 static Index ABQNextIndex(ABQ abq, Index index);
+static Addr ABQElement(ABQ abq, Index index);
 
 
 /* Methods */
 
 /* ABQInit -- Initialize an ABQ
  *
- * items is the number of items the queue can hold
+ * elements is the number of elements the queue can hold
  */
-Res ABQInit(Arena arena, ABQ abq, void *owner, Count items)
+Res ABQInit(Arena arena, ABQ abq, void *owner, Count elements, Size elementSize)
 {
-  Count elements;
   void *p;
   Res res;
 
   AVERT(Arena, arena);
   AVER(abq != NULL);
-  AVER(items > 0);
+  AVER(elements > 0);
 
-  elements = items + 1;
- 
-  res = ControlAlloc(&p, arena, ABQQueueSize(elements),
+  /* Necessary in order to be able to distinguish "empty" from "full" */
+  elements = elements + 1;
+
+  res = ControlAlloc(&p, arena, ABQQueueSize(elements, elementSize),
                      /* withReservoirPermit */ FALSE);
   if (res != ResOK)
     return res;
 
   abq->elements = elements;
+  abq->elementSize = elementSize;
   abq->in = 0;
   abq->out = 0;
-  abq->queue = (CBSBlock *)p;
+  abq->queue = p;
 
   METER_INIT(abq->push, "push", owner);
   METER_INIT(abq->pop, "pop", owner);
@@ -67,19 +66,12 @@ Res ABQInit(Arena arena, ABQ abq, void *owner, Count items)
 /* ABQCheck -- validate an ABQ */
 Bool ABQCheck(ABQ abq)
 {
-  Index index;
- 
   CHECKS(ABQ, abq);
   CHECKL(abq->elements > 0);
+  CHECKL(abq->elementSize > 0);
   CHECKL(abq->in < abq->elements);
   CHECKL(abq->out < abq->elements);
   CHECKL(abq->queue != NULL);
-  /* Is this really a local check? */
-  for (index = abq->out; index != abq->in; ) {
-    CHECKL(CBSBlockCheck(abq->queue[index]));
-    if (++index == abq->elements)
-      index = 0;
-  }
 
   return TRUE;
 }
@@ -95,7 +87,7 @@ void ABQFinish(Arena arena, ABQ abq)
   METER_EMIT(&abq->pop);
   METER_EMIT(&abq->peek);
   METER_EMIT(&abq->delete);
-  ControlFree(arena, abq->queue, ABQQueueSize(abq->elements));
+  ControlFree(arena, abq->queue, ABQQueueSize(abq->elements, abq->elementSize));
  
   abq->elements = 0;
   abq->queue = NULL;
@@ -104,18 +96,17 @@ void ABQFinish(Arena arena, ABQ abq)
 }
 
 
-/* ABQPush -- push a block onto the tail of the ABQ */
-Res ABQPush(ABQ abq, CBSBlock block)
+/* ABQPush -- push an element onto the tail of the ABQ */
+Res ABQPush(ABQ abq, Addr element)
 {
   AVERT(ABQ, abq);
-  AVERT(CBSBlock, block);
 
   METER_ACC(abq->push, ABQDepth(abq));
 
   if (ABQIsFull(abq))
     return ResFAIL;
  
-  abq->queue[abq->in] = block;
+  mps_lib_memcpy(ABQElement(abq, abq->in), element, abq->elementSize);
   abq->in = ABQNextIndex(abq, abq->in);
 
   AVERT(ABQ, abq);
@@ -123,10 +114,10 @@ Res ABQPush(ABQ abq, CBSBlock block)
 }
 
 
-/* ABQPop -- pop a block from the head of the ABQ */
-Res ABQPop(ABQ abq, CBSBlock *blockReturn)
+/* ABQPop -- pop an element from the head of the ABQ */
+Res ABQPop(ABQ abq, Addr elementReturn)
 {
-  AVER(blockReturn != NULL);
+  AVER(elementReturn != NULL);
   AVERT(ABQ, abq);
 
   METER_ACC(abq->pop, ABQDepth(abq));
@@ -134,8 +125,7 @@ Res ABQPop(ABQ abq, CBSBlock *blockReturn)
   if (ABQIsEmpty(abq))
     return ResFAIL;
 
-  *blockReturn = abq->queue[abq->out];
-  AVERT(CBSBlock, *blockReturn);
+  mps_lib_memcpy(elementReturn, ABQElement(abq, abq->out), abq->elementSize);
 
   abq->out = ABQNextIndex(abq, abq->out);
  
@@ -145,9 +135,9 @@ Res ABQPop(ABQ abq, CBSBlock *blockReturn)
 
 
 /* ABQPeek -- peek at the head of the ABQ */
-Res ABQPeek(ABQ abq, CBSBlock *blockReturn)
+Res ABQPeek(ABQ abq, Addr elementReturn)
 {
-  AVER(blockReturn != NULL);
+  AVER(elementReturn != NULL);
   AVERT(ABQ, abq);
 
   METER_ACC(abq->peek, ABQDepth(abq));
@@ -155,8 +145,7 @@ Res ABQPeek(ABQ abq, CBSBlock *blockReturn)
   if (ABQIsEmpty(abq))
     return ResFAIL;
 
-  *blockReturn = abq->queue[abq->out];
-  AVERT(CBSBlock, *blockReturn);
+  mps_lib_memcpy(elementReturn, ABQElement(abq, abq->out), abq->elementSize);
 
   /* Identical to pop, but don't increment out */
 
@@ -165,46 +154,49 @@ Res ABQPeek(ABQ abq, CBSBlock *blockReturn)
 }
 
 
-/* ABQDelete -- delete a block from the ABQ */
-Res ABQDelete(ABQ abq, CBSBlock block)
+typedef struct ABQDeleteClosureStruct *ABQDeleteClosure;
+typedef struct ABQDeleteClosureStruct {
+  Addr element;
+  Size elementSize;
+  Res res;
+} ABQDeleteClosureStruct;
+
+
+static Res ABQDeleteCallback(ABQDisposition *dispositionReturn, Addr element,
+                             void *closureP)
+{
+  ABQDeleteClosure closure = closureP;
+  if (mps_lib_memcmp(element, closure->element, closure->elementSize) == 0) {
+    *dispositionReturn = ABQDispositionDELETE;
+    closure->res = ResOK;
+  } else {
+    *dispositionReturn = ABQDispositionKEEP;
+  }
+  return ResOK;
+}
+
+
+/* ABQDelete -- delete an element from the ABQ */
+Res ABQDelete(ABQ abq, Addr element)
 {
-  Index index, next, in;
-  CBSBlock *queue;
+  ABQDeleteClosureStruct closure;
 
   AVERT(ABQ, abq);
-  AVERT(CBSBlock, block);
 
   METER_ACC(abq->delete, ABQDepth(abq));
 
-  index = abq->out;
-  in = abq->in;
-  queue = abq->queue;
- 
-  while (index != in) {
-    if (queue[index] == block) {
-      goto found;
-    }
-    index = ABQNextIndex(abq, index);
-  }
-
-  return ResFAIL;
+  closure.element = element;
+  closure.elementSize = abq->elementSize;
+  closure.res = ResFAIL;
 
-found:
-  /* index points to the node to be removed */
-  next = ABQNextIndex(abq, index);
-  while (next != in) {
-    queue[index] = queue[next];
-    index = next;
-    next = ABQNextIndex(abq, index);
-  }
-  abq->in = index;
-  AVERT(ABQ, abq);
-  return ResOK;
+  ABQIterate(abq, ABQDeleteCallback, &closure);
+  
+  return closure.res;
 }
 
 
 /* ABQDescribe -- Describe an ABQ */
-Res ABQDescribe(ABQ abq, mps_lib_FILE *stream)
+Res ABQDescribe(ABQ abq, ABQDescribeElement describeElement, mps_lib_FILE *stream)
 {
   Res res;
   Index index;
@@ -224,11 +216,10 @@ Res ABQDescribe(ABQ abq, mps_lib_FILE *stream)
     return res;
 
   for (index = abq->out; index != abq->in; ) {
-    res = CBSBlockDescribe(abq->queue[index], stream);
+    res = (*describeElement)(ABQElement(abq, index), stream);
     if(res != ResOK)
       return res;
-    if (++index == abq->elements)
-      index = 0;
+    index = ABQNextIndex(abq, index);
   }
 
   res = WriteF(stream, "\n", NULL);
@@ -274,7 +265,7 @@ Bool ABQIsFull(ABQ abq)
 }
 
 
-/* ABQDepth -- return the number of items in an ABQ */
+/* ABQDepth -- return the number of elements in an ABQ */
 Count ABQDepth(ABQ abq)
 {
   Index out, in;
@@ -290,13 +281,65 @@ Count ABQDepth(ABQ abq)
 }
 
 
+/* ABQDispositionCheck -- check method for an ABQDisposition value */
+static Bool ABQDispositionCheck(ABQDisposition disposition)
+{
+  CHECKL(disposition == ABQDispositionKEEP
+         || disposition == ABQDispositionDELETE);
+  UNUSED(disposition); /* <code/mpm.c#check.unused> */
+
+  return TRUE;
+}
+
+
+/* ABQIterate -- call 'iterate' for each element in an ABQ */
+void ABQIterate(ABQ abq, ABQIterateMethod iterate, void *closureP)
+{
+  Index copy, index, in;
+  Res res;
+
+  AVERT(ABQ, abq);
+  AVER(FUNCHECK(iterate));
+
+  copy = abq->out;
+  index = abq->out;
+  in = abq->in;
+ 
+  while (index != in) {
+    Addr element = ABQElement(abq, index);
+    ABQDisposition disposition = ABQDispositionNONE;
+    res = (*iterate)(&disposition, element, closureP);
+    AVERT(ABQDisposition, disposition);
+    if (disposition == ABQDispositionKEEP) {
+      if (copy != index)
+        mps_lib_memcpy(ABQElement(abq, copy), element, abq->elementSize);
+      copy = ABQNextIndex(abq, copy);
+    }
+    index = ABQNextIndex(abq, index);
+    if (res != ResOK)
+      break;
+  }
+
+  /* If any elements were deleted, need to copy remainder of queue. */
+  if (copy != index) {
+    while (index != in) {
+      mps_lib_memcpy(ABQElement(abq, copy), ABQElement(abq, index),
+                     abq->elementSize);
+      copy = ABQNextIndex(abq, copy);
+      index = ABQNextIndex(abq, index);
+    }
+    abq->in = copy;
+  }
+
+  AVERT(ABQ, abq);
+}
+
+
 /* ABQQueueSize -- calculate the storage required for the vector to
-   store elements items */
-static Size ABQQueueSize(Count elements)
+   store the elements */
+static Size ABQQueueSize(Count elements, Size elementSize)
 {
-  /* strange but true: the sizeof expression calculates the size of a
-     single queue element */
-  return (Size)(sizeof(((ABQ)NULL)->queue[0]) * elements);
+  return (Size)(elements * elementSize);
 }
 
 
@@ -310,6 +353,12 @@ static Index ABQNextIndex(ABQ abq, Index index)
   return next;
 }
 
+/* ABQElement -- return pointer to the index'th element in the queue
+   vector. */
+static Addr ABQElement(ABQ abq, Index index) {
+  return AddrAdd(abq->queue, index * abq->elementSize);
+}
+
 
 /* C. COPYRIGHT AND LICENSE
  *
diff --git a/mps/code/abq.h b/mps/code/abq.h
index e39635dfcaa..085b1ed3d66 100644
--- a/mps/code/abq.h
+++ b/mps/code/abq.h
@@ -1,18 +1,17 @@
-/* abq.h: ABQ INTERFACE
+/* abq.h: QUEUE INTERFACE
  *
  * $Id$
  * Copyright (c) 2001 Ravenbrook Limited.  See end of file for license.
  *
- * .purpose: A FIFO queue substrate for <code/poolmv2.c>
+ * .purpose: A fixed-length FIFO queue.
  *
- * .source: <design/poolmvt/>
+ * .design: <design/abq/>
  */
 
 #ifndef abq_h
 #define abq_h
 
 #include "meter.h"
-#include "cbs.h"
 #include "mpm.h"
 
 
@@ -24,17 +23,22 @@
 /* Prototypes  */
 
 typedef struct ABQStruct *ABQ;
-extern Res ABQInit(Arena arena, ABQ abq, void *owner, Count items);
+typedef Res (*ABQDescribeElement)(Addr element, mps_lib_FILE *stream);
+typedef unsigned ABQDisposition;
+typedef Res (*ABQIterateMethod)(ABQDisposition *dispositionReturn, Addr element, void *closureP);
+
+extern Res ABQInit(Arena arena, ABQ abq, void *owner, Count elements, Size elementSize);
 extern Bool ABQCheck(ABQ abq);
 extern void ABQFinish(Arena arena, ABQ abq);
-extern Res ABQPush(ABQ abq, CBSBlock block);
-extern Res ABQPop(ABQ abq, CBSBlock *blockReturn);
-extern Res ABQPeek(ABQ abq, CBSBlock *blockReturn);
-extern Res ABQDelete(ABQ abq, CBSBlock block);
-extern Res ABQDescribe(ABQ abq, mps_lib_FILE *stream);
+extern Res ABQPush(ABQ abq, Addr element);
+extern Res ABQPop(ABQ abq, Addr elementReturn);
+extern Res ABQPeek(ABQ abq, Addr elementReturn);
+extern Res ABQDelete(ABQ abq, Addr element);
+extern Res ABQDescribe(ABQ abq, ABQDescribeElement describeElement, mps_lib_FILE *stream);
 extern Bool ABQIsEmpty(ABQ abq);
 extern Bool ABQIsFull(ABQ abq);
 extern Count ABQDepth(ABQ abq);
+extern void ABQIterate(ABQ abq, ABQIterateMethod iterate, void *closureP);
 
 
 /* Types */
@@ -42,9 +46,10 @@ extern Count ABQDepth(ABQ abq);
 typedef struct ABQStruct
 {
   Count elements;
+  Size elementSize;
   Index in;
   Index out;
-  CBSBlock *queue;
+  Addr queue;
 
   /* Meter queue depth at each operation */
   METER_DECL(push);
@@ -55,6 +60,12 @@ typedef struct ABQStruct
   Sig sig;
 } ABQStruct;
 
+enum {
+  ABQDispositionKEEP = 1, /* keep item in queue */
+  ABQDispositionDELETE,   /* delete element from queue */
+  ABQDispositionNONE      /* no disposition (error) */
+};
+
 #endif /* abq_h */
 
 
diff --git a/mps/code/abqtest.c b/mps/code/abqtest.c
index 7de0ee537a7..f1685cde4b7 100644
--- a/mps/code/abqtest.c
+++ b/mps/code/abqtest.c
@@ -41,54 +41,42 @@ static unsigned popee = 1;
 static unsigned deleted = 0;
 
 
-typedef struct TestStruct *Test;
+typedef struct TestBlockStruct *TestBlock;
 
-typedef struct TestStruct
+typedef struct TestBlockStruct
 {
-  Test next;
+  TestBlock next;
   unsigned id;
-  CBSBlockStruct cbsBlockStruct;
-} TestStruct;
+  Addr base;
+  Addr limit;
+} TestBlockStruct;
 
 
-static CBSBlock TestCBSBlock(Test t)
-{
-  return &t->cbsBlockStruct;
-}
-
-static Test CBSBlockTest(CBSBlock c)
-{
-  return PARENT(TestStruct, cbsBlockStruct, c);
-}
-
+static TestBlock testBlocks = NULL;
 
-static Test testBlocks = NULL;
 
-
-static CBSBlock CreateCBSBlock(unsigned no)
+static TestBlock CreateTestBlock(unsigned no)
 {
-  Test b = malloc(sizeof(TestStruct));
+  TestBlock b = malloc(sizeof(TestBlockStruct));
   cdie(b != NULL, "malloc");
 
   b->next = testBlocks;
   b->id = no;
-  b->cbsBlockStruct.base = 0;
-  b->cbsBlockStruct.limit = 0;
+  b->base = 0;
+  b->limit = 0;
 
   testBlocks = b;
 
-  return TestCBSBlock(b);
+  return b;
 }
 
 
-static void DestroyCBSBlock(CBSBlock c)
+static void DestroyTestBlock(TestBlock b)
 {
-  Test b = CBSBlockTest(c);
-
   if (b == testBlocks)
     testBlocks = b->next;
   else {
-    Test prev;
+    TestBlock prev;
  
     for (prev = testBlocks; prev != 0; prev = prev->next)
       if (prev->next == b) {
@@ -104,12 +92,13 @@ static void DestroyCBSBlock(CBSBlock c)
 static void step(void)
 {
   Res res;
-  CBSBlock a;
+  TestBlock a;
 
   switch (abqRnd(9)) {
     case 0: case 1: case 2: case 3:
   push:
-      res = ABQPush(&abq, CreateCBSBlock(pushee));
+      a = CreateTestBlock(pushee);
+      res = ABQPush(&abq, (Addr)&a);
       if (res != ResOK) {
         goto pop;
       }
@@ -117,7 +106,7 @@ static void step(void)
       break;
     case 5: case 6: case 7: case 8:
   pop:
-      res = ABQPop(&abq, &a);
+      res = ABQPop(&abq, (Addr)&a);
       if (res != ResOK){
         goto push;
       }
@@ -125,20 +114,20 @@ static void step(void)
         popee++;
         deleted = 0;
       }
-      cdie(CBSBlockTest(a)->id == popee, "pop");
+      cdie(a->id == popee, "pop");
       popee++;
-      DestroyCBSBlock(a);
+      DestroyTestBlock(a);
       break;
     default:
       if (!deleted & (pushee > popee)) {
-        Test b;
+        TestBlock b;
      
         deleted = (unsigned)abqRnd (pushee - popee) + popee;
         for (b = testBlocks; b != NULL; b = b->next)
           if (b->id == deleted)
             break;
         cdie(b != NULL, "found to delete");
-        res = ABQDelete(&abq, TestCBSBlock(b));
+        res = ABQDelete(&abq, (Addr)&b);
         cdie(res == ResOK, "ABQDelete");
       }
   }
@@ -159,7 +148,7 @@ extern int main(int argc, char *argv[])
   die(mps_arena_create(&arena, mps_arena_class_vm(), testArenaSIZE),
       "mps_arena_create");
 
-  die(ABQInit((Arena)arena, &abq, NULL, ABQ_SIZE),
+  die(ABQInit((Arena)arena, &abq, NULL, ABQ_SIZE, sizeof(TestBlock)),
       "ABQInit");
 
   abqSize = ABQ_SIZE;