![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to malloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / f77 / alt|
Return to malloc.c CVS log | Up to [Research Unix] / researchv10no / cmd / f77 / alt |
1.1 root 1: #define ASSERT(p) if(!(p))botch("p");else
2: botch(s)
3: char *s;
4: {
5: printf("assertion botched: %s\n",s);
6: abort();
7: }
8: /* C storage allocator
9: * circular first-fit strategy
10: * works with noncontiguous, but monotonically linked, arena
11: * each block is preceded by a ptr to the (pointer of)
12: * the next following block
13: * blocks are exact number of words long; BUSY
14: * bit in ptr is 1 for busy, 0 for idle
15: * gaps in arena are merely noted as busy blocks
16: * last block of arena (pointed to by alloct) is empty and
17: * has a pointer to first
18: * idle blocks are coalesced during space search
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) ((int)(p)+BUSY)
27: #define clearbusy(p) ((int)(p)&~BUSY)
28:
29: struct store { struct store *ptr; };
30:
31: struct store allocs[] = { /*initial arena*/
32: setbusy(&allocs[1].ptr),
33: setbusy(&allocs[0].ptr)
34: };
35: struct store *allocp = &allocs[1]; /*search ptr*/
36: struct store *alloct = &allocs[1]; /*arena top*/
37: struct store *allocx; /*for benefit of realloc*/
38: struct store *sbrk();
39:
40: struct store *
41: malloc(nbytes)
42: unsigned nbytes;
43: {
44: register struct store *p, *q;
45: register nw;
46: static temp; /*coroutines assume no auto*/
47:
48: nw = (nbytes+2*WORD-1)/WORD;
49: ASSERT(allocp>allocs && allocp<=alloct);
50: for(p=allocp; ; ) {
51: for(temp=0; ; ) {
52: if(!testbusy(p->ptr)) {
53: while(!testbusy((q=p->ptr)->ptr)) {
54: ASSERT(q>p&&q<alloct);
55: p->ptr = q->ptr;
56: }
57: if(q>=p+nw && p+nw>=p)
58: goto found;
59: }
60: q = p;
61: p = clearbusy(p->ptr);
62: if(p>q)
63: ASSERT(p<=alloct);
64: else if(q!=alloct || p!=allocs) {
65: write(2,"corrupt arena\n",14);
66: exit(0175);
67: } else if(++temp>1)
68: break;
69: }
70: temp = (nw+BLOCK/WORD)&~(BLOCK/WORD-1);
71: q = sbrk(0);
72: if(q+temp < q)
73: return(NULL);
74: q = sbrk(temp*WORD);
75: if((int)q == -1)
76: return(NULL);
77: ASSERT(q>alloct);
78: alloct->ptr = q;
79: if(q!=alloct+1)
80: alloct->ptr = setbusy(alloct->ptr);
81: alloct = q->ptr = q+temp-1;
82: alloct->ptr = setbusy(allocs);
83: }
84: found:
85: allocp = p + nw;
86: ASSERT(allocp<=alloct);
87: if(q>allocp) {
88: allocx = allocp->ptr;
89: allocp->ptr = p->ptr;
90: }
91: p->ptr = setbusy(allocp);
92: return(p+1);
93: }
94: /* freeing strategy tuned for LIFO allocation
95: */
96: free(p)
97: register struct store *p;
98: {
99: ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
100: allocp = --p;
101: ASSERT(testbusy(p->ptr));
102: p->ptr = clearbusy(p->ptr);
103: ASSERT(p->ptr > allocp && p->ptr <= alloct);
104: }
105:
106: struct { unsigned tag:4, vtype:4;};
107:
108: prbusy()
109: {
110: register struct store *p, *q;
111:
112: ASSERT(allocp>allocs && allocp<=alloct);
113: for(p=allocs; ; ) {
114: if(testbusy(p->ptr))
115: {
116: printf("busy 0%o, tag %d, type %d, length %d\n",
117: p, p[1].tag, p[1].vtype,
118: clearbusy(p->ptr) - (int) p - 2 );
119: }
120: q = p;
121: p = clearbusy(p->ptr);
122: if(p>q)
123: ASSERT(p<=alloct);
124: else if(q!=alloct || p!=allocs)
125: {
126: write(2,"corrupt arena\n",14);
127: exit(0175);
128: }
129: else return;
130: }
131: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.