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