Commit | Line | Data |
---|---|---|
394a1d25 C |
1 | /************************************************************************* |
2 | * This program is copyright (C) 1985, 1986 by Jonathan Payne. It is * | |
3 | * provided to you without charge for use only on a licensed Unix * | |
4 | * system. You may copy JOVE provided that this notice is included with * | |
5 | * the copy. You may not sell copies of this program or versions * | |
6 | * modified for use on microcomputer systems, unless the copies are * | |
7 | * included with a Unix system distribution and the source is provided. * | |
8 | *************************************************************************/ | |
9 | ||
10 | #include "tune.h" | |
11 | ||
12 | #ifdef MY_MALLOC | |
13 | ||
14 | /* avoid break bug */ | |
15 | #ifdef pdp11 | |
16 | # define GRANULE 64 | |
17 | #else | |
18 | # define GRANULE 0 | |
19 | #endif | |
20 | ||
21 | /* C storage allocator | |
22 | * circular first-fit strategy | |
23 | * works with noncontiguous, but monotonically linked, arena | |
24 | * each block is preceded by a ptr to the (pointer of) | |
25 | * the next following block | |
26 | * blocks are exact number of words long | |
27 | * aligned to the data type requirements of ALIGN | |
28 | * pointers to blocks must have BUSY bit 0 | |
29 | * bit in ptr is 1 for busy, 0 for idle | |
30 | * gaps in arena are merely noted as busy blocks | |
31 | * last block of arena (pointed to by alloct) is empty and | |
32 | * has a pointer to first | |
33 | * idle blocks are coalesced during space search | |
34 | * | |
35 | * a different implementation may need to redefine | |
36 | * ALIGN, NALIGN, BLOCK, BUSY, INT | |
37 | * where INT is integer type to which a pointer can be cast | |
38 | */ | |
39 | ||
40 | #define INT int | |
41 | #define ALIGN int | |
42 | #define NALIGN 1 | |
43 | #define WORD sizeof(union store) | |
44 | #define BLOCK 1024 /* a multiple of WORD*/ | |
45 | #define BUSY 1 | |
46 | #define NULL 0 | |
47 | #define testbusy(p) ((INT)(p)&BUSY) | |
48 | #define setbusy(p) (union store *) ((INT) (p) | BUSY) | |
49 | #define clearbusy(p) (union store *) ((INT) (p) &~ BUSY) | |
50 | ||
51 | union store { | |
52 | union store *ptr; | |
53 | ALIGN dummy[NALIGN]; | |
54 | int calloc; /*calloc clears an array of integers*/ | |
55 | }; | |
56 | ||
57 | static union store allocs[2], /*initial arena*/ | |
58 | *allocp, /*search ptr*/ | |
59 | *alloct, /*arena top*/ | |
60 | *allocx; /*for benefit of realloc*/ | |
61 | ||
62 | char *sbrk(); | |
63 | ||
64 | char * | |
65 | malloc(nbytes) | |
66 | unsigned int nbytes; | |
67 | { | |
68 | register union store *p, | |
69 | *q; | |
70 | register int nw; | |
71 | static int temp; /* coroutines assume no auto */ | |
72 | ||
73 | if (allocs[0].ptr == 0) { /* first time */ | |
74 | allocs[0].ptr = setbusy(&allocs[1]); | |
75 | allocs[1].ptr = setbusy(&allocs[0]); | |
76 | alloct = &allocs[1]; | |
77 | allocp = &allocs[0]; | |
78 | } | |
79 | nw = (nbytes + WORD + WORD - 1) / WORD; | |
80 | for (p = allocp; ; ) { | |
81 | for (temp = 0; ; ) { | |
82 | if (!testbusy(p->ptr)) { | |
83 | while (!testbusy((q = p->ptr)->ptr)) | |
84 | p->ptr = q->ptr; | |
85 | if(q >= p + nw && p + nw >= p) | |
86 | goto found; | |
87 | } | |
88 | q = p; | |
89 | p = clearbusy(p->ptr); | |
90 | if (p > q) | |
91 | ; | |
92 | else if (q != alloct || p != allocs) | |
93 | return NULL; | |
94 | else if (++temp > 1) | |
95 | break; | |
96 | } | |
97 | temp = ((nw + BLOCK/WORD) / (BLOCK/WORD)) * (BLOCK/WORD); | |
98 | q = (union store *) sbrk(0); | |
99 | if (q + temp + GRANULE < q) | |
100 | return NULL; | |
101 | q = (union store *) sbrk(temp * WORD); | |
102 | if ((INT) q == -1) | |
103 | return NULL; | |
104 | alloct->ptr = q; | |
105 | if (q != alloct+1) | |
106 | alloct->ptr = setbusy(alloct->ptr); | |
107 | alloct = q->ptr = q + temp - 1; | |
108 | alloct->ptr = setbusy(allocs); | |
109 | } | |
110 | found: | |
111 | allocp = p + nw; | |
112 | if (q > allocp) { | |
113 | allocx = allocp->ptr; | |
114 | allocp->ptr = p->ptr; | |
115 | } | |
116 | p->ptr = setbusy(allocp); | |
117 | return (char *) (p + 1); | |
118 | } | |
119 | ||
120 | /* freeing strategy tuned for LIFO allocation */ | |
121 | ||
122 | free(ap) | |
123 | register char *ap; | |
124 | { | |
125 | register union store *p = (union store *) ap; | |
126 | ||
127 | allocp = --p; | |
128 | p->ptr = clearbusy(p->ptr); | |
129 | } | |
130 | ||
131 | /* realloc(p, nbytes) reallocates a block obtained from malloc() | |
132 | * and freed since last call of malloc() | |
133 | * to have new size nbytes, and old content | |
134 | * returns new location, or 0 on failure | |
135 | */ | |
136 | ||
137 | char * | |
138 | realloc(obj, nbytes) | |
139 | char *obj; | |
140 | unsigned int nbytes; | |
141 | { | |
142 | register union store *q, | |
143 | *p = (union store *) obj; | |
144 | union store *s, | |
145 | *t; | |
146 | register unsigned int nw; | |
147 | unsigned int onw; | |
148 | ||
149 | if (testbusy(p[-1].ptr)) | |
150 | free((char *) p); | |
151 | onw = p[-1].ptr - p; | |
152 | q = (union store *) malloc(nbytes); | |
153 | if(q == NULL || q == p) | |
154 | return((char *) q); | |
155 | s = p; | |
156 | t = q; | |
157 | nw = (nbytes + WORD - 1)/WORD; | |
158 | if (nw < onw) | |
159 | onw = nw; | |
160 | while (onw-- != 0) | |
161 | *t++ = *s++; | |
162 | if(q < p && q + nw >= p) | |
163 | (q + (q+nw-p))->ptr = allocx; | |
164 | return (char *) q; | |
165 | } | |
166 | ||
167 | #endif MY_MALLOC |