![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to omalloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / libc / gen|
Return to omalloc.c CVS log | Up to [Research Unix] / researchv10no / 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: /* C storage allocator
14: * circular first-fit strategy
15: * works with noncontiguous, but monotonically linked, arena
16: * each block is preceded by a ptr to the (pointer of)
17: * the next following block
18: * blocks are exact number of words long
19: * aligned to the data type requirements of ALIGN
20: * pointers to blocks must have BUSY bit 0
21: * bit in ptr is 1 for busy, 0 for idle
22: * gaps in arena are merely noted as busy blocks
23: * last block of arena is empty and
24: * has a pointer to first
25: * idle blocks are coalesced during space search
26: *
27: * a different implementation may need to redefine
28: * ALIGN, NALIGN, BLOCK, BUSY, INT
29: * where INT is integer type to which a pointer can be cast
30: */
31: #define INT int
32: #define ALIGN int
33: #define NALIGN 1
34: #define WORD sizeof(union store)
35: #define BLOCK 1024
36: #define BUSY 1
37: #define NULL 0
38: #define testbusy(p) ((INT)(p)&BUSY)
39: #define setbusy(p) (union store *)((INT)(p)|BUSY)
40: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
41:
42: union store {
43: union store *ptr;
44: ALIGN dummy[NALIGN];
45: int calloc; /*calloc clears an array of integers*/
46: };
47:
48: static union store alloca; /* initial arena */
49: static union store *allocb = &alloca; /*arena base*/
50: static union store *allocp = &alloca; /*search ptr*/
51: static union store *allocx; /*for benefit of realloc*/
52: extern char *sbrk();
53:
54: char *
55: malloc(nbytes)
56: unsigned nbytes;
57: {
58: register union store *p, *q;
59: register nw;
60: register temp;
61: register union store *r = 0;
62:
63: nw = (nbytes+WORD+WORD-1)/WORD;
64: ASSERT(allock(allocp));
65: for(; ; ) { /* done at most twice */
66: p = allocp;
67: if(alloca.ptr!=0) /*C can't initialize union*/
68: for(temp=0; ; ) {
69: if(!testbusy(p->ptr)) {
70: while(!testbusy((q=p->ptr)->ptr)) {
71: ASSERT(q>p);
72: p->ptr = q->ptr;
73: allocp = p;
74: }
75: if(q>=p+nw && p+nw>=p)
76: goto found;
77: r = p;
78: }
79: q = p;
80: p = clearbusy(p->ptr);
81: if(p <= q) {
82: ASSERT(p==allocb);
83: if(p != allocb)
84: return(NULL);
85: if(++temp>1)
86: break;
87: }
88: }
89: temp = nw;
90: p = (union store *)sbrk(0);
91: if (r && !testbusy(r->ptr) && r->ptr + 1 == p)
92: temp -= p - r - 1;
93: temp = ((temp+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
94: if(p+temp <= p)
95: return(NULL);
96: for(; ; ) {
97: q = (union store *)sbrk(temp*WORD);
98: if((INT)q != -1)
99: break;
100: temp -= (temp-nw)/2;
101: if(temp-nw <= 1)
102: return(NULL);
103: }
104: ialloc((char *)q, (unsigned)temp*WORD);
105: }
106: found:
107: allocp = p + nw;
108: if(q>allocp) {
109: allocx = allocp->ptr;
110: allocp->ptr = p->ptr;
111: }
112: p->ptr = setbusy(allocp);
113: return((char *)(p+1));
114: }
115:
116: /* freeing strategy tuned for LIFO allocation
117: */
118: free(ap)
119: char *ap;
120: {
121: register union store *p = (union store *)ap;
122:
123: allocp = --p;
124: ASSERT(allock(allocp));
125: ASSERT(testbusy(p->ptr));
126: p->ptr = clearbusy(p->ptr);
127: ASSERT(p->ptr > allocp);
128: }
129:
130: /* ialloc(q, nbytes) inserts a block that did not come
131: * from malloc into the arena
132: *
133: * q points to new block
134: * r points to last of new block
135: * p points to last cell of arena before new block
136: * s points to first cell of arena after new block
137: */
138: ialloc(qq, nbytes)
139: char *qq;
140: unsigned nbytes;
141: {
142: register union store *p, *q, *s;
143: union store *r;
144:
145: q = (union store *)qq;
146: r = q + (nbytes/WORD) - 1;
147: q->ptr = r;
148: if(alloca.ptr==0) /*C can't initialize union*/
149: alloca.ptr = &alloca;
150: for(p=allocb; ; p=s) {
151: s = clearbusy(p->ptr);
152: if(s==allocb)
153: break;
154: ASSERT(s>p);
155: if(s>r) {
156: if(p<q)
157: break;
158: else
159: ASSERT(p>r);
160: }
161: }
162: p->ptr = q==p+1? q: setbusy(q);
163: r->ptr = s==r+1? s: setbusy(s);
164: if(allocb > q)
165: allocb = q;
166: allocp = allocb;
167: }
168:
169: /* realloc(p, nbytes) reallocates a block obtained from malloc()
170: * and freed since last call of malloc()
171: * to have new size nbytes, and old content
172: * returns new location, or 0 on failure
173: */
174:
175: char *
176: realloc(pp, nbytes)
177: char *pp;
178: unsigned nbytes;
179: {
180: register union store *q;
181: register union store *p = (union store *)pp;
182: union store *s, *t;
183: register unsigned nw;
184: unsigned onw;
185:
186: ASSERT(allock(p-1));
187: if(testbusy(p[-1].ptr))
188: free((char *)p);
189: onw = p[-1].ptr - p;
190: q = (union store *)malloc(nbytes);
191: if(q==NULL || q==p)
192: return((char *)q);
193: ASSERT(q<p||q>p[-1].ptr);
194: s = p;
195: t = q;
196: nw = (nbytes+WORD-1)/WORD;
197: if(nw<onw)
198: onw = nw;
199: while(onw--!=0)
200: *t++ = *s++;
201: ASSERT(clearbusy(q[-1].ptr)-q==nw);
202: if(q<p && q+nw>=p)
203: (q+(q+nw-p))->ptr = allocx;
204: ASSERT(allock(q-1));
205: return((char *)q);
206: }
207:
208: #ifdef debug
209: allock(q)
210: union store *q;
211: {
212: #ifdef longdebug
213: register union store *p, *r;
214: int x;
215: x = 0;
216: p = allocb;
217: if(alloca.ptr==0)
218: return(1);
219: for( ; (r=clearbusy(p->ptr)) > p; p=r) {
220: if(p==q)
221: x++;
222: }
223: return(r==allocb&(x==1|p==q));
224: #else
225: return(q>=allocb);
226: #endif
227: }
228: #endif
229:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.