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