![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dballoc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / libI77 / notused|
Return to dballoc.c CVS log | Up to [Research Unix] / researchv10dc / libI77 / notused |
1.1 root 1: /* @(#)dballoc.c 1.2 */
2: #define debug YES
3: #ifndef debug
4: #define ASSERT(p)
5: #endif
6: #ifdef debug
7: #define ASSERT(p) if(!(p))botch("p");else
8: botch(s)
9: char *s;
10: {
11: printf("assertion botched: %s\n",s);
12: abort();
13: }
14: #endif
15: /* C storage allocator
16: * circular first-fit strategy
17: * works with noncontiguous, but monotonically linked, arena
18: * each block is preceded by a ptr to the (pointer of)
19: * the next following block
20: * blocks are exact number of words long; BUSY
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 (pointed to by alloct) is empty and
24: * has a pointer to first
25: * idle blocks are coalesced during space search
26: */
27: /* all these defines must be powers of 2 */
28: #define WORD sizeof(struct store)
29: #define BLOCK 1024
30: #define BUSY 1
31: #define NULL 0
32: #define testbusy(p) ((int)(p)&BUSY)
33: #define setbusy(p) (struct store *)((int)(p)+BUSY)
34: #define clearbusy(p) (struct store *)((int)(p)&~BUSY)
35:
36: struct store { struct store *ptr; };
37:
38: struct store allocs[] = { /*initial arena*/
39: setbusy(&allocs[1].ptr),
40: setbusy(&allocs[0].ptr)
41: };
42: struct store *allocp = &allocs[1]; /*search ptr*/
43: struct store *alloct = &allocs[1]; /*arena top*/
44: struct store *allocx = 0; /*for benefit of realloc*/
45: struct store *sbrk();
46:
47: struct store *
48: malloc(nbytes)
49: unsigned nbytes;
50: {
51: struct store *p, *q;
52: register nw;
53: static temp; /*coroutines assume no auto*/
54:
55: #ifdef verbose
56: printf("malloc(%d) ",nbytes);
57: #endif
58: nw = (nbytes+2*WORD-1)/WORD;
59: ASSERT(allocp>allocs && allocp<=alloct);
60: for(p=allocp; ; ) {
61: for(temp=0; ; ) {
62: if(!testbusy(p->ptr)) {
63: while(!testbusy((q=p->ptr)->ptr)) {
64: ASSERT(q>p&&q<alloct);
65: p->ptr = q->ptr;
66: }
67: if(q>=p+nw && p+nw>=p)
68: goto found;
69: }
70: q = p;
71: p = clearbusy(p->ptr);
72: if(p>q)
73: ASSERT(p<=alloct);
74: else if(q!=alloct || p!=allocs) {
75: write(2,"corrupt arena\n",14);
76: #ifdef debug
77: abort();
78: #endif
79: exit(0175);
80: } else if(++temp>1)
81: break;
82: }
83: temp = (nw+BLOCK/WORD)&~(BLOCK/WORD-1);
84: q = sbrk(temp*WORD); /*SYSDEP*/
85: if((int)q == -1)
86: return(NULL);
87: ASSERT(q>alloct);
88: alloct->ptr = q;
89: if(q!=alloct+1)
90: alloct->ptr = setbusy(alloct->ptr);
91: alloct = q->ptr = q+temp-1;
92: alloct->ptr = setbusy(allocs);
93: }
94: found:
95: allocp = p + nw;
96: ASSERT(allocp<=alloct);
97: if(q>allocp) {
98: allocx = allocp->ptr;
99: allocp->ptr = p->ptr;
100: }
101: p->ptr = setbusy(allocp);
102: #ifdef verbose
103: printf("= %o\n",p+1);
104: #endif
105: return(p+1);
106: }
107: /* freeing strategy tuned for LIFO allocation
108: */
109: free(p)
110: struct store *p;
111: {
112: struct store *savep=p;
113: #ifdef verbose
114: printf("free(%o)\n",p);
115: #endif
116: ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
117: allocp = --p;
118: ASSERT(testbusy(p->ptr));
119: p->ptr = clearbusy(p->ptr);
120: ASSERT(p->ptr > allocp && p->ptr <= alloct);
121: }
122: char *calloc(nbytes,count)
123: { char *c;
124: c=(char *)malloc(nbytes*count);
125: return(c);
126: }
127: /*
128: ahist(s) char *s;
129: { char **ap;
130: printf("%s allocp %o alloct %o\n",s,allocp,alloct);
131: for(ap= allocs;ap<alloct;ap= *ap&~BUSY)
132: if(*ap&BUSY) printf("%o ",ap);
133: printf("\n");
134: }
135: */
136: struct store *
137: realloc(p, nbytes)
138: register struct store *p;
139: unsigned nbytes;
140: {
141: register struct store *q;
142: struct store *s, *t;
143: register unsigned nw;
144: unsigned onw;
145:
146: onw = p[-1].ptr - p;
147: q = malloc(nbytes);
148: if(q==NULL || q==p)
149: return(q);
150: s = p;
151: t = q;
152: nw = (nbytes+WORD-1)/WORD;
153: if(nw<onw)
154: onw = nw;
155: while(onw--!=0)
156: (t++)->ptr = (s++)->ptr;
157: if(q<p && q+nw>=p)
158: (q+(q+nw-p))->ptr = allocx;
159: return(q);
160: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.