![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / jerq / src / lib / j|
Return to alloc.c CVS log | Up to [Research Unix] / researchv9 / jerq / src / lib / j |
1.1 root 1: #ifdef alloc
2: #undef alloc
3: #undef free
4: #endif
5: #ifdef debug
6: #define ASSERT(p) if(!(p))botch("p");else
7: botch(s)
8: char *s;
9: {
10: printf("assertion botched: %s\n",s);
11: abort();
12: }
13: #else
14: #define ASSERT(p)
15: #endif
16:
17: /* C storage allocator
18: * first-fit strategy
19: * works with noncontiguous, but monotonically linked, arena
20: * each block is preceded by a ptr to the (pointer of)
21: * the next following block
22: * blocks are exact number of words long
23: * aligned to the data type requirements of ALIGN
24: * pointers to blocks must have BUSY bit 0
25: * bit in ptr is 1 for busy, 0 for idle
26: * gaps in arena are merely noted as busy blocks
27: * last block of arena is empty and
28: * has a pointer to first
29: * idle blocks are coalesced during space search
30: *
31: * a different implementation may need to redefine
32: * ALIGN, NALIGN, BUSY, INT
33: * where INT is integer type to which a pointer can be cast
34: */
35: #define INT long
36: #define ALIGN int
37: #define NALIGN 1
38: #define WORD sizeof(union store)
39: #define BUSY 1
40: #define NULL 0
41: #define testbusy(p) ((INT)(p)&BUSY)
42: #define setbusy(p) (union store *)((INT)(p)|BUSY)
43: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
44:
45: union store {
46: struct {
47: union store *Uptr;
48: char * Uproc; /* pointer to process of allocating guy */
49: } u;
50: union store *ptr;
51: ALIGN dummy[NALIGN];
52: int calloc; /*calloc clears an array of integers*/
53: };
54: #define proc u.Uproc
55:
56: char *allocstartp; /* &end, but passed in because this is in ROM */
57: char *allocendp; /* should adjust according to load */
58: #define START allocstartp
59: #define FIRSTWORD ((union store *)(START))
60: #define LASTWORD ((union store *)(allocendp-4))
61: static union store *allocb; /*arena base*/
62: #ifdef REALLOC
63: static union store *allocx; /*for benefit of realloc*/
64: #endif
65:
66: allocinit(s, e)
67: int *s, *e;
68: {
69: allocstartp=(char *)s;
70: allocendp=(char *)e;
71: FIRSTWORD->ptr = LASTWORD;
72: LASTWORD->ptr = (union store *)(START+1);
73: allocb = (union store *)START;
74: }
75:
76: char *
77: realalloc(nbytes, whichproc)
78: unsigned nbytes;
79: char *whichproc;
80: {
81: register union store *p, *q;
82: register nw;
83: register union store *allocp;
84: static int temp;
85:
86: nw = (nbytes+WORD+WORD-1)/WORD;
87: ASSERT(allock(allocb));
88: for(; ; ) { /* done at most twice */
89: p = allocb;
90: allocp = allocb;
91: for(temp=0; ; ) {
92: if(!testbusy(p->ptr)) {
93: while(!testbusy((q=p->ptr)->ptr)) {
94: ASSERT(q>p);
95: p->ptr = q->ptr;
96: allocp = p;
97: }
98: if(q>=p+nw && p+nw>=p)
99: goto found;
100: }
101: q = p;
102: p = clearbusy(p->ptr);
103: if(p <= q) {
104: ASSERT(p==allocb);
105: if(p != allocb)
106: return(NULL);
107: if(++temp > 1)
108: break;
109: }
110: }
111: return NULL; /* get more space, someday */
112: }
113: found:
114: allocp = p + nw;
115: if(q>allocp) {
116: #ifdef REALLOC
117: allocx = allocp->ptr;
118: #endif
119: allocp->ptr = p->ptr;
120: }
121: p->ptr = setbusy(allocp);
122: /* clear the storage, for jerqs only */
123: for(q=p+1; q<p+nw; q++){
124: q->ptr=0;
125: q->proc=0; /* cough */
126: }
127: p->proc = whichproc;
128: return((char *)(p+1));
129: }
130:
131: char *
132: alloc(nbytes)
133: unsigned nbytes;
134: {
135: return realalloc(nbytes, (char *)0);
136: }
137:
138: /* freeing strategy tuned for LIFO allocation
139: */
140: free(ap)
141: char *ap;
142: {
143: register union store *p = (union store *)ap-1;
144:
145: ASSERT(allock(p));
146: ASSERT(testbusy(p->ptr));
147: p->ptr = clearbusy(p->ptr);
148: p->proc = 0;
149: ASSERT(p->ptr > p);
150: }
151:
152: /* free all storage associated with the named process
153: */
154: freeall(whichproc)
155: register char *whichproc;
156: {
157: register union store *p, *r;
158:
159: if ((p=allocb)->proc == whichproc) /* first block on chain */
160: free((char *)(p+1));
161: for(p=allocb; (r=clearbusy(p->ptr)) > p; p=r) /* rest of chain... */
162: if((r->proc == whichproc) && (r != LASTWORD))
163: free((char *)(r+1)); /* ...except LASTWORD */
164: gcfreeall(whichproc);
165: }
166:
167: #ifdef REALLOC
168: /* realloc(p, nbytes) reallocates a block obtained from alloc()
169: * and freed since last call of alloc()
170: * to have new size nbytes, and old content
171: * returns new location, or 0 on failure
172: */
173:
174: char *
175: realloc(pp, nbytes)
176: char *pp;
177: unsigned nbytes;
178: {
179: register union store *q;
180: register union store *p = (union store *)pp;
181: union store *s, *t;
182: register unsigned nw;
183: unsigned onw;
184:
185: ASSERT(allock(p-1));
186: if(testbusy(p[-1].ptr))
187: free((char *)p);
188: onw = p[-1].ptr - p;
189: q = (union store *)alloc(nbytes);
190: if(q==NULL || q==p)
191: return((char *)q);
192: ASSERT(q<p||q>p[-1].ptr);
193: s = p;
194: t = q;
195: nw = (nbytes+WORD-1)/WORD;
196: if(nw<onw)
197: onw = nw;
198: while(onw--!=0)
199: *t++ = *s++;
200: ASSERT(clearbusy(q[-1].ptr)-q==nw);
201: if(q<p && q+nw>=p)
202: (q+(q+nw-p))->ptr = allocx;
203: ASSERT(allock(q-1));
204: return((char *)q);
205: }
206: #endif
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(((union store *)START)->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: abort(){
229: printf("abort\n");
230: for(;;);
231: }
232: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.