1*6868Srrh # include "../hdr/macros.h" 2*6868Srrh SCCSID(@(#)xalloc 2.1); 3*6868Srrh 4*6868Srrh /* 5*6868Srrh xalloc/xfree based on alloc/free in C library at one time. 6*6868Srrh Also xfreeall() frees all memory allocated (calls brk(II)). 7*6868Srrh 8*6868Srrh Xfree always coalesces contiguous free blocks. 9*6868Srrh Xalloc uses a first fit strategy. 10*6868Srrh Xalloc always allocates words (rounds up). 11*6868Srrh Xalloc actually allocates one more word than the 12*6868Srrh amount requested. The extra word (the first word of the 13*6868Srrh allocated block) contains the size (in bytes) of the entire block. 14*6868Srrh This size is used by xfree to identify contiguous blocks, 15*6868Srrh and is used by xalloc to implement the first fit strategy. 16*6868Srrh 17*6868Srrh Bad things will happen if the size word is changed. 18*6868Srrh Worse things happen if xfree is called with a 19*6868Srrh garbage argument. 20*6868Srrh 21*6868Srrh Xalloc returns the address of the allocated area on success, 22*6868Srrh fatal() on failure. 23*6868Srrh Xfree and xfreeall don't return anything. 24*6868Srrh */ 25*6868Srrh 26*6868Srrh struct fb { 27*6868Srrh unsigned f_size; 28*6868Srrh char *f_next; 29*6868Srrh }; 30*6868Srrh 31*6868Srrh struct fb Freelist { 32*6868Srrh 0, 33*6868Srrh 0x3FFFFFFF, 34*6868Srrh }; 35*6868Srrh 36*6868Srrh # define SLOP (sizeof(int *)) 37*6868Srrh 38*6868Srrh extern end; 39*6868Srrh unsigned Lastbrk &end; 40*6868Srrh 41*6868Srrh xalloc(asize) 42*6868Srrh unsigned asize; 43*6868Srrh { 44*6868Srrh register unsigned usize; 45*6868Srrh register struct fb *np, *cp; 46*6868Srrh 47*6868Srrh if((usize = asize) == 0) 48*6868Srrh return(0); 49*6868Srrh usize =+ 2*sizeof(int *) -1; 50*6868Srrh usize =& ~(sizeof(int *) -1); 51*6868Srrh for(;;) { 52*6868Srrh cp = &Freelist; 53*6868Srrh while((np = cp->f_next) != 0x3FFFFFFF) { 54*6868Srrh if(np->f_size>=usize) { 55*6868Srrh /* 56*6868Srrh Don't break the block up if it 57*6868Srrh is not more than SLOP bigger than the 58*6868Srrh amount needed. 59*6868Srrh */ 60*6868Srrh if(usize+SLOP >= np->f_size) 61*6868Srrh cp->f_next = np->f_next; 62*6868Srrh /* 63*6868Srrh Break the block into 2 pieces. 64*6868Srrh */ 65*6868Srrh else { 66*6868Srrh cp = cp->f_next = ((int)np) + usize; 67*6868Srrh cp->f_size = np->f_size - usize; 68*6868Srrh cp->f_next = np->f_next; 69*6868Srrh np->f_size = usize; 70*6868Srrh } 71*6868Srrh zero(&np->f_next,usize-sizeof(int *)); 72*6868Srrh return(&np->f_next); 73*6868Srrh } 74*6868Srrh cp = np; 75*6868Srrh } 76*6868Srrh /* 77*6868Srrh Nothing on the free list is big enough; 78*6868Srrh get more core from the operating system. 79*6868Srrh */ 80*6868Srrh asize = usize<1024? 1024: usize; 81*6868Srrh asize = (asize+511) & (~511); 82*6868Srrh if((cp = sbrk(asize)) == -1) { 83*6868Srrh return(fatal("out of space (ut9)")); 84*6868Srrh } 85*6868Srrh Lastbrk = ((int)cp) + asize; 86*6868Srrh cp->f_size = asize; 87*6868Srrh /* 88*6868Srrh Add the new piece to the free list. 89*6868Srrh */ 90*6868Srrh xfree(&cp->f_next); 91*6868Srrh } 92*6868Srrh } 93*6868Srrh 94*6868Srrh 95*6868Srrh xfree(aptr) 96*6868Srrh char *aptr; 97*6868Srrh { 98*6868Srrh register struct fb *ptr, *cp, *np; 99*6868Srrh 100*6868Srrh if (aptr && aptr < Lastbrk) { 101*6868Srrh ptr = aptr-sizeof(int *); 102*6868Srrh cp = &Freelist; 103*6868Srrh while((np = cp->f_next) < ptr) 104*6868Srrh cp = np; 105*6868Srrh /* 106*6868Srrh Try to coalesce with the following block. 107*6868Srrh */ 108*6868Srrh if(((int)ptr) + ptr->f_size == ((int)np)) { 109*6868Srrh ptr->f_size =+ np->f_size; 110*6868Srrh ptr->f_next = np->f_next; 111*6868Srrh np = ptr; 112*6868Srrh } else 113*6868Srrh ptr->f_next = np; 114*6868Srrh /* 115*6868Srrh Try to coalesce with the preceding block. 116*6868Srrh */ 117*6868Srrh if(((int)cp) + cp->f_size == ((int)ptr)) { 118*6868Srrh cp->f_size =+ ptr->f_size; 119*6868Srrh cp->f_next = ptr->f_next; 120*6868Srrh } else 121*6868Srrh cp->f_next = ptr; 122*6868Srrh } 123*6868Srrh } 124*6868Srrh 125*6868Srrh 126*6868Srrh xfreeall() 127*6868Srrh { 128*6868Srrh brk(&end); 129*6868Srrh Lastbrk = &end; 130*6868Srrh Freelist.f_size = 0; 131*6868Srrh Freelist.f_next = 0x3FFFFFFF; 132*6868Srrh } 133