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