[mLib] / dynarray.h

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