1: static char Sccsid[] = "aq.c @(#)aq.c 1.1 10/1/82 Berkeley ";
2: /*
3: * malloc/free/afreset -- dynamic memory allocation
4: *
5: *
6: * This source file is a slight modificattion of the alloc/free system
7: * described by Kernighan and Ritchie in "The C Programming Language",
8: * pp. 174-177.
9: *
10: * The modifications include allocation by a bestfit (rather than
11: * firstfit) strategy, and ability to reset memory completely.
12: */
13:
14: /* NOTE: the "afnfree" and "afnused" values are not precise. They
15: * do not currently refect the allocation and release of headers.
16: * This will be changed soon (I hope).
17: * --J. Bruner
18: */
19:
20:
21: #define NULL 0 /* null value */
22: #ifndef vax
23: #define NALLOC 128 /* # of units requested on each "sbrk" */
24: #else
25: #define NALLOC 1024 /* lots of memory each time for vaxes */
26: #endif
27:
28: typedef int ALIGN; /* force alignment on PDP-11 and VAX */
29:
30: union { /* free block header structure */
31: struct {
32: union header *ptr; /* next free block */
33: unsigned size; /* size of this free block */
34: } s;
35: ALIGN x; /* force alignment of blocks */
36: };
37:
38:
39: typedef union header ;
40:
41:
42: static HEADER base; /* empty list to get started */
43: static HEADER *allocp = NULL; /* last allocated block */
44:
45: int aftrace = 0;
46: int afnfree, afnused;
47:
48:
49: char *
50: malloc(nbytes)
51: unsigned nbytes;
52: {
53: HEADER *morecore();
54: register HEADER *p, *q;
55: register HEADER *rp;
56: HEADER *rq;
57: register unsigned nunits;
58:
59: /* malloc is a general-purpose memory allocator. It is called
60: * with the desired number of bytes, expressed as an unsigned
61: * integer, and it returns the address of the allocated memory.
62: * If "aftrace" is non-zero, a trace of the allocation will
63: * be printed. If it is not possible to alloate what is
64: * requested, the error "workspace exceeded" will result.
65: *
66: * This routine was originally called "alloc" but was changed
67: * to "malloc" because an increasing number of library routines
68: * perform dynamic memory allocation. A macro in "apl.h"
69: * converts calls on "alloc" to calls on "malloc".
70: */
71:
72: nunits = 1+(nbytes+sizeof(HEADER)-1)/sizeof(HEADER);
73: if ((q=allocp) == NULL){
74: base.s.ptr = allocp = q = &base; /* start list */
75: base.s.size = 0;
76: }
77:
78:
79: /* Search list for smallest free block */
80:
81: rp = NULL;
82: for(p=q->s.ptr;;q=p, p=p->s.ptr){
83: while(1){
84: if (p->s.size >= nunits){
85: if ((!rp) || p->s.size < rp->s.size){
86: rp = p;
87: rq = q;
88: }
89: if (p->s.size == nunits) break;
90: }
91:
92: if (p == allocp)
93: break;
94:
95: q = p;
96: p = p->s.ptr;
97: }
98:
99: if (rp) break;
100: if ((p=morecore(nunits)) == NULL)
101: error("workspace exceeded");
102: }
103:
104:
105:
106: /* Allocate memory as needed */
107:
108: if (rp->s.size == nunits)
109: rq->s.ptr = rp->s.ptr;
110: else {
111: rp->s.size -= nunits;
112: rp += rp->s.size;
113: rp->s.size = nunits;
114: }
115: allocp = rq;
116:
117: if (aftrace)
118: printf("[alloc: %d at %o]\n",
119: (int)nunits*sizeof(HEADER), rp);
120:
121: afnfree -= nunits;
122: afnused += nunits;
123: return((char *)(rp+1));
124: }
125:
126:
127: static HEADER *
128: morecore(nu)
129: unsigned nu;
130: {
131: char *sbrk();
132: register char *cp;
133: register HEADER *up;
134: register int rnu;
135:
136: /* Ask system for more memory. Requests are made in blocks
137: * of NALLOC header units. Returns NULL if request fails,
138: * "allocp" on success.
139: */
140:
141: rnu = NALLOC * ((nu+NALLOC-1) / NALLOC);
142: cp = sbrk(rnu * sizeof(HEADER));
143: if ((int)cp == -1)
144: return(NULL); /* no more space */
145:
146: if (aftrace)
147: printf("[morecore: %d at %o]\n", rnu*sizeof(HEADER),
148: cp);
149:
150: up = (HEADER *)cp;
151: up->s.size = rnu;
152: free((char *)(up+1));
153: return(allocp);
154: }
155:
156:
157: free(ap)
158: char *ap;
159: {
160: register HEADER *p, *q;
161: register unsigned fsize;
162:
163:
164: /* Put block into free list. Used by "morecore" to put a newly-
165: * allocated block of memory into the freelist -- also used to
166: * return a previously allocated block to the freelist.
167: */
168:
169: p = (HEADER *)ap - 1; /* point to header */
170: fsize = p->s.size;
171:
172: for (q=allocp; !(p > q && p < q->s.ptr); q=q->s.ptr)
173: if (q >= q->s.ptr && (p > q || p < q->s.ptr))
174: break;
175:
176: if (p+p->s.size == q->s.ptr){ /* join to upper nbr */
177: p->s.size += q->s.ptr->s.size;
178: p->s.ptr = q->s.ptr->s.ptr;
179: } else
180: p->s.ptr = q->s.ptr;
181:
182: if (q+q->s.size == p){ /* join to lower nbr */
183: q->s.size += p->s.size;
184: q->s.ptr = p->s.ptr;
185: } else
186: q->s.ptr = p;
187:
188: allocp = q;
189:
190: afnfree += fsize;
191: afnused -= fsize;
192: if (aftrace)
193: printf("[free: %d at %o]\n", fsize*sizeof(HEADER), ap);
194:
195: }
196:
197:
198: afreset(){
199:
200: extern end;
201:
202: /* Zap all dynamic allocation by resettting the lists and
203: * releasing all additional memory.
204: */
205:
206: allocp = NULL;
207: brk((char *)&end);
208: afnfree = afnused = 0;
209: if (aftrace)
210: printf("[afreset: dynamic allocation released]\n");
211:
212: }
Defined functions
free
defined in line
157; used 28 times
- in line 152
- in /usr/src/new/apl/src/a0.c line
161-165(2),
394-397(2),
424,
543,
554,
571,
577-578(2)
- in /usr/src/new/apl/src/a7.c line
33
- in /usr/src/new/apl/src/a8.c line
67
- in /usr/src/new/apl/src/aa.c line
58
- in /usr/src/new/apl/src/ai.c line
132,
184-189(2),
199,
214,
220,
251,
525
- in /usr/src/new/apl/src/aj.c line
342
- in /usr/src/new/apl/src/al.c line
35-37(2),
44,
153,
169
Defined variables
Sccsid
defined in line
1;
never used
base
defined in line
42; used 3 times
Defined union's
defined in line
30; used 4 times
Defined typedef's
ALIGN
defined in line
28; used 1 times
defined in line
39; used 17 times
Defined macros
NULL
defined in line
21; used 6 times