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