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