![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to malloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 40BSD / cmd / csh|
Return to malloc.c CVS log | Up to [CSRG BSD Unix] / 40BSD / cmd / csh |
1.1 root 1: static char *sccsid = "@(#)malloc.c 4.1 10/9/80";
2:
3: #ifdef debug
4: #define ASSERT(p) if(!(p))botch("p");else
5: botch(s)
6: char *s;
7: {
8: printf("assertion botched: %s\n",s);
9: abort();
10: }
11: #else
12: #define ASSERT(p)
13: #endif
14:
15: /* avoid break bug */
16: #ifdef pdp11
17: #define GRANULE 64
18: #else
19: #define GRANULE 0
20: #endif
21: /* C storage allocator
22: * circular first-fit strategy
23: * works with noncontiguous, but monotonically linked, arena
24: * each block is preceded by a ptr to the (pointer of)
25: * the next following block
26: * blocks are exact number of words long
27: * aligned to the data type requirements of ALIGN
28: * pointers to blocks must have BUSY bit 0
29: * bit in ptr is 1 for busy, 0 for idle
30: * gaps in arena are merely noted as busy blocks
31: * last block of arena (pointed to by alloct) is empty and
32: * has a pointer to first
33: * idle blocks are coalesced during space search
34: *
35: * a different implementation may need to redefine
36: * ALIGN, NALIGN, BLOCK, BUSY, INT
37: * where INT is integer type to which a pointer can be cast
38: */
39: #define INT int
40: #define ALIGN int
41: #define NALIGN 1
42: #define WORD sizeof(union store)
43: #define BLOCK 1024 /* a multiple of WORD*/
44: #define BUSY 1
45: #define NULL 0
46: #define testbusy(p) ((INT)(p)&BUSY)
47: #define setbusy(p) (union store *)((INT)(p)|BUSY)
48: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
49:
50: union store { union store *ptr;
51: ALIGN dummy[NALIGN];
52: int calloc; /*calloc clears an array of integers*/
53: };
54:
55: static union store allocs[2]; /*initial arena*/
56: static union store *allocp; /*search ptr*/
57: static union store *alloct; /*arena top*/
58: static union store *allocx; /*for benefit of realloc*/
59: char *sbrk();
60:
61: char *
62: malloc(nbytes)
63: unsigned nbytes;
64: {
65: register union store *p, *q;
66: register nw;
67: static temp; /*coroutines assume no auto*/
68:
69: if(allocs[0].ptr==0) { /*first time*/
70: allocs[0].ptr = setbusy(&allocs[1]);
71: allocs[1].ptr = setbusy(&allocs[0]);
72: alloct = &allocs[1];
73: allocp = &allocs[0];
74: }
75: nw = (nbytes+WORD+WORD-1)/WORD;
76: ASSERT(allocp>=allocs && allocp<=alloct);
77: ASSERT(allock());
78: for(p=allocp; ; ) {
79: for(temp=0; ; ) {
80: if(!testbusy(p->ptr)) {
81: while(!testbusy((q=p->ptr)->ptr)) {
82: ASSERT(q>p&&q<alloct);
83: p->ptr = q->ptr;
84: }
85: if(q>=p+nw && p+nw>=p)
86: goto found;
87: }
88: q = p;
89: p = clearbusy(p->ptr);
90: if(p>q)
91: ASSERT(p<=alloct);
92: else if(q!=alloct || p!=allocs) {
93: ASSERT(q==alloct&&p==allocs);
94: return(NULL);
95: } else if(++temp>1)
96: break;
97: }
98: temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
99: q = (union store *)sbrk(0);
100: if(q+temp+GRANULE < q) {
101: return(NULL);
102: }
103: q = (union store *)sbrk(temp*WORD);
104: if((INT)q == -1) {
105: return(NULL);
106: }
107: ASSERT(q>alloct);
108: alloct->ptr = q;
109: if(q!=alloct+1)
110: alloct->ptr = setbusy(alloct->ptr);
111: alloct = q->ptr = q+temp-1;
112: alloct->ptr = setbusy(allocs);
113: }
114: found:
115: allocp = p + nw;
116: ASSERT(allocp<=alloct);
117: if(q>allocp) {
118: allocx = allocp->ptr;
119: allocp->ptr = p->ptr;
120: }
121: p->ptr = setbusy(allocp);
122: return((char *)(p+1));
123: }
124:
125: /* freeing strategy tuned for LIFO allocation
126: */
127: free(ap)
128: register char *ap;
129: {
130: register union store *p = (union store *)ap;
131:
132: ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
133: ASSERT(allock());
134: allocp = --p;
135: ASSERT(testbusy(p->ptr));
136: p->ptr = clearbusy(p->ptr);
137: ASSERT(p->ptr > allocp && p->ptr <= alloct);
138: }
139:
140: /* realloc(p, nbytes) reallocates a block obtained from malloc()
141: * and freed since last call of malloc()
142: * to have new size nbytes, and old content
143: * returns new location, or 0 on failure
144: */
145:
146: char *
147: realloc(p, nbytes)
148: register union store *p;
149: unsigned nbytes;
150: {
151: register union store *q;
152: union store *s, *t;
153: register unsigned nw;
154: unsigned onw;
155:
156: if(testbusy(p[-1].ptr))
157: free((char *)p);
158: onw = p[-1].ptr - p;
159: q = (union store *)malloc(nbytes);
160: if(q==NULL || q==p)
161: return((char *)q);
162: s = p;
163: t = q;
164: nw = (nbytes+WORD-1)/WORD;
165: if(nw<onw)
166: onw = nw;
167: while(onw--!=0)
168: *t++ = *s++;
169: if(q<p && q+nw>=p)
170: (q+(q+nw-p))->ptr = allocx;
171: return((char *)q);
172: }
173:
174: #ifdef debug
175: allock()
176: {
177: #ifdef longdebug
178: register union store *p;
179: int x;
180: x = 0;
181: for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
182: if(p==allocp)
183: x++;
184: }
185: ASSERT(p==alloct);
186: return(x==1|p==allocp);
187: #else
188: return(1);
189: #endif
190: }
191: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.