自学教程：C++ AVERT函数代码示例

static void bufferNoSetRankSet(Buffer buffer, RankSet rankset){  AVERT(Buffer, buffer);  AVERT(RankSet, rankset);  NOTREACHED; /* .norank */}

static Res MVFFInit(Pool pool, ArgList args){  Size extendBy = MVFF_EXTEND_BY_DEFAULT;  Size avgSize = MVFF_AVG_SIZE_DEFAULT;  Size align = MVFF_ALIGN_DEFAULT;  Bool slotHigh = MVFF_SLOT_HIGH_DEFAULT;  Bool arenaHigh = MVFF_ARENA_HIGH_DEFAULT;  Bool firstFit = MVFF_FIRST_FIT_DEFAULT;  MVFF mvff;  Arena arena;  Res res;  void *p;  ArgStruct arg;  AVERT(Pool, pool);  arena = PoolArena(pool);  /* .arg: class-specific additional arguments; see */  /* <design/poolmvff/#method.init> */  /* .arg.check: we do the same checks here and in MVFFCheck */  /* except for arenaHigh, which is stored only in the segPref. */    if (ArgPick(&arg, args, MPS_KEY_EXTEND_BY))    extendBy = arg.val.size;    if (ArgPick(&arg, args, MPS_KEY_MEAN_SIZE))    avgSize = arg.val.size;    if (ArgPick(&arg, args, MPS_KEY_ALIGN))    align = arg.val.align;  if (ArgPick(&arg, args, MPS_KEY_MVFF_SLOT_HIGH))    slotHigh = arg.val.b;    if (ArgPick(&arg, args, MPS_KEY_MVFF_ARENA_HIGH))    arenaHigh = arg.val.b;    if (ArgPick(&arg, args, MPS_KEY_MVFF_FIRST_FIT))    firstFit = arg.val.b;  AVER(extendBy > 0);           /* .arg.check */  AVER(avgSize > 0);            /* .arg.check */  AVER(avgSize <= extendBy);    /* .arg.check */  AVER(SizeIsAligned(align, MPS_PF_ALIGN));  AVERT(Bool, slotHigh);  AVERT(Bool, arenaHigh);  AVERT(Bool, firstFit);  mvff = Pool2MVFF(pool);  mvff->extendBy = extendBy;  if (extendBy < ArenaAlign(arena))    mvff->minSegSize = ArenaAlign(arena);  else    mvff->minSegSize = extendBy;  mvff->avgSize = avgSize;  pool->alignment = align;  mvff->slotHigh = slotHigh;  mvff->firstFit = firstFit;  res = ControlAlloc(&p, arena, sizeof(SegPrefStruct), FALSE);  if (res != ResOK)    return res;  mvff->segPref = (SegPref)p;  SegPrefInit(mvff->segPref);  SegPrefExpress(mvff->segPref, arenaHigh ? SegPrefHigh : SegPrefLow, NULL);  mvff->total = 0;  mvff->free = 0;  res = FreelistInit(FreelistOfMVFF(mvff), align);  if (res != ResOK)    goto failInit;  res = CBSInit(CBSOfMVFF(mvff), arena, (void *)mvff, align,                /* fastFind */ TRUE, /* zoned */ FALSE, args);  if (res != ResOK)    goto failInit;  mvff->sig = MVFFSig;  AVERT(MVFF, mvff);  EVENT8(PoolInitMVFF, pool, arena, extendBy, avgSize, align,         BOOL(slotHigh), BOOL(arenaHigh), BOOL(firstFit));  return ResOK;failInit:  ControlFree(arena, p, sizeof(SegPrefStruct));  return res;}

Addr VMBase(VM vm){  AVERT(VM, vm);  return vm->base;}

Count SplayDebugCount(SplayTree splay){  AVERT(SplayTree, splay);  return TreeDebugCount(SplayTreeRoot(splay), splay->compare, splay->nodeKey);}

static Compare SplaySplitRev(SplayStateStruct *stateReturn,                             SplayTree splay, TreeKey key,                             TreeCompareFunction compare){  Tree middle, leftLast, rightFirst;  Compare cmp;  AVERT(SplayTree, splay);  AVER(FUNCHECK(compare));  AVER(!SplayTreeIsEmpty(splay));    leftLast = TreeEMPTY;  rightFirst = TreeEMPTY;  middle = SplayTreeRoot(splay);  for (;;) {    cmp = compare(middle, key);    switch(cmp) {    default:      NOTREACHED;      /* defensive fall-through */    case CompareEQUAL:      goto stop;    case CompareLESS:      if (!TreeHasLeft(middle))        goto stop;      middle = SplayZigRev(middle, &rightFirst);      cmp = compare(middle, key);      switch(cmp) {      default:        NOTREACHED;        /* defensive fall-through */      case CompareEQUAL:        goto stop;      case CompareLESS:        if (!TreeHasLeft(middle))          goto stop;        middle = SplayZigZigRev(middle, &rightFirst);        splay->updateNode(splay, TreeRight(rightFirst));        break;      case CompareGREATER:        if (!TreeHasRight(middle))          goto stop;        middle = SplayZagRev(middle, &leftLast);        break;      }      break;    case CompareGREATER:      if (!TreeHasRight(middle))        goto stop;      middle = SplayZagRev(middle, &leftLast);      cmp = compare(middle, key);      switch(cmp) {      default:        NOTREACHED;        /* defensive fall-through */      case CompareEQUAL:        goto stop;      case CompareGREATER:        if (!TreeHasRight(middle))          goto stop;        middle = SplayZagZagRev(middle, &leftLast);        splay->updateNode(splay, TreeLeft(leftLast));        break;      case CompareLESS:        if (!TreeHasLeft(middle))          goto stop;        middle = SplayZigRev(middle, &rightFirst);        break;      }      break;    }  }stop:  stateReturn->middle = middle;  stateReturn->leftLast = leftLast;  stateReturn->rightFirst = rightFirst;  return cmp;}

Align VMAlign(VM vm){  AVERT(VM, vm);  return vm->align;}

static Bool MessageOnQueue(Message message){  AVERT(Message, message);  return !RingIsSingle(&message->queueRing);}

static Bool SplaySplay(SplayNode *nodeReturn, SplayTree tree,                       void *key, SplayCompareMethod compareMethod) {    /* The sides structure avoids a boundary case in SplayLink* */    SplayNodeStruct sides; /* rightTop and leftTop */    SplayNode top, leftLast, rightFirst;    Bool found;    Compare compareTop;    AVERT(SplayTree, tree);    AVER(nodeReturn != NULL);    AVER(FUNCHECK(compareMethod));    top = SplayTreeRoot(tree); /* will be copied back at end */    if (top == NULL) {        *nodeReturn = NULL;        return FALSE;    }    /* short-circuit case where node is already top */    compareTop = (*compareMethod)(key, top);    if (compareTop == CompareEQUAL) {        *nodeReturn = top;        return TRUE;    }    SplayNodeInit(&sides); /* left and right trees now NULL */    leftLast = &sides;    rightFirst = &sides;    while(TRUE) {        /* compareTop is already initialised above. */        switch(compareTop) {        case CompareLESS: {            SplayNode topLeft = SplayNodeLeftChild(top);            if (topLeft == NULL) {                found = FALSE;                goto assemble;            } else {                Compare compareTopLeft = (*compareMethod)(key, topLeft);                switch(compareTopLeft) {                case CompareEQUAL: {                 /* zig */                    SplayLinkRight(&top, &rightFirst);                    found = TRUE;                    goto assemble;                    } /* break; */                case CompareLESS: {                  /* zig-zig */                    if (SplayNodeLeftChild(topLeft) == NULL)                        goto terminalZig;                    SplayRotateRight(&top, tree);                    SplayLinkRight(&top, &rightFirst);                }                break;                case CompareGREATER: {               /* zig-zag */                    if (SplayNodeRightChild(topLeft) == NULL)                        goto terminalZig;                    SplayLinkRight(&top, &rightFirst);                    SplayLinkLeft(&top, &leftLast);                }                break;                default: {                    NOTREACHED;                }                break;                }            }        }        break;        case CompareGREATER: {            SplayNode topRight = SplayNodeRightChild(top);            if (topRight == NULL) {                found = FALSE;                goto assemble;            } else {                Compare compareTopRight = (*compareMethod)(key, topRight);                switch(compareTopRight) {                case CompareEQUAL: {                 /* zag */                    SplayLinkLeft(&top, &leftLast);                    found = TRUE;                    goto assemble;                    } /* break; */                case CompareGREATER: {               /* zag-zag */                    if (SplayNodeRightChild(topRight) == NULL)                        goto terminalZag;                    SplayRotateLeft(&top, tree);                    SplayLinkLeft(&top, &leftLast);                }                break;                case CompareLESS: {                  /* zag-zig *///.........这里部分代码省略.........

void SplayTreeFinish(SplayTree tree){    AVERT(SplayTree, tree);    SplayTreeSetRoot(tree, NULL);    tree->compare = NULL;}

static Bool BTFindResRangeHigh(Index *baseReturn, Index *limitReturn,                               BT bt,                               Index searchBase, Index searchLimit,                               Count minLength,                               Count maxLength){  Bool foundRes;         /* true if a reset bit is found */  Index resLimit;        /* limit of a candidate reset range */  Index resIndex;        /* index of highest reset bit found */  Index unseenLimit;     /* limit of testing so far */  Index minBase;         /* base of minimal acceptable range */  Index resBase;         /* base of search for a candidate range */  AVER(baseReturn != NULL);  AVER(limitReturn != NULL);  AVERT(BT, bt);  AVER(searchBase < searchLimit);  AVER(minLength > 0);  AVER(minLength <= maxLength);  AVER(maxLength <= searchLimit - searchBase);  foundRes = FALSE;     /* don't know first reset bit */  minBase = 0;          /* avoid spurious compiler warning */  resLimit = searchLimit;    /* haven't seen anything yet */  unseenLimit = searchLimit; /* haven't seen anything yet */  resBase = searchBase + minLength -1;  while (resLimit > resBase) {    Index setIndex;  /* index of first set bit found */    Bool foundSet = FALSE; /* true if a set bit is found */    /* Find the first reset bit if it's not already known */    if (!foundRes) {      /* Look for the limit of a range */      BTFindResHigh(&foundRes, &resIndex, bt, resBase, unseenLimit);      if (!foundRes) {        /* failure */        return FALSE;      }      resLimit = resIndex + 1;      unseenLimit = resIndex;      minBase = resLimit - minLength;    }    /* Look to see if there is any set bit in the minimum range */    BTFindSet(&foundSet, &setIndex, bt, minBase, unseenLimit);    if (!foundSet) {      /* Found minimum range. Extend it. */      Index setBase;   /* base of search for set bit */      Index setLimit;  /* limit search for set bit */      Index baseIndex; /* base of reset range found */      foundSet = FALSE;      setLimit = minBase;      if ((searchBase + maxLength) > resLimit)        setBase = searchBase;      else        setBase  = resLimit - maxLength;      if (setLimit > setBase)        BTFindSetHigh(&foundSet, &setIndex, bt, setBase, setLimit);      if (foundSet)        baseIndex = setIndex+1;      else        baseIndex = setBase;           AVER(resLimit - baseIndex >= minLength);      AVER(resLimit - baseIndex <= maxLength);      *baseReturn = baseIndex;      *limitReturn = resLimit;      return TRUE;         } else {      /* Range was too small. Try again */      unseenLimit = minBase;      resLimit = setIndex;      if (resLimit != minBase) {        /* Already found the start of next candidate range. This wraps         * round if minLength > resLimit (all the variables are         * unsigned so this behaviour is defined), but that means that         * resLimit <= resBase and so the loop will exit. */        AVER(resLimit >= minLength || resLimit <= resBase);        minBase = resLimit - minLength;      } else {        foundRes = FALSE;      }    }  }  /* failure */  return FALSE;}

static void SplayAssemble(SplayTree tree, SplayNode top,                          SplayNode leftTop, SplayNode leftLast,                          SplayNode rightTop, SplayNode rightFirst) {    AVERT(SplayTree, tree);    AVERT(SplayNode, top);    AVER(leftTop == NULL ||         (SplayNodeCheck(leftTop) && SplayNodeCheck(leftLast)));    AVER(rightTop == NULL ||         (SplayNodeCheck(rightTop) && SplayNodeCheck(rightFirst)));    if (leftTop != NULL) {        SplayNodeSetRightChild(leftLast, SplayNodeLeftChild(top));        SplayNodeSetLeftChild(top, leftTop);        if (tree->updateNode != NULL) {            /* Update client property using pointer reversal (Ugh!). */            SplayNode node, parent, rightChild;            /* Reverse the pointers between leftTop and leftLast */            /* leftLast is not reversed. */            node = leftTop;            parent = NULL;            while(node != leftLast) {                rightChild = SplayNodeRightChild(node);                SplayNodeSetRightChild(node, parent); /* pointer reversal */                parent = node;                node = rightChild;            }            /* Now restore the pointers, updating the client property. */            /* node is leftLast, parent is the last parent (or NULL). */            SplayNodeUpdate(tree, node);            while(node != leftTop) {                rightChild = node;                node = parent;                parent = SplayNodeRightChild(node);                SplayNodeSetRightChild(node, rightChild); /* un-reverse pointer */                SplayNodeUpdate(tree, node);            }        }    }    /* otherwise leave top->left alone */    if (rightTop != NULL) {        SplayNodeSetLeftChild(rightFirst, SplayNodeRightChild(top));        SplayNodeSetRightChild(top, rightTop);        if (tree->updateNode != NULL) {            /* Update client property using pointer reversal (Ugh!). */            SplayNode node, parent, leftChild;            /* Reverse the pointers between rightTop and rightFirst */            /* ightFirst is not reversed. */            node = rightTop;            parent = NULL;            while(node != rightFirst) {                leftChild = SplayNodeLeftChild(node);                SplayNodeSetLeftChild(node, parent); /* pointer reversal */                parent = node;                node = leftChild;            }            /* Now restore the pointers, updating the client property. */            /* node is rightFirst, parent is the last parent (or NULL). */            SplayNodeUpdate(tree, node);            while(node != rightTop) {                leftChild = node;                node = parent;                parent = SplayNodeLeftChild(node);                SplayNodeSetLeftChild(node, leftChild); /* un-reverse pointer */                SplayNodeUpdate(tree, node);            }        }    }    /* otherwise leave top->right alone */    if (tree->updateNode != NULL)        SplayNodeUpdate(tree, top);}

static Bool BTFindResRange(Index *baseReturn, Index *limitReturn,                           BT bt,                           Index searchBase, Index searchLimit,                           Count minLength, Count maxLength){  Bool foundRes;         /* true if a reset bit is found */  Index resBase;         /* base of a candidate reset range */  Index unseenBase;      /* base of testing so far */  Index minLimit;        /* limit of minimal acceptable range */  Index resLimit;        /* limit of search for a candidate range */  AVER(baseReturn != NULL);  AVER(limitReturn != NULL);  AVERT(BT, bt);  AVER(searchBase < searchLimit);  AVER(minLength > 0);  AVER(minLength <= maxLength);  AVER(maxLength <= searchLimit - searchBase);  foundRes = FALSE;     /* don't know first reset bit */  minLimit = 0;         /* avoid spurious compiler warning */  resBase = searchBase; /* haven't seen anything yet */  unseenBase = searchBase;  /* haven't seen anything yet */  resLimit = searchLimit - minLength + 1;  while (resBase < resLimit) {    Index setIndex;  /* index of last set bit found */    Bool foundSet = FALSE; /* true if a set bit is found */    /* Find the first reset bit if it's not already known */    if (!foundRes) {      BTFindRes(&foundRes, &resBase, bt, unseenBase, resLimit);      if (!foundRes) {        /* failure */        return FALSE;      }      unseenBase = resBase + 1;      minLimit = resBase + minLength;    }    /* Look to see if there is any set bit in the minimum range */    BTFindSetHigh(&foundSet, &setIndex, bt, unseenBase, minLimit);    if (!foundSet) {      /* Found minimum range. Extend it. */      Index setBase;   /* base of search for set bit */      Index setLimit;  /* limit search for set bit */      foundSet = FALSE;      setBase = minLimit;      setLimit = resBase + maxLength;      if (setLimit > searchLimit)        setLimit = searchLimit;      if (setLimit > setBase)        BTFindSet(&foundSet, &setIndex, bt, setBase, setLimit);      if (!foundSet)        setIndex = setLimit;             AVER(setIndex - resBase >= minLength);      AVER(setIndex - resBase <= maxLength);      *baseReturn = resBase;      *limitReturn = setIndex;      return TRUE;           } else {      /* Range was too small. Try again */      unseenBase = minLimit;      resBase = setIndex + 1;      if (resBase != minLimit) {        /* Already found the start of next candidate range */        minLimit = resBase + minLength;        /* minLimit might just have gone out of bounds, but in that         * case resBase >= resLimit and so the loop will exit. */        AVER(minLimit <= searchLimit || resBase >= resLimit);      } else {        foundRes = FALSE;      }    }  }  /* failure */  return FALSE;}

static Res ArenaRootsWalk(Globals arenaGlobals, mps_roots_stepper_t f,                          void *p, size_t s){  Arena arena;  rootsStepClosureStruct rscStruct;  rootsStepClosure rsc = &rscStruct;  Trace trace;  ScanState ss;  Rank rank;  Res res;  Seg seg;  AVERT(Globals, arenaGlobals);  AVER(FUNCHECK(f));  /* p and s are arbitrary client-provided closure data. */  arena = GlobalsArena(arenaGlobals);  /* Scan all the roots with a minimal trace.  Invoke the scanner with a */  /* rootsStepClosure, which is a subclass of ScanState and contains the */  /* client-provided closure.  Supply a special fix method in order to */  /* call the client closure.  This fix method must perform no tracing */  /* operations of its own. */  res = TraceCreate(&trace, arena, TraceStartWhyWALK);  /* Have to fail if no trace available.  Unlikely due to .assume.parked. */  if (res != ResOK)    return res;  /* ArenaRootsWalk only passes references to GCable pools to the client. */  /* NOTE: I'm not sure why this is. RB 2012-07-24 */  if (SegFirst(&seg, arena)) {    do {      if (PoolHasAttr(SegPool(seg), AttrGC)) {        res = TraceAddWhite(trace, seg);        AVER(res == ResOK);      }    } while (SegNext(&seg, arena, seg));  }  /* Make the roots grey so that they are scanned */  res = RootsIterate(arenaGlobals, rootWalkGrey, trace);  /* Make this trace look like any other trace. */  arena->flippedTraces = TraceSetAdd(arena->flippedTraces, trace);  rootsStepClosureInit(rsc, arenaGlobals, trace, RootsWalkFix, f, p, s);  ss = rootsStepClosure2ScanState(rsc);  for(rank = RankAMBIG; rank < RankLIMIT; ++rank) {    ss->rank = rank;    AVERT(ScanState, ss);    res = RootsIterate(arenaGlobals, rootWalk, (void *)ss);    if (res != ResOK)      break;  }  /* Turn segments black again. */  if (SegFirst(&seg, arena)) {    do {      if (PoolHasAttr(SegPool(seg), AttrGC)) {        SegSetGrey(seg, TraceSetDel(SegGrey(seg), trace));        SegSetWhite(seg, TraceSetDel(SegWhite(seg), trace));      }    } while (SegNext(&seg, arena, seg));  }  rootsStepClosureFinish(rsc);  /* Make this trace look like any other finished trace. */  trace->state = TraceFINISHED;  TraceDestroy(trace);  AVER(!ArenaEmergency(arena)); /* There was no allocation. */  return res;}

static void bufferNoReassignSeg(Buffer buffer, Seg seg){  AVERT(Buffer, buffer);  AVERT(Seg, seg);  NOTREACHED; /* .noseg */}

Size VMReserved(VM vm){  AVERT(VM, vm);  return vm->reserved;}

DEFINE_CLASS(Inst, Inst, klass){  InstClassInitInternal(klass);  klass->instStruct.klass = CLASS(InstClass);  AVERT(InstClass, klass);}

Size VMMapped(VM vm){  AVERT(VM, vm);  return vm->mapped;}

void FreelistFinish(Freelist fl){  AVERT(Freelist, fl);  fl->sig = SigInvalid;  fl->list = NULL;}

Res VMCreate(VM *vmReturn, Size size){  void *addr;  Align align;  int zero_fd;  VM vm;  Res res;  AVER(vmReturn != NULL);  align = (Align)sysconf(_SC_PAGESIZE);  AVER(SizeIsP2(align));  size = SizeAlignUp(size, align);  if((size == 0) || (size > (Size)(size_t)-1))    return ResRESOURCE;  zero_fd = open("/dev/zero", O_RDONLY);  if(zero_fd == -1)    return ResFAIL;  /* Map in a page to store the descriptor on. */  addr = mmap((void *)0, (size_t)SizeAlignUp(sizeof(VMStruct), align),              PROT_READ | PROT_WRITE, MAP_PRIVATE,              zero_fd, (off_t)0);  if(addr == MAP_FAILED) {    AVER(errno == ENOMEM || errno == EAGAIN); /* .assume.mmap.err */    res = (errno == ENOMEM || errno == EAGAIN) ? ResMEMORY : ResFAIL;    goto failVMMap;  }  vm = (VM)addr;  vm->zero_fd = zero_fd;  vm->align = align;  /* .map.reserve: MAP_AUTORESRV is necessary to avoid reserving swap. */  addr = mmap((void *)0, (size_t)size, PROT_NONE, MAP_SHARED | MAP_AUTORESRV,	      zero_fd, (off_t)0);  if(addr == MAP_FAILED) {    AVER(errno == ENOMEM); /* .assume.mmap.err */    res = (errno == ENOMEM) ? ResRESOURCE : ResFAIL;    goto failReserve;  }  vm->base = (Addr)addr;  vm->limit = AddrAdd(vm->base, size);  vm->reserved = size;  vm->mapped = (Size)0;  vm->sig = VMSig;  AVERT(VM, vm);  EVENT_PAA(VMCreate, vm, vm->base, vm->limit);  *vmReturn = vm;  return ResOK;failReserve:  (void)munmap((void *)vm, (size_t)SizeAlignUp(sizeof(VMStruct), align));failVMMap:  (void)close(zero_fd);  return res;}

/* FreelistBlockNext -- return the next block in the list, or NULL if * there are no more blocks. */static FreelistBlock FreelistBlockNext(FreelistBlock block){  AVERT(FreelistBlock, block);  return FreelistTagReset(block->small.next);}

void SplayTrivUpdate(SplayTree splay, Tree tree){  AVERT(SplayTree, splay);  AVERT(Tree, tree);}

static void FreelistBlockSetNext(FreelistBlock block, FreelistBlock next){  AVERT(FreelistBlock, block);  block->small.next = FreelistTagCopy(next, block->small.next);}

static Compare SplaySplitDown(SplayStateStruct *stateReturn,                              SplayTree splay, TreeKey key,                              TreeCompareFunction compare){  TreeStruct sentinel;  Tree middle, leftLast, rightFirst, leftPrev, rightNext;  Compare cmp;  AVERT(SplayTree, splay);  AVER(FUNCHECK(compare));  AVER(!SplayTreeIsEmpty(splay));  AVER(!SplayHasUpdate(splay));    TreeInit(&sentinel);  leftLast = &sentinel;  rightFirst = &sentinel;  middle = SplayTreeRoot(splay);  for (;;) {    cmp = compare(middle, key);    switch(cmp) {    default:      NOTREACHED;      /* defensive fall-through */    case CompareEQUAL:      goto stop;    case CompareLESS:      if (!TreeHasLeft(middle))        goto stop;      middle = SplayZig(middle, &rightFirst, &rightNext);      cmp = compare(middle, key);      switch(cmp) {      default:        NOTREACHED;        /* defensive fall-through */      case CompareEQUAL:        goto stop;      case CompareLESS:        if (!TreeHasLeft(middle))          goto stop;        middle = SplayZigZig(middle, &rightFirst, rightNext);        break;      case CompareGREATER:        if (!TreeHasRight(middle))          goto stop;        middle = SplayZag(middle, &leftLast, &leftPrev);        break;      }      break;    case CompareGREATER:      if (!TreeHasRight(middle))        goto stop;      middle = SplayZag(middle, &leftLast, &leftPrev);      cmp = compare(middle, key);      switch(cmp) {      default:        NOTREACHED;        /* defensive fall-through */      case CompareEQUAL:        goto stop;      case CompareGREATER:        if (!TreeHasRight(middle))          goto stop;        middle = SplayZagZag(middle, &leftLast, leftPrev);        break;      case CompareLESS:        if (!TreeHasLeft(middle))          goto stop;        middle = SplayZig(middle, &rightFirst, &rightNext);        break;      }      break;    }  }stop:  stateReturn->middle = middle;  stateReturn->left = TreeRight(&sentinel);  stateReturn->leftLast = leftLast == &sentinel ? TreeEMPTY : leftLast;  stateReturn->right = TreeLeft(&sentinel);  stateReturn->rightFirst = rightFirst == &sentinel ? TreeEMPTY : rightFirst;  return cmp;}

/* AMSTBufferFill -- the pool class buffer fill method * * Calls next method - but possibly splits or merges the chosen * segment. * * .merge: A merge is performed when the next method returns the * entire segment, this segment had previously been split from the * segment below, and the segment below is appropriately similar * (i.e. not already attached to a buffer and similarly coloured) * * .split: If we're not merging, a split is performed if the next method * returns the entire segment, and yet lower half of the segment would * meet the request. */static Res AMSTBufferFill(Addr *baseReturn, Addr *limitReturn,                          Pool pool, Buffer buffer, Size size){  Addr base, limit;  Arena arena;  AMS ams;  AMST amst;  Bool b;  Seg seg;  AMSTSeg amstseg;  Res res;  AVERT(Pool, pool);  AVER(baseReturn != NULL);  AVER(limitReturn != NULL);  /* other parameters are checked by next method */  arena = PoolArena(pool);  ams = PoolAMS(pool);  amst = PoolAMST(pool);  /* call next method */  res = NextMethod(Pool, AMSTPool, bufferFill)(&base, &limit, pool, buffer, size);  if (res != ResOK)    return res;  b = SegOfAddr(&seg, arena, base);  AVER(b);  amstseg = Seg2AMSTSeg(seg);  if (SegLimit(seg) == limit && SegBase(seg) == base) {    if (amstseg->prev != NULL) {      Seg segLo = AMSTSeg2Seg(amstseg->prev);      if (!SegHasBuffer(segLo) &&          SegGrey(segLo) == SegGrey(seg) &&          SegWhite(segLo) == SegWhite(seg)) {        /* .merge */        Seg mergedSeg;        Res mres;        AMSUnallocateRange(ams, seg, base, limit);        mres = SegMerge(&mergedSeg, segLo, seg);        if (ResOK == mres) { /* successful merge */          AMSAllocateRange(ams, mergedSeg, base, limit);          /* leave range as-is */        } else {            /* failed to merge */          AVER(amst->failSegs); /* deliberate fails only */          AMSAllocateRange(ams, seg, base, limit);        }      }    } else {      Size half = SegSize(seg) / 2;      if (half >= size && SizeIsArenaGrains(half, arena)) {        /* .split */        Addr mid = AddrAdd(base, half);        Seg segLo, segHi;        Res sres;        AMSUnallocateRange(ams, seg, mid, limit);        sres = SegSplit(&segLo, &segHi, seg, mid);        if (ResOK == sres) { /* successful split */          limit = mid;  /* range is lower segment */        } else {            /* failed to split */          AVER(amst->failSegs); /* deliberate fails only */          AMSAllocateRange(ams, seg, mid, limit);        }      }    }  }  *baseReturn = base;  *limitReturn = limit;  return ResOK;}

/* MVFFFreeSegs -- Free segments from given range * * Given a free range, attempts to find entire segments within * it, and returns them to the arena, updating total size counter. * * This is usually called immediately after MVFFAddToFreeList. * It is not combined with MVFFAddToFreeList because the latter * is also called when new segments are added under MVFFAlloc. */static void MVFFFreeSegs(MVFF mvff, Addr base, Addr limit){  Seg seg = NULL;       /* suppress "may be used uninitialized" */  Arena arena;  Bool b;  Addr segLimit;  /* limit of the current segment when iterating */  Addr segBase;   /* base of the current segment when iterating */  Res res;  AVERT(MVFF, mvff);  AVER(base < limit);  /* Could profitably AVER that the given range is free, */  /* but the CBS doesn't provide that facility. */  if (AddrOffset(base, limit) < mvff->minSegSize)    return; /* not large enough for entire segments */  arena = PoolArena(MVFF2Pool(mvff));  b = SegOfAddr(&seg, arena, base);  AVER(b);  segBase = SegBase(seg);  segLimit = SegLimit(seg);  while(segLimit <= limit) { /* segment ends in range */    if (segBase >= base) { /* segment starts in range */      RangeStruct range, oldRange;      RangeInit(&range, segBase, segLimit);      res = CBSDelete(&oldRange, CBSOfMVFF(mvff), &range);      if (res == ResOK) {        mvff->free -= RangeSize(&range);      } else if (ResIsAllocFailure(res)) {        /* CBS ran out of memory for splay nodes, which must mean that         * there were fragments on both sides: see         * <design/cbs/#function.cbs.delete.fail>. Handle this by         * deleting the whole of oldRange (which requires no         * allocation) and re-inserting the fragments. */        RangeStruct oldRange2;        res = CBSDelete(&oldRange2, CBSOfMVFF(mvff), &oldRange);        AVER(res == ResOK);        AVER(RangesEqual(&oldRange2, &oldRange));        mvff->free -= RangeSize(&oldRange);        AVER(RangeBase(&oldRange) != segBase);        {          Addr leftBase = RangeBase(&oldRange);          Addr leftLimit = segBase;          res = MVFFAddToFreeList(&leftBase, &leftLimit, mvff);        }        AVER(RangeLimit(&oldRange) != segLimit);        {          Addr rightBase = segLimit;          Addr rightLimit = RangeLimit(&oldRange);          res = MVFFAddToFreeList(&rightBase, &rightLimit, mvff);        }      } else if (res == ResFAIL) {        /* Not found in the CBS: must be found in the Freelist. */        res = FreelistDelete(&oldRange, FreelistOfMVFF(mvff), &range);        AVER(res == ResOK);        mvff->free -= RangeSize(&range);      }      AVER(res == ResOK);      AVER(RangesNest(&oldRange, &range));      /* Can't free the segment earlier, because if it was on the       * Freelist rather than the CBS then it likely contains data       * that needs to be read in order to update the Freelist. */      SegFree(seg);      mvff->total -= RangeSize(&range);    }    /* Avoid calling SegNext if the next segment would fail */    /* the loop test, mainly because there might not be a */    /* next segment. */    if (segLimit == limit) /* segment ends at end of range */      break;    b = SegFindAboveAddr(&seg, arena, segBase);    AVER(b);    segBase = SegBase(seg);    segLimit = SegLimit(seg);  }  return;}

Res ChunkInit(Chunk chunk, Arena arena, Addr base, Addr limit, Size reserved,              BootBlock boot){  Size size;  Count pages;  Shift pageShift;  Size pageTableSize;  Addr allocBase;  void *p;  Res res;  /* chunk is supposed to be uninitialized, so don't check it. */  AVERT(Arena, arena);  AVER(base != NULL);  AVER(AddrIsAligned(base, ArenaGrainSize(arena)));  AVER(base < limit);  AVER(AddrIsAligned(limit, ArenaGrainSize(arena)));  AVERT(BootBlock, boot);  chunk->serial = (arena->chunkSerial)++;  chunk->arena = arena;  RingInit(&chunk->arenaRing);  chunk->pageSize = ArenaGrainSize(arena);  chunk->pageShift = pageShift = SizeLog2(chunk->pageSize);  chunk->base = base;  chunk->limit = limit;  chunk->reserved = reserved;  size = ChunkSize(chunk);  /* .overhead.pages: Chunk overhead for the page allocation table. */  chunk->pages = pages = size >> pageShift;  res = BootAlloc(&p, boot, (size_t)BTSize(pages), MPS_PF_ALIGN);  if (res != ResOK)    goto failAllocTable;  chunk->allocTable = p;  pageTableSize = SizeAlignUp(pages * sizeof(PageUnion), chunk->pageSize);  chunk->pageTablePages = pageTableSize >> pageShift;  res = Method(Arena, arena, chunkInit)(chunk, boot);  if (res != ResOK)    goto failClassInit;  /* @@@@ Is BootAllocated always right? */  /* Last thing we BootAlloc'd is pageTable.  We requested pageSize */  /* alignment, and pageTableSize is itself pageSize aligned, so */  /* BootAllocated should also be pageSize aligned. */  AVER(AddrIsAligned(BootAllocated(boot), chunk->pageSize));  chunk->allocBase = (Index)(BootAllocated(boot) >> pageShift);  /* Init allocTable after class init, because it might be mapped there. */  BTResRange(chunk->allocTable, 0, pages);  /* Check that there is some usable address space remaining in the chunk. */  allocBase = PageIndexBase(chunk, chunk->allocBase);  AVER(allocBase < chunk->limit);  /* Add the chunk's free address space to the arena's freeLand, so that     we can allocate from it. */  if (arena->hasFreeLand) {    res = ArenaFreeLandInsert(arena, allocBase, chunk->limit);    if (res != ResOK)      goto failLandInsert;  }  TreeInit(&chunk->chunkTree);  chunk->sig = ChunkSig;  AVERT(Chunk, chunk);  ArenaChunkInsert(arena, chunk);  return ResOK;failLandInsert:  Method(Arena, arena, chunkFinish)(chunk);  /* .no-clean: No clean-ups needed past this point for boot, as we will     discard the chunk. */failClassInit:failAllocTable:  return res;}

Res VMCreate(VM *vmReturn, Size size, void *params){  Align align;  VM vm;  int pagesize;  void *addr;  Res res;  AVER(vmReturn != NULL);  AVER(params != NULL);  /* Find out the page size from the OS */  pagesize = getpagesize();  /* check the actual returned pagesize will fit in an object of */  /* type Align. */  AVER(pagesize > 0);  AVER((unsigned long)pagesize <= (unsigned long)(Align)-1);  align = (Align)pagesize;  AVER(SizeIsP2(align));  size = SizeAlignUp(size, align);  if((size == 0) || (size > (Size)(size_t)-1))    return ResRESOURCE;  /* Map in a page to store the descriptor on. */  addr = mmap(0, (size_t)SizeAlignUp(sizeof(VMStruct), align),              PROT_READ | PROT_WRITE,              MAP_ANON | MAP_PRIVATE,              -1, 0);  /* On Darwin the MAP_FAILED return value is not documented, but does   * work.  MAP_FAILED _is_ documented by POSIX.   */  if(addr == MAP_FAILED) {    int e = errno;    AVER(e == ENOMEM); /* .assume.mmap.err */    return ResMEMORY;  }  vm = (VM)addr;  vm->align = align;  /* See .assume.not-last. */  addr = mmap(0, (size_t)size,              PROT_NONE, MAP_ANON | MAP_PRIVATE,              -1, 0);  if(addr == MAP_FAILED) {    int e = errno;    AVER(e == ENOMEM); /* .assume.mmap.err */    res = ResRESOURCE;    goto failReserve;  }  vm->base = (Addr)addr;  vm->limit = AddrAdd(vm->base, size);  vm->reserved = size;  vm->mapped = (Size)0;  vm->sig = VMSig;  AVERT(VM, vm);  EVENT3(VMCreate, vm, vm->base, vm->limit);  *vmReturn = vm;  return ResOK;failReserve:  (void)munmap((void *)vm, (size_t)SizeAlignUp(sizeof(VMStruct), align));  return res;}

Bool RingIsSingle(Ring ring){  AVERT(Ring, ring);  return (ring->next == ring);}

Addr VMLimit(VM vm){  AVERT(VM, vm);  return vm->limit;}

static RankSet bufferTrivRankSet(Buffer buffer){  AVERT(Buffer, buffer);  /* vanilla buffers can only have empty rank set */  return RankSetEMPTY;}