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

   1 /* -*-c-*-
   2  *
   3  * $Id: dynarray.h,v 1.4 1999/05/13 22:48:55 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.4  1999/05/13 22:48:55  mdw
  34  * Change `-ise' to `-ize' throughout.
  35  *
  36  * Revision 1.3  1999/05/06 19:51:35  mdw
  37  * Reformatted the LGPL notice a little bit.
  38  *
  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
  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
 152  *              @init@ = how to initialize a chunk
 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