chiark / gitweb /
Initialize the token buffer properly.
[mLib] / sub.c
CommitLineData
0875b58f 1/* -*-c-*-
2 *
ff0f0220 3 * $Id: sub.c,v 1.5 1999/05/19 20:27:11 mdw Exp $
0875b58f 4 *
5 * Allocation of known-size blocks
6 *
7 * (c) 1998 Straylight/Edgeware
8 */
9
c846879c 10/*----- Licensing notice --------------------------------------------------*
0875b58f 11 *
12 * This file is part of the mLib utilities library.
13 *
14 * mLib is free software; you can redistribute it and/or modify
c846879c 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 *
0875b58f 19 * mLib 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
c846879c 22 * GNU Library General Public License for more details.
23 *
24 * You should have received a copy of the GNU Library General Public
0bd98442 25 * License along with mLib; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
27 * MA 02111-1307, USA.
0875b58f 28 */
29
30/*----- Revision history --------------------------------------------------*
31 *
32 * $Log: sub.c,v $
ff0f0220 33 * Revision 1.5 1999/05/19 20:27:11 mdw
34 * Change naming to match newer mLib conventions.
35 *
8c6d948b 36 * Revision 1.4 1999/05/13 22:48:55 mdw
37 * Change `-ise' to `-ize' throughout.
38 *
0bd98442 39 * Revision 1.3 1999/05/06 19:51:35 mdw
40 * Reformatted the LGPL notice a little bit.
41 *
c846879c 42 * Revision 1.2 1999/05/05 18:50:31 mdw
43 * Change licensing conditions to LGPL.
44 *
45 * Revision 1.1.1.1 1998/06/17 23:44:42 mdw
46 * Initial version of mLib
0875b58f 47 *
48 */
49
50/*----- The big idea ------------------------------------------------------*
51 *
52 * This file provides an extra layer over @malloc@. It provides fast
8c6d948b 53 * turnover for small blocks, and tries to minimize the per-block overhead.
0875b58f 54 *
55 * To do its job, @alloc@ must place an extra restriction on you: you must
56 * know the size of a block when you free it. Usually you'll have this
57 * information encoded in some way either in the block or in the thing that
58 * referenced it, so this isn't a hardship.
59 *
60 * It works fairly simply. If a request for a big block (as defined by the
61 * constants below) comes in, it gets sent on to @malloc@ unmolested. For
62 * small blocks, it goes straight to a `bin' -- a list containing free blocks
63 * of exactly that size, or the nearest bigger size we can manage. If the
64 * bin is empty, a `chunk' is allocated from @malloc@: this has enough room
65 * for lots of blocks of the requested size, so it ets split up and each
66 * individual small block is added to the bin list. The first block in the
67 * bin list is then removed and given to the caller. In this way, @malloc@
68 * only stores its information once for lots of little blocks, so we save
69 * memory. Because I know where the correct bin is just from the block size,
70 * and I don't need to do any searching at all in the usual case (because the
71 * list isn't empty) I can get a speed advantage too.
72 *
73 * This code is almost certainly not ANSI conformant, although I'm not
74 * actually sure. If some kind soul would let me know how seriously I've
75 * violated the standard, and whether this is easily fixable, I'd be
76 * grateful.
77 */
78
79/*----- Header files ------------------------------------------------------*/
80
81/* --- ANSI headers --- */
82
83#include <stdio.h>
84#include <stdlib.h>
85#include <string.h>
86
87/* --- Local headers --- */
88
89#undef TRACK_ENABLE /* Can't track suballoc routines */
90#include "alloc.h"
91
92/*----- Configuration and tuning ------------------------------------------*/
93
94/* --- The largest block I'll handle here --- *
95 *
96 * Anything larger will be handed on to @malloc@.
97 */
98
99#define SUB_MAXBIN 256
100
101/* --- Preferred chunk size --- *
102 *
103 * When a bin is empty, I'll allocate a large chunk of approximately this
104 * size and divvy it up into small bin-sized blocks.
105 */
106
107#define SUB_CHUNK 4096
108
109/*----- Other useful macros -----------------------------------------------*/
110
111/* --- The granularity of bin buffers --- *
112 *
113 * All blocks allocated by the binner are a multiple of this size. I've
114 * chosen @void *@ because I need to store @void *@ things in here.
115 */
116
117#define SUB_GRANULE sizeof(void *)
118
119/* --- Finding the right bin for a given size --- *
120 *
121 * This chooses the correct bin for an allocation. Input is the size of
122 * block wanted; result is the bin index.
123 */
124
125#define SUB_BIN(x) (((x) + SUB_GRANULE - 1) / SUB_GRANULE)
126
127/* --- Convert a bin back to the block size --- *
128 *
129 * This gives the size of block contained in a given bin.
130 */
131
132#define SUB_BINSZ(x) ((x) * SUB_GRANULE)
133
134/* --- Number of bins required --- */
135
136#define SUB_BINS (SUB_MAXBIN / SUB_GRANULE + 1)
137
138/*----- Static variables --------------------------------------------------*/
139
ff0f0220 140static void *bins[SUB_BINS];
141static size_t sizes[SUB_BINS];
0875b58f 142
143/*----- Main code ---------------------------------------------------------*/
144
145/* --- @sub_alloc@ --- *
146 *
147 * Arguments: @size_t s@ = size of chunk wanted
148 *
149 * Returns: Pointer to a block at least as large as the one wanted.
150 *
151 * Use: Allocates a small block of memory. If there is no more
152 * memory left, the exception @EXC_NOMEM@ is raised.
153 */
154
155void *sub_alloc(size_t s)
156{
157 int bin = SUB_BIN(s);
158 void *p;
159
160 /* --- Handle oversize blocks --- */
161
162 if (bin >= SUB_BINS)
163 return (xmalloc(s));
164
165 /* --- If the bin is empty, find some memory --- */
166
ff0f0220 167 if (!bins[bin]) {
0875b58f 168 char *p, *q;
169
ff0f0220 170 p = xmalloc(sizes[bin]);
171 q = p + sizes[bin];
0875b58f 172
173 s = SUB_BINSZ(bin);
174
175 q -= s;
176 *(void **)q = 0;
177
178 while (q > p) {
179 q -= s;
180 *(void **)q = q + s;
181 }
182
ff0f0220 183 bins[bin] = p;
0875b58f 184 }
185
186 /* --- Extract the first block in the list --- */
187
ff0f0220 188 p = bins[bin];
189 bins[bin] = *(void **)p;
0875b58f 190 return (p);
191}
192
193/* --- @sub_free@ --- *
194 *
195 * Arguments: @void *p@ = address of block to free
196 * @size_t s@ = size of block
197 *
198 * Returns: ---
199 *
200 * Use: Frees a block allocated by @sub_alloc@.
201 */
202
203void sub_free(void *p, size_t s)
204{
205 int bin = SUB_BIN(s);
206
207 if (bin >= SUB_BINS)
208 free(p);
209 else {
ff0f0220 210 *(void **)p = bins[bin];
211 bins[bin] = p;
0875b58f 212 }
213}
214
215/* --- @sub_init@ --- *
216 *
217 * Arguments: ---
218 *
219 * Returns: ---
220 *
8c6d948b 221 * Use: Initializes the magic allocator.
0875b58f 222 */
223
224void sub_init(void)
225{
226 int i;
227
8c6d948b 228 /* --- Initialize the sizes bins --- */
0875b58f 229
230 for (i = 1; i < SUB_BINS; i++) {
ff0f0220 231 sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
0875b58f 232 SUB_BINSZ(i) * SUB_BINSZ(i));
233 }
234}
235
236/*----- Debugging code ----------------------------------------------------*/
237
238#ifdef TEST_RIG
239
240#define BLOCKS 1024
241#define SIZE_MAX 2048
242#define ITERATIONS 500000
243
244int main(void)
245{
246 static void *block[BLOCKS];
247 static size_t size[BLOCKS];
248 size_t allocced = 0;
249 int i;
250 long count;
251
252 sub_init();
253
254 for (count = 0; count < ITERATIONS; count++) {
255 i = rand() % BLOCKS;
256 if (block[i]) {
257 sub_free(block[i], size[i]);
258 block[i] = 0;
259 allocced -= size[i];
260 } else {
261 block[i] = sub_alloc(size[i] =
262 rand() % (SUB_MAXBIN - 128) + 128);
263 allocced += size[i];
264 memset(block[i], 0, size[i]); /* trample allocated storage */
265 }
266 }
267
268 return (0);
269}
270
271#endif
272
273/*----- That's all, folks -------------------------------------------------*/