3 * $Id: dynarray.h,v 1.1 1998/06/17 23:44:42 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 General Public License as published by
16 * the Free Software Foundation; either version 2 of the License, or
17 * (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 General Public License for more details.
24 * You should have received a copy of the GNU General Public License
25 * along with mLib; if not, write to the Free Software Foundation,
26 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
29 /*----- Revision history --------------------------------------------------*
31 * $Log: dynarray.h,v $
32 * Revision 1.1 1998/06/17 23:44:42 mdw
44 /*----- Required header files ---------------------------------------------*/
57 /*----- Horrific hacking -------------------------------------------------*
59 * Several bits of this code need extending arrays (in particular, the array
60 * handler and the label allocator), although the sizes of the objects being
63 * This file contains (horrors!) a sort of C++ template-a-like which
64 * implements such growing arrays. Read on, if your constitution can stand
68 /* --- Macro: @DYNDECLS@ --- *
70 * Arguments: @prefix@ = prefix string which begins all external
72 * @obtype@ = the element type of the array
73 * @chunksize@ = the number of items in a chunk
75 * Use: Provides declarations suitable for use in a header file which
76 * define functions for manipulating the specific dynamic array
77 * described in the arguments.
80 #define DYNDECLS(prefix, obtype, chunksize) /* ... */ \
82 /* --- Define some constants --- */ \
85 prefix ## __mask = chunksize - 1, \
86 prefix ## __size = chunksize \
89 /* --- Type definitions --- */ \
91 typedef obtype prefix ## __object; \
93 typedef struct prefix ## _chunk { \
94 struct prefix ## _chunk *next; \
96 prefix ## __object o[prefix ## __size]; \
99 /* --- External routines --- */ \
101 /* --- @PREFIX_find@ --- * \
103 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
104 * @size_t index@ = index into array which we want \
106 * Returns: Pointer to the object at appropriate index, or null \
108 * Use: Indexes an item without creating it if it's not there \
112 extern prefix ## __object *prefix ## _find(prefix ## _chunk **base, \
115 /* --- @PREFIX_new@ --- * \
117 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
118 * @size_t index@ = index into array which we want \
120 * Returns: Pointer to the object at appropriate index \
122 * Use: Indexes an item, creating it if necessary. \
125 extern prefix ## __object *prefix ## _new(prefix ## _chunk **base, \
128 /* --- @PREFIX_free@ --- * \
130 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
134 * Use: Releases all the memory directly attached to an array. \
137 extern void prefix ## _free(prefix ## _chunk **base);
139 /* --- Macro: @DYNARRAY@ --- *
141 * Arguments: @prefix@ = prefix string for uniquification
142 * @init@ = how to initialise a chunk
143 * @kill@ = how to free a chunk
145 * Use: Builds template routines for dynamically growing arrays.
146 * The two arguments @init@ and @kill@ must use the macros
150 #define DYNARRAY(prefix, init, kill) /* ... */ \
152 /* --- @PREFIX_find@ --- * \
154 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
155 * @size_t index@ = index into array which we want \
157 * Returns: Pointer to the object at appropriate index, or null \
159 * Use: Indexes an item without creating it if it's not there \
163 prefix ## __object *prefix ## _find(prefix ## _chunk **base, \
166 size_t chunkid = index & ~prefix ## __mask; \
167 prefix ## _chunk *p = *base; \
168 index &= prefix ## __mask; \
171 if (!p || p->base > chunkid) \
173 if (p->base == chunkid) \
178 return (p->o + index); \
181 /* --- @PREFIX_new@ --- * \
183 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
184 * @size_t index@ = index into array which we want \
186 * Returns: Pointer to the object at appropriate index \
188 * Use: Indexes an item, creating it if necessary. \
191 prefix ## __object *prefix ## _new(prefix ## _chunk **base, \
194 size_t chunkid = index & ~prefix ## __mask; \
195 prefix ## _chunk *p = (prefix ## _chunk *)base; \
196 index &= prefix ## __mask; \
198 while (p->next && p->next->base < chunkid) \
201 if (!p->next || p->next->base != chunkid) { \
202 prefix ## _chunk *q = CREATE(prefix ## _chunk); \
207 DYN__GRABARGS(init, (q, prefix)); \
210 return (p->next->o + index); \
213 /* --- @PREFIX_free@ --- * \
215 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
219 * Use: Releases all the memory directly attached to an array. \
222 void prefix ## _free(prefix ## _chunk **base) \
224 prefix ## _chunk *p = *base, *q; \
227 DYN__GRABARGS(kill, (p, prefix)); \
236 /* --- A vile bit of hacking --- *
238 * All of this yukkiness is a perfectly legitimate consequence of the (daft)
239 * rules about when macro arguments get expanded.
243 #define DYN__ID2(x, y) x, y
244 #define DYN__CONTORT(mac, args) mac args
245 #define DYN__GRABARGS(mac, args, more) \
246 DYN__CONTORT(mac, (DYN__ID args, DYN__ID2 more))
248 /* --- Macro: @DYNITER@ --- *
250 * Arguments: @what@ = what to do for each item -- a macro or function
251 * which is passed the address of an item
253 * Use: Does something for each item.
256 #define DYNITER DYN__ITER ,
257 #define DYN__ITER(what, chunk, prefix) do { \
259 for (i = 0; i < prefix ## __size; i++) \
260 what(chunk->o + i); \
263 /* --- Macro: @DYNNOP@ --- *
270 #define DYNNOP DYN__NOP, (dummy)
271 #define DYN__NOP(dummy, chunk, prefix) /* nop */
273 /*----- That's all, folks -------------------------------------------------*/