malloc.c

c库的部分源代码 用惯了操作系统提供的内存api,你是否了解系统的运行机制,这是提供动态内存分配最简单的实现代码 静态的代码库 可用各种c编译

/****************************************************************
	Memory allocator.
	Copyright 1992 Software Development Systems, Inc.
	All Rights Reserved.
****************************************************************/
#include <stdlib.h>
#include <errno.h>
#include "abbr.h"
#include "alloc.h"

/************************************************************************
    NOTE: These pointers are assumed to be ZEROed on startup.
    This happens automatically because the startup code zeroes the
    region "ram" before it calls "main".  However, if you modify
    the startup code or change the region these variables go into,
    make sure you still zero these variables before using any
    of the "malloc" routines.
************************************************************************/
struct hdr *_first_area;	/* Head of doubly linked area list */
struct hdr *_last_area;		/* Dummy area at end of last section */
struct hdr *_free_list;		/* Head of doubly linked free list */

/************************************************************************
    Insert area pointed to by "p" into the doubly linked free list.
    (Assumes that DISABLE was already called.)
************************************************************************/
void _infree( struct hdr *p ) {
    p->bckfree = 0;
    if ( p->fwdfree = _free_list ) _free_list->bckfree = p;
    _free_list = p; }

/************************************************************************
    Remove area pointed to by "p" from the doubly linked free list.
    (Assumes that DISABLE was already called.)
************************************************************************/
void _rmfree( struct hdr *p ) {  register struct hdr *f, *b;
    f = p->fwdfree;
    b = p->bckfree;
    if ( b ) b->fwdfree = f;
    else     _free_list = f;
    if ( f ) f->bckfree = b; }

/***********************************************************************
    Allocate a new area of at least "sizeneeded" bytes.
    Return zero on failure, setting errno to ENOMEM.
    Also return zero if "sizeneeded" is zero.
***********************************************************************/
void *malloc( register size_t sizeneeded ) {
    register struct hdr *p, *x, *bestbig;
    register size_t sizebig, size;  auto long realsz;

    if ( !sizeneeded ) return 0;

    sizeneeded = ((sizeneeded + ALIGNMASK) & ~ALIGNMASK) + sizeof(struct busy);
    if ( sizeneeded < sizeof(struct hdr) ) sizeneeded = sizeof(struct hdr);

    /****************************************************************
	Look down the free list to find an area which contains
	enough bytes.  The first one found that is large enough
	but not twice as large will be used.  We keep track of
	the smallest one that is twice as large or larger so we
	can use it if we don't find anything smaller in the list.
    ****************************************************************/
    bestbig = 0;	/* best big one so far (size will be in sizebig) */
    sizebig = 0;	/* no size yet (avoids warning message) */
    DISABLE();
    for ( p = _free_list; p; p = p->fwdfree ) {
	if ( (size = (char*)p->busy.nextarea - (char*)p) >= sizeneeded ) {
	    if ( size < sizeneeded+sizeneeded ) break;
	    if ( !bestbig || size<sizebig ) { bestbig = p; sizebig = size; }}}

    if ( !p && !(p = bestbig) ) {
	/****************************************************************
	    No available area is big enough.  Get a new section of
	    memory from the system with enough extra bytes for a dummy
	    area header at the end of the section.  Turn the section
	    into a free area and a dummy busy area.  (The actual amount
	    of memory allocated in the section by "mbrk" will often be
	    more than requested, at the discretion of "mbrk".)
	****************************************************************/
	if ( !(p=(struct hdr*)mbrk(
		    (long)(sizeneeded+sizeof(struct busy)), &realsz )) ) {
	    errno = ENOMEM;
	    ENABLE();
	    return 0; }

	realsz &= ~ALIGNMASK;

	if ( _last_area &&
	     (char*)p == ((char*)_last_area + sizeof(struct busy)) ) {
	    /********************************************************
		New section is contiguous with the last section
		returned by "mbrk" so use the old "_last_area" header
		as the header for the new free area.
		(Note: section sizes returned by "mbrk" must be a
		multiple of the size of a pointer for the contiguous
		test to succeed.)
	    ********************************************************/
	    p = _last_area;
	    realsz += sizeof(struct busy);
	    /********************************************************
		Check if previous area is free and combine it now.
	    ********************************************************/
	    if ( (x = p->busy.prevarea) && !ISBUSY(x) ) {
		_rmfree( x );		/* remove area x from free list */
		realsz += (char*)p - (char*)x;
		p = x; }}		/* prepare to rewrite header of x */
	else {
	    /********************************************************
		Create a new header for the new free area.
	    ********************************************************/
	    if ( _last_area ) {
		p->busy.prevarea = _last_area;
		_last_area->busy.nextarea = (struct hdr*)((char*)p+BUSY); }
	    else {
		p->busy.prevarea = 0;
		_first_area = p; }}

	/********************************************************
	    Reserve a minimal dummy area (just a busy header)
	    at the end of the new memory section to represent
	    any gap that may occur between this section and the
	    next section.  The "nextarea" pointer of the new
	    free area points to this busy dummy area.
	********************************************************/
	p->busy.nextarea = _last_area =
	    (struct hdr *)((char*)p + realsz - sizeof(struct busy));
	_last_area->busy.prevarea = p;
	_last_area->busy.nextarea = (struct hdr *)BUSY;

	/****************************************************************
	    Insert the new free area into the doubly linked free list.
	****************************************************************/
	_infree(p); }

    /****************************************************************
	The free area to use is pointed to by "p".
    ****************************************************************/
    if ( (char*)p->busy.nextarea-(char*)p-sizeneeded > sizeof(struct hdr) ) {
	/***************************************************************
	    Remove free area "p" from the free list, split it into
	    two areas, putting the second area in the free list
	    and turning first area into a busy area and returning
	    its data pointer.
	    (NOTE: although this is slightly more work than leaving
	    the first area in the free list and making the second
	    area be busy, it is better to keep the free area at the
	    end of the section so that it might be combined with
	    area in a newly allocated contiguous section later.)
	***************************************************************/
	x = (struct hdr*)((char*)p + sizeneeded);
	p->busy.nextarea->busy.prevarea = x;
	x->busy.prevarea = p;
	x->busy.nextarea = p->busy.nextarea;
	p->busy.nextarea = (struct hdr*)((char*)x + BUSY);
	_rmfree( p );
	_infree( x ); }
    else {
	/*****************************************************************
	    Remove free area "p" from the doubly linked free list,
	    and turn free area "p" into a busy area.
	*****************************************************************/
	_rmfree( p );
	p->busy.nextarea = (struct hdr*)((char*)p->busy.nextarea+BUSY); }

    /****************************************************************
	Return data pointer for area "p".
    ****************************************************************/
    ENABLE();
    return (char*)p + sizeof(struct busy); }