3 * $Id: dynarray.h,v 1.4 1999/05/13 22:48:55 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.4 1999/05/13 22:48:55 mdw
34 * Change `-ise' to `-ize' throughout.
36 * Revision 1.3 1999/05/06 19:51:35 mdw
37 * Reformatted the LGPL notice a little bit.
39 * Revision 1.2 1999/05/05 18:50:31 mdw
40 * Change licensing conditions to LGPL.
42 * Revision 1.1.1.1 1998/06/17 23:44:42 mdw
43 * Initial version of mLib
54 /*----- Required header files ---------------------------------------------*/
67 /*----- Horrific hacking -------------------------------------------------*
69 * Several bits of this code need extending arrays (in particular, the array
70 * handler and the label allocator), although the sizes of the objects being
73 * This file contains (horrors!) a sort of C++ template-a-like which
74 * implements such growing arrays. Read on, if your constitution can stand
78 /* --- Macro: @DYNDECLS@ --- *
80 * Arguments: @prefix@ = prefix string which begins all external
82 * @obtype@ = the element type of the array
83 * @chunksize@ = the number of items in a chunk
85 * Use: Provides declarations suitable for use in a header file which
86 * define functions for manipulating the specific dynamic array
87 * described in the arguments.
90 #define DYNDECLS(prefix, obtype, chunksize) /* ... */ \
92 /* --- Define some constants --- */ \
95 prefix ## __mask = chunksize - 1, \
96 prefix ## __size = chunksize \
99 /* --- Type definitions --- */ \
101 typedef obtype prefix ## __object; \
103 typedef struct prefix ## _chunk { \
104 struct prefix ## _chunk *next; \
106 prefix ## __object o[prefix ## __size]; \
107 } prefix ## _chunk; \
109 /* --- External routines --- */ \
111 /* --- @PREFIX_find@ --- * \
113 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
114 * @size_t index@ = index into array which we want \
116 * Returns: Pointer to the object at appropriate index, or null \
118 * Use: Indexes an item without creating it if it's not there \
122 extern prefix ## __object *prefix ## _find(prefix ## _chunk **base, \
125 /* --- @PREFIX_new@ --- * \
127 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
128 * @size_t index@ = index into array which we want \
130 * Returns: Pointer to the object at appropriate index \
132 * Use: Indexes an item, creating it if necessary. \
135 extern prefix ## __object *prefix ## _new(prefix ## _chunk **base, \
138 /* --- @PREFIX_free@ --- * \
140 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
144 * Use: Releases all the memory directly attached to an array. \
147 extern void prefix ## _free(prefix ## _chunk **base);
149 /* --- Macro: @DYNARRAY@ --- *
151 * Arguments: @prefix@ = prefix string for uniquification
152 * @init@ = how to initialize a chunk
153 * @kill@ = how to free a chunk
155 * Use: Builds template routines for dynamically growing arrays.
156 * The two arguments @init@ and @kill@ must use the macros
160 #define DYNARRAY(prefix, init, kill) /* ... */ \
162 /* --- @PREFIX_find@ --- * \
164 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
165 * @size_t index@ = index into array which we want \
167 * Returns: Pointer to the object at appropriate index, or null \
169 * Use: Indexes an item without creating it if it's not there \
173 prefix ## __object *prefix ## _find(prefix ## _chunk **base, \
176 size_t chunkid = index & ~prefix ## __mask; \
177 prefix ## _chunk *p = *base; \
178 index &= prefix ## __mask; \
181 if (!p || p->base > chunkid) \
183 if (p->base == chunkid) \
188 return (p->o + index); \
191 /* --- @PREFIX_new@ --- * \
193 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
194 * @size_t index@ = index into array which we want \
196 * Returns: Pointer to the object at appropriate index \
198 * Use: Indexes an item, creating it if necessary. \
201 prefix ## __object *prefix ## _new(prefix ## _chunk **base, \
204 size_t chunkid = index & ~prefix ## __mask; \
205 prefix ## _chunk *p = (prefix ## _chunk *)base; \
206 index &= prefix ## __mask; \
208 while (p->next && p->next->base < chunkid) \
211 if (!p->next || p->next->base != chunkid) { \
212 prefix ## _chunk *q = CREATE(prefix ## _chunk); \
217 DYN__GRABARGS(init, (q, prefix)); \
220 return (p->next->o + index); \
223 /* --- @PREFIX_free@ --- * \
225 * Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
229 * Use: Releases all the memory directly attached to an array. \
232 void prefix ## _free(prefix ## _chunk **base) \
234 prefix ## _chunk *p = *base, *q; \
237 DYN__GRABARGS(kill, (p, prefix)); \
246 /* --- A vile bit of hacking --- *
248 * All of this yukkiness is a perfectly legitimate consequence of the (daft)
249 * rules about when macro arguments get expanded.
253 #define DYN__ID2(x, y) x, y
254 #define DYN__CONTORT(mac, args) mac args
255 #define DYN__GRABARGS(mac, args, more) \
256 DYN__CONTORT(mac, (DYN__ID args, DYN__ID2 more))
258 /* --- Macro: @DYNITER@ --- *
260 * Arguments: @what@ = what to do for each item -- a macro or function
261 * which is passed the address of an item
263 * Use: Does something for each item.
266 #define DYNITER DYN__ITER ,
267 #define DYN__ITER(what, chunk, prefix) do { \
269 for (i = 0; i < prefix ## __size; i++) \
270 what(chunk->o + i); \
273 /* --- Macro: @DYNNOP@ --- *
280 #define DYNNOP DYN__NOP, (dummy)
281 #define DYN__NOP(dummy, chunk, prefix) /* nop */
283 /*----- That's all, folks -------------------------------------------------*/