contrib/flex/src/sym.c

   1 /* sym - symbol table routines */
   2
   3 /*  Copyright (c) 1990 The Regents of the University of California. */
   4 /*  All rights reserved. */
   5
   6 /*  This code is derived from software contributed to Berkeley by */
   7 /*  Vern Paxson. */
   8
   9 /*  The United States Government has rights in this work pursuant */
  10 /*  to contract no. DE-AC03-76SF00098 between the United States */
  11 /*  Department of Energy and the University of California. */
  12
  13 /*  This file is part of flex. */
  14
  15 /*  Redistribution and use in source and binary forms, with or without */
  16 /*  modification, are permitted provided that the following conditions */
  17 /*  are met: */
  18
  19 /*  1. Redistributions of source code must retain the above copyright */
  20 /*     notice, this list of conditions and the following disclaimer. */
  21 /*  2. Redistributions in binary form must reproduce the above copyright */
  22 /*     notice, this list of conditions and the following disclaimer in the */
  23 /*     documentation and/or other materials provided with the distribution. */
  24
  25 /*  Neither the name of the University nor the names of its contributors */
  26 /*  may be used to endorse or promote products derived from this software */
  27 /*  without specific prior written permission. */
  28
  29 /*  THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */
  30 /*  IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */
  31 /*  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */
  32 /*  PURPOSE. */
  33
  34 #include "flexdef.h"
  35
  36 /* Variables for symbol tables:
  37  * sctbl - start-condition symbol table
  38  * ndtbl - name-definition symbol table
  39  * ccltab - character class text symbol table
  40  */
  41
  42 struct hash_entry {
  43         struct hash_entry *prev, *next;
  44         char   *name;
  45         char   *str_val;
  46         int     int_val;
  47 };
  48
  49 typedef struct hash_entry **hash_table;
  50
  51 #define NAME_TABLE_HASH_SIZE 101
  52 #define START_COND_HASH_SIZE 101
  53 #define CCL_HASH_SIZE 101
  54
  55 static struct hash_entry *ndtbl[NAME_TABLE_HASH_SIZE];
  56 static struct hash_entry *sctbl[START_COND_HASH_SIZE];
  57 static struct hash_entry *ccltab[CCL_HASH_SIZE];
  58
  59
  60 /* declare functions that have forward references */
  61
  62 static int addsym(char[], char *, int, hash_table, int);
  63 static struct hash_entry *findsym (const char *sym, hash_table table,
  64                                    int table_size);
  65 static int hashfunct(const char *, int);
  66
  67
  68 /* addsym - add symbol and definitions to symbol table
  69  *
  70  * -1 is returned if the symbol already exists, and the change not made.
  71  */
  72
  73 static int addsym (char sym[], char *str_def, int int_def, hash_table table, int table_size)
  74 {
  75         int    hash_val = hashfunct (sym, table_size);
  76         struct hash_entry *sym_entry = table[hash_val];
  77         struct hash_entry *new_entry;
  78         struct hash_entry *successor;
  79
  80         while (sym_entry) {
  81                 if (!strcmp (sym, sym_entry->name)) {   /* entry already exists */
  82                         return -1;
  83                 }
  84
  85                 sym_entry = sym_entry->next;
  86         }
  87
  88         /* create new entry */
  89         new_entry = malloc(sizeof(struct hash_entry));
  90
  91         if (new_entry == NULL)
  92                 flexfatal (_("symbol table memory allocation failed"));
  93
  94         if ((successor = table[hash_val]) != 0) {
  95                 new_entry->next = successor;
  96                 successor->prev = new_entry;
  97         }
  98         else
  99                 new_entry->next = NULL;
 100
 101         new_entry->prev = NULL;
 102         new_entry->name = sym;
 103         new_entry->str_val = str_def;
 104         new_entry->int_val = int_def;
 105
 106         table[hash_val] = new_entry;
 107
 108         return 0;
 109 }
 110
 111
 112 /* cclinstal - save the text of a character class */
 113
 114 void    cclinstal (char ccltxt[], int cclnum)
 115 {
 116         /* We don't bother checking the return status because we are not
 117          * called unless the symbol is new.
 118          */
 119
 120         (void) addsym (xstrdup(ccltxt),
 121                        (char *) 0, cclnum, ccltab, CCL_HASH_SIZE);
 122 }
 123
 124
 125 /* ccllookup - lookup the number associated with character class text
 126  *
 127  * Returns 0 if there's no CCL associated with the text.
 128  */
 129
 130 int     ccllookup (char ccltxt[])
 131 {
 132         return findsym (ccltxt, ccltab, CCL_HASH_SIZE)->int_val;
 133 }
 134
 135
 136 /* findsym - find symbol in symbol table */
 137
 138 static struct hash_entry *findsym (const char *sym, hash_table table, int table_size)
 139 {
 140         static struct hash_entry empty_entry = {
 141                 NULL, NULL, NULL, NULL, 0,
 142         };
 143         struct hash_entry *sym_entry =
 144
 145                 table[hashfunct (sym, table_size)];
 146
 147         while (sym_entry) {
 148                 if (!strcmp (sym, sym_entry->name))
 149                         return sym_entry;
 150                 sym_entry = sym_entry->next;
 151         }
 152
 153         return &empty_entry;
 154 }
 155
 156 /* hashfunct - compute the hash value for "str" and hash size "hash_size" */
 157
 158 static int hashfunct (const char *str, int hash_size)
 159 {
 160         int hashval;
 161         int locstr;
 162
 163         hashval = 0;
 164         locstr = 0;
 165
 166         while (str[locstr]) {
 167                 hashval = (hashval << 1) + (unsigned char) str[locstr++];
 168                 hashval %= hash_size;
 169         }
 170
 171         return hashval;
 172 }
 173
 174
 175 /* ndinstal - install a name definition */
 176
 177 void    ndinstal (const char *name, char definition[])
 178 {
 179
 180         if (addsym (xstrdup(name),
 181                     xstrdup(definition), 0,
 182                     ndtbl, NAME_TABLE_HASH_SIZE))
 183                         synerr (_("name defined twice"));
 184 }
 185
 186
 187 /* ndlookup - lookup a name definition
 188  *
 189  * Returns a nil pointer if the name definition does not exist.
 190  */
 191
 192 char   *ndlookup (const char *nd)
 193 {
 194         return findsym (nd, ndtbl, NAME_TABLE_HASH_SIZE)->str_val;
 195 }
 196
 197
 198 /* scextend - increase the maximum number of start conditions */
 199
 200 void    scextend (void)
 201 {
 202         current_max_scs += MAX_SCS_INCREMENT;
 203
 204         ++num_reallocs;
 205
 206         scset = reallocate_integer_array (scset, current_max_scs);
 207         scbol = reallocate_integer_array (scbol, current_max_scs);
 208         scxclu = reallocate_integer_array (scxclu, current_max_scs);
 209         sceof = reallocate_integer_array (sceof, current_max_scs);
 210         scname = reallocate_char_ptr_array (scname, current_max_scs);
 211 }
 212
 213
 214 /* scinstal - make a start condition
 215  *
 216  * NOTE
 217  *    The start condition is "exclusive" if xcluflg is true.
 218  */
 219
 220 void    scinstal (const char *str, int xcluflg)
 221 {
 222
 223         if (++lastsc >= current_max_scs)
 224                 scextend ();
 225
 226         scname[lastsc] = xstrdup(str);
 227
 228         if (addsym(scname[lastsc], NULL, lastsc,
 229                     sctbl, START_COND_HASH_SIZE))
 230                         format_pinpoint_message (_
 231                                                  ("start condition %s declared twice"),
 232 str);
 233
 234         scset[lastsc] = mkstate (SYM_EPSILON);
 235         scbol[lastsc] = mkstate (SYM_EPSILON);
 236         scxclu[lastsc] = xcluflg;
 237         sceof[lastsc] = false;
 238 }
 239
 240
 241 /* sclookup - lookup the number associated with a start condition
 242  *
 243  * Returns 0 if no such start condition.
 244  */
 245
 246 int     sclookup (const char *str)
 247 {
 248         return findsym (str, sctbl, START_COND_HASH_SIZE)->int_val;
 249 }