New functions `dstr_putf' and `dstr_vputf' which do `printf'-style

[mLib] / dynarray.h

/* -*-c-*-
 *
 * $Id: dynarray.h,v 1.1 1998/06/17 23:44:42 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 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 General Public License for more details.
 *
 * You should have received a copy of the GNU 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.1  1998/06/17 23:44:42  mdw
 * Initial revision
 *
 */

#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