chiark - git - mdw - mLib/blob - struct/sym.h

   1 /* -*-c-*-
   2  *
   3  * Symbol table management
   4  *
   5  * (c) 1998 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of the mLib utilities library.
  11  *
  12  * mLib is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * mLib is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with mLib; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 #ifndef MLIB_SYM_H
  29 #define MLIB_SYM_H
  30
  31 #ifdef __cplusplus
  32   extern "C" {
  33 #endif
  34
  35 /*----- Required headers --------------------------------------------------*/
  36
  37 #include <stddef.h>
  38
  39 #ifndef MLIB_BITS_H
  40 #  include "bits.h"
  41 #endif
  42
  43 #ifndef MLIB_HASH_H
  44 #  include "hash.h"
  45 #endif
  46
  47 #ifndef MLIB_SUB_H
  48 #  include "sub.h"
  49 #endif
  50
  51 /*----- Tuning parameters -------------------------------------------------*/
  52
  53 /* --- Initial hash table size --- *
  54  *
  55  * This is the initial @mask@ value.  It must be of the form %$2^n - 1$%,
  56  * so that it can be used to mask of the bottom bits of a hash value.
  57  */
  58
  59 #define SYM_INITSZ 32                   /* Size of a new hash table */
  60
  61 /* --- Maximum load factor --- *
  62  *
  63  * This parameter controls how much the table has to be loaded before the
  64  * table is extended.  The number of elements %$n$%, the number of bins %$b$%
  65  * and the limit %$l$% satisfy the relation %$n < bl$%; if a new item is
  66  * added to the table and this relation is found to be false, the table is
  67  * doubled in size.
  68  */
  69
  70 #define SYM_LIMIT(n) ((n) * 2)          /* Load factor for growing table */
  71
  72 /*----- Type definitions --------------------------------------------------*/
  73
  74 /* --- Symbol table --- *
  75  *
  76  * A @sym_table@ contains the information needed to manage a symbol table.
  77  * Users shouldn't fiddle with this information directly, but it needs to be
  78  * here so that objects of the correct type can be created.
  79  */
  80
  81 typedef struct sym_table {
  82   hash_table t;
  83   subarena *s;
  84   size_t load;
  85 } sym_table;
  86
  87 /* --- A symbol table entry --- *
  88  *
  89  * I don't care what actually gets stored in symbol entries because I don't
  90  * create them: that's the responsibility of my client.  All I care about
  91  * here is that whatever gets passed to me is a structure whose first member
  92  * is a @sym_base@.  The ANSI guarantees about structure layout are
  93  * sufficient to allow me to manipulate such objects.
  94  */
  95
  96 typedef struct sym_base {
  97   hash_base b;                          /* Base structure */
  98   char *name;                           /* Pointer to name string */
  99   size_t len;                           /* Length of the symbol's name */
 100 } sym_base;
 101
 102 /* --- Macros for picking out useful information --- *
 103  *
 104  * Note that @SYM_LEN@ returns the size of the symbol key.  For textual keys,
 105  * this will include the terminating null.
 106  */
 107
 108 #define SYM_NAME(sy) ((const char *)(((sym_base *)(sy))->name))
 109 #define SYM_LEN(sy) (((sym_base *)(sy))->len + 0)
 110 #define SYM_HASH(sy) (((sym_base *)(sy))->b.hash + 0)
 111
 112 /* --- An iterator block --- */
 113
 114 typedef struct { hash_iter i; } sym_iter;
 115
 116 /*----- External functions ------------------------------------------------*/
 117
 118 /* --- @sym_create@ --- *
 119  *
 120  * Arguments:   @sym_table *t@ = symbol table to initialize
 121  *
 122  * Returns:     ---
 123  *
 124  * Use:         Initializes the given symbol table.  Raises @EXC_NOMEM@ if
 125  *              there isn't enough memory.
 126  */
 127
 128 extern void sym_create(sym_table */*t*/);
 129
 130 /* --- @sym_destroy@ --- *
 131  *
 132  * Arguments:   @sym_table *t@ = pointer to symbol table in question
 133  *
 134  * Returns:     ---
 135  *
 136  * Use:         Destroys a symbol table, freeing all the memory it used to
 137  *              occupy.
 138  */
 139
 140 extern void sym_destroy(sym_table */*t*/);
 141
 142 /* --- @sym_find@ --- *
 143  *
 144  * Arguments:   @sym_table *t@ = pointer to symbol table in question
 145  *              @const char *n@ = pointer to symbol name to look up
 146  *              @long l@ = length of the name string or negative to measure
 147  *              @size_t sz@ = size of desired symbol object, or zero
 148  *              @unsigned *f@ = pointer to a flag, or null.
 149  *
 150  * Returns:     The address of a @sym_base@ structure, or null if not found
 151  *              and @sz@ is zero.
 152  *
 153  * Use:         Looks up a symbol in a given symbol table.  The name is
 154  *              passed by the address of its first character.  The length
 155  *              may be given, in which case the name may contain arbitrary
 156  *              binary data, or it may be given as a negative number, in
 157  *              which case the length of the name is calculated as
 158  *              @strlen(n) + 1@.
 159  *
 160  *              The return value is the address of a pointer to a @sym_base@
 161  *              block (which may have other things on the end, as above).  If
 162  *              the symbol could be found, the return value points to the
 163  *              symbol block.  If the symbol wasn't there, then if @sz@ is
 164  *              nonzero, a new symbol is created and its address is returned;
 165  *              otherwise a null pointer is returned.  The exception
 166  *              @EXC_NOMEM@ is raised if the block can't be allocated.
 167  *
 168  *              The value of @*f@ indicates whether a new symbol entry was
 169  *              created: a nonzero value indicates that an old value was
 170  *              found.
 171  */
 172
 173 extern void *sym_find(sym_table */*t*/, const char */*n*/, long /*l*/,
 174                       size_t /*sz*/, unsigned */*f*/);
 175
 176 /* --- @sym_remove@ --- *
 177  *
 178  * Arguments:   @sym_table *t@ = pointer to a symbol table object
 179  *              @void *b@ = pointer to symbol table entry
 180  *
 181  * Returns:     ---
 182  *
 183  * Use:         Removes the object from the symbol table.  The space occupied
 184  *              by the object and its name is freed; anything else attached
 185  *              to the entry should already be gone by this point.
 186  */
 187
 188 extern void sym_remove(sym_table */*t*/, void */*b*/);
 189
 190 /* --- @sym_mkiter@ --- *
 191  *
 192  * Arguments:   @sym_iter *i@ = pointer to an iterator object
 193  *              @sym_table *t@ = pointer to a symbol table object
 194  *
 195  * Returns:     ---
 196  *
 197  * Use:         Creates a new symbol table iterator which may be used to
 198  *              iterate through a symbol table.
 199  */
 200
 201 #define SYM_MKITER(i_, t_) HASH_MKITER(&(i_)->i, &(t_)->t)
 202
 203 extern void sym_mkiter(sym_iter */*i*/, sym_table */*t*/);
 204
 205 /* --- @sym_next@ --- *
 206  *
 207  * Arguments:   @sym_iter *i@ = pointer to iterator object
 208  *
 209  * Returns:     Pointer to the next symbol found, or null when finished.
 210  *
 211  * Use:         Returns the next symbol from the table.  Symbols are not
 212  *              returned in any particular order.
 213  */
 214
 215 #define SYM_NEXT(i_, p) do {                                            \
 216   hash_base *_q;                                                        \
 217   HASH_NEXT(&(i_)->i, _q);                                              \
 218   (p) = (void *)_q;                                                     \
 219 } while (0)
 220
 221 extern void *sym_next(sym_iter */*i*/);
 222
 223 /*----- That's all, folks -------------------------------------------------*/
 224
 225 #ifdef __cplusplus
 226   }
 227 #endif
 228
 229 #endif