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

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