external/bsd/flex/dist/sym.c

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