ncbi_heapmgr.c

ncbi源码

        }
        p = b;
        b = (SHEAP_Block*)((char*) b + b->size);
    }

    /* Heap exhausted, no free block found */
    if (free >= size)
        b = s_HEAP_Collect(heap);
    else if (!heap->expand)
        return 0;
    else {
        TNCBI_Size hsize =
            (TNCBI_Size) _HEAP_ALIGN(heap->size + size, heap->chunk);
        ptrdiff_t dp = (char*) p - (char*) heap->base;
        void* base;

        if (!(base = (*heap->expand)(heap->base, hsize, heap->arg)))
            return 0;
        p = (SHEAP_Block*)((char*) base + dp);
        if (!HEAP_ISLAST(p))
            CORE_LOG(eLOG_Warning, "Heap Alloc: Last block lost");
        if (HEAP_ISUSED(p)) {
            p->flag &= ~HEAP_LAST;
            /* New block is the very top on the heap */
            b = (SHEAP_Block*)((char*) base + heap->size);
            b->size = hsize - heap->size;
            b->flag = HEAP_FREE | HEAP_LAST;
        } else {
            /* Extend last free block */
            p->size += hsize - heap->size;
            b = p;
        }
        heap->base = base;
        heap->size = hsize;
    }
    assert(b && HEAP_ISFREE(b) && b->size >= size);
    return s_HEAP_Take(b, size);
}


void HEAP_Free(HEAP heap, SHEAP_Block* ptr)
{
    SHEAP_Block* b, *p = 0;

    if (!heap || !ptr) {
        if (ptr)
            CORE_LOG(eLOG_Warning, "Heap Free: Cannot free in NULL heap");
        return;
    }

    if (!heap->chunk) {
        CORE_LOG(eLOG_Warning, "Heap Free: Heap is read-only");
        return;
    }

    b = (SHEAP_Block*) heap->base;
    while ((char*) b < (char*) heap->base + heap->size) {
        if (HEAP_ISFREE(b)) {
            if (b == ptr) {
                CORE_LOG(eLOG_Warning, "Heap Free: Freeing free block");
                return;
            }
        } else if (HEAP_ISUSED(b)) {
            if (b == ptr) {
                b->flag = HEAP_FREE | (b->flag & HEAP_LAST);
                s_HEAP_Join(p, b);
                return;
            }
        } else {
            CORE_LOGF(eLOG_Warning,
                      ("Heap Free: Heap corrupted (0x%08X, %u)",
                       b->flag, (unsigned) b->size));
            return;
        }
        p = b;
        b = (SHEAP_Block*)((char*) p + p->size);
    }
    CORE_LOG(eLOG_Warning, "Heap Free: Block not found");
}


SHEAP_Block* HEAP_Walk(const HEAP heap, const SHEAP_Block* p)
{
    SHEAP_Block* b;

    if (!heap) {
        CORE_LOG(eLOG_Warning, "Heap Walk: NULL heap");
        return 0;
    }
    if (!p ||
        ((char*) p >= (char*) heap->base &&
         (char*) p <  (char*) heap->base + heap->size)) {
        b = (SHEAP_Block*)(p ? (char*) p + p->size : (char*) heap->base);
        if ((char*) b < (char*) heap->base + heap->size) {
            if (b->size >= sizeof(*b) &&
                b->size == (TNCBI_Size) HEAP_ALIGN(b->size) &&
                (char*) b + b->size <= (char*) heap->base + heap->size &&
                (HEAP_ISFREE(b) || HEAP_ISUSED(b))) {
                /* Block 'b' seems valid, but... */
                if (!p)
                    return b;
                if (HEAP_ISLAST(p))
                    CORE_LOG(eLOG_Warning, "Heap Walk: Misplaced last block");
                else if (HEAP_ISFREE(b) && HEAP_ISFREE(p)) {
                    const SHEAP_Block* c = (const SHEAP_Block*) heap->base;
                    while ((char*) c < (char*) p) {
                        if (HEAP_ISFREE(c) &&
                            (char*) c + c->size >= (char*) b + b->size)
                            break;
                        c = (SHEAP_Block*)((char*) c + c->size);
                    }
                    if ((char*) c < (char*) p)
                        return b;
                    CORE_LOG(eLOG_Warning, "Heap Walk: Adjacent free blocks");
                } else
                    return b;
            } else
                CORE_LOGF(eLOG_Warning,
                          ("Heap Walk: Heap corrupted (0x%08X, %u)",
                           b->flag, (unsigned) b->size));
        } else if ((char*) b > (char*) heap->base + heap->size)
            CORE_LOG(eLOG_Warning, "Heap Walk: Heap corrupted");
        else if (!HEAP_ISLAST(p))
            CORE_LOG(eLOG_Warning, "Heap Walk: Last block lost");
    } else
        CORE_LOG(eLOG_Warning, "Heap Walk: Alien pointer passed");
    return 0;
}


TNCBI_Size HEAP_Trim(HEAP heap)
{
    TNCBI_Size   size, last_size;
    SHEAP_Block* f;

    if (!heap)
        return 0;
    if (!heap->chunk) {
        CORE_LOG(eLOG_Error, "Heap Trim: Heap is read-only");
        return 0;
    }

    if (!(f =s_HEAP_Collect(heap)) || HEAP_ISUSED(f) || f->size < heap->chunk){
        last_size = 0;
        size      = heap->size;
    } else if ((char*) f != heap->base) {
        assert(f->size >= _HEAP_ALIGNMENT);
        last_size = f->size % heap->chunk;
        if (last_size) {
            if (last_size < _HEAP_ALIGNMENT)
                last_size += heap->chunk;
            size = heap->size - f->size + last_size;
        } else {
            SHEAP_Block* b = (SHEAP_Block*) heap->base, *p = 0;
            while (b != f) {
                p = b;
                b = (SHEAP_Block*)((char*) b + b->size);
            }
            size = heap->size - f->size;
            assert(p);
            f = p;
        }
    } else {
        last_size = heap->chunk;
        size      = heap->chunk;
    }

    assert(size % heap->chunk == 0);
    if (heap->expand) {
        void* base = (*heap->expand)(heap->base, size, heap->arg);
        if (!base)
            return 0;
        if (f) {
            ptrdiff_t dp = (char*) f - (char*) heap->base;
            f = (SHEAP_Block*)((char*) base + dp);
            f->flag |= HEAP_LAST;
            if (last_size)
                f->size = last_size;
        }
        heap->base = base;
        heap->size = size;
    } else if (size != heap->size)
        CORE_LOG(eLOG_Error, "Heap Trim: Heap is not trimmable");
    return heap->size;
}


HEAP HEAP_CopySerial(const HEAP heap, size_t extra, int serial)
{
    HEAP   newheap;
    void*  newbase;

    extra = HEAP_ALIGN(extra);
    if (!heap ||
        !(newbase = malloc(HEAP_ALIGN(heap->size) + extra + sizeof(*newheap))))
        return 0;
    memcpy(newbase, heap->base, heap->size);
    newheap = (HEAP)((char*) newbase + HEAP_ALIGN(heap->size) + extra);
    newheap->base   = newbase;
    newheap->size   = heap->size;
    newheap->chunk  = 0/*read-only*/;
    newheap->expand = 0;
    newheap->arg    = 0;
    newheap->copy   = serial ? serial : 1/*copy*/;
    return newheap;
}


void HEAP_Detach(HEAP heap)
{
    if (heap)
        free(heap->copy ? heap->base : heap);
}


void HEAP_Destroy(HEAP heap)
{
    if (heap) {
        if (!heap->chunk && !heap->copy)
            CORE_LOG(eLOG_Warning, "Heap Destroy: Heap is read-only");
        else if (heap->expand/*NB: false for heap copies*/)
            (*heap->expand)(heap->base, 0, heap->arg);
        HEAP_Detach(heap);
    }
}


void* HEAP_Base(const HEAP heap)
{
    return heap ? heap->base : 0;
}


TNCBI_Size HEAP_Size(const HEAP heap)
{
    return heap ? heap->size : 0;
}


int HEAP_Serial(const HEAP heap)
{
    return heap ? heap->copy : 0;
}


/*
 * --------------------------------------------------------------------------
 * $Log: ncbi_heapmgr.c,v $
 * Revision 1000.0  2003/10/29 16:36:50  gouriano
 * PRODUCTION: IMPORTED [ORIGINAL] Dev-tree R6.26
 *
 * Revision 6.26  2003/10/02 14:52:23  lavr
 * Wrapped long lines in the change log
 *
 * Revision 6.25  2003/09/24 02:56:55  ucko
 * HEAP_AttachEx: size_t -> TNCBI_Size per prototype (needed on 64-bit archs)
 *
 * Revision 6.24  2003/09/23 21:06:30  lavr
 * +HEAP_AttachEx()
 *
 * Revision 6.23  2003/08/28 21:09:58  lavr
 * Accept (and allocate) additional heap extent in HEAP_CopySerial()
 *
 * Revision 6.22  2003/08/25 16:53:37  lavr
 * Add/remove spaces here and there to comply with coding rules...
 *
 * Revision 6.21  2003/08/25 16:47:08  lavr
 * Fix in pointer arith since the base changed from "char*" to "void*"
 *
 * Revision 6.20  2003/08/25 14:50:50  lavr
 * Heap arena ptrs changed to be "void*";  expand routine to take user arg
 *
 * Revision 6.19  2003/08/11 19:08:04  lavr
 * HEAP_Attach() reimplemented via HEAP_AttachEx() [not public yet]
 * HEAP_Trim() fixed to call expansion routine where applicable
 *
 * Revision 6.18  2003/07/31 17:54:03  lavr
 * +HEAP_Trim()
 *
 * Revision 6.17  2003/03/24 19:45:15  lavr
 * Added few minor changes and comments
 *
 * Revision 6.16  2002/08/16 15:37:22  lavr
 * Warn if allocation attempted on a NULL heap
 *
 * Revision 6.15  2002/08/12 15:15:15  lavr
 * More thorough check for the free-in-the-middle heap blocks
 *
 * Revision 6.14  2002/04/13 06:33:52  lavr
 * +HEAP_Base(), +HEAP_Size(), +HEAP_Serial(), new HEAP_CopySerial()
 *
 * Revision 6.13  2001/07/31 15:07:58  lavr
 * Added paranoia log message: freeing a block in a NULL heap
 *
 * Revision 6.12  2001/07/13 20:09:27  lavr
 * If remaining space in a block is equal to block header,
 * do not leave this space as a padding of the block been allocated,
 * but instead form a new block consisting only of the header.
 * The block becomes a subject for a later garbage collecting.
 *
 * Revision 6.11  2001/07/03 20:24:03  lavr
 * Added function: HEAP_Copy()
 *
 * Revision 6.10  2001/06/25 15:32:41  lavr
 * Typo fixed
 *
 * Revision 6.9  2001/06/19 22:22:56  juran
 * Heed warning:  Make s_HEAP_Take() static
 *
 * Revision 6.8  2001/06/19 19:12:01  lavr
 * Type change: size_t -> TNCBI_Size; time_t -> TNCBI_Time
 *
 * Revision 6.7  2001/03/02 20:08:26  lavr
 * Typos fixed
 *
 * Revision 6.6  2001/02/14 22:03:09  lavr
 * 0x... constants explicitly made unsigned
 *
 * Revision 6.5  2001/01/12 23:51:39  lavr
 * Message logging modified for use LOG facility only
 *
 * Revision 6.4  2000/05/23 21:41:07  lavr
 * Alignment changed to 'double'
 *
 * Revision 6.3  2000/05/17 14:22:30  lavr
 * Small cosmetic changes
 *
 * Revision 6.2  2000/05/16 15:06:05  lavr
 * Minor changes for format <-> argument correspondence in warnings
 *
 * Revision 6.1  2000/05/12 18:33:44  lavr
 * First working revision
 *
 * ==========================================================================
 */