[mLib] / dynarray.h

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