sbheap.c

C标准库源代码

            //  if region count was zero, set bit in region vector
            //  set bit in header entry vector, increment region count
            if (indEntry < 32)
            {
                if (pRegion->cntRegionSize[indEntry]++ == 0)
                    pHeader->bitvEntryHi |= 0x80000000L >> indEntry;
                pRegion->bitvGroupHi[indGroup] |= 0x80000000L >> indEntry;
            }
            else
            {
                if (pRegion->cntRegionSize[indEntry]++ == 0)
                    pHeader->bitvEntryLo |= 0x80000000L >> (indEntry - 32);
                pRegion->bitvGroupLo[indGroup] |= 0x80000000L >>
                                                           (indEntry - 32);
            }
        }
    }

    //  adjust the entry size front and back
    pEntry->sizeFront = sizeEntry;
    ((PENTRYEND)((char *)pEntry + sizeEntry -
                        sizeof(ENTRYEND)))->sizeBack = sizeEntry;

        //  one less allocation in group - test if empty
    if (--pGroup->cntEntries == 0)
    {
        //  if a group has been deferred, free that group
        if (__sbh_pHeaderDefer)
        {
            //  if now zero, decommit the group data heap
            pHeapDecommit = (void *)((char *)__sbh_pHeaderDefer->pHeapData +
                                    __sbh_indGroupDefer * BYTES_PER_GROUP);
            VirtualFree(pHeapDecommit, BYTES_PER_GROUP, MEM_DECOMMIT);

            //  set bit in commit vector
            __sbh_pHeaderDefer->bitvCommit |=
                                          0x80000000 >> __sbh_indGroupDefer;

            //  clear entry vector for the group and header vector bit
            //  if needed
            __sbh_pHeaderDefer->pRegion->bitvGroupLo[__sbh_indGroupDefer] = 0;
            if (--__sbh_pHeaderDefer->pRegion->cntRegionSize[63] == 0)
                __sbh_pHeaderDefer->bitvEntryLo &= ~0x00000001L;

            //  if commit vector is the initial value,
            //  remove the region if it is not the last
            if (__sbh_pHeaderDefer->bitvCommit == BITV_COMMIT_INIT)
            {
                //  release the address space for heap data
                VirtualFree(__sbh_pHeaderDefer->pHeapData, 0, MEM_RELEASE);

                //  free the region memory area
                HeapFree(_crtheap, 0, __sbh_pHeaderDefer->pRegion);

                //  remove entry from header list by copying over
                memmove((void *)__sbh_pHeaderDefer,
                            (void *)(__sbh_pHeaderDefer + 1),
                            (int)(__sbh_pHeaderList + __sbh_cntHeaderList) -
                            (int)(__sbh_pHeaderDefer + 1));
                __sbh_cntHeaderList--;

                //  if pHeader was after the one just removed, adjust it
                if (pHeader > __sbh_pHeaderDefer)
                    pHeader--;

                //  initialize scan pointer to start of list
                __sbh_pHeaderScan = __sbh_pHeaderList;
            }
        }

        //  defer the group just freed
        __sbh_pHeaderDefer = pHeader;
        __sbh_indGroupDefer = indGroup;
    }
}

/***
*void * __sbh_alloc_block(intSize) - allocate a block
*
*Purpose:
*       Allocate a block from the small-block heap, the specified number of
*       bytes in size.
*
*Entry:
*       intSize - size of the allocation request in bytes
*
*Exit:
*       Returns a pointer to the newly allocated block, if successful.
*       Returns NULL, if failure.
*
*Exceptions:
*
*******************************************************************************/

void * __cdecl __sbh_alloc_block (int intSize)
{
    PHEADER     pHeaderLast = __sbh_pHeaderList + __sbh_cntHeaderList;
    PHEADER     pHeader;
    PREGION     pRegion;
    PGROUP      pGroup;
    PENTRY      pEntry;
    PENTRY      pHead;
    BITVEC      bitvEntryLo;
    BITVEC      bitvEntryHi;
    BITVEC      bitvTest;
    int         sizeEntry;
    int         indEntry;
    int         indGroupUse;
    int         sizeNewFree;
    int         indNewFree;

    //  add 8 bytes entry overhead and round up to next para size
    sizeEntry = (intSize + 2 * sizeof(int) + (BYTES_PER_PARA - 1))
                                          & ~(BYTES_PER_PARA - 1);

    //  determine index and mask from entry size
    //  Hi MSB: bit 0      size: 1 paragraph
    //          bit 1            2 paragraphs
    //          ...              ...
    //          bit 30           31 paragraphs
    //          bit 31           32 paragraphs
    //  Lo MSB: bit 0      size: 33 paragraph
    //          bit 1            34 paragraphs
    //          ...              ...
    //          bit 30           63 paragraphs
    //          bit 31           64+ paragraphs
    indEntry = (sizeEntry >> 4) - 1;
    if (indEntry < 32)
    {
        bitvEntryHi = 0xffffffffUL >> indEntry;
        bitvEntryLo = 0xffffffffUL;
    }
    else
    {
        bitvEntryHi = 0;
        bitvEntryLo = 0xffffffffUL >> (indEntry - 32);
    }

    //  scan header list from rover to end for region with a free
    //  entry with an adequate size
    pHeader = __sbh_pHeaderScan;
    while (pHeader < pHeaderLast)
    {
        if ((bitvEntryHi & pHeader->bitvEntryHi) |
            (bitvEntryLo & pHeader->bitvEntryLo))
            break;
        pHeader++;
    }

    //  if no entry, scan from list start up to the rover
    if (pHeader == pHeaderLast)
    {
        pHeader = __sbh_pHeaderList;
        while (pHeader < __sbh_pHeaderScan)
        {
            if ((bitvEntryHi & pHeader->bitvEntryHi) |
                (bitvEntryLo & pHeader->bitvEntryLo))
                break;
            pHeader++;
        }

        //  no free entry exists, scan list from rover to end
        //  for available groups to commit
        if (pHeader == __sbh_pHeaderScan)
        {
            while (pHeader < pHeaderLast)
            {
                if (pHeader->bitvCommit)
                    break;
                pHeader++;
            }

            //  if no available groups, scan from start to rover
            if (pHeader == pHeaderLast)
            {
                pHeader = __sbh_pHeaderList;
                while (pHeader < __sbh_pHeaderScan)
                {
                    if (pHeader->bitvCommit)
                        break;
                    pHeader++;
                }

                //  if no available groups, create a new region
                if (pHeader == __sbh_pHeaderScan)
                    if (!(pHeader = __sbh_alloc_new_region()))
                        return NULL;
            }

            //  commit a new group in region associated with pHeader
            if ((pHeader->pRegion->indGroupUse =
                                    __sbh_alloc_new_group(pHeader)) == -1)
                return NULL;
        }
    }
    __sbh_pHeaderScan = pHeader;

    pRegion = pHeader->pRegion;
    indGroupUse = pRegion->indGroupUse;

    //  determine the group to allocate from
    if (indGroupUse == -1 ||
                    !((bitvEntryHi & pRegion->bitvGroupHi[indGroupUse]) |
                      (bitvEntryLo & pRegion->bitvGroupLo[indGroupUse])))
    {
        //  preferred group could not allocate entry, so
        //  scan through all defined vectors
        indGroupUse = 0;
        while (!((bitvEntryHi & pRegion->bitvGroupHi[indGroupUse]) |
                 (bitvEntryLo & pRegion->bitvGroupLo[indGroupUse])))
            indGroupUse++;
    }
    pGroup = &pRegion->grpHeadList[indGroupUse];

    //  determine bucket index
    indEntry = 0;

    //  get high entry intersection - if zero, use the lower one
    if (!(bitvTest = bitvEntryHi & pRegion->bitvGroupHi[indGroupUse]))
    {
        indEntry = 32;
        bitvTest = bitvEntryLo & pRegion->bitvGroupLo[indGroupUse];
    }
       while ((int)bitvTest >= 0)
    {
           bitvTest <<= 1;
           indEntry++;
    }
    pEntry = pGroup->listHead[indEntry].pEntryNext;

    //  compute size and bucket index of new free entry

    //  for zero-sized entry, the index is -1
    sizeNewFree = pEntry->sizeFront - sizeEntry;
    indNewFree = (sizeNewFree >> 4) - 1;
    if (indNewFree > 63)
        indNewFree = 63;

    //  only modify entry pointers if bucket index changed
    if (indNewFree != indEntry)
    {
        //  test entry is sole member of bucket (next == prev),
        if (pEntry->pEntryNext == pEntry->pEntryPrev)
        {
            //  clear bit in group vector, decrement region count
            //  if region count is now zero, clear bit in region vector
            if (indEntry < 32)
            {
                pRegion->bitvGroupHi[indGroupUse] &=
                                            ~(0x80000000L >> indEntry);
                if (--pRegion->cntRegionSize[indEntry] == 0)
                    pHeader->bitvEntryHi &= ~(0x80000000L >> indEntry);
            }
            else
            {
                pRegion->bitvGroupLo[indGroupUse] &=
                                            ~(0x80000000L >> (indEntry - 32));
                if (--pRegion->cntRegionSize[indEntry] == 0)
                    pHeader->bitvEntryLo &= ~(0x80000000L >> (indEntry - 32));
            }
        }

        //  unlink entry from list
        pEntry->pEntryPrev->pEntryNext = pEntry->pEntryNext;
        pEntry->pEntryNext->pEntryPrev = pEntry->pEntryPrev;

        //  if free entry size is still nonzero, reconnect it
        if (sizeNewFree != 0)
        {
            //  add entry to the start of the bucket list
            pHead = (PENTRY)((char *)&pGroup->listHead[indNewFree] -
                                                           sizeof(int));
            pEntry->pEntryNext = pHead->pEntryNext;
            pEntry->pEntryPrev = pHead;
            pHead->pEntryNext = pEntry;
            pEntry->pEntryNext->pEntryPrev = pEntry;

            //  test entry is sole member of bucket (next == prev),
            if (pEntry->pEntryNext == pEntry->pEntryPrev)
            {
                //  if region count was zero, set bit in region vector
                //  set bit in group vector, increment region count
                if (indNewFree < 32)
                {
                    if (pRegion->cntRegionSize[indNewFree]++ == 0)
                        pHeader->bitvEntryHi |= 0x80000000L >> indNewFree;
                    pRegion->bitvGroupHi[indGroupUse] |=
                                                0x80000000L >> indNewFree;
                }
                else
                {
                    if (pRegion->cntRegionSize[indNewFree]++ == 0)
                        pHeader->bitvEntryLo |=
                                        0x80000000L >> (indNewFree - 32);
                    pRegion->bitvGroupLo[indGroupUse] |=
                                        0x80000000L >> (indNewFree - 32);
                }
            }
        }
    }

    //  change size of free entry (front and back)
    if (sizeNewFree != 0)
    {
        pEntry->sizeFront = sizeNewFree;
        ((PENTRYEND)((char *)pEntry + sizeNewFree -
                    sizeof(ENTRYEND)))->sizeBack = sizeNewFree;
    }

    //  mark the allocated entry
    pEntry = (PENTRY)((char *)pEntry + sizeNewFree);
    pEntry->sizeFront = sizeEntry + 1;
    ((PENTRYEND)((char *)pEntry + sizeEntry -
                    sizeof(ENTRYEND)))->sizeBack = sizeEntry + 1;

    //  one more allocation in group - test if group was empty
    if (pGroup->cntEntries++ == 0)
    {
        //  if allocating into deferred group, cancel deferral
        if (pHeader == __sbh_pHeaderDefer &&
                                  indGroupUse == __sbh_indGroupDefer)
            __sbh_pHeaderDefer = NULL;
    }

    pRegion->indGroupUse = indGroupUse;

    return (void *)((char *)pEntry + sizeof(int));
}

/***
*PHEADER __sbh_alloc_new_region()
*
*Purpose:
*       Add a new HEADER structure in the header list.  Allocate a new
*       REGION structure and initialize.  Reserve memory for future
*       group commitments.
*
*Entry:
*       None.
*
*Exit:
*       Returns a pointer to newly created HEADER entry, if successful.
*       Returns NULL, if failure.
*
*Exceptions:
*
*******************************************************************************/

PHEADER __cdecl __sbh_alloc_new_region (void)
{
    PHEADER     pHeader;

    //  create a new entry in the header list

    //  if list if full, realloc to extend its size
    if (__sbh_cntHeaderList == __sbh_sizeHeaderList)
    {