#define DEBUG#undef DEBUG#include <stdio.h>#include "runtime.h"/**//* allocate/free routines for heap blocks/* Note that everything called from outside the garbage collector/* should be prepared to abort at any point as the result of a signal./**//* * Free heap blocks are kept on a list sorted by address. * The hb_hdr.hbh_sz field of a free heap block contains the length * (in bytes) of the entire block. * Neighbors are coalesced. */struct hblk *savhbp = (struct hblk *)0;  /* heap block preceding next */					 /* block to be examined by   */					 /* allochblk.                *//* * Return 1 if there is a heap block sufficient for object size sz, * 0 otherwise.  Advance savhbp to point to the block prior to the * first such block. */int sufficient_hb(sz)int sz;{register struct hblk *hbp;struct hblk *prevhbp;int size_needed, size_avail;int first_time = 1;    size_needed = WORDS_TO_BYTES(sz>0? sz : -sz);    size_needed = (size_needed+sizeof(struct hblkhdr)+HBLKSIZE-1) & ~HBLKMASK;#   ifdef DEBUG	printf("sufficient_hb: sz = %d, size_needed = 0x%X\n", sz, size_needed);#   endif    /* search for a big enough block in free list */	hbp = savhbp;	for(;;) {	    prevhbp = hbp;	    hbp = ((prevhbp == (struct hblk *)0)		    ? hblkfreelist		    : prevhbp->hb_next);	    if( prevhbp == savhbp && !first_time) {		/* no sufficiently big blocks on free list */		return(0);	    }	    first_time = 0;	    if( hbp == (struct hblk *)0 ) continue;	    size_avail = hbp->hb_sz;	    if( size_avail >= size_needed ) {		savhbp = prevhbp;		return(1);	    }	}}/* * Allocate (and return pointer to) a heap block *   for objects of size |sz|. * * NOTE: Caller is responsible for adding it to global hblklist *       and for building an object freelist in it. * * The new block is guaranteed to be cleared if sz > 0. */struct hblk *allochblk(sz)long sz;{    register struct hblk *thishbp;    register struct hblk *hbp;    struct hblk *prevhbp;    long size_needed,            /* number of bytes in requested objects */         uninit,                 /* => Found uninitialized block         */         size_avail;    int first_time = 1;    char *sbrk();			/* data segment size increasing	*/    char *brk();			/* functions			*/    size_needed = WORDS_TO_BYTES(sz>0? sz : -sz);    size_needed = (size_needed+sizeof(struct hblkhdr)+HBLKSIZE-1) & ~HBLKMASK;#   ifdef DEBUG	printf("(allochblk) sz = %x, size_needed = 0x%X\n", sz, size_needed);#   endif    /* search for a big enough block in free list */	hbp = savhbp;	for(;;) {	    prevhbp = hbp;	    hbp = ((prevhbp == (struct hblk *)0)                    ? hblkfreelist		    : prevhbp->hb_next);	    if( prevhbp == savhbp && !first_time) {		/* no sufficiently big blocks on free list, */		/* let thishbp --> a newly-allocated block, */		/* free it (to merge into existing block    */		/* list) and start the search again, this   */		/* time with guaranteed success.            */                  int size_to_get = size_needed + hincr * HBLKSIZE;		  extern int holdsigs();		  int Omask;		  /* Don't want to deal with signals in the middle of this */		      Omask = holdsigs();                    update_hincr;		    thishbp = HBLKPTR(((unsigned)sbrk(0))+HBLKSIZE-1 );		    heaplim = (char *) (((unsigned)thishbp) + size_to_get);		    if( (brk(heaplim)) == ((char *)-1) ) {                        write(2,"Out of Memory!  Giving up ...\n", 30);			exit(-1);		    }#                   ifdef PRINTSTATS			printf("Need to increase heap size by %d\n",			       size_to_get);			fflush(stdout);#                   endif		    heapsize += size_to_get;		    thishbp->hb_sz = 			BYTES_TO_WORDS(size_to_get - sizeof(struct hblkhdr));		    freehblk(thishbp);		    /* Reenable signals */		      sigsetmask(Omask);		    hbp = savhbp;		    first_time = 1;		continue;	    }	    first_time = 0;	    if( hbp == (struct hblk *)0 ) continue;	    size_avail = hbp->hb_sz;	    if( size_avail >= size_needed ) {		/* found a big enough block       */		/* let thishbp --> the block      */		/* set prevhbp, hbp to bracket it */		    thishbp = hbp;		    if( size_avail == size_needed ) {			hbp = hbp->hb_next;			uninit = thishbp -> hb_uninit;		    } else {			uninit = thishbp -> hb_uninit;			thishbp -> hb_uninit = 1; 				/* Just in case we get interrupted by a */				/* signal                               */			hbp = (struct hblk *)			    (((unsigned)thishbp) + size_needed);			hbp->hb_uninit = uninit;			hbp->hb_next = thishbp->hb_next;			hbp->hb_sz = size_avail - size_needed;		    }		/* remove *thishbp from hblk freelist */		    if( prevhbp == (struct hblk *)0 ) {			hblkfreelist = hbp;		    } else {			prevhbp->hb_next = hbp;		    }		/* save current list search position */		    savhbp = prevhbp;		break;	    }	}    /* set size and mask field of *thishbp correctly */	thishbp->hb_sz = sz;	thishbp->hb_mask = -1;  /* may be changed by new_hblk */    /* Clear block if necessary */	if (uninit && sz > 0) {	    register word * p = &(thishbp -> hb_body[0]);	    register word * plim;	    plim = (word *)(((char *)thishbp) + size_needed);	    while (p < plim) {		*p++ = 0;	    }	}    /* Clear mark bits */	{	    register word *p = (word *)(&(thishbp -> hb_marks[0]));	    register word * plim = (word *)(&(thishbp -> hb_marks[MARK_BITS_SZ]));	    while (p < plim) {		*p++ = 0;	    }	}#   ifdef DEBUG	printf("Returning 0x%X\n", thishbp);	fflush(stdout);#   endif    return( thishbp );} /* Clear the header information in a previously allocated heap block p *//* so that it can be coalesced with an initialized heap block.         */static clear_header(p)register struct hblk *p;{    p -> hb_sz = 0;#   ifndef HBLK_MAP      p -> hb_index = (struct hblk **)0;#   endif    p -> hb_next = 0;    p -> hb_mask = 0;#   if MARK_BITS_SZ <= 60	/* Since this block was deallocated, only spurious mark      */	/* bits corresponding to the header could conceivably be set */	p -> hb_marks[0] = 0;	p -> hb_marks[1] = 0;#   else	--> fix it#   endif}/* * Free a heap block. * * Assume the block is not currently on hblklist. * * Coalesce the block with its neighbors if possible. * All mark words (except possibly the first) are assumed to be cleared. * The body is assumed to be cleared unless hb_uninit is nonzero. */voidfreehblk(p)register struct hblk *p;{register struct hblk *hbp, *prevhbp;register int size;    /* savhbp may become invalid due to coalescing.  Clear it. */	savhbp = (struct hblk *)0;    size = p->hb_sz;    if( size < 0 ) size = -size;    size = 	((WORDS_TO_BYTES(size)+sizeof(struct hblkhdr)+HBLKSIZE-1)		 & (~HBLKMASK));    p->hb_sz = size;    prevhbp = (struct hblk *) 0;    hbp = hblkfreelist;    while( (hbp != (struct hblk *)0) && (hbp < p) ) {	prevhbp = hbp;	hbp = hbp->hb_next;    }    /* Coalesce with successor, if possible */      if( (((unsigned)p)+size) == ((unsigned)hbp) ) {	(p -> hb_uninit) |= (hbp -> hb_uninit);	p->hb_next = hbp->hb_next;	p->hb_sz += hbp->hb_sz;	if (!p -> hb_uninit) clear_header(hbp);      } else {	p->hb_next = hbp;      }    if( prevhbp == (struct hblk *)0 ) {	hblkfreelist = p;    } else if( (((unsigned)prevhbp) + prevhbp->hb_hdr.hbh_sz) ==	    ((unsigned)p) ) {      /* Coalesce with predecessor */	(prevhbp->hb_uninit) |= (p -> hb_uninit);	prevhbp->hb_next = p->hb_next;	prevhbp->hb_sz += p->hb_sz;	if (!prevhbp -> hb_uninit) clear_header(p);    } else {	prevhbp->hb_next = p;    }}/* Add a heap block to hblklist or hblkmap.  */void add_hblklist(hbp)struct hblk * hbp;{# ifdef HBLK_MAP    long size = hbp->hb_sz;    long index = divHBLKSZ(((long)hbp) - ((long)heapstart));    long i;    if( size < 0 ) size = -size;    size = (divHBLKSZ(WORDS_TO_BYTES(size)+sizeof(struct hblkhdr)+HBLKSIZE-1));	   /* in units of HBLKSIZE */    hblkmap[index] = HBLK_VALID;    for (i = 1; i < size; i++) {	if (i < 0x7f) {	    hblkmap[index+i] = i;	} else {	    /* May overflow a char.  Store largest possible value */	    hblkmap[index+i] = 0x7e;	}    }# else    if (last_hblk >= &hblklist[MAXHBLKS]) {	fprintf(stderr, "Not configured for enough memory\n");	exit(1);    }    *last_hblk = hbp;    hbp -> hb_index = last_hblk;    last_hblk++;# endif}/* Delete a heap block from hblklist or hblkmap.  */void del_hblklist(hbp)struct hblk * hbp;{# ifdef HBLK_MAP    long size = hbp->hb_sz;    long index = divHBLKSZ(((long)hbp) - ((long)heapstart));    long i;    if( size < 0 ) size = -size;    size = (divHBLKSZ(WORDS_TO_BYTES(size)+sizeof(struct hblkhdr)+HBLKSIZE-1));	   /* in units of HBLKSIZE */    for (i = 0; i < size; i++) {	hblkmap[index+i] = HBLK_INVALID;    }# else    register struct hblk ** list_entry;    last_hblk--;    /* Let **last_hblk use the slot previously occupied by *hbp */	list_entry = hbp -> hb_index;	(*last_hblk) -> hb_index = list_entry;	*list_entry = *last_hblk;# endif}/* Initialize hblklist */void init_hblklist(){#   ifdef DEBUG	printf("Here we are in init_hblklist - ");	printf("last_hblk = %x\n",&(hblklist[0]));#   endif#   ifndef HBLK_MAP      last_hblk = &(hblklist[0]);#   endif}