![[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 [CSRG BSD Unix] / 3BSD / cmd / px|
Return to malloc.c CVS log | Up to [CSRG BSD Unix] / 3BSD / cmd / px |
1.1 root 1: #ifdef debug
2: #define ASSERT(p,t) if(!(p))return(t(TRASHED));else
3: #else
4: #define ASSERT(p,t)
5: #endif
6:
7: /* avoid break bug */
8: #ifdef pdp11
9: #define GRANULE 64
10: #else
11: #define GRANULE 0
12: #endif
13: /* C storage allocator
14: * circular first-fit strategy
15: * works with noncontiguous, but monotonically linked, arena
16: * each block is preceded by a ptr to the (pointer of)
17: * the next following block
18: * blocks are exact number of words long
19: * aligned to the data type requirements of ALIGN
20: * pointers to blocks must have BUSY bit 0
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: * a different implementation may need to redefine
28: * ALIGN, NALIGN, BLOCK, BUSY, INT
29: * where INT is integer type to which a pointer can be cast
30: */
31: #define INT int
32: #define ALIGN int
33: #define NALIGN 1
34: #define WORD sizeof(union store)
35: #define BLOCK 1024 /* a multiple of WORD*/
36: #define BUSY 1
37: #define NULL 0
38: #define TRASHED -1
39: #define testbusy(p) ((INT)(p)&BUSY)
40: #define setbusy(p) (union store *)((INT)(p)|BUSY)
41: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
42:
43: union store { union store *ptr;
44: ALIGN dummy[NALIGN];
45: int calloc; /*calloc clears an array of integers*/
46: };
47:
48: static union store allocs[2]; /*initial arena*/
49: static union store *allocp; /*search ptr*/
50: static union store *alloct; /*arena top*/
51: static union store *allocx; /*for benefit of realloc*/
52: char *sbrk();
53:
54: char *
55: malloc(nbytes)
56: unsigned nbytes;
57: {
58: register union store *p, *q;
59: register nw;
60: static temp; /*coroutines assume no auto*/
61:
62: if(allocs[0].ptr==0) { /*first time*/
63: allocs[0].ptr = setbusy(&allocs[1]);
64: allocs[1].ptr = setbusy(&allocs[0]);
65: alloct = &allocs[1];
66: allocp = &allocs[0];
67: }
68: nw = (nbytes+WORD+WORD-1)/WORD;
69: ASSERT(allocp>=allocs && allocp<=alloct,(char *));
70: ASSERT(allock(),(char *));
71: for(p=allocp; ; ) {
72: for(temp=0; ; ) {
73: if(!testbusy(p->ptr)) {
74: while(!testbusy((q=p->ptr)->ptr)) {
75: ASSERT(q>p&&q<alloct,(char *));
76: p->ptr = q->ptr;
77: }
78: if(q>=p+nw && p+nw>=p)
79: goto found;
80: }
81: q = p;
82: p = clearbusy(p->ptr);
83: if(p>q)
84: ASSERT(p<=alloct,(char *));
85: else if(q!=alloct || p!=allocs) {
86: ASSERT(q==alloct&&p==allocs,(char *));
87: return(NULL);
88: } else if(++temp>1)
89: break;
90: }
91: temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
92: q = (union store *)sbrk(0);
93: if(q+temp+GRANULE < q) {
94: return(NULL);
95: }
96: q = (union store *)sbrk(temp*WORD);
97: if((INT)q == -1) {
98: return(NULL);
99: }
100: ASSERT(q>alloct,(char *));
101: alloct->ptr = q;
102: if(q!=alloct+1)
103: alloct->ptr = setbusy(alloct->ptr);
104: alloct = q->ptr = q+temp-1;
105: alloct->ptr = setbusy(allocs);
106: }
107: found:
108: allocp = p + nw;
109: ASSERT(allocp<=alloct,(char *));
110: if(q>allocp) {
111: allocx = allocp->ptr;
112: allocp->ptr = p->ptr;
113: }
114: p->ptr = setbusy(allocp);
115: return((char *)(p+1));
116: }
117:
118: /* freeing strategy tuned for LIFO allocation
119: */
120: free(ap)
121: register char *ap;
122: {
123: register union store *p = (union store *)ap;
124:
125: ASSERT(p != 0,(long));
126: ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct,(long));
127: ASSERT(allock(),(long));
128: allocp = --p;
129: ASSERT(testbusy(p->ptr),(long));
130: p->ptr = clearbusy(p->ptr);
131: ASSERT(p->ptr > allocp && p->ptr <= alloct,(long));
132: return(NULL);
133: }
134:
135: /* realloc(p, nbytes) reallocates a block obtained from malloc()
136: * and freed since last call of malloc()
137: * to have new size nbytes, and old content
138: * returns new location, or 0 on failure
139: */
140:
141: char *
142: realloc(p, nbytes)
143: register union store *p;
144: unsigned nbytes;
145: {
146: register union store *q;
147: union store *s, *t;
148: register unsigned nw;
149: unsigned onw;
150:
151: if(testbusy(p[-1].ptr))
152: free((char *)p);
153: onw = p[-1].ptr - p;
154: q = (union store *)malloc(nbytes);
155: if(q==NULL || q==p)
156: return((char *)q);
157: s = p;
158: t = q;
159: nw = (nbytes+WORD-1)/WORD;
160: if(nw<onw)
161: onw = nw;
162: while(onw--!=0)
163: *t++ = *s++;
164: if(q<p && q+nw>=p)
165: (q+(q+nw-p))->ptr = allocx;
166: return((char *)q);
167: }
168:
169: #ifdef debug
170: allock()
171: {
172: #ifdef longdebug
173: register union store *p;
174: int x;
175: x = 0;
176: for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
177: if(p==allocp)
178: x++;
179: }
180: ASSERT(p==alloct,(long));
181: return(x==1|p==allocp);
182: #else
183: return(1);
184: #endif
185: }
186: #endif
187:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.