DataMuseum.dk

top - download

    Length: 7081 (0x1ba9)
    Types: TextFile
    Notes: UNIX file
    Names: »malloc.c«

└─⟦f27320a65⟧ Bits:30001972 Commodore 900 hard disk image with partial source code
    └─⟦f4b8d8c84⟧ UNIX V7 Filesystem
        └─ ⟦this⟧ »unimenu/src/menu/malloc.c« 

TextFile

#ifndef LINT
static	char	sccs_id[] = "@(#)malloc.c	1.1 15:35:08 4/6/85";
#endif
/*
 *
 * malloc	dynamic memory allocation function
 *
 * notes	malloc allocates a block of nbytes and returns
 *		a pointer to it. Each block consists of a header
 *		and a data area of nbytes.
 *		malloc searches the list of blocks it has
 *		allocated and uses the first free block that is
 *		big enough. Adjacent free blocks are combined as we
 *		search, and large blocks are split if nbytes
 *		is smaller than the number of bytes available in the block.
 *		If no free block large enough is available, malloc
 *		calls sbrk to get more memory.
 *
 *		This malloc keeps a "fence post" at each end of the
 *		header to try and determine if the header has been overwritten
 *
 * 		This is not the most efficent scheme speedwise, but it is
 *		fairly robust and does a good job of garbage collection.
 *
 * original code 11/12/84 dan mitchell
 */
/*#define DEBUG*/

#define		BMAGIC		0x1234
#define		EMAGIC		0x4321
#define		NULL		0

/* NOTE: MINBLK should always be a multiple of 16 bytes
 * 	due to the fact that sbrk rounds up to a paragraph
 *	boundary.
 */
#define		MINBLK		16	/* smallest block we'll allocate */

typedef	struct	_m_hdr
{
	int		h_bmagic;	/* valid header flag */
	unsigned int	h_siz;		/* size of this block */
	int		h_inuse;	/* in use flag		*/
	char		*h_data;	/* pointer to the data	*/
	struct	_m_hdr	*h_nxt;		/* pointer to next header */
	struct	_m_hdr	*h_prev;	/* pointer to previous header */
	int		h_emagic;	/* valid header flag	*/
	unsigned int	h_spare;	/* round to 16 bytes	*/
} M_HDR;

static	M_HDR	mlist = { BMAGIC, 0, 1, 0, 0, 0, EMAGIC, 0 };

char	*malloc( nbytes )
unsigned int	nbytes;
{
M_HDR	*hdrp, *tmp, *last;
char	*sbrk();
unsigned int	msize;

	if ( nbytes < MINBLK )
		msize = MINBLK + sizeof(M_HDR);
	else
		msize = nbytes + sizeof(M_HDR);

	msize += 16 - (msize % 16);	/* round for sbrk() */

	last = hdrp = &mlist;
	tmp = (M_HDR *) NULL;

	while( hdrp )		/* search the list */
	{
		if ( hdrp->h_bmagic != BMAGIC || hdrp->h_emagic != EMAGIC)
		{
			/* header has been corrupted */
#ifdef DEBUG
			write(2, "malloc: Header list corrupted\r\n", 31);
			pnum(2, hdrp);
#endif
			return (NULL);
		}
		if ( !(hdrp->h_inuse) )
		{
			if ( hdrp->h_siz >= msize )
			{
				/* block not in use and big enough */
				tmp = hdrp;
				break;
			}
			else if ( !(last->h_inuse) )
			{
				/* combine these two blocks */
				if (combine(hdrp))
				{
					hdrp = last;
					if (last->h_siz >= msize)
					{
						tmp = last;
						break;
					}
				}
			}
		}
		last = hdrp;
		hdrp = hdrp->h_nxt;
	}

	/*
	 * if a block wasn't found then get more memory with sbrk
	 */
	if ( tmp == (M_HDR *) NULL )
	{
		/*
		 * this should probably sbrk for some minimum
		 * amount - like maybe 1k.
		 * for now just get enough for this block
		 */
		if ( (tmp = (M_HDR *) sbrk(msize)) == (M_HDR *) (-1) )
		{
#ifdef DEBUG
			write(2, "malloc: sbrk failed\r\n", 21);
#endif
			return (NULL);
		}
		/*
		 * install the new block at the end of the list
		 */
		last->h_nxt = tmp;
		tmp->h_bmagic = BMAGIC;
		tmp->h_siz = msize;
		tmp->h_nxt = NULL;
		tmp->h_prev = last;
		tmp->h_emagic = EMAGIC;
		tmp->h_data = (char *) (((unsigned) tmp) + sizeof(M_HDR));
	}
	else if (tmp->h_siz > (msize + sizeof(M_HDR) + MINBLK) )
	{
		/* this block is big enough to split */
		split(tmp, msize);
	}
	
	/*
	 * tmp now points to a big enough block
	 */
	tmp->h_inuse = 1;

#ifdef DEBUG
	prnmlist();
#endif
	return ( tmp->h_data );
}

/*
 * combine	combine unused blocks
 *		ptr and its previous block are combined if
 *		they are contiguous and both free
 *
 *		(bwd <-> ptr <-> fwd) becomes (bwd <-> fwd)
 *
 */		
static int combine(ptr)
M_HDR	*ptr;
{
M_HDR	*bwd, *fwd;

#ifdef DEBUG
write(2, "combine: ", 9);
pnum(2, ptr);
write(2, "\n", 1);
#endif

	bwd = ptr->h_prev;
	fwd = ptr->h_nxt;

	if (bwd == NULL || bwd->h_inuse || ptr->h_inuse)
		return (0);	/* sanity check */

	if ( (M_HDR *) ((unsigned) bwd + bwd->h_siz) == ptr )
	{
		/* blocks are contiguous - join */
		if ( fwd )
			fwd->h_prev = ptr->h_prev;
		bwd->h_nxt = fwd;
		bwd->h_siz += ptr->h_siz;
		return (1);
	}
	else
		return (0);
}

/*
 * split	break up a large block into two smaller blocks
 *
 *		(blk <--> nxt) becomes (blk <--> tmp <--> nxt)
 */
static int split(blk, size)
M_HDR 	*blk;
unsigned int	size;
{
M_HDR	*tmp;

#ifdef DEBUG
write(2, "split: ", 7);
pnum(2, blk); write(2, " ", 1);
pnum(2, size);
write(2, "\n", 1);
#endif

	tmp = (M_HDR *)((unsigned int) blk + size);
	tmp->h_nxt = blk->h_nxt;
	tmp->h_prev = blk;
	if (blk->h_nxt)
		blk->h_nxt->h_prev = tmp;
	blk->h_nxt = tmp;
	tmp->h_siz = blk->h_siz - size;
	blk->h_siz = size;
	tmp->h_bmagic = BMAGIC;
	tmp->h_emagic = EMAGIC;
	tmp->h_inuse = 0;
	tmp->h_data = (char *) ((unsigned) tmp + sizeof(M_HDR));

}


/*
 * free		free is the compainon routine to malloc
 *		it simply marks a block as unused so that
 *		the next call to malloc can use it if needed
 *
 * history	original code	11/12/84	dan mitchell
 */
free(ptr)
char	*ptr;
{
M_HDR	*hdrp;

	hdrp = (M_HDR *) ((unsigned) ptr - sizeof(M_HDR) );


	if (hdrp->h_bmagic != BMAGIC || hdrp->h_emagic != EMAGIC )
	{
		/* not a valid looking header */
		write(2, "free: bad address\r\n", 20);
#ifdef DEBUG
		pnum(2, ptr);
		write(2, "\n", 1);
		prnmlist();
#endif
		return (1);
	}
	
	hdrp->h_inuse = 0;

	return (0);
}


#ifdef DEBUG
/* some debugging code that prints out the list */
prnmlist()
{
M_HDR	*hdrp;

	hdrp = &mlist;
	printf("location, size, magicb, magice, prev, nxt, inuse\n");
	while ( hdrp )
	{
		printf("%d\t%d\t%d\t%d\t%d\t%d\t%d\n", hdrp, hdrp->h_siz,
			hdrp->h_bmagic, hdrp->h_emagic, hdrp->prev, hdrp->h_nxt,
			hdrp->h_inuse);
		hdrp = hdrp->h_nxt;
	}
}
#endif	DEBUG


/*
 * realloc	this routine trys to make better use of memory
 *		it can be used to increase or decrease the block's
 *		size.
 */
char *realloc(ptr, size)
char		*ptr;
unsigned	size;
{
M_HDR		*blk;
unsigned	newsiz;
char	*newptr, *tmp1, *tmp2;
int		i;

	blk = (M_HDR *) ( (unsigned) ptr - sizeof(M_HDR));

	if (blk->h_bmagic != BMAGIC || blk->h_emagic != EMAGIC)
		return (NULL);

	newsiz = (size + sizeof(M_HDR));

	/*
	 * see if we can split this block
	 */
	if ( blk->h_siz > (newsiz + sizeof(M_HDR) + MINBLK) )
	{
		blk->h_inuse = 1;
		split(blk, newsiz);
		return ( ptr );
	}
	
	/*
	 * if we can't split it but it's big enough already
	 * don't do anything
	 */
	if (blk->h_siz >= newsiz )
	{
		blk->h_inuse = 1;
		return (ptr);
	}

	/*
	 * otherwise get some more memory
	 */
	if ( (newptr = malloc(size)) == NULL )
	{
		return (NULL);				/* no more memory */
	}
	else
	{
		tmp1 = ptr;				/* copy old into new */
		tmp2 = newptr;
		for ( i = 0; i < size; i++)
			*tmp2++ = *tmp1++;
		free ( ptr );				/* free up the old */
		return (newptr);
	}
}


char *calloc(nelem, elsize)
unsigned	nelem;
unsigned	elsize;
{
char	*malloc();
char	*ptr, *tmp;
int	size;
	
	size = nelem * elsize;

	if ( (ptr = malloc(size)) )
	{
		for ( tmp = ptr; size; size--)
			*tmp++ = '\0';
	}

	return ( ptr );
}

cfree(ptr)
char	*ptr;
{
	free(ptr);
}