[mLib] / dynarray.h

/* -*-c-*-
 *
 * $Id: dynarray.h,v 1.3 1999/05/06 19:51:35 mdw Exp $
 *
 * Dynamic arrays implementation
 *
 * (c) 1998 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of the mLib utilities library.
 *
 * mLib is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * mLib is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with mLib; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------*
 *
 * $Log: dynarray.h,v $
 * Revision 1.3  1999/05/06 19:51:35  mdw
 * Reformatted the LGPL notice a little bit.
 *
 * Revision 1.2  1999/05/05 18:50:31  mdw
 * Change licensing conditions to LGPL.
 *
 * Revision 1.1.1.1  1998/06/17 23:44:42  mdw
 * Initial version of mLib
 *
 */

#ifndef DYNARRAY_H
#define DYNARRAY_H

#ifdef __cplusplus
  extern "C" {
#endif

/*----- Required header files ---------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>

#ifndef SUB_H
#  include "sub.h"
#endif

#ifndef TRACK_H
#  include "track.h"
#endif

/*----- Horrific hacking -------------------------------------------------*
 *
 * Several bits of this code need extending arrays (in particular, the array
 * handler and the label allocator), although the sizes of the objects being
 * arrayed differs.
 *
 * This file contains (horrors!) a sort of C++ template-a-like which
 * implements such growing arrays.  Read on, if your constitution can stand
 * it...
 */

/* --- Macro: @DYNDECLS@ --- *
 *
 * Arguments:	@prefix@ = prefix string which begins all external
 *			identifiers
 *		@obtype@ = the element type of the array
 *		@chunksize@ = the number of items in a chunk
 *
 * Use:		Provides declarations suitable for use in a header file which
 *		define functions for manipulating the specific dynamic array
 *		described in the arguments.
 */

#define DYNDECLS(prefix, obtype, chunksize) /* ... */			\
									\
/* --- Define some constants --- */					\
									\
enum {									\
  prefix ## __mask = chunksize - 1, 					\
  prefix ## __size = chunksize						\
};									\
									\
/* --- Type definitions --- */						\
									\
typedef obtype prefix ## __object;					\
									\
typedef struct prefix ## _chunk {					\
  struct prefix ## _chunk *next;					\
  size_t base;								\
  prefix ## __object o[prefix ## __size];				\
} prefix ## _chunk;							\
									\
/* --- External routines --- */						\
									\
/* --- @PREFIX_find@ --- *						\
 *									\
 * Arguments:	@PREFIX_chunk **base@ = anchor address of chunk list	\
 *		@size_t index@ = index into array which we want		\
 *									\
 * Returns:	Pointer to the object at appropriate index, or null	\
 *									\
 * Use:		Indexes an item without creating it if it's not there	\
 *		already.						\
 */									\
									\
extern prefix ## __object *prefix ## _find(prefix ## _chunk **base,	\
					   size_t index);		\
									\
/* --- @PREFIX_new@ --- *						\
 *									\
 * Arguments:	@PREFIX_chunk **base@ = anchor address of chunk list	\
 *		@size_t index@ = index into array which we want		\
 *									\
 * Returns:	Pointer to the object at appropriate index		\
 *									\
 * Use:		Indexes an item, creating it if necessary.		\
 */									\
									\
extern prefix ## __object *prefix ## _new(prefix ## _chunk **base,	\
					  size_t index);		\
									\
/* --- @PREFIX_free@ --- *						\
 *									\
 * Arguments:	@PREFIX_chunk **base@ = anchor address of chunk list	\
 *									\
 * Returns:	---							\
 *									\
 * Use:		Releases all the memory directly attached to an array.	\
 */									\
									\
extern void prefix ## _free(prefix ## _chunk **base);

/* --- Macro: @DYNARRAY@ --- *
 *
 * Arguments:	@prefix@ = prefix string for uniquification
 *		@init@ = how to initialise a chunk
 *		@kill@ = how to free a chunk
 *
 * Use:		Builds template routines for dynamically growing arrays.
 *		The two arguments @init@ and @kill@ must use the macros
 *		described below.
 */

#define DYNARRAY(prefix, init, kill) /* ... */				\
									\
/* --- @PREFIX_find@ --- *						\
 *									\
 * Arguments:	@PREFIX_chunk **base@ = anchor address of chunk list	\
 *		@size_t index@ = index into array which we want		\
 *									\
 * Returns:	Pointer to the object at appropriate index, or null	\
 *									\
 * Use:		Indexes an item without creating it if it's not there	\
 *		already.						\
 */									\
									\
prefix ## __object *prefix ## _find(prefix ## _chunk **base,		\
				    size_t index)			\
{									\
  size_t chunkid = index & ~prefix ## __mask;				\
  prefix ## _chunk *p = *base;						\
  index &= prefix ## __mask;						\
									\
  for (;;) {								\
    if (!p || p->base > chunkid)					\
      return (0);							\
    if (p->base == chunkid)						\
      break;								\
    p = p->next;							\
  }									\
									\
  return (p->o + index);						\
}									\
									\
/* --- @PREFIX_new@ --- *						\
 *									\
 * Arguments:	@PREFIX_chunk **base@ = anchor address of chunk list	\
 *		@size_t index@ = index into array which we want		\
 *									\
 * Returns:	Pointer to the object at appropriate index		\
 *									\
 * Use:		Indexes an item, creating it if necessary.		\
 */									\
									\
prefix ## __object *prefix ## _new(prefix ## _chunk **base,		\
				   size_t index)			\
{									\
  size_t chunkid = index & ~prefix ## __mask;				\
  prefix ## _chunk *p = (prefix ## _chunk *)base;			\
  index &= prefix ## __mask;						\
									\
  while (p->next && p->next->base < chunkid)				\
    p = p->next;							\
									\
  if (!p->next || p->next->base != chunkid) {				\
    prefix ## _chunk *q = CREATE(prefix ## _chunk);			\
    q->next = p->next;							\
    p->next = q;							\
    q->base = chunkid;							\
									\
    DYN__GRABARGS(init, (q, prefix));					\
  }									\
									\
  return (p->next->o + index);						\
}									\
									\
/* --- @PREFIX_free@ --- *						\
 *									\
 * Arguments:	@PREFIX_chunk **base@ = anchor address of chunk list	\
 *									\
 * Returns:	---							\
 *									\
 * Use:		Releases all the memory directly attached to an array.	\
 */									\
									\
void prefix ## _free(prefix ## _chunk **base)				\
{									\
  prefix ## _chunk *p = *base, *q;					\
									\
  while (p) {								\
    DYN__GRABARGS(kill, (p, prefix));					\
    q = p;								\
    p = p->next;							\
    DESTROY(q);								\
  }									\
									\
  *base = 0;								\
}

/* --- A vile bit of hacking --- *
 *
 * All of this yukkiness is a perfectly legitimate consequence of the (daft)
 * rules about when macro arguments get expanded.
 */

#define DYN__ID(x) x
#define DYN__ID2(x, y) x, y
#define DYN__CONTORT(mac, args) mac args
#define DYN__GRABARGS(mac, args, more)					\
    DYN__CONTORT(mac, (DYN__ID args, DYN__ID2 more))

/* --- Macro: @DYNITER@ --- *
 *
 * Arguments:	@what@ = what to do for each item -- a macro or function
 *			which is passed the address of an item
 *
 * Use:		Does something for each item.
 */

#define DYNITER DYN__ITER ,
#define DYN__ITER(what, chunk, prefix) do {				\
  int i;								\
  for (i = 0; i < prefix ## __size; i++)				\
    what(chunk->o + i);							\
} while (0)

/* --- Macro: @DYNNOP@ --- *
 *
 * Arguments:	---
 *
 * Use:		Does nothing.
 */

#define DYNNOP DYN__NOP, (dummy)
#define DYN__NOP(dummy, chunk, prefix) /* nop */

/*----- That's all, folks -------------------------------------------------*/

#ifdef __cplusplus
  }
#endif

#endif
Commit	Line	Data
0875b58f	1	/* --c--
0875b58f	2	*
0bd98442	3	* $Id: dynarray.h,v 1.3 1999/05/06 19:51:35 mdw Exp $
0875b58f	4	*
	5	* Dynamic arrays implementation
	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: dynarray.h,v $
0bd98442	33	* Revision 1.3 1999/05/06 19:51:35 mdw
	34	* Reformatted the LGPL notice a little bit.
	35	*
c846879c	36	* Revision 1.2 1999/05/05 18:50:31 mdw
	37	* Change licensing conditions to LGPL.
	38	*
	39	* Revision 1.1.1.1 1998/06/17 23:44:42 mdw
	40	* Initial version of mLib
0875b58f	41	*
	42	*/
	43
	44	#ifndef DYNARRAY_H
	45	#define DYNARRAY_H
	46
	47	#ifdef __cplusplus
	48	extern "C" {
	49	#endif
	50
	51	/----- Required header files ---------------------------------------------/
	52
	53	#include <stdio.h>
	54	#include <stdlib.h>
	55
	56	#ifndef SUB_H
	57	# include "sub.h"
	58	#endif
	59
	60	#ifndef TRACK_H
	61	# include "track.h"
	62	#endif
	63
	64	/----- Horrific hacking -------------------------------------------------
	65	*
	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
	68	* arrayed differs.
	69	*
	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
	72	* it...
	73	*/
	74
	75	/* --- Macro: @DYNDECLS@ --- *
	76	*
	77	* Arguments: @prefix@ = prefix string which begins all external
	78	* identifiers
	79	* @obtype@ = the element type of the array
	80	* @chunksize@ = the number of items in a chunk
	81	*
	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.
	85	*/
	86
	87	#define DYNDECLS(prefix, obtype, chunksize) /* ... */ \
	88	\
	89	/* --- Define some constants --- */ \
	90	\
	91	enum { \
	92	prefix ## __mask = chunksize - 1, \
	93	prefix ## __size = chunksize \
	94	}; \
	95	\
	96	/* --- Type definitions --- */ \
	97	\
	98	typedef obtype prefix ## __object; \
	99	\
	100	typedef struct prefix ## _chunk { \
	101	struct prefix ## _chunk *next; \
	102	size_t base; \
	103	prefix ## __object o[prefix ## __size]; \
	104	} prefix ## _chunk; \
105	\
106	/* --- External routines --- */ \
107	\
108	/* --- @PREFIX_find@ --- * \
109	* \
110	* Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
111	* @size_t index@ = index into array which we want \
112	* \
113	* Returns: Pointer to the object at appropriate index, or null \
114	* \
115	* Use: Indexes an item without creating it if it's not there \
116	* already. \
117	*/ \
118	\
119	extern prefix ## __object prefix ## _find(prefix ## _chunk *base, \
120	size_t index); \
121	\
122	/* --- @PREFIX_new@ --- * \
123	* \
124	* Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
125	* @size_t index@ = index into array which we want \
126	* \
127	* Returns: Pointer to the object at appropriate index \
128	* \
129	* Use: Indexes an item, creating it if necessary. \
130	*/ \
131	\
132	extern prefix ## __object prefix ## _new(prefix ## _chunk *base, \
133	size_t index); \
134	\
135	/* --- @PREFIX_free@ --- * \
136	* \
137	* Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
138	* \
139	* Returns: --- \
140	* \
141	* Use: Releases all the memory directly attached to an array. \
142	*/ \
143	\
144	extern void prefix ## _free(prefix ## _chunk **base);
145
146	/* --- Macro: @DYNARRAY@ --- *
147	*
148	* Arguments: @prefix@ = prefix string for uniquification
149	* @init@ = how to initialise a chunk
150	* @kill@ = how to free a chunk
151	*
152	* Use: Builds template routines for dynamically growing arrays.
153	* The two arguments @init@ and @kill@ must use the macros
154	* described below.
155	*/
156
157	#define DYNARRAY(prefix, init, kill) /* ... */ \
158	\
159	/* --- @PREFIX_find@ --- * \
160	* \
161	* Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
162	* @size_t index@ = index into array which we want \
163	* \
164	* Returns: Pointer to the object at appropriate index, or null \
165	* \
166	* Use: Indexes an item without creating it if it's not there \
167	* already. \
168	*/ \
169	\
170	prefix ## __object prefix ## _find(prefix ## _chunk *base, \
171	size_t index) \
172	{ \
173	size_t chunkid = index & ~prefix ## __mask; \
174	prefix ## _chunk p = base; \
175	index &= prefix ## __mask; \
176	\
177	for (;;) { \
178	if (!p \|\| p->base > chunkid) \
179	return (0); \
180	if (p->base == chunkid) \
181	break; \
182	p = p->next; \
183	} \
184	\
185	return (p->o + index); \
186	} \
187	\
188	/* --- @PREFIX_new@ --- * \
189	* \
190	* Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
191	* @size_t index@ = index into array which we want \
192	* \
193	* Returns: Pointer to the object at appropriate index \
194	* \
195	* Use: Indexes an item, creating it if necessary. \
196	*/ \
197	\
198	prefix ## __object prefix ## _new(prefix ## _chunk *base, \
199	size_t index) \
200	{ \
201	size_t chunkid = index & ~prefix ## __mask; \
202	prefix ## _chunk p = (prefix ## _chunk )base; \
203	index &= prefix ## __mask; \
204	\
205	while (p->next && p->next->base < chunkid) \
206	p = p->next; \
207	\
208	if (!p->next \|\| p->next->base != chunkid) { \
209	prefix ## _chunk *q = CREATE(prefix ## _chunk); \
210	q->next = p->next; \
211	p->next = q; \
212	q->base = chunkid; \
213	\
214	DYN__GRABARGS(init, (q, prefix)); \
215	} \
216	\
217	return (p->next->o + index); \
218	} \
219	\
220	/* --- @PREFIX_free@ --- * \
221	* \
222	* Arguments: @PREFIX_chunk **base@ = anchor address of chunk list \
223	* \
224	* Returns: --- \
225	* \
226	* Use: Releases all the memory directly attached to an array. \
227	*/ \
228	\
229	void prefix ## _free(prefix ## _chunk **base) \
230	{ \
231	prefix ## _chunk p = base, *q; \
232	\
233	while (p) { \
234	DYN__GRABARGS(kill, (p, prefix)); \
235	q = p; \
236	p = p->next; \
237	DESTROY(q); \
238	} \
239	\
240	*base = 0; \
241	}
242
243	/* --- A vile bit of hacking --- *
244	*
245	* All of this yukkiness is a perfectly legitimate consequence of the (daft)
246	* rules about when macro arguments get expanded.
247	*/
248
249	#define DYN__ID(x) x
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))
254
255	/* --- Macro: @DYNITER@ --- *
256	*
257	* Arguments: @what@ = what to do for each item -- a macro or function
258	* which is passed the address of an item
259	*
260	* Use: Does something for each item.
261	*/
262
263	#define DYNITER DYN__ITER ,
264	#define DYN__ITER(what, chunk, prefix) do { \
265	int i; \
266	for (i = 0; i < prefix ## __size; i++) \
267	what(chunk->o + i); \
268	} while (0)
269
270	/* --- Macro: @DYNNOP@ --- *
271	*
272	* Arguments: ---
273	*
274	* Use: Does nothing.
275	*/
276
277	#define DYNNOP DYN__NOP, (dummy)
278	#define DYN__NOP(dummy, chunk, prefix) /* nop */
279
280	/----- That's all, folks -------------------------------------------------/
281
282	#ifdef __cplusplus
283	}
284	#endif
285
286	#endif