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

   1 /* -*-c-*-
   2  *
   3  * $Id: dynarray.h,v 1.2 1999/05/05 18:50:31 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 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  *
  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 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.
  27  */
  28
  29 /*----- Revision history --------------------------------------------------*
  30  *
  31  * $Log: dynarray.h,v $
  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
  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