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