d3409d5e |
1 | /* -*-c-*- |
2 | * |
48d66950 |
3 | * $Id: mparena.c,v 1.3 1999/11/22 13:58:00 mdw Exp $ |
d3409d5e |
4 | * |
5 | * Allocation and freeing of MP buffers |
6 | * |
7 | * (c) 1999 Straylight/Edgeware |
8 | */ |
9 | |
10 | /*----- Licensing notice --------------------------------------------------* |
11 | * |
12 | * This file is part of Catacomb. |
13 | * |
14 | * Catacomb is free software; you can redistribute it and/or modify |
15 | * it under the terms of the GNU Library General Public License as |
16 | * published by the Free Software Foundation; either version 2 of the |
17 | * License, or (at your option) any later version. |
18 | * |
19 | * Catacomb is distributed in the hope that it will be useful, |
20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22 | * GNU Library General Public License for more details. |
23 | * |
24 | * You should have received a copy of the GNU Library General Public |
25 | * License along with Catacomb; if not, write to the Free |
26 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, |
27 | * MA 02111-1307, USA. |
28 | */ |
29 | |
30 | /*----- Revision history --------------------------------------------------* |
31 | * |
32 | * $Log: mparena.c,v $ |
48d66950 |
33 | * Revision 1.3 1999/11/22 13:58:00 mdw |
34 | * Document the tweakables. |
35 | * |
12a9a6e5 |
36 | * Revision 1.2 1999/11/21 22:14:19 mdw |
37 | * Fix bug. Improve diagnostic capabilities. |
38 | * |
d3409d5e |
39 | * Revision 1.1 1999/11/17 18:02:16 mdw |
40 | * New multiprecision integer arithmetic suite. |
41 | * |
42 | */ |
43 | |
44 | /*----- Header files ------------------------------------------------------*/ |
45 | |
46 | #include <stdio.h> |
47 | #include <stdlib.h> |
48 | #include <string.h> |
49 | |
50 | #include <mLib/alloc.h> |
51 | #include <mLib/sub.h> |
52 | |
53 | #include "mparena.h" |
54 | |
12a9a6e5 |
55 | /*----- Tweakables --------------------------------------------------------*/ |
56 | |
48d66950 |
57 | /* --- @MPARENA_TRIVIAL@ --- * |
58 | * |
59 | * Make the allocator a passthrough. It immediately calls the underlying |
60 | * allocation functions rather than attempting to keep track of blocks |
61 | * itself. |
62 | */ |
63 | |
12a9a6e5 |
64 | /* #define MPARENA_TRIVIAL */ |
65 | |
48d66950 |
66 | /* --- @MPARENA_DEBUG@ --- * |
67 | * |
68 | * The name of an output trace file to which logging information about the |
69 | * state of arena trees should be written. If unset, no logging is done. |
70 | */ |
71 | |
12a9a6e5 |
72 | /* #define MPARENA_DEBUG "mparena.out" */ |
73 | |
d3409d5e |
74 | /*----- Default allocator -------------------------------------------------*/ |
75 | |
76 | static void *defalloc(mparena *a, size_t sz) { return xmalloc(sz); } |
77 | static void deffree(mparena *a, void *p) { free(p); } |
78 | |
79 | mparena_ops mparena_defops = { defalloc, deffree }; |
80 | |
81 | /*----- Static variables --------------------------------------------------*/ |
82 | |
12a9a6e5 |
83 | #ifdef MPARENA_DEBUG |
84 | static FILE *debugfp = 0; |
85 | |
86 | # define MPARENA_OPENFILE do { \ |
87 | if (!debugfp) { \ |
88 | if ((debugfp = fopen(MPARENA_DEBUG, "w")) == 0) { \ |
89 | fprintf(stderr, "couldn't open debug output file\n"); \ |
90 | exit(EXIT_FAILURE); \ |
91 | } \ |
92 | } \ |
93 | } while (0) |
94 | |
95 | #endif |
96 | |
d3409d5e |
97 | static mparena arena = { 0, &mparena_defops }; |
98 | |
99 | #define MPARENA_RESOLVE(a) do { \ |
100 | if ((a) == MPARENA_GLOBAL) \ |
101 | (a) = &arena; \ |
102 | } while (0) |
103 | |
104 | /*----- Main code ---------------------------------------------------------*/ |
105 | |
106 | /* --- @tdump@ --- * |
107 | * |
108 | * Arguments: @mparena_node *n@ = pointer to tree node to dump |
109 | * |
110 | * Returns: --- |
111 | * |
112 | * Use: Recursively dumps out the allocation tree. |
113 | */ |
114 | |
12a9a6e5 |
115 | #ifdef MPARENA_DEBUG |
116 | |
d3409d5e |
117 | static void tdump(mparena_node *n) |
118 | { |
119 | if (!n) |
12a9a6e5 |
120 | putc('*', debugfp); |
d3409d5e |
121 | else { |
12a9a6e5 |
122 | putc('(', debugfp); |
d3409d5e |
123 | tdump(n->left); |
12a9a6e5 |
124 | fprintf(debugfp, ", %u, ", n->v[0]); |
d3409d5e |
125 | tdump(n->right); |
12a9a6e5 |
126 | putc(')', debugfp); |
d3409d5e |
127 | } |
128 | } |
129 | |
12a9a6e5 |
130 | #endif |
131 | |
d3409d5e |
132 | /* --- @mparena_create@ --- * |
133 | * |
134 | * Arguments: @mparena *a@ = pointer to arena block |
135 | * |
136 | * Returns: --- |
137 | * |
138 | * Use: Initializes an MP arena so that blocks can be allocated from |
139 | * it. |
140 | */ |
141 | |
142 | void mparena_create(mparena *a) |
143 | { |
144 | a->root = 0; |
145 | a->ops = &mparena_defops; |
146 | } |
147 | |
148 | /* --- @mparena_setops@ --- * |
149 | * |
150 | * Arguments: @mparena *a@ = pointer to arena block |
151 | * @mparena_ops *ops@ = pointer to operations block or null |
152 | * |
153 | * Returns: The previous operations block. |
154 | * |
155 | * Use: Sets or queries the operations attached to an arena. |
156 | */ |
157 | |
158 | mparena_ops *mparena_setops(mparena *a, mparena_ops *ops) |
159 | { |
160 | mparena_ops *o; |
161 | MPARENA_RESOLVE(a); |
162 | o = a->ops; |
163 | if (ops) |
164 | a->ops = ops; |
165 | return (0); |
166 | } |
167 | |
168 | /* --- @mparena_destroy@ --- * |
169 | * |
170 | * Arguments: @mparena *a@ = pointer to arena block |
171 | * |
172 | * Returns: --- |
173 | * |
174 | * Use: Frees an MP arena, and all the vectors held within it. The |
175 | * blocks which are currently allocated can be freed into some |
176 | * other arena. |
177 | */ |
178 | |
179 | static void tfree(mparena *a, mparena_node *n) |
180 | { |
181 | a->ops->free(a, n->v); |
182 | if (n->left) |
183 | tfree(a, n->left); |
184 | if (n->right) |
185 | tfree(a, n->right); |
186 | DESTROY(n); |
187 | } |
188 | |
189 | void mparena_destroy(mparena *a) |
190 | { |
191 | tfree(a, a->root); |
192 | a->root = 0; |
193 | } |
194 | |
195 | /* --- @mpalloc@ --- * |
196 | * |
197 | * Arguments: @mparena *a@ = pointer to arena block |
198 | * @size_t sz@ = number of digits required |
199 | * |
200 | * Returns: Pointer to a suitably sized block. |
201 | * |
202 | * Use: Allocates a lump of data suitable for use as an array of MP |
203 | * digits. |
204 | */ |
205 | |
12a9a6e5 |
206 | #ifdef MPARENA_TRIVIAL |
207 | |
208 | mpw *mpalloc(mparena *a, size_t sz) |
209 | { |
210 | MPARENA_RESOLVE(a); |
211 | return (a->ops->alloc(a, MPWS(sz))); |
212 | } |
213 | |
214 | #else |
215 | |
d3409d5e |
216 | mpw *mpalloc(mparena *a, size_t sz) |
217 | { |
218 | mparena_node **nn, *n; |
219 | mpw *v; |
220 | |
221 | MPARENA_RESOLVE(a); |
222 | nn = &a->root; |
223 | |
12a9a6e5 |
224 | #ifdef MPARENA_DEBUG |
225 | MPARENA_OPENFILE; |
226 | fprintf(debugfp, "alloc %u\n before: ", sz); |
227 | tdump(a->root); putc('\n', debugfp); |
228 | if (sz == 0) |
229 | asm("nop"); |
d3409d5e |
230 | #endif |
231 | |
232 | /* --- First, find a block which is big enough --- */ |
233 | |
234 | again: |
235 | n = *nn; |
236 | if (!n) { |
12a9a6e5 |
237 | #ifdef MPARENA_DEBUG |
238 | fputs(" failed\n", debugfp); |
239 | #endif |
d3409d5e |
240 | v = a->ops->alloc(a, MPWS(sz + 1)); |
241 | v[0] = sz; |
242 | return (v + 1); |
243 | } |
244 | if (n->v[0] < sz) { |
245 | nn = &n->right; |
246 | goto again; |
247 | } |
248 | |
249 | /* --- Now try to find a smaller block which is suitable --- */ |
250 | |
251 | while (n->left && n->left->v[0] >= sz) { |
252 | nn = &n->left; |
253 | n = *nn; |
254 | } |
255 | |
256 | /* --- If the block we've got is still too large, start digging --- */ |
257 | |
12a9a6e5 |
258 | if (n->v[0] > sz * 2) { |
d3409d5e |
259 | nn = &n->left; |
260 | goto again; |
261 | } |
262 | |
263 | /* --- I've now found a suitable block --- */ |
264 | |
265 | v = n->v; |
266 | |
267 | /* --- Remove this node from the tree --- */ |
268 | |
269 | if (!n->left) |
270 | *nn = n->right; |
271 | else if (!n->right) |
272 | *nn = n->left; |
273 | else { |
274 | mparena_node *left = n->left; |
275 | mparena_node *p = *nn = n->right; |
276 | while (p->left) |
277 | p = p->left; |
278 | p->left = left; |
279 | } |
280 | |
12a9a6e5 |
281 | #ifdef MPARENA_DEBUG |
282 | fputs(" after: ", debugfp); |
283 | tdump(a->root); putc('\n', debugfp); |
284 | #endif |
285 | |
d3409d5e |
286 | /* --- Get rid of this node now --- */ |
287 | |
288 | DESTROY(n); |
289 | return (v + 1); |
290 | } |
291 | |
12a9a6e5 |
292 | #endif |
293 | |
d3409d5e |
294 | /* --- @mpfree@ --- * |
295 | * |
296 | * Arguments: @mparena *a@ = pointer to arena block |
297 | * @mpw *v@ = pointer to allocated vector |
298 | * |
299 | * Returns: --- |
300 | * |
301 | * Use: Returns an MP vector to an arena. It doesn't have to be |
302 | * returned to the arena from which it was allocated. |
303 | */ |
304 | |
12a9a6e5 |
305 | #ifdef MPARENA_TRIVIAL |
306 | |
307 | void mpfree(mparena *a, mpw *v) |
308 | { |
309 | MPARENA_RESOLVE(a); |
310 | a->ops->free(a, v); |
311 | } |
312 | |
313 | #else |
314 | |
d3409d5e |
315 | void mpfree(mparena *a, mpw *v) |
316 | { |
317 | mparena_node **nn, *n; |
318 | size_t sz = *--v; |
319 | |
320 | MPARENA_RESOLVE(a); |
d3409d5e |
321 | |
12a9a6e5 |
322 | #ifdef MPARENA_DEBUG |
323 | MPARENA_OPENFILE; |
324 | fprintf(debugfp, "free %u\n before: ", sz); |
325 | tdump(a->root); putc('\n', debugfp); |
326 | #endif |
327 | |
328 | nn = &a->root; |
d3409d5e |
329 | while (*nn) { |
330 | n = *nn; |
331 | if (n->v[0] > sz) |
332 | nn = &n->left; |
333 | else |
334 | nn = &n->right; |
335 | } |
336 | |
337 | n = CREATE(mparena_node); |
338 | n->left = n->right = 0; |
339 | n->v = v; |
340 | *nn = n; |
341 | |
12a9a6e5 |
342 | #ifdef MPARENA_DEBUG |
343 | fputs(" after: ", debugfp); |
344 | tdump(a->root); putc('\n', debugfp); |
d3409d5e |
345 | #endif |
346 | } |
347 | |
12a9a6e5 |
348 | #endif |
349 | |
d3409d5e |
350 | /*----- That's all, folks -------------------------------------------------*/ |