Make the cbs module more abstract by removing cbsblock from the public interface. avoid re-entrancy problems by removing the callback interface. public interfaces like cbsiteratemethod now operate in terms of address ranges rather than cbsblocks.

The functions CBSInsert, CBSDelete and CBSFind* now additionally return an "old" address range which gives the former base and limit of the block that has just been updated. This gives clients enough information to update their caches if need be.
Update CBS test and design accordingly.

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

3 files changed, 73 insertions, 439 deletions

diff --git a/mps/code/cbs.c b/mps/code/cbs.c
index f40d075b27e..7b17d295f32 100644
--- a/mps/code/cbs.c
+++ b/mps/code/cbs.c
@@ -21,6 +21,24 @@
 SRCID(cbs, "$Id$");
 
 
+typedef struct CBSBlockStruct *CBSBlock;
+typedef struct CBSBlockStruct {
+  SplayNodeStruct splayNode;
+  Addr base;
+  Addr limit;
+  Size maxSize; /* accurate maximum block size of sub-tree */
+} CBSBlockStruct;
+
+
+extern Bool CBSBlockCheck(CBSBlock block);
+/* CBSBlockBase -- See <design/cbs/#function.cbs.block.base> */
+#define CBSBlockBase(block) ((block)->base)
+/* CBSBlockLimit -- See <design/cbs/#function.cbs.block.limit> */
+#define CBSBlockLimit(block) ((block)->limit)
+#define CBSBlockSize(block) AddrOffset((block)->base, (block)->limit)
+extern Size (CBSBlockSize)(CBSBlock block);
+
+
 #define cbsOfSplayTree(tree) PARENT(CBSStruct, splayTree, (tree))
 #define cbsBlockOfSplayNode(node) PARENT(CBSBlockStruct, splayNode, (node))
 #define splayTreeOfCBS(tree) (&((cbs)->splayTree))
@@ -65,10 +83,6 @@ Bool CBSCheck(CBS cbs)
   CHECKD(Pool, cbs->blockPool);
   CHECKL(BoolCheck(cbs->fastFind));
   CHECKL(BoolCheck(cbs->inCBS));
-  CHECKL(cbs->new == NULL || FUNCHECK(cbs->new));
-  CHECKL(cbs->delete == NULL || FUNCHECK(cbs->delete));
-  CHECKL(cbs->grow == NULL || FUNCHECK(cbs->grow));
-  CHECKL(cbs->shrink == NULL || FUNCHECK(cbs->shrink));
   /* No MeterCheck */
 
   return TRUE;
@@ -206,17 +220,11 @@ static void cbsUpdateNode(SplayTree tree, SplayNode node,
  * See <design/cbs/#function.cbs.init>.
  */
 
-Res CBSInit(Arena arena, CBS cbs, void *owner,
-            CBSChangeSizeMethod new, CBSChangeSizeMethod delete,
-            CBSChangeSizeMethod grow, CBSChangeSizeMethod shrink,
-            Size minSize, Align alignment,
-            Bool fastFind)
+Res CBSInit(Arena arena, CBS cbs, void *owner, Align alignment, Bool fastFind)
 {
   Res res;
 
   AVERT(Arena, arena);
-  AVER(new == NULL || FUNCHECK(new));
-  AVER(delete == NULL || FUNCHECK(delete));
 
   SplayTreeInit(splayTreeOfCBS(cbs), &cbsSplayCompare,
                 fastFind ? &cbsUpdateNode : NULL);
@@ -226,11 +234,6 @@ Res CBSInit(Arena arena, CBS cbs, void *owner,
     return res;
   cbs->splayTreeSize = 0;
 
-  cbs->new = new;
-  cbs->delete = delete;
-  cbs->grow = grow;
-  cbs->shrink = shrink;
-  cbs->minSize = minSize;
   cbs->fastFind = fastFind;
   cbs->alignment = alignment;
   cbs->inCBS = TRUE;
@@ -292,9 +295,6 @@ static void cbsBlockDelete(CBS cbs, CBSBlock block)
   /* make invalid */
   block->limit = block->base;
 
-  if (cbs->delete != NULL && oldSize >= cbs->minSize)
-    (*(cbs->delete))(cbs, block, oldSize, (Size)0);
-
   PoolFree(cbs->blockPool, (Addr)block, sizeof(CBSBlockStruct));
 
   return;
@@ -315,11 +315,6 @@ static void cbsBlockShrink(CBS cbs, CBSBlock block, Size oldSize)
                      keyOfCBSBlock(block));
     AVER(CBSBlockSize(block) <= block->maxSize);
   }
-
-  if (cbs->delete != NULL && oldSize >= cbs->minSize && newSize < cbs->minSize)
-    (*(cbs->delete))(cbs, block, oldSize, newSize);
-  else if (cbs->shrink != NULL && newSize >= cbs->minSize)
-    (*(cbs->shrink))(cbs, block, oldSize, newSize);
 }
 
 static void cbsBlockGrow(CBS cbs, CBSBlock block, Size oldSize)
@@ -337,11 +332,6 @@ static void cbsBlockGrow(CBS cbs, CBSBlock block, Size oldSize)
                      keyOfCBSBlock(block));
     AVER(CBSBlockSize(block) <= block->maxSize);
   }
-
-  if (cbs->new != NULL && oldSize < cbs->minSize && newSize >= cbs->minSize)
-    (*(cbs->new))(cbs, block, oldSize, newSize);
-  else if (cbs->grow != NULL && oldSize >= cbs->minSize)
-    (*(cbs->grow))(cbs, block, oldSize, newSize);
 }
 
 static Res cbsBlockNew(CBS cbs, Addr base, Addr limit)
@@ -373,9 +363,6 @@ static Res cbsBlockNew(CBS cbs, Addr base, Addr limit)
   AVER(res == ResOK);
   STATISTIC(++cbs->splayTreeSize);
 
-  if (cbs->new != NULL && newSize >= cbs->minSize)
-    (*(cbs->new))(cbs, block, (Size)0, newSize);
-
   return ResOK;
 
 failPoolAlloc:
@@ -485,12 +472,14 @@ fail:
  * See <design/cbs/#functions.cbs.insert>.
  */
 
-Res CBSInsertReturningRange(Addr *baseReturn, Addr *limitReturn,
-                            CBS cbs, Addr base, Addr limit)
+Res CBSInsert(Addr *baseReturn, Addr *limitReturn,
+              CBS cbs, Addr base, Addr limit)
 {
   Addr newBase, newLimit;
   Res res;
 
+  AVER(baseReturn != NULL);
+  AVER(limitReturn != NULL);
   AVERT(CBS, cbs);
   CBSEnter(cbs);
 
@@ -511,24 +500,11 @@ Res CBSInsertReturningRange(Addr *baseReturn, Addr *limitReturn,
   return res;
 }
 
-Res CBSInsert(CBS cbs, Addr base, Addr limit)
-{
-  Res res;
-  Addr newBase, newLimit;
-
-  /* all parameters checked by CBSInsertReturningRange */
-  /* CBSEnter/Leave done by CBSInsertReturningRange */
-
-  res = CBSInsertReturningRange(&newBase, &newLimit,
-                                cbs, base, limit);
-
-  return res;
-}
-
 
 /* cbsDeleteFrom* -- delete blocks from different parts of the CBS */
 
-static Res cbsDeleteFromTree(CBS cbs, Addr base, Addr limit)
+static Res cbsDeleteFromTree(Addr *baseReturn, Addr *limitReturn,
+                             CBS cbs, Addr base, Addr limit)
 {
   Res res;
   CBSBlock cbsBlock;
@@ -548,6 +524,9 @@ static Res cbsDeleteFromTree(CBS cbs, Addr base, Addr limit)
     goto failLimitCheck;
   }
 
+  *baseReturn = cbsBlock->base;
+  *limitReturn = cbsBlock->limit;
+
   if (base == cbsBlock->base) {
     if (limit == cbsBlock->limit) { /* entire block */
       cbsBlockDelete(cbs, cbsBlock);
@@ -609,7 +588,8 @@ failSplayTreeSearch:
  * See <design/cbs/#function.cbs.delete>.
  */
 
-Res CBSDelete(CBS cbs, Addr base, Addr limit)
+Res CBSDelete(Addr *baseReturn, Addr *limitReturn,
+              CBS cbs, Addr base, Addr limit)
 {
   Res res;
 
@@ -621,14 +601,14 @@ Res CBSDelete(CBS cbs, Addr base, Addr limit)
   AVER(AddrIsAligned(base, cbs->alignment));
   AVER(AddrIsAligned(limit, cbs->alignment));
 
-  res = cbsDeleteFromTree(cbs, base, limit);
+  res = cbsDeleteFromTree(baseReturn, limitReturn, cbs, base, limit);
 
   CBSLeave(cbs);
   return res;
 }
 
 
-Res CBSBlockDescribe(CBSBlock block, mps_lib_FILE *stream)
+static Res CBSBlockDescribe(CBSBlock block, mps_lib_FILE *stream)
 {
   Res res;
 
@@ -678,7 +658,7 @@ static void cbsIterateInternal(CBS cbs, CBSIterateMethod iterate, void *closureP
   splayNode = SplayTreeFirst(splayTree, NULL);
   while(splayNode != NULL) {
     cbsBlock = cbsBlockOfSplayNode(splayNode);
-    if (!(*iterate)(cbs, cbsBlock, closureP)) {
+    if (!(*iterate)(cbs, CBSBlockBase(cbsBlock), CBSBlockLimit(cbsBlock), closureP)) {
       break;
     }
     METER_ACC(cbs->splaySearch, cbs->splayTreeSize);
@@ -700,110 +680,6 @@ void CBSIterate(CBS cbs, CBSIterateMethod iterate, void *closureP)
 }
 
 
-/* CBSIterateLarge -- Iterate only large blocks
- *
- * This function iterates only blocks that are larger than or equal
- * to the minimum size.
- */
-
-typedef struct CBSIterateLargeClosureStruct {
-  void *p;
-  CBSIterateMethod f;
-} CBSIterateLargeClosureStruct, *CBSIterateLargeClosure;
-
-static Bool cbsIterateLargeAction(CBS cbs, CBSBlock block, void *p)
-{
-  Bool b = TRUE;
-  CBSIterateLargeClosure closure;
-
-  closure = (CBSIterateLargeClosure)p;
-  AVER(closure != NULL);
-
-  if (CBSBlockSize(block) >= cbs->minSize)
-    b = (closure->f)(cbs, block, closure->p);
-
-  return b;
-}
-
-
-void CBSIterateLarge(CBS cbs, CBSIterateMethod iterate, void *closureP)
-{
-  CBSIterateLargeClosureStruct closure;
-
-  AVERT(CBS, cbs);
-  CBSEnter(cbs);
-
-  AVER(FUNCHECK(iterate));
-
-  closure.p = closureP;
-  closure.f = iterate;
-  cbsIterateInternal(cbs, &cbsIterateLargeAction, (void *)&closure);
-
-  CBSLeave(cbs);
-  return;
-}
-
-
-/* CBSSetMinSize -- Set minimum interesting size for cbs
- *
- * This function may invoke the shrink and grow methods as
- * appropriate.  See <design/cbs/#function.cbs.set.min-size>.
- */
-
-typedef struct {
-  Size old;
-  Size new;
-} CBSSetMinSizeClosureStruct, *CBSSetMinSizeClosure;
-
-static Bool cbsSetMinSizeGrow(CBS cbs, CBSBlock block, void *p)
-{
-  CBSSetMinSizeClosure closure;
-  Size size;
- 
-  closure = (CBSSetMinSizeClosure)p;
-  AVER(closure->old > closure->new);
-  size = CBSBlockSize(block);
-  if (size < closure->old && size >= closure->new)
-    (*cbs->new)(cbs, block, size, size);
-
-  return TRUE;
-}
-
-static Bool cbsSetMinSizeShrink(CBS cbs, CBSBlock block, void *p)
-{
-  CBSSetMinSizeClosure closure;
-  Size size;
- 
-  closure = (CBSSetMinSizeClosure)p;
-  AVER(closure->old < closure->new);
-  size = CBSBlockSize(block);
-  if (size >= closure->old && size < closure->new)
-    (*cbs->delete)(cbs, block, size, size);
-
-  return TRUE;
-}
-
-void CBSSetMinSize(CBS cbs, Size minSize)
-{
-  CBSSetMinSizeClosureStruct closure;
-
-  AVERT(CBS, cbs);
-  CBSEnter(cbs);
-
-  closure.old = cbs->minSize;
-  closure.new = minSize;
-
-  if (minSize < cbs->minSize)
-    cbsIterateInternal(cbs, &cbsSetMinSizeGrow, (void *)&closure);
-  else if (minSize > cbs->minSize)
-    cbsIterateInternal(cbs, &cbsSetMinSizeShrink, (void *)&closure);
-
-  cbs->minSize = minSize;
-
-  CBSLeave(cbs);
-}
-
-
 /* CBSFindDeleteCheck -- check method for a CBSFindDelete value */
 
 static Bool CBSFindDeleteCheck(CBSFindDelete findDelete)
@@ -817,13 +693,11 @@ static Bool CBSFindDeleteCheck(CBSFindDelete findDelete)
 }
 
 
-/* cbsFindDeleteRange -- delete approriate range of block found */
-
-typedef Res (*cbsDeleteMethod)(CBS cbs, Addr base, Addr limit);
+/* cbsFindDeleteRange -- delete appropriate range of block found */
 
 static void cbsFindDeleteRange(Addr *baseReturn, Addr *limitReturn,
+                               Addr *oldBaseReturn, Addr *oldLimitReturn,
                                CBS cbs, Addr base, Addr limit, Size size,
-                               cbsDeleteMethod delete,
                                CBSFindDelete findDelete)
 {
   Bool callDelete = TRUE;
@@ -834,7 +708,6 @@ static void cbsFindDeleteRange(Addr *baseReturn, Addr *limitReturn,
   AVER(base < limit);
   AVER(size > 0);
   AVER(AddrOffset(base, limit) >= size);
-  AVER(FUNCHECK(delete));
   AVERT(CBSFindDelete, findDelete);
 
   switch(findDelete) {
@@ -862,7 +735,7 @@ static void cbsFindDeleteRange(Addr *baseReturn, Addr *limitReturn,
 
   if (callDelete) {
     Res res;
-    res = (*delete)(cbs, base, limit);
+    res = cbsDeleteFromTree(oldBaseReturn, oldLimitReturn, cbs, base, limit);
     AVER(res == ResOK);
   }
 
@@ -874,11 +747,11 @@ static void cbsFindDeleteRange(Addr *baseReturn, Addr *limitReturn,
 /* CBSFindFirst -- find the first block of at least the given size */
 
 Bool CBSFindFirst(Addr *baseReturn, Addr *limitReturn,
+                  Addr *oldBaseReturn, Addr *oldLimitReturn,
                   CBS cbs, Size size, CBSFindDelete findDelete)
 {
   Bool found;
   Addr base = (Addr)0, limit = (Addr)0; /* only defined when found is TRUE */
-  cbsDeleteMethod deleteMethod = NULL;
 
   AVERT(CBS, cbs);
   CBSEnter(cbs);
@@ -904,14 +777,13 @@ Bool CBSFindFirst(Addr *baseReturn, Addr *limitReturn,
       AVER(CBSBlockSize(block) >= size);
       base = CBSBlockBase(block);
       limit = CBSBlockLimit(block);
-      deleteMethod = &cbsDeleteFromTree;
     }
   }
 
   if (found) {
     AVER(AddrOffset(base, limit) >= size);
-    cbsFindDeleteRange(baseReturn, limitReturn, cbs, base, limit, size,
-                       deleteMethod, findDelete);
+    cbsFindDeleteRange(baseReturn, limitReturn, oldBaseReturn, oldLimitReturn,
+                       cbs, base, limit, size, findDelete);
   }
 
   CBSLeave(cbs);
@@ -922,11 +794,11 @@ Bool CBSFindFirst(Addr *baseReturn, Addr *limitReturn,
 /* CBSFindLast -- find the last block of at least the given size */
 
 Bool CBSFindLast(Addr *baseReturn, Addr *limitReturn,
+                 Addr *oldBaseReturn, Addr *oldLimitReturn,
                  CBS cbs, Size size, CBSFindDelete findDelete)
 {
   Bool found;
   Addr base = (Addr)0, limit = (Addr)0; /* only defined in found is TRUE */
-  cbsDeleteMethod deleteMethod = NULL;
 
   AVERT(CBS, cbs);
   CBSEnter(cbs);
@@ -951,14 +823,13 @@ Bool CBSFindLast(Addr *baseReturn, Addr *limitReturn,
       AVER(CBSBlockSize(block) >= size);
       base = CBSBlockBase(block);
       limit = CBSBlockLimit(block);
-      deleteMethod = &cbsDeleteFromTree;
     }
   }
 
   if (found) {
     AVER(AddrOffset(base, limit) >= size);
-    cbsFindDeleteRange(baseReturn, limitReturn, cbs, base, limit, size,
-                       deleteMethod, findDelete);
+    cbsFindDeleteRange(baseReturn, limitReturn, oldBaseReturn, oldLimitReturn,
+                       cbs, base, limit, size, findDelete);
   }
 
   CBSLeave(cbs);
@@ -969,11 +840,11 @@ Bool CBSFindLast(Addr *baseReturn, Addr *limitReturn,
 /* CBSFindLargest -- find the largest block in the CBS */
 
 Bool CBSFindLargest(Addr *baseReturn, Addr *limitReturn,
+                    Addr *oldBaseReturn, Addr *oldLimitReturn,
                     CBS cbs, CBSFindDelete findDelete)
 {
   Bool found = FALSE;
   Addr base = (Addr)0, limit = (Addr)0; /* only defined when found is TRUE */
-  cbsDeleteMethod deleteMethod = NULL;
   Size size = 0; /* suppress bogus warning from MSVC */
 
   AVERT(CBS, cbs);
@@ -1002,13 +873,12 @@ Bool CBSFindLargest(Addr *baseReturn, Addr *limitReturn,
       AVER(CBSBlockSize(block) >= size);
       base = CBSBlockBase(block);
       limit = CBSBlockLimit(block);
-      deleteMethod = &cbsDeleteFromTree;
     }
   }
 
   if (found) {
-    cbsFindDeleteRange(baseReturn, limitReturn, cbs, base, limit, size,
-                       deleteMethod, findDelete);
+    cbsFindDeleteRange(baseReturn, limitReturn, oldBaseReturn, oldLimitReturn,
+                       cbs, base, limit, size, findDelete);
   }
 
   CBSLeave(cbs);
@@ -1031,8 +901,6 @@ Res CBSDescribe(CBS cbs, mps_lib_FILE *stream)
   res = WriteF(stream,
                "CBS $P {\n", (WriteFP)cbs,
                "  blockPool: $P\n", (WriteFP)cbs->blockPool,
-               "  new: $F ", (WriteFF)cbs->new,
-               "  delete: $F \n", (WriteFF)cbs->delete,
                NULL);
   if (res != ResOK) return res;
 
diff --git a/mps/code/cbs.h b/mps/code/cbs.h
index ddbda2343f3..7662c9978ed 100644
--- a/mps/code/cbs.h
+++ b/mps/code/cbs.h
@@ -15,10 +15,7 @@
 
 
 typedef struct CBSStruct *CBS;
-typedef struct CBSBlockStruct *CBSBlock;
-typedef void (*CBSChangeSizeMethod)(CBS cbs, CBSBlock block,
-              Size oldSize, Size newSize);
-typedef Bool (*CBSIterateMethod)(CBS cbs, CBSBlock block, void *closureP);
+typedef Bool (*CBSIterateMethod)(CBS cbs, Addr base, Addr limit, void *closureP);
 
 
 #define CBSSig ((Sig)0x519CB599) /* SIGnature CBS */
@@ -27,11 +24,6 @@ typedef struct CBSStruct {
   SplayTreeStruct splayTree;
   Count splayTreeSize;
   Pool blockPool;
-  CBSChangeSizeMethod new;
-  CBSChangeSizeMethod delete;
-  CBSChangeSizeMethod grow;
-  CBSChangeSizeMethod shrink;
-  Size minSize;
   Align alignment;
   Bool fastFind;
   Bool inCBS; /* prevent reentrance */
@@ -40,44 +32,19 @@ typedef struct CBSStruct {
   Sig sig; /* sig at end because embeded */
 } CBSStruct;
 
-typedef struct CBSBlockStruct {
-  SplayNodeStruct splayNode;
-  Addr base;
-  Addr limit;
-  Size maxSize; /* accurate maximum block size of sub-tree */
-} CBSBlockStruct;
-
-
 extern Bool CBSCheck(CBS cbs);
-extern Bool CBSBlockCheck(CBSBlock block);
 
 extern Res CBSInit(Arena arena, CBS cbs, void *owner,
-                   CBSChangeSizeMethod new,
-                   CBSChangeSizeMethod delete,
-                   CBSChangeSizeMethod grow,
-                   CBSChangeSizeMethod shrink,
-                   Size minSize,
-                   Align alignment,
-                   Bool fastFind);
+                   Align alignment, Bool fastFind);
 extern void CBSFinish(CBS cbs);
 
-extern Res CBSInsert(CBS cbs, Addr base, Addr limit);
-extern Res CBSInsertReturningRange(Addr *baseReturn, Addr *limitReturn,
-                                   CBS cbs, Addr base, Addr limit);
-extern Res CBSDelete(CBS cbs, Addr base, Addr limit);
+extern Res CBSInsert(Addr *baseReturn, Addr *limitReturn,
+                     CBS cbs, Addr base, Addr limit);
+extern Res CBSDelete(Addr *baseReturn, Addr *limitReturn,
+                     CBS cbs, Addr base, Addr limit);
 extern void CBSIterate(CBS cbs, CBSIterateMethod iterate, void *closureP);
-extern void CBSIterateLarge(CBS cbs, CBSIterateMethod iterate, void *closureP);
-extern void CBSSetMinSize(CBS cbs, Size minSize);
 
 extern Res CBSDescribe(CBS cbs, mps_lib_FILE *stream);
-extern Res CBSBlockDescribe(CBSBlock block, mps_lib_FILE *stream);
-
-/* CBSBlockBase -- See <design/cbs/#function.cbs.block.base> */
-#define CBSBlockBase(block) ((block)->base)
-/* CBSBlockLimit -- See <design/cbs/#function.cbs.block.limit> */
-#define CBSBlockLimit(block) ((block)->limit)
-#define CBSBlockSize(block) AddrOffset((block)->base, (block)->limit)
-extern Size (CBSBlockSize)(CBSBlock block);
 
 typedef unsigned CBSFindDelete;
 enum {
@@ -88,11 +55,13 @@ enum {
 };
 
 extern Bool CBSFindFirst(Addr *baseReturn, Addr *limitReturn,
+                         Addr *oldBaseReturn, Addr *oldLimitReturn,
                          CBS cbs, Size size, CBSFindDelete findDelete);
 extern Bool CBSFindLast(Addr *baseReturn, Addr *limitReturn,
+                        Addr *oldBaseReturn, Addr *oldLimitReturn,
                         CBS cbs, Size size, CBSFindDelete findDelete);
-
 extern Bool CBSFindLargest(Addr *baseReturn, Addr *limitReturn,
+                           Addr *oldBaseReturn, Addr *oldLimitReturn,
                            CBS cbs, CBSFindDelete findDelete);
 
 
diff --git a/mps/code/cbstest.c b/mps/code/cbstest.c
index adb976081e2..3b72e875c28 100644
--- a/mps/code/cbstest.c
+++ b/mps/code/cbstest.c
@@ -20,28 +20,11 @@ SRCID(cbstest, "$Id$");
 
 #define ArraySize ((Size)123456)
 #define NOperations ((Size)125000)
-#define MinSize ((Size)120) /* Arbitrary size */
 #define Alignment ((Align)sizeof(void *))
 
 
 static Count NAllocateTried, NAllocateSucceeded, NDeallocateTried,
-  NDeallocateSucceeded, NNewBlocks, NDeleteBlocks, NGrowBlocks,
-  NShrinkBlocks;
-
-
-/* Used to predict which callbacks will be called, and with which values. */
-/* At most one callback of each type will be called. */
-typedef struct CallbackPredictionStruct {
-  Bool shouldBeCalled;
-  Size oldSize;
-  Addr base;
-  Addr limit;
-} CallbackPredictionStruct, *CallbackPrediction;
-
-static CallbackPredictionStruct CallbackNew;
-static CallbackPredictionStruct CallbackDelete;
-static CallbackPredictionStruct CallbackGrow;
-static CallbackPredictionStruct CallbackShrink;
+  NDeallocateSucceeded;
 
 
 typedef struct CheckCBSClosureStruct {
@@ -64,89 +47,14 @@ static Index (indexOfAddr)(Addr block, Addr a)
 }
 
 
-/* This function encapsulates the common tests for the callbacks. */
-
-static void testCallback(CBS cbs, CBSBlock cbsBlock,
-                         Size oldSize, Size newSize,
-                         CallbackPrediction prediction)
-{
-  Insist(CBSCheck(cbs));
-  Insist(CBSBlockCheck(cbsBlock));
-  Insist(prediction->shouldBeCalled);
-  Insist(oldSize == prediction->oldSize);
-
-  if (newSize == 0) {
-    Insist(prediction->base == 0);
-    Insist(prediction->limit == 0);
-  } else {
-    Insist(CBSBlockSize(cbsBlock) == newSize);
-    Insist(newSize == AddrOffset(prediction->base, prediction->limit));
-    Insist(CBSBlockBase(cbsBlock) == prediction->base);
-    Insist(CBSBlockLimit(cbsBlock) == prediction->limit);
-  }
-
-  prediction->shouldBeCalled = FALSE;
-}
-
-
-static void cbsNewCallback(CBS cbs, CBSBlock cbsBlock,
-                           Size oldSize, Size newSize)
+static Bool checkCBSAction(CBS cbs, Addr base, Addr limit, void *p)
 {
-  testCallback(cbs, cbsBlock, oldSize, newSize, &CallbackNew);
-  Insist(oldSize < cbs->minSize);
-  Insist(newSize >= cbs->minSize);
-
-  NNewBlocks++;
-}
-
-
-static void cbsDeleteCallback(CBS cbs, CBSBlock cbsBlock,
-                              Size oldSize, Size newSize)
-{
-  testCallback(cbs, cbsBlock, oldSize, newSize, &CallbackDelete);
-  Insist(oldSize >= cbs->minSize);
-  Insist(newSize < cbs->minSize);
-
-  NDeleteBlocks++;
-}
-
-
-static void cbsGrowCallback(CBS cbs, CBSBlock cbsBlock,
-                            Size oldSize, Size newSize)
-{
-  testCallback(cbs, cbsBlock, oldSize, newSize, &CallbackGrow);
-  Insist(oldSize >= cbs->minSize);
-  Insist(newSize >= cbs->minSize);
-  Insist(oldSize < newSize);
-
-  NGrowBlocks++;
-}
-
-
-static void cbsShrinkCallback(CBS cbs, CBSBlock cbsBlock,
-                              Size oldSize, Size newSize)
-{
-  testCallback(cbs, cbsBlock, oldSize, newSize, &CallbackShrink);
-  Insist(oldSize >= cbs->minSize);
-  Insist(newSize >= cbs->minSize);
-  Insist(oldSize > newSize);
-
-  NShrinkBlocks++;
-}
-
-
-static Bool checkCBSAction(CBS cbs, CBSBlock cbsBlock, void *p)
-{
-  Addr base, limit;
   CheckCBSClosure closure = (CheckCBSClosure)p;
 
   /* Don't need to check cbs every time */
   UNUSED(cbs);
   Insist(closure != NULL);
 
-  base = CBSBlockBase(cbsBlock);
-  limit = CBSBlockLimit(cbsBlock);
-
   if (base > closure->oldLimit) {
     Insist(BTIsSetRange(closure->allocTable,
                       indexOfAddr(closure->base, closure->oldLimit),
@@ -285,46 +193,14 @@ static void randomRange(Addr *baseReturn, Addr *limitReturn,
 }
 
 
-/* Set callback expectations */
-
-static void clearExpectations(void)
-{
-  CallbackNew.shouldBeCalled = FALSE;
-  CallbackDelete.shouldBeCalled = FALSE;
-  CallbackGrow.shouldBeCalled = FALSE;
-  CallbackShrink.shouldBeCalled = FALSE;
-}
-
-static void expectCallback(CallbackPrediction prediction,
-                           Size oldSize, Addr base, Addr limit)
-{
-  Insist(prediction->shouldBeCalled == FALSE);
-  Insist(base == (Addr)0 || limit > base);
-  Insist(oldSize != (Size)0 || base != (Addr)0);
-  Insist(base != (Addr)0 || limit == (Addr)0);
-
-  prediction->shouldBeCalled = TRUE;
-  prediction->oldSize = oldSize;
-  prediction->base = base;
-  prediction->limit = limit;
-}
-
-
-static void checkExpectations(void)
-{
-  Insist(!CallbackNew.shouldBeCalled);
-  Insist(!CallbackDelete.shouldBeCalled);
-  Insist(!CallbackGrow.shouldBeCalled);
-  Insist(!CallbackShrink.shouldBeCalled);
-} 
-
-
 static void allocate(CBS cbs, Addr block, BT allocTable,
                      Addr base, Addr limit)
 {
   Res res;
   Index ib, il;                  /* Indexed for base and limit */
   Bool isFree;
+  Addr oldBase, oldLimit;
+  Addr outerBase, outerLimit;    /* interval containing [ib, il) */
 
   ib = indexOfAddr(block, base);
   il = indexOfAddr(block, limit);
@@ -339,7 +215,6 @@ static void allocate(CBS cbs, Addr block, BT allocTable,
   NAllocateTried++;
 
   if (isFree) {
-    Addr outerBase, outerLimit;    /* interval containing [ib, il) */
     Size left, right, total;       /* Sizes of block and two fragments */
 
     outerBase =
@@ -350,39 +225,9 @@ static void allocate(CBS cbs, Addr block, BT allocTable,
     left = AddrOffset(outerBase, base);
     right = AddrOffset(limit, outerLimit);
     total = AddrOffset(outerBase, outerLimit);
-
-    /* based on detailed knowledge of CBS behaviour */
-    checkExpectations();
-    if (total >= MinSize && left < MinSize && right < MinSize) {
-      if (left == (Size)0 && right == (Size)0) {
-        expectCallback(&CallbackDelete, total, (Addr)0, (Addr)0);
-      } else if (left >= right) {
-        expectCallback(&CallbackDelete, total, outerBase, base);
-      } else {
-        expectCallback(&CallbackDelete, total, limit, outerLimit);
-      }
-    } else if (left >= MinSize && right >= MinSize) {
-      if (left >= right) {
-        expectCallback(&CallbackShrink, total, outerBase, base);
-        expectCallback(&CallbackNew, (Size)0, limit, outerLimit);
-      } else {
-        expectCallback(&CallbackNew, (Size)0, outerBase, base);
-        expectCallback(&CallbackShrink, total, limit, outerLimit);
-      }
-    } else if (total >= MinSize) {
-      if (left >= right) {
-        Insist(left >= MinSize);
-        Insist(right < MinSize);
-        expectCallback(&CallbackShrink, total, outerBase, base);
-      } else {
-        Insist(left < MinSize);
-        Insist(right >= MinSize);
-        expectCallback(&CallbackShrink, total, limit, outerLimit);
-      }
-    }
   }
 
-  res = CBSDelete(cbs, base, limit);
+  res = CBSDelete(&oldBase, &oldLimit, cbs, base, limit);
 
   if (!isFree) {
     die_expect((mps_res_t)res, MPS_RES_FAIL,
@@ -390,9 +235,10 @@ static void allocate(CBS cbs, Addr block, BT allocTable,
   } else { /* isFree */
     die_expect((mps_res_t)res, MPS_RES_OK,
                "failed to delete free block");
+    Insist(oldBase == outerBase);
+    Insist(oldLimit == outerLimit);
     NAllocateSucceeded++;
     BTSetRange(allocTable, ib, il);
-    checkExpectations();
   }
 }
 
@@ -439,36 +285,9 @@ static void deallocate(CBS cbs, Addr block, BT allocTable,
     left = AddrOffset(outerBase, base);
     right = AddrOffset(limit, outerLimit);
     total = AddrOffset(outerBase, outerLimit);
-
-    /* based on detailed knowledge of CBS behaviour */
-    checkExpectations();
-    if (total >= MinSize && left < MinSize && right < MinSize) {
-      if (left >= right)
-        expectCallback(&CallbackNew, left, outerBase, outerLimit);
-      else
-        expectCallback(&CallbackNew, right, outerBase, outerLimit);
-    } else if (left >= MinSize && right >= MinSize) {
-      if (left >= right) {
-        expectCallback(&CallbackDelete, right, (Addr)0, (Addr)0);
-        expectCallback(&CallbackGrow, left, outerBase, outerLimit);
-      } else {
-        expectCallback(&CallbackDelete, left, (Addr)0, (Addr)0);
-        expectCallback(&CallbackGrow, right, outerBase, outerLimit);
-      }
-    } else if (total >= MinSize) {
-      if (left >= right) {
-        Insist(left >= MinSize);
-        Insist(right < MinSize);
-        expectCallback(&CallbackGrow, left, outerBase, outerLimit);
-      } else {
-        Insist(left < MinSize);
-        Insist(right >= MinSize);
-        expectCallback(&CallbackGrow, right, outerBase, outerLimit);
-      }
-    }
   }
 
-  res = CBSInsertReturningRange(&freeBase, &freeLimit, cbs, base, limit);
+  res = CBSInsert(&freeBase, &freeLimit, cbs, base, limit);
 
   if (!isAllocated) {
     die_expect((mps_res_t)res, MPS_RES_FAIL,
@@ -479,7 +298,6 @@ static void deallocate(CBS cbs, Addr block, BT allocTable,
 
     NDeallocateSucceeded++;
     BTResRange(allocTable, ib, il);
-    checkExpectations();
     Insist(freeBase == outerBase);
     Insist(freeLimit == outerLimit);
   }
@@ -492,18 +310,17 @@ static void find(CBS cbs, void *block, BT alloc, Size size, Bool high,
   Bool expected, found;
   Index expectedBase, expectedLimit;
   Addr foundBase, foundLimit, remainderBase, remainderLimit;
+  Addr oldBase, oldLimit, origBase, origLimit;
   Size oldSize, newSize;
 
-  checkExpectations();
-
   expected = (high ? BTFindLongResRangeHigh : BTFindLongResRange)
                (&expectedBase, &expectedLimit, alloc,
                 (Index)0, (Index)ArraySize, (Count)size);
 
   if (expected) {
     oldSize = (expectedLimit - expectedBase) * Alignment;
-    remainderBase = addrOfIndex(block, expectedBase);
-    remainderLimit = addrOfIndex(block, expectedLimit);
+    remainderBase = origBase = addrOfIndex(block, expectedBase);
+    remainderLimit = origLimit = addrOfIndex(block, expectedLimit);
 
     switch(findDelete) {
     case CBSFindDeleteNONE: {
@@ -524,32 +341,24 @@ static void find(CBS cbs, void *block, BT alloc, Size size, Bool high,
 
     if (findDelete != CBSFindDeleteNONE) {
       newSize = AddrOffset(remainderBase, remainderLimit);
-
-      if (oldSize >= MinSize) {
-        if (newSize == 0)
-          expectCallback(&CallbackDelete, oldSize, (Addr)0, (Addr)0);
-        else if (newSize < MinSize)
-          expectCallback(&CallbackDelete, oldSize,
-                         remainderBase, remainderLimit);
-        else
-          expectCallback(&CallbackShrink, oldSize,
-                         remainderBase, remainderLimit);
-      }
     }
   }
 
   found = (high ? CBSFindLast : CBSFindFirst)
-    (&foundBase, &foundLimit, cbs, size * Alignment, findDelete);
+    (&foundBase, &foundLimit, &oldBase, &oldLimit, 
+     cbs, size * Alignment, findDelete);
 
   Insist(found == expected);
 
   if (found) {
     Insist(expectedBase == indexOfAddr(block, foundBase));
     Insist(expectedLimit == indexOfAddr(block, foundLimit));
-    checkExpectations();
 
-    if (findDelete != CBSFindDeleteNONE)
+    if (findDelete != CBSFindDeleteNONE) {
+      Insist(oldBase == origBase);
+      Insist(oldLimit == origLimit);
       BTSetRange(alloc, expectedBase, expectedLimit);
+    }
   }
 
   return;
@@ -576,10 +385,7 @@ extern int main(int argc, char *argv[])
   randomize(argc, argv);
 
   NAllocateTried = NAllocateSucceeded = NDeallocateTried =
-    NDeallocateSucceeded = NNewBlocks = NDeleteBlocks =
-    NGrowBlocks = NShrinkBlocks = 0;
-
-  clearExpectations();
+    NDeallocateSucceeded = 0;
 
   die(mps_arena_create(&mpsArena, mps_arena_class_vm(), testArenaSIZE),
       "mps_arena_create");
@@ -588,10 +394,7 @@ extern int main(int argc, char *argv[])
   die((mps_res_t)BTCreate(&allocTable, arena, ArraySize),
       "failed to create alloc table");
 
-  die((mps_res_t)CBSInit(arena, &cbsStruct, NULL, &cbsNewCallback,
-                         &cbsDeleteCallback, &cbsGrowCallback,
-                         &cbsShrinkCallback, MinSize,
-                         Alignment, TRUE),
+  die((mps_res_t)CBSInit(arena, &cbsStruct, NULL, Alignment, TRUE),
       "failed to initialise CBS");
   cbs = &cbsStruct;
 
@@ -636,8 +439,6 @@ extern int main(int argc, char *argv[])
       checkCBS(cbs, allocTable, dummyBlock);
   }
 
-  checkExpectations();
-
   /* CBSDescribe prints a very long line. */
   /* CBSDescribe(cbs, mps_lib_get_stdout()); */
 
@@ -645,10 +446,6 @@ extern int main(int argc, char *argv[])
   printf("Number of allocations succeeded: %ld\n", NAllocateSucceeded);
   printf("Number of deallocations attempted: %ld\n", NDeallocateTried);
   printf("Number of deallocations succeeded: %ld\n", NDeallocateSucceeded);
-  printf("Number of new large blocks: %ld\n", NNewBlocks);
-  printf("Number of deleted large blocks: %ld\n", NDeleteBlocks);
-  printf("Number of grown large blocks: %ld\n", NGrowBlocks);
-  printf("Number of shrunk large blocks: %ld\n", NShrinkBlocks);
   printf("%s: Conclusion: Failed to find any defects.\n", argv[0]);
   return 0;
 }