Make the abq module manage elements of arbitrary type (knowing only their address and size) instead of managing cbsblock only. (this is preparatory to removing cbsblock from the cbs public interface.)

Update abqtest to use the new interface.
Add ABQ design.

Copied from Perforce
 Change: 182013
 ServerID: perforce.ravenbrook.com

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;