chiark - git - mdw - mLib/blob - dynarray.h

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