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