3 * $Id: dynarray.h,v 1.3 1999/05/06 19:51:35 mdw Exp $
5 * Dynamic arrays implementation
7 * (c) 1998 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of the mLib utilities library.
14 * mLib 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.
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
22 * GNU Library General Public License for more details.
24 * You should have received a copy of the GNU Library General Public
25 * License along with mLib; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
30 /*----- Revision history --------------------------------------------------*
32 * $Log: dynarray.h,v $
33 * Revision 1.3 1999/05/06 19:51:35 mdw
34 * Reformatted the LGPL notice a little bit.
36 * Revision 1.2 1999/05/05 18:50:31 mdw
37 * Change licensing conditions to LGPL.
39 * Revision 1.1.1.1 1998/06/17 23:44:42 mdw
40 * Initial version of mLib
51 /*----- Required header files ---------------------------------------------*/
64 /*----- Horrific hacking -------------------------------------------------*
66 * Several bits of this code need extending arrays (in particular, the array
67 * handler and the label allocator), although the sizes of the objects being
70 * This file contains (horrors!) a sort of C++ template-a-like which
71 * implements such growing arrays. Read on, if your constitution can stand
75 /* --- Macro: @DYNDECLS@ --- *
77 * Arguments: @prefix@ = prefix string which begins all external
79 * @obtype@ = the element type of the array
80 * @chunksize@ = the number of items in a chunk
82 * Use: Provides declarations suitable for use in a header file which
83 * define functions for manipulating the specific dynamic array
84 * described in the arguments.
87 #define DYNDECLS(prefix, obtype, chunksize) /* ... */ \
89 /* --- Define some constants --- */ \
92 prefix ## __mask = chunksize - 1, \
93 prefix ## __size = chunksize \
96 /* --- Type definitions --- */ \
98 typedef obtype prefix ## __object; \
100 typedef struct prefix ## _chunk { \
101 struct prefix ## _chunk *next; \
103 prefix ## __object o[prefix ## __size]; \
104 } prefix ## _chunk; \
106 /* --- External routines --- */ \
108 /* --- @PREFIX_find@ --- * \
110 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
111 * @size_t index@ = index into array which we want \
113 * Returns: Pointer to the object at appropriate index, or null \
115 * Use: Indexes an item without creating it if it's not there \
119 extern prefix ## __object *prefix ## _find(prefix ## _chunk **base, \
122 /* --- @PREFIX_new@ --- * \
124 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
125 * @size_t index@ = index into array which we want \
127 * Returns: Pointer to the object at appropriate index \
129 * Use: Indexes an item, creating it if necessary. \
132 extern prefix ## __object *prefix ## _new(prefix ## _chunk **base, \
135 /* --- @PREFIX_free@ --- * \
137 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
141 * Use: Releases all the memory directly attached to an array. \
144 extern void prefix ## _free(prefix ## _chunk **base);
146 /* --- Macro: @DYNARRAY@ --- *
148 * Arguments: @prefix@ = prefix string for uniquification
149 * @init@ = how to initialise a chunk
150 * @kill@ = how to free a chunk
152 * Use: Builds template routines for dynamically growing arrays.
153 * The two arguments @init@ and @kill@ must use the macros
157 #define DYNARRAY(prefix, init, kill) /* ... */ \
159 /* --- @PREFIX_find@ --- * \
161 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
162 * @size_t index@ = index into array which we want \
164 * Returns: Pointer to the object at appropriate index, or null \
166 * Use: Indexes an item without creating it if it's not there \
170 prefix ## __object *prefix ## _find(prefix ## _chunk **base, \
173 size_t chunkid = index & ~prefix ## __mask; \
174 prefix ## _chunk *p = *base; \
175 index &= prefix ## __mask; \
178 if (!p || p->base > chunkid) \
180 if (p->base == chunkid) \
185 return (p->o + index); \
188 /* --- @PREFIX_new@ --- * \
190 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
191 * @size_t index@ = index into array which we want \
193 * Returns: Pointer to the object at appropriate index \
195 * Use: Indexes an item, creating it if necessary. \
198 prefix ## __object *prefix ## _new(prefix ## _chunk **base, \
201 size_t chunkid = index & ~prefix ## __mask; \
202 prefix ## _chunk *p = (prefix ## _chunk *)base; \
203 index &= prefix ## __mask; \
205 while (p->next && p->next->base < chunkid) \
208 if (!p->next || p->next->base != chunkid) { \
209 prefix ## _chunk *q = CREATE(prefix ## _chunk); \
214 DYN__GRABARGS(init, (q, prefix)); \
217 return (p->next->o + index); \
220 /* --- @PREFIX_free@ --- * \
222 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
226 * Use: Releases all the memory directly attached to an array. \
229 void prefix ## _free(prefix ## _chunk **base) \
231 prefix ## _chunk *p = *base, *q; \
234 DYN__GRABARGS(kill, (p, prefix)); \
243 /* --- A vile bit of hacking --- *
245 * All of this yukkiness is a perfectly legitimate consequence of the (daft)
246 * rules about when macro arguments get expanded.
250 #define DYN__ID2(x, y) x, y
251 #define DYN__CONTORT(mac, args) mac args
252 #define DYN__GRABARGS(mac, args, more) \
253 DYN__CONTORT(mac, (DYN__ID args, DYN__ID2 more))
255 /* --- Macro: @DYNITER@ --- *
257 * Arguments: @what@ = what to do for each item -- a macro or function
258 * which is passed the address of an item
260 * Use: Does something for each item.
263 #define DYNITER DYN__ITER ,
264 #define DYN__ITER(what, chunk, prefix) do { \
266 for (i = 0; i < prefix ## __size; i++) \
267 what(chunk->o + i); \
270 /* --- Macro: @DYNNOP@ --- *
277 #define DYNNOP DYN__NOP, (dummy)
278 #define DYN__NOP(dummy, chunk, prefix) /* nop */
280 /*----- That's all, folks -------------------------------------------------*/