/* cbs.c: COALESCING BLOCK STRUCTURE IMPLEMENTATION
 *
 * $Id: //info.ravenbrook.com/project/mps/version/1.104/code/cbs.c#1 $
 * Copyright (c) 2001 Ravenbrook Limited.  See end of file for license.
 *
 * .intro: This is a portable implementation of coalescing block
 * structures.
 *
 * .purpose: CBSs are used to manage potentially unbounded
 * collections of memory blocks.
 *
 * .sources: <design/cbs/>.
 */

#include "cbs.h"
#include "splay.h"
#include "meter.h"
#include "poolmfs.h"
#include "mpm.h"

SRCID(cbs, "$Id: //info.ravenbrook.com/project/mps/version/1.104/code/cbs.c#1 $");


/* See <design/cbs/#align> */
#define cbsMinimumAlignment ((Align)sizeof(void *))

#define cbsOfSplayTree(tree) PARENT(CBSStruct, splayTree, (tree))
#define cbsBlockOfSplayNode(node) PARENT(CBSBlockStruct, splayNode, (node))
#define splayTreeOfCBS(tree) (&((cbs)->splayTree))
#define splayNodeOfCBSBlock(block) (&((block)->splayNode))
#define keyOfCBSBlock(block) ((void *)&((block)->base))


/* CBSEmergencyBlock* -- Getters and setters for emergency blocks
 *
 * See <design/cbs/#impl.low-mem.inline.block>.
 */

#define CBSEmergencyBlockBase(block) ((Addr)(block))
#define CBSEmergencyBlockLimit(block) ((Addr)((block)[1]))
#define CBSEmergencyBlockSize(block) \
  (AddrOffset(CBSEmergencyBlockBase(block), CBSEmergencyBlockLimit(block)))
#define CBSEmergencyBlockNext(block) ((CBSEmergencyBlock)((block)[0]))

#define CBSEmergencyBlockSetNext(block, next) \
  BEGIN (block)[0] = (void *)(next); END
#define CBSEmergencyBlockSetLimit(block, limit) \
  BEGIN (block)[1] = (void *)(limit); END


/* CBSEmergencyGrain* -- Getters and setters for emergency grains
 *
 * See <design/cbs/#impl.low-mem.inline.grain>.
 */

#define CBSEmergencyGrainBase(grain) ((Addr)(grain))
#define CBSEmergencyGrainLimit(cbs, grain) \
  AddrAdd(CBSEmergencyGrainBase(grain), CBSEmergencyGrainSize(cbs))
#define CBSEmergencyGrainSize(cbs) ((cbs)->alignment)
#define CBSEmergencyGrainNext(grain) ((CBSEmergencyGrain)((grain)[0]))

#define CBSEmergencyGrainSetNext(grain, next) \
  BEGIN (grain)[0] = (void *)(next); END


static CBSEmergencyBlock CBSEmergencyBlockInit(Addr base, Addr limit)
{
  CBSEmergencyBlock block = (CBSEmergencyBlock)base;
  CBSEmergencyBlockSetNext(block, NULL);
  CBSEmergencyBlockSetLimit(block, limit);
  return block;
}

static CBSEmergencyGrain CBSEmergencyGrainInit(CBS cbs, Addr base, Addr limit)
{
  CBSEmergencyGrain grain = (CBSEmergencyGrain)base;
  AVER(AddrOffset(base, limit) == CBSEmergencyGrainSize(cbs));
  CBSEmergencyGrainSetNext(grain, NULL);
  return grain;
}


/* CBSEnter, CBSLeave -- Avoid re-entrance
 *
 * .enter-leave: The callbacks are restricted in what they may call.
 * These functions enforce this.
 *
 * .enter-leave.simple: Simple queries may be called from callbacks.
 */

static void CBSEnter(CBS cbs)
{
  /* Don't need to check as always called from interface function. */
  AVER(!cbs->inCBS);
  cbs->inCBS = TRUE;
  return;
}

static void CBSLeave(CBS cbs)
{
  /* Don't need to check as always called from interface function. */
  AVER(cbs->inCBS);
  cbs->inCBS = FALSE;
  return;
}


/* CBSCheck -- Check CBS */

Bool CBSCheck(CBS cbs)
{
  /* See .enter-leave.simple. */
  CHECKS(CBS, cbs);
  CHECKL(cbs != NULL);
  CHECKL(SplayTreeCheck(splayTreeOfCBS(cbs)));
  /* nothing to check about splayTreeSize */
  CHECKD(Pool, cbs->blockPool);
  CHECKL(BoolCheck(cbs->mayUseInline));
  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));
  CHECKL(cbs->mayUseInline || cbs->emergencyBlockList == NULL);
  CHECKL(cbs->mayUseInline || cbs->emergencyGrainList == NULL);
  /* See <design/cbs/#align> */
  CHECKL(!cbs->mayUseInline ||
         AlignIsAligned(cbs->alignment, cbsMinimumAlignment));
  /* can't check emergencyBlockList or emergencyGrainList more */
  /* Checking eblSize and eglSize is too laborious without a List ADT */
  /* No MeterCheck */

  return TRUE;
}


/* CBSBlockCheck -- See <design/cbs/#function.cbs.block.check> */

Bool CBSBlockCheck(CBSBlock block)
{
  /* See .enter-leave.simple. */
  UNUSED(block); /* Required because there is no signature */
  CHECKL(block != NULL);
  CHECKL(SplayNodeCheck(splayNodeOfCBSBlock(block)));

  /* If the block is in the middle of being deleted, */
  /* the pointers will be equal. */
  CHECKL(CBSBlockBase(block) <= CBSBlockLimit(block));
  /* Can't check maxSize because it may be invalid at the time */
  return TRUE;
}


/* CBSBlockSize -- see <design/cbs/#function.cbs.block.size> */

Size (CBSBlockSize)(CBSBlock block)
{
  /* See .enter-leave.simple. */
  return CBSBlockSize(block);
}


/* cbsSplayCompare -- Compare key to [base,limit)
 *
 * See <design/splay/#type.splay.compare.method>
 */

static Compare cbsSplayCompare(void *key, SplayNode node)
{
  Addr base1, base2, limit2;
  CBSBlock cbsBlock;

  /* NULL key compares less than everything. */
  if (key == NULL)
    return CompareLESS;

  AVER(node != NULL);

  base1 = *(Addr *)key;
  cbsBlock = cbsBlockOfSplayNode(node);
  base2 = cbsBlock->base;
  limit2 = cbsBlock->limit;

  if (base1 < base2)
    return CompareLESS;
  else if (base1 >= limit2)
    return CompareGREATER;
  else
    return CompareEQUAL;
}


/* cbsTestNode, cbsTestTree -- test for nodes larger than the S parameter */

static Bool cbsTestNode(SplayTree tree, SplayNode node,
                        void *closureP, unsigned long closureS)
{
  Size size;
  CBSBlock block;

  AVERT(SplayTree, tree);
  AVERT(SplayNode, node);
  AVER(closureP == NULL);
  AVER(closureS > 0);
  AVER(cbsOfSplayTree(tree)->fastFind);

  size = (Size)closureS;
  block = cbsBlockOfSplayNode(node);

  return CBSBlockSize(block) >= size;
}

static Bool cbsTestTree(SplayTree tree, SplayNode node,
                        void *closureP, unsigned long closureS)
{
  Size size;
  CBSBlock block;

  AVERT(SplayTree, tree);
  AVERT(SplayNode, node);
  AVER(closureP == NULL);
  AVER(closureS > 0);
  AVER(cbsOfSplayTree(tree)->fastFind);

  size = (Size)closureS;
  block = cbsBlockOfSplayNode(node);

  return block->maxSize >= size;
}


/* cbsUpdateNode -- update size info after restructuring */

static void cbsUpdateNode(SplayTree tree, SplayNode node,
                          SplayNode leftChild, SplayNode rightChild)
{
  Size maxSize;
  CBSBlock block;

  AVERT(SplayTree, tree);
  AVERT(SplayNode, node);
  if (leftChild != NULL)
    AVERT(SplayNode, leftChild);
  if (rightChild != NULL)
    AVERT(SplayNode, rightChild);
  AVER(cbsOfSplayTree(tree)->fastFind);

  block = cbsBlockOfSplayNode(node);
  maxSize = CBSBlockSize(block);

  if (leftChild != NULL) {
    Size size = cbsBlockOfSplayNode(leftChild)->maxSize;
    if (size > maxSize)
      maxSize = size;
  }

  if (rightChild != NULL) {
    Size size = cbsBlockOfSplayNode(rightChild)->maxSize;
    if (size > maxSize)
      maxSize = size;
  }

  block->maxSize = maxSize;
}


/* CBSInit -- Initialise a CBS structure
 *
 * 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 mayUseInline, Bool fastFind)
{
  Res res;

  AVERT(Arena, arena);
  AVER(new == NULL || FUNCHECK(new));
  AVER(delete == NULL || FUNCHECK(delete));
  AVER(BoolCheck(mayUseInline));
  if (mayUseInline) {
    /* See <design/cbs/#align> */
    if (!AlignIsAligned(alignment, cbsMinimumAlignment))
      return ResPARAM;
  }

  SplayTreeInit(splayTreeOfCBS(cbs), &cbsSplayCompare,
                fastFind ? &cbsUpdateNode : NULL);
  res = PoolCreate(&(cbs->blockPool), arena, PoolClassMFS(),
                   sizeof(CBSBlockStruct) * 64, sizeof(CBSBlockStruct));
  if (res != ResOK)
    return res;
  cbs->splayTreeSize = 0;

  cbs->new = new;
  cbs->delete = delete;
  cbs->grow = grow;
  cbs->shrink = shrink;
  cbs->minSize = minSize;
  cbs->mayUseInline = mayUseInline;
  cbs->fastFind = fastFind;
  cbs->alignment = alignment;
  cbs->inCBS = TRUE;
  cbs->emergencyBlockList = NULL;
  cbs->eblSize = 0;
  cbs->emergencyGrainList = NULL;
  cbs->eglSize = 0;

  METER_INIT(cbs->splaySearch, "size of splay tree", (void *)cbs);
  METER_INIT(cbs->eblSearch, "size of emergencyBlockList", (void *)cbs);
  METER_INIT(cbs->eglSearch, "size of emergencyGrainList", (void *)cbs);

  cbs->sig = CBSSig;

  AVERT(CBS, cbs);
  EVENT_PP(CBSInit, cbs, owner);
  UNUSED(owner); /* @@@@ hack: unused in non-event varieties */
  CBSLeave(cbs);
  return ResOK;
}


/* CBSFinish -- Finish a CBS structure
 *
 * See <design/cbs/#function.cbs.finish>.
 */

void CBSFinish(CBS cbs)
{
  AVERT(CBS, cbs);
  CBSEnter(cbs);

  METER_EMIT(&cbs->splaySearch);
  METER_EMIT(&cbs->eblSearch);
  METER_EMIT(&cbs->eglSearch);

  cbs->sig = SigInvalid;

  SplayTreeFinish(splayTreeOfCBS(cbs));
  PoolDestroy(cbs->blockPool);
  cbs->emergencyBlockList = NULL;
  cbs->emergencyGrainList = NULL;
}


/* Node change operators
 *
 * These four functions are called whenever blocks are created,
 * destroyed, grow, or shrink.  They report to the client, and
 * perform the necessary memory management.  They are responsible
 * for the client interaction logic.
 */

static void cbsBlockDelete(CBS cbs, CBSBlock block)
{
  Res res;
  Size oldSize;

  AVERT(CBS, cbs);
  AVERT(CBSBlock, block);

  oldSize = CBSBlockSize(block);

  METER_ACC(cbs->splaySearch, cbs->splayTreeSize);
  res = SplayTreeDelete(splayTreeOfCBS(cbs), splayNodeOfCBSBlock(block),
                        keyOfCBSBlock(block));
  AVER(res == ResOK); /* Must be possible to delete node */
  STATISTIC(--cbs->splayTreeSize);

  /* 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;
}

static void cbsBlockShrink(CBS cbs, CBSBlock block, Size oldSize)
{
  Size newSize;

  AVERT(CBS, cbs);
  AVERT(CBSBlock, block);

  newSize = CBSBlockSize(block);
  AVER(oldSize > newSize);

  if (cbs->fastFind) {
    SplayNodeRefresh(splayTreeOfCBS(cbs), splayNodeOfCBSBlock(block),
                     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)
{
  Size newSize;

  AVERT(CBS, cbs);
  AVERT(CBSBlock, block);

  newSize = CBSBlockSize(block);
  AVER(oldSize < newSize);

  if (cbs->fastFind) {
    SplayNodeRefresh(splayTreeOfCBS(cbs), splayNodeOfCBSBlock(block),
                     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)
{
  CBSBlock block;
  Res res;
  Addr p;
  Size newSize;

  AVERT(CBS, cbs);

  res = PoolAlloc(&p, cbs->blockPool, sizeof(CBSBlockStruct),
                  /* withReservoirPermit */ FALSE);
  if (res != ResOK)
    goto failPoolAlloc;
  block = (CBSBlock)p;

  SplayNodeInit(splayNodeOfCBSBlock(block));
  block->base = base;
  block->limit = limit;
  newSize = CBSBlockSize(block);
  block->maxSize = newSize;

  AVERT(CBSBlock, block);

  METER_ACC(cbs->splaySearch, cbs->splayTreeSize);
  res = SplayTreeInsert(splayTreeOfCBS(cbs), splayNodeOfCBSBlock(block),
                        keyOfCBSBlock(block));
  AVER(res == ResOK);
  STATISTIC(++cbs->splayTreeSize);

  if (cbs->new != NULL && newSize >= cbs->minSize)
    (*(cbs->new))(cbs, block, (Size)0, newSize);

  return ResOK;

failPoolAlloc:
  AVER(res != ResOK);
  return res;
}


/* cbsInsertIntoTree -- Insert a range into the splay tree */

static Res cbsInsertIntoTree(Addr *baseReturn, Addr *limitReturn,
                             CBS cbs, Addr base, Addr limit)
{
  Res res;
  Addr newBase, newLimit;
  SplayNode leftSplay, rightSplay;
  CBSBlock leftCBS, rightCBS;
  Bool leftMerge, rightMerge;
  Size oldSize;

  AVERT(CBS, cbs);
  AVER(base != (Addr)0);
  AVER(base < limit);
  AVER(AddrIsAligned(base, cbs->alignment));
  AVER(AddrIsAligned(limit, cbs->alignment));

  METER_ACC(cbs->splaySearch, cbs->splayTreeSize);
  res = SplayTreeNeighbours(&leftSplay, &rightSplay,
                            splayTreeOfCBS(cbs), (void *)&base);
  if (res != ResOK)
    goto fail;

  if (leftSplay == NULL) {
    leftCBS = NULL;
    leftMerge = FALSE;
  } else {
    leftCBS = cbsBlockOfSplayNode(leftSplay);
    AVER(leftCBS->limit <= base); /* by cbsSplayCompare */
    leftMerge = leftCBS->limit == base;
  }

  if (rightSplay == NULL) {
    rightCBS = NULL;
    rightMerge = FALSE;
  } else {
    rightCBS = cbsBlockOfSplayNode(rightSplay);
    if (rightCBS != NULL && limit > rightCBS->base) {
      res = ResFAIL;
      goto fail;
    }
    rightMerge = rightCBS->base == limit;
  }

  newBase = leftMerge ? CBSBlockBase(leftCBS) : base;
  newLimit = rightMerge ? CBSBlockLimit(rightCBS) : limit;

  if (leftMerge) {
    if (rightMerge) {
      Size oldLeftSize = CBSBlockSize(leftCBS);
      Size oldRightSize = CBSBlockSize(rightCBS);

      /* must block larger neighbour and destroy smaller neighbour; */
      /* see <design/cbs/#function.cbs.insert.callback> */
      if (oldLeftSize >= oldRightSize) {
        Addr rightLimit = rightCBS->limit;
        cbsBlockDelete(cbs, rightCBS);
        leftCBS->limit = rightLimit;
        cbsBlockGrow(cbs, leftCBS, oldLeftSize);
      } else { /* left block is smaller */
        Addr leftBase = leftCBS->base;
        cbsBlockDelete(cbs, leftCBS);
        rightCBS->base = leftBase;
        cbsBlockGrow(cbs, rightCBS, oldRightSize);
      }
    } else { /* leftMerge, !rightMerge */
      oldSize = CBSBlockSize(leftCBS);
      leftCBS->limit = limit;
      cbsBlockGrow(cbs, leftCBS, oldSize);
    }
  } else { /* !leftMerge */
    if (rightMerge) {
      oldSize = CBSBlockSize(rightCBS);
      rightCBS->base = base;
      cbsBlockGrow(cbs, rightCBS, oldSize);
    } else { /* !leftMerge, !rightMerge */
      res = cbsBlockNew(cbs, base, limit);
      if (res != ResOK)
        goto fail;
    }
  }

  AVER(newBase <= base);
  AVER(newLimit >= limit);
  *baseReturn = newBase;
  *limitReturn = newLimit;

  return ResOK;

fail:
  AVER(res != ResOK);
  return res;
}


/* cbsCoalesceWithEmergencyLists -- coalesce received range with EBL and EGL
 *
 * Attempts to extend the range about to be freed by adding ranges from
 * the emergency lists.  May remove blocks from the emergency list.
 */

static Res cbsCoalesceWithEmergencyLists(Addr *baseIO, Addr *limitIO, CBS cbs)
{
  Addr base, limit;
  Count nCoalescences = 0;

  AVER(baseIO != NULL);
  AVER(limitIO != NULL);
  AVERT(CBS, cbs);
  AVER(cbs->mayUseInline);

  base = *baseIO;
  limit = *limitIO;
  AVER(base < limit);

  if (cbs->emergencyBlockList != NULL) {
    CBSEmergencyBlock prev, block, next;
    Addr blockBase, blockLimit;

    METER_ACC(cbs->eblSearch, cbs->eblSize);
    for(block = cbs->emergencyBlockList, prev = NULL;
        block != NULL && CBSEmergencyBlockBase(block) <= limit;
        block = CBSEmergencyBlockNext(block)) {

      blockBase = CBSEmergencyBlockBase(block);
      blockLimit = CBSEmergencyBlockLimit(block);
      AVER(blockBase < blockLimit);

      if (prev != NULL)
        AVER(CBSEmergencyBlockLimit(prev) < blockBase);

      if (blockLimit == base) {
        base = blockBase;
        next = CBSEmergencyBlockNext(block);
        if (prev == NULL)
          cbs->emergencyBlockList = next;
        else
          CBSEmergencyBlockSetNext(prev, next);
        ++nCoalescences;
        STATISTIC(--cbs->eblSize);
        AVER(cbs->emergencyBlockList != NULL || cbs->eblSize == 0);
      } else if (blockBase == limit) {
        limit = blockLimit;
        next = CBSEmergencyBlockNext(block);
        if (prev == NULL)
          cbs->emergencyBlockList = next;
        else
          CBSEmergencyBlockSetNext(prev, next);
        ++nCoalescences;
        STATISTIC(--cbs->eblSize);
        AVER(cbs->emergencyBlockList != NULL || cbs->eblSize == 0);
        /* For loop will stop at next test */
      } else if (blockLimit > base) {
        return ResFAIL; /* range intersects block */
      } else {
        prev = block; /* Only move prev if we didn't delete */
      }
    }
    /* block's next is still valid, even if it's been coalesced */
  }
 
  if (cbs->emergencyGrainList != NULL) {
    CBSEmergencyGrain prev, grain, next;
    Addr grainBase, grainLimit;

    METER_ACC(cbs->eglSearch, cbs->eglSize);
    for(grain = cbs->emergencyGrainList, prev = NULL;
        grain != NULL && CBSEmergencyGrainBase(grain) <= limit &&
          nCoalescences < 2;
        grain = CBSEmergencyGrainNext(grain)) {
      grainBase = CBSEmergencyGrainBase(grain);
      grainLimit = CBSEmergencyGrainLimit(cbs, grain);
      AVER(grainBase < grainLimit);

      if (prev != NULL)
        AVER(CBSEmergencyGrainLimit(cbs, prev) < grainBase);

      if (grainLimit == base) {
        base = grainBase;
        next = CBSEmergencyGrainNext(grain);
        if (prev == NULL)
          cbs->emergencyGrainList = next;
        else
          CBSEmergencyGrainSetNext(prev, next);
        ++nCoalescences;
        STATISTIC(--cbs->eglSize);
        AVER(cbs->emergencyGrainList != NULL || cbs->eglSize == 0);
      } else if (grainBase == limit) {
        limit = grainLimit;
        next = CBSEmergencyGrainNext(grain);
        if (prev == NULL)
          cbs->emergencyGrainList = next;
        else
          CBSEmergencyGrainSetNext(prev, next);
        ++nCoalescences;
        STATISTIC(--cbs->eglSize);
        AVER(cbs->emergencyGrainList != NULL || cbs->eglSize == 0);
        break;
      } else if (grainLimit > base) {
        return ResFAIL; /* range intersects grain */
      } else {
        prev = grain;
      }
    }
    /* grain's next is still valid, even if it's been coalesced */
  }

  /* Because the lists are known to have isolated ranges, there can */
  /* be no more than 2 coalescences. */
  AVER(nCoalescences <= 2);

  *baseIO = base;
  *limitIO = limit;
  return ResOK;
}


/* cbsAddToEmergencyLists -- Adds range to emergency lists
 *
 * The range must be unadjacent to any items on the emergency lists.
 */

static Res cbsAddToEmergencyLists(CBS cbs, Addr base, Addr limit)
{
  Res res = ResOK;
  Size size;

  AVERT(CBS, cbs);
  AVER(base < limit);
  AVER(cbs->mayUseInline);

  size = AddrOffset(base, limit);
  /* Use the block list if possible.  See <design/cbs/#align>. */
  if (size > cbsMinimumAlignment) {
    CBSEmergencyBlock prev, block, new;
    new = CBSEmergencyBlockInit(base, limit);
    METER_ACC(cbs->eblSearch, cbs->eblSize);
    for(prev = NULL, block = cbs->emergencyBlockList;
        block != NULL && CBSEmergencyBlockBase(block) < base;
        prev = block, block = CBSEmergencyBlockNext(block)) {
      if (prev != NULL)
        AVER(CBSEmergencyBlockLimit(prev) < CBSEmergencyBlockBase(block));
      AVER(CBSEmergencyBlockBase(block) < CBSEmergencyBlockLimit(block));
    }

    if (prev != NULL && block != NULL)
      AVER(CBSEmergencyBlockLimit(prev) < CBSEmergencyBlockBase(block));
     
    /* check ordering: prev ... new ... block */
    if (prev != NULL && CBSEmergencyBlockLimit(prev) >= base)
      return ResFAIL; /* range intersects with existing block */

    if (block != NULL && limit >= CBSEmergencyBlockBase(block))
      return ResFAIL; /* range intersects with existing block */

    if (prev == NULL)
      cbs->emergencyBlockList = new;
    else
      CBSEmergencyBlockSetNext(prev, new);
    CBSEmergencyBlockSetNext(new, block); /* may be NULL */
    STATISTIC(++cbs->eblSize);
  } else if (size == CBSEmergencyGrainSize(cbs)) {
    CBSEmergencyGrain prev, grain, new;
    new = CBSEmergencyGrainInit(cbs, base, limit);
    METER_ACC(cbs->eglSearch, cbs->eglSize);
    for(prev = NULL, grain = cbs->emergencyGrainList;
        grain != NULL && CBSEmergencyGrainBase(grain) < base;
        prev = grain, grain = CBSEmergencyGrainNext(grain)) {
      if (prev != NULL)
        AVER(CBSEmergencyGrainLimit(cbs, prev) <
             CBSEmergencyGrainBase(grain));
    }

    if (prev != NULL && grain != NULL)
      AVER(CBSEmergencyGrainLimit(cbs, prev) < CBSEmergencyGrainBase(grain));
     
    /* check ordering: prev ... new ... grain */
    if (prev != NULL && CBSEmergencyGrainLimit(cbs, prev) >= base)
      return ResFAIL; /* range intersects with existing grain */

    if (grain != NULL && limit >= CBSEmergencyGrainBase(grain))
      return ResFAIL; /* range intersects with existing grain */

    if (prev == NULL)
      cbs->emergencyGrainList = new;
    else
      CBSEmergencyGrainSetNext(prev, new);
    CBSEmergencyGrainSetNext(new, grain); /* may be NULL */
    STATISTIC(++cbs->eglSize);
  } else {
    NOTREACHED;
    res = ResFAIL; /* in case AVERs are compiled out */
  }

  return res;
}


/* cbsFlushEmergencyLists -- Attempt to move ranges to CBS proper */

static void cbsFlushEmergencyLists(CBS cbs)
{
  Res res = ResOK;
  Addr base, limit;

  AVERT(CBS, cbs);
  AVER(cbs->mayUseInline);

  if (cbs->emergencyBlockList != NULL) {
    CBSEmergencyBlock block;
    METER_ACC(cbs->eblSearch, cbs->eblSize);
    for(block = cbs->emergencyBlockList;
        block != NULL;
        block = CBSEmergencyBlockNext(block)) {
      AVER(CBSEmergencyBlockBase(block) < CBSEmergencyBlockLimit(block));
      res = cbsInsertIntoTree(&base, &limit,
                              cbs, CBSEmergencyBlockBase(block),
                              CBSEmergencyBlockLimit(block));
      if (res == ResOK) {
        AVER(cbs->emergencyBlockList == block);
        /* Emergency block is isolated in CBS */
        AVER(base == CBSEmergencyBlockBase(block));
        AVER(limit == CBSEmergencyBlockLimit(block));

        cbs->emergencyBlockList = CBSEmergencyBlockNext(block);
        STATISTIC(--cbs->eblSize);
        AVER(cbs->emergencyBlockList != NULL || cbs->eblSize == 0);
      } else {
        AVER(ResIsAllocFailure(res));
        goto done;
      }
    }
  }

  if (cbs->emergencyGrainList != NULL) {
    CBSEmergencyGrain grain;
    METER_ACC(cbs->eglSearch, cbs->eglSize);
    for(grain = cbs->emergencyGrainList;
        grain != NULL;
        grain = CBSEmergencyGrainNext(grain)) {
      res = cbsInsertIntoTree(&base, &limit,
                              cbs, CBSEmergencyGrainBase(grain),
                              CBSEmergencyGrainLimit(cbs, grain));
      if (res == ResOK) {
        AVER(cbs->emergencyGrainList == grain);
        /* Emergency grain is isolated in CBS */
        AVER(base == CBSEmergencyGrainBase(grain));
        AVER(limit == CBSEmergencyGrainLimit(cbs, grain));

        cbs->emergencyGrainList = CBSEmergencyGrainNext(grain);
        STATISTIC(--cbs->eglSize);
        AVER(cbs->emergencyGrainList != NULL || cbs->eglSize == 0);
      } else {
        AVER(ResIsAllocFailure(res));
        goto done;
      }
    }
  }

  done:
  return;
}


/* CBSInsert -- Insert a range into the CBS
 *
 * See <design/cbs/#functions.cbs.insert>.
 */

Res CBSInsertReturningRange(Addr *baseReturn, Addr *limitReturn,
                            CBS cbs, Addr base, Addr limit)
{
  Addr newBase, newLimit;
  Res res;

  AVERT(CBS, cbs);
  CBSEnter(cbs);

  AVER(base != (Addr)0);
  AVER(base < limit);
  AVER(AddrIsAligned(base, cbs->alignment));
  AVER(AddrIsAligned(limit, cbs->alignment));

  if (cbs->mayUseInline) {
    newBase = base;
    newLimit = limit;

    res = cbsCoalesceWithEmergencyLists(&newBase, &newLimit, cbs);
    if (res != ResOK) {
      AVER(res == ResFAIL);
      goto done;
    }

    res = cbsInsertIntoTree(&newBase, &newLimit, cbs, newBase, newLimit);
    /* newBase and newLimit only changed if res == ResOK */

    if (ResIsAllocFailure(res)) {
      res = cbsAddToEmergencyLists(cbs, newBase, newLimit);
      if (res != ResOK) {
        AVER(res == ResFAIL);
        goto done;
      }
    } else {
      /* Attempt to clear emergency lists */
      cbsFlushEmergencyLists(cbs);
    }
  } else {
    res = cbsInsertIntoTree(&newBase, &newLimit, cbs, base, limit);
  }

  done:
  if (res == ResOK) {
    AVER(newBase <= base);
    AVER(limit <= newLimit);
    *baseReturn = newBase;
    *limitReturn = newLimit;
  }

  CBSLeave(cbs);
  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)
{
  Res res;
  CBSBlock cbsBlock;
  SplayNode splayNode;
  Size oldSize;

  /* parameters already checked */

  METER_ACC(cbs->splaySearch, cbs->splayTreeSize);
  res = SplayTreeSearch(&splayNode, splayTreeOfCBS(cbs), (void *)&base);
  if (res != ResOK)
    goto failSplayTreeSearch;
  cbsBlock = cbsBlockOfSplayNode(splayNode);

  if (limit > cbsBlock->limit) {
    res = ResFAIL;
    goto failLimitCheck;
  }

  if (base == cbsBlock->base) {
    if (limit == cbsBlock->limit) { /* entire block */
      cbsBlockDelete(cbs, cbsBlock);
    } else { /* remaining fragment at right */
      AVER(limit < cbsBlock->limit);
      oldSize = CBSBlockSize(cbsBlock);
      cbsBlock->base = limit;
      cbsBlockShrink(cbs, cbsBlock, oldSize);
    }
  } else {
    AVER(base > cbsBlock->base);
    if (limit == cbsBlock->limit) { /* remaining fragment at left */
      oldSize = CBSBlockSize(cbsBlock);
      cbsBlock->limit = base;
      cbsBlockShrink(cbs, cbsBlock, oldSize);
    } else { /* two remaining fragments */
      Size leftNewSize = AddrOffset(cbsBlock->base, base);
      Size rightNewSize = AddrOffset(limit, cbsBlock->limit);
      /* must shrink larger fragment and create smaller; */
      /* see <design/cbs/#function.cbs.delete.callback> */
      if (leftNewSize >= rightNewSize) {
        Addr oldLimit = cbsBlock->limit;
        AVER(limit < cbsBlock->limit);
        oldSize = CBSBlockSize(cbsBlock);
        cbsBlock->limit = base;
        cbsBlockShrink(cbs, cbsBlock, oldSize);
        res = cbsBlockNew(cbs, limit, oldLimit);
        if (res != ResOK) {
          AVER(ResIsAllocFailure(res));
          if (cbs->mayUseInline) {
            res = cbsAddToEmergencyLists(cbs, limit, oldLimit);
            AVER(res == ResOK);
          } else {
            goto failNew;
          }
        }
      } else { /* right fragment is larger */
        Addr oldBase = cbsBlock->base;
        AVER(base > cbsBlock->base);
        oldSize = CBSBlockSize(cbsBlock);
        cbsBlock->base = limit;
        cbsBlockShrink(cbs, cbsBlock, oldSize);
        res = cbsBlockNew(cbs, oldBase, base);
        if (res != ResOK) {
          AVER(ResIsAllocFailure(res));
          if (cbs->mayUseInline) {
            res = cbsAddToEmergencyLists(cbs, oldBase, base);
            AVER(res == ResOK);
          } else {
            goto failNew;
          }
        }
      }
    }
  }

  return ResOK;

failNew:
failLimitCheck:
failSplayTreeSearch:
  AVER(res != ResOK);
  return res;
}


static Res cbsDeleteFromEmergencyBlockList(CBS cbs, Addr base, Addr limit)
{
  Res res;
  Addr blockBase, blockLimit;
  CBSEmergencyBlock prev, block;

  /* parameters already checked in caller */
  AVER(cbs->mayUseInline);

  METER_ACC(cbs->eblSearch, cbs->eblSize);
  for(prev = NULL, block = cbs->emergencyBlockList;
      block != NULL && CBSEmergencyBlockLimit(block) < limit;
      prev = block, block = CBSEmergencyBlockNext(block)) {
    AVER(CBSEmergencyBlockBase(block) < CBSEmergencyBlockLimit(block));
    if (CBSEmergencyBlockBase(block) >= base)
      return ResFAIL;
    if (prev != NULL)
      AVER(CBSEmergencyBlockLimit(prev) < CBSEmergencyBlockBase(block));
  }

  if (block != NULL) {
    blockBase = CBSEmergencyBlockBase(block);
    blockLimit = CBSEmergencyBlockLimit(block);
    AVER(blockBase < blockLimit);
    AVER(blockLimit >= limit);

    if (blockBase <= base && limit <= blockLimit) {
      /* remove from list */
      if (prev == NULL)
        cbs->emergencyBlockList = CBSEmergencyBlockNext(block);
      else
        CBSEmergencyBlockSetNext(prev, CBSEmergencyBlockNext(block));
      STATISTIC(--cbs->eblSize);
      AVER(cbs->emergencyBlockList != NULL || cbs->eblSize == 0);
      if (blockBase < base) {
        res = cbsAddToEmergencyLists(cbs, blockBase, base);
        if (res != ResOK)
          return res;
      }
      if (limit < blockLimit) {
        res = cbsAddToEmergencyLists(cbs, limit, blockLimit);
        if (res != ResOK)
          return res;
      }
      return ResOK;
    } else {
      return ResFAIL; /* partly in list */
    }
  }
  return ResFAIL; /* not in list at all */
}


static Res cbsDeleteFromEmergencyGrainList(CBS cbs, Addr base, Addr limit)
{
  Addr grainBase, grainLimit;
  CBSEmergencyGrain prev, grain;

  /* parameters already checked in caller */
  AVER(cbs->mayUseInline);
  if (AddrOffset(base, limit) != CBSEmergencyGrainSize(cbs))
    return ResFAIL;

  METER_ACC(cbs->eglSearch, cbs->eglSize);
  for(prev = NULL, grain = cbs->emergencyGrainList;
      grain != NULL && CBSEmergencyGrainLimit(cbs, grain) < limit;
      prev = grain, grain = CBSEmergencyGrainNext(grain)) {
    if (prev != NULL)
      AVER(CBSEmergencyGrainLimit(cbs, prev) < CBSEmergencyGrainBase(grain));
  }  

  if (grain != NULL) {
    grainBase = CBSEmergencyGrainBase(grain);
    grainLimit = CBSEmergencyGrainLimit(cbs, grain);
    AVER(grainLimit >= limit);

    if (grainBase <= base && limit <= grainLimit) {
      AVER(grainBase == base);
      AVER(grainLimit == limit);
      /* remove from list */
      if (prev == NULL)
        cbs->emergencyGrainList = CBSEmergencyGrainNext(grain);
      else
        CBSEmergencyGrainSetNext(prev, CBSEmergencyGrainNext(grain));
      STATISTIC(--cbs->eglSize);
      AVER(cbs->emergencyGrainList != NULL || cbs->eglSize == 0);
      return ResOK;
    } else {
      return ResFAIL; /* range is partly in list */
    }
  }
  return ResFAIL; /* range is not in list at all */
}


/* CBSDelete -- Remove a range from a CBS
 *
 * See <design/cbs/#function.cbs.delete>.
 */

Res CBSDelete(CBS cbs, Addr base, Addr limit)
{
  Res res;

  AVERT(CBS, cbs);
  CBSEnter(cbs);

  AVER(base != NULL);
  AVER(limit > base);
  AVER(AddrIsAligned(base, cbs->alignment));
  AVER(AddrIsAligned(limit, cbs->alignment));

  res = cbsDeleteFromTree(cbs, base, limit);

  /* We rely on the consistency of the three free structures. */
  /* These checks don't distinguish "partially in" from "not in". */
  if (cbs->mayUseInline) {
    AVER(res == ResOK || res == ResFAIL);
    if (res == ResFAIL) { /* wasn't in tree */
      res = cbsDeleteFromEmergencyBlockList(cbs, base, limit);
      if (res == ResFAIL) { /* wasn't in block list */
        res = cbsDeleteFromEmergencyGrainList(cbs, base, limit);
      }
    }
    /* always worth trying, wherever we found the deleted block */
    if (res == ResOK)
      cbsFlushEmergencyLists(cbs);
  }

  CBSLeave(cbs);
  return res;
}


Res CBSBlockDescribe(CBSBlock block, mps_lib_FILE *stream)
{
  Res res;

  if (stream == NULL) return ResFAIL;

  res = WriteF(stream,
               "[$P,$P) {$U}",
               (WriteFP)block->base,
               (WriteFP)block->limit,
               (WriteFU)block->maxSize,
               NULL);
  return res;
}

static Res CBSSplayNodeDescribe(SplayNode splayNode, mps_lib_FILE *stream)
{
  Res res;

  if (splayNode == NULL) return ResFAIL;
  if (stream == NULL) return ResFAIL;

  res = CBSBlockDescribe(cbsBlockOfSplayNode(splayNode), stream);
  return res;
}


/* CBSIterate -- Iterate all blocks in CBS
 *
 * This is not necessarily efficient.
 * See <design/cbs/#function.cbs.iterate>.
 */

/* Internal version without enter/leave checking. */
static void cbsIterateInternal(CBS cbs, CBSIterateMethod iterate, void *closureP)
{
  SplayNode splayNode;
  SplayTree splayTree;
  CBSBlock cbsBlock;

  AVERT(CBS, cbs);
  AVER(FUNCHECK(iterate));

  splayTree = splayTreeOfCBS(cbs);
  /* .splay-iterate.slow: We assume that splay tree iteration does */
  /* searches and meter it. */
  METER_ACC(cbs->splaySearch, cbs->splayTreeSize);
  splayNode = SplayTreeFirst(splayTree, NULL);
  while(splayNode != NULL) {
    cbsBlock = cbsBlockOfSplayNode(splayNode);
    if (!(*iterate)(cbs, cbsBlock, closureP)) {
      break;
    }
    METER_ACC(cbs->splaySearch, cbs->splayTreeSize);
    splayNode = SplayTreeNext(splayTree, splayNode, keyOfCBSBlock(cbsBlock));
  }
  return;
}

void CBSIterate(CBS cbs, CBSIterateMethod iterate, void *closureP)
{
  AVERT(CBS, cbs);
  AVER(FUNCHECK(iterate));
  CBSEnter(cbs);

  cbsIterateInternal(cbs, iterate, closureP);

  CBSLeave(cbs);
  return;
}


/* 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)
{
  CHECKL(findDelete == CBSFindDeleteNONE || findDelete == CBSFindDeleteLOW
         || findDelete == CBSFindDeleteHIGH
         || findDelete == CBSFindDeleteENTIRE);
  UNUSED(findDelete); /* <code/mpm.c#check.unused> */

  return TRUE;
}


/* cbsFindDeleteRange -- delete approriate range of block found */

typedef Res (*cbsDeleteMethod)(CBS cbs, Addr base, Addr limit);

static void cbsFindDeleteRange(Addr *baseReturn, Addr *limitReturn,
                               CBS cbs, Addr base, Addr limit, Size size,
                               cbsDeleteMethod delete,
                               CBSFindDelete findDelete)
{
  Bool callDelete = TRUE;

  AVER(baseReturn != NULL);
  AVER(limitReturn != NULL);
  AVERT(CBS, cbs);
  AVER(base < limit);
  AVER(size > 0);
  AVER(AddrOffset(base, limit) >= size);
  AVER(FUNCHECK(delete));
  AVERT(CBSFindDelete, findDelete);

  switch(findDelete) {

  case CBSFindDeleteNONE: {
    callDelete = FALSE;
  } break;

  case CBSFindDeleteLOW: {
    limit = AddrAdd(base, size);
  } break;

  case CBSFindDeleteHIGH: {
    base = AddrSub(limit, size);
  } break;

  case CBSFindDeleteENTIRE: {
    /* do nothing */
  } break;

  default: {
    NOTREACHED;
  } break;
  }

  if (callDelete) {
    Res res;
    res = (*delete)(cbs, base, limit);
    AVER(res == ResOK);
  }

  *baseReturn = base;
  *limitReturn = limit;
}


/* CBSFindFirst -- find the first block of at least the given size */

Bool CBSFindFirst(Addr *baseReturn, Addr *limitReturn,
                  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);

  AVER(baseReturn != NULL);
  AVER(limitReturn != NULL);
  AVER(size > 0);
  AVER(sizeof(unsigned long) >= sizeof(Size));
  AVER(SizeIsAligned(size, cbs->alignment));
  AVER(cbs->fastFind);
  AVERT(CBSFindDelete, findDelete);

  cbsFlushEmergencyLists(cbs); /* might do some good */

  {
    SplayNode node;

    METER_ACC(cbs->splaySearch, cbs->splayTreeSize);
    found = SplayFindFirst(&node, splayTreeOfCBS(cbs), &cbsTestNode,
                           &cbsTestTree, NULL, (unsigned long)size);

    if (found) {
      CBSBlock block;

      block = cbsBlockOfSplayNode(node);
      AVER(CBSBlockSize(block) >= size);
      base = CBSBlockBase(block);
      limit = CBSBlockLimit(block);
      deleteMethod = &cbsDeleteFromTree;
    }
  }

  if (cbs->emergencyBlockList != NULL) {
    CBSEmergencyBlock block;

    METER_ACC(cbs->eblSearch, cbs->eblSize);
    for(block = cbs->emergencyBlockList;
        block != NULL &&
        (!found || CBSEmergencyBlockBase(block) < base);
        block = CBSEmergencyBlockNext(block)) {
      if (CBSEmergencyBlockSize(block) >= size) {
        found = TRUE;
        base = CBSEmergencyBlockBase(block);
        limit = CBSEmergencyBlockLimit(block);
        deleteMethod = &cbsDeleteFromEmergencyBlockList;
        /* @@@@ Could remove in place more efficiently. */
        break;
      }     
    }
  }

  if (cbs->emergencyGrainList != NULL &&
     size <= CBSEmergencyGrainSize(cbs)) {
    /* Take first grain */
    CBSEmergencyGrain grain = cbs->emergencyGrainList;

    if (!found || CBSEmergencyGrainBase(grain) < base) {
      found = TRUE;
      base = CBSEmergencyGrainBase(grain);
      limit = CBSEmergencyGrainLimit(cbs, grain);
      deleteMethod = &cbsDeleteFromEmergencyGrainList;
    }
  }

  if (found) {
    AVER(AddrOffset(base, limit) >= size);
    cbsFindDeleteRange(baseReturn, limitReturn, cbs, base, limit, size,
                       deleteMethod, findDelete);
  }

  CBSLeave(cbs);
  return found;
}


/* CBSFindLast -- find the last block of at least the given size */

Bool CBSFindLast(Addr *baseReturn, Addr *limitReturn,
                 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);

  AVER(baseReturn != NULL);
  AVER(limitReturn != NULL);
  AVER(size > 0);
  AVER(sizeof(unsigned long) >= sizeof(Size));
  AVER(SizeIsAligned(size, cbs->alignment));
  AVER(cbs->fastFind);
  AVERT(CBSFindDelete, findDelete);

  cbsFlushEmergencyLists(cbs); /* might do some good */

  {
    SplayNode node;

    METER_ACC(cbs->splaySearch, cbs->splayTreeSize);
    found = SplayFindLast(&node, splayTreeOfCBS(cbs), &cbsTestNode,
                          &cbsTestTree, NULL, (unsigned long)size);
    if (found) {
      CBSBlock block;

      block = cbsBlockOfSplayNode(node);
      AVER(CBSBlockSize(block) >= size);
      base = CBSBlockBase(block);
      limit = CBSBlockLimit(block);
      deleteMethod = &cbsDeleteFromTree;
    }
  }

  if (cbs->emergencyBlockList != NULL) {
    CBSEmergencyBlock block;

    METER_ACC(cbs->eblSearch, cbs->eblSize);
    for(block = cbs->emergencyBlockList;
        block != NULL;
        block = CBSEmergencyBlockNext(block)) {
      if (CBSEmergencyBlockSize(block) >= size &&
         (!found || CBSEmergencyBlockBase(block) > base)) {
        found = TRUE;
        base = CBSEmergencyBlockBase(block);
        limit = CBSEmergencyBlockLimit(block);
        deleteMethod = &cbsDeleteFromEmergencyBlockList;
        /* @@@@ Could remove in place more efficiently. */
      }     
    }
  }

  if (cbs->emergencyGrainList != NULL &&
     size <= CBSEmergencyGrainSize(cbs)) {
    CBSEmergencyGrain grain;

    /* Find last grain */
    METER_ACC(cbs->eglSearch, cbs->eglSize);
    for(grain = cbs->emergencyGrainList;
        CBSEmergencyGrainNext(grain) != NULL;
        grain = CBSEmergencyGrainNext(grain))
      NOOP;

    if (!found || CBSEmergencyGrainBase(grain) > base) {
      found = TRUE;
      base = CBSEmergencyGrainBase(grain);
      limit = CBSEmergencyGrainLimit(cbs, grain);
      deleteMethod = &cbsDeleteFromEmergencyGrainList;
      /* @@@@ Could remove in place more efficiently */
    }
  }

  if (found) {
    AVER(AddrOffset(base, limit) >= size);
    cbsFindDeleteRange(baseReturn, limitReturn, cbs, base, limit, size,
                       deleteMethod, findDelete);
  }

  CBSLeave(cbs);
  return found;
}


/* CBSFindLargest -- find the largest block in the CBS */

Bool CBSFindLargest(Addr *baseReturn, Addr *limitReturn,
                    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);
  CBSEnter(cbs);

  AVER(baseReturn != NULL);
  AVER(limitReturn != NULL);
  AVER(sizeof(unsigned long) >= sizeof(Size));
  AVER(cbs->fastFind);
  AVERT(CBSFindDelete, findDelete);

  cbsFlushEmergencyLists(cbs); /* might do some good */

  {
    SplayNode root;
    Bool notEmpty;

    notEmpty = SplayRoot(&root, splayTreeOfCBS(cbs));
    if (notEmpty) {
      CBSBlock block;
      SplayNode node;

      size = cbsBlockOfSplayNode(root)->maxSize;
      METER_ACC(cbs->splaySearch, cbs->splayTreeSize);
      found = SplayFindFirst(&node, splayTreeOfCBS(cbs), &cbsTestNode,
                             &cbsTestTree, NULL, (unsigned long)size);
      AVER(found); /* maxSize is exact, so we will find it. */
      block = cbsBlockOfSplayNode(node);
      AVER(CBSBlockSize(block) >= size);
      base = CBSBlockBase(block);
      limit = CBSBlockLimit(block);
      deleteMethod = &cbsDeleteFromTree;
    }
  }

  if (cbs->emergencyBlockList != NULL) {
    CBSEmergencyBlock block;

    /* Scan the whole list -- could maintain a maxSize to avoid it. */
    METER_ACC(cbs->eblSearch, cbs->eblSize);
    for(block = cbs->emergencyBlockList;
        block != NULL;
        block = CBSEmergencyBlockNext(block)) {
      if (CBSEmergencyBlockSize(block) >= size) {
        /* .pref: >= so that it prefers the emerg. list to the tree */
        found = TRUE;
        size = CBSEmergencyBlockSize(block);
        base = CBSEmergencyBlockBase(block);
        limit = CBSEmergencyBlockLimit(block);
        deleteMethod = &cbsDeleteFromEmergencyBlockList;
        /* @@@@ Could remove in place more efficiently. */
      }     
    }
  }

  /* If something was found, it will be larger than an emerg. grain. */
  if (!found && cbs->emergencyGrainList != NULL) {
    /* Take first grain */
    CBSEmergencyGrain grain = cbs->emergencyGrainList;

    found = TRUE;
    size = CBSEmergencyGrainSize(cbs);
    base = CBSEmergencyGrainBase(grain);
    limit = CBSEmergencyGrainLimit(cbs, grain);
    deleteMethod = &cbsDeleteFromEmergencyGrainList;
  }

  if (found) {
    cbsFindDeleteRange(baseReturn, limitReturn, cbs, base, limit, size,
                       deleteMethod, findDelete);
  }

  CBSLeave(cbs);
  return found;
}


/* CBSDescribe -- describe a CBS
 *
 * See <design/cbs/#function.cbs.describe>.
 */

Res CBSDescribe(CBS cbs, mps_lib_FILE *stream)
{
  Res res;

  if (!CHECKT(CBS, cbs)) return ResFAIL;
  if (stream == NULL) return ResFAIL;

  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;

  res = SplayTreeDescribe(splayTreeOfCBS(cbs), stream, &CBSSplayNodeDescribe);
  if (res != ResOK) return res;

  res = METER_WRITE(cbs->splaySearch, stream);
  if (res != ResOK) return res;
  res = METER_WRITE(cbs->eblSearch, stream);
  if (res != ResOK) return res;
  res = METER_WRITE(cbs->eglSearch, stream);
  if (res != ResOK) return res;

  res = WriteF(stream, "}\n", NULL);
  return res;
}


/* C. COPYRIGHT AND LICENSE
 *
 * Copyright (C) 2001-2002 Ravenbrook Limited <http://www.ravenbrook.com/>.
 * All rights reserved.  This is an open source license.  Contact
 * Ravenbrook for commercial licensing options.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 * 
 * 2. Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * 3. Redistributions in any form must be accompanied by information on how
 * to obtain complete source code for this software and any accompanying
 * software that uses this software.  The source code must either be
 * included in the distribution or be available for no more than the cost
 * of distribution plus a nominal fee, and must be freely redistributable
 * under reasonable conditions.  For an executable file, complete source
 * code means the source code for all modules it contains. It does not
 * include source code for modules or files that typically accompany the
 * major components of the operating system on which the executable file
 * runs.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 * PURPOSE, OR NON-INFRINGEMENT, ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDERS AND CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */