contrib/flex/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 PROTO ((register char[], char *, int, hash_table, int));
  63 static struct hash_entry *findsym PROTO ((register const char *sym,
  64                                           hash_table table,
  65
  66                                           int table_size));
  67 static int hashfunct PROTO ((register const char *, int));
  68
  69
  70 /* addsym - add symbol and definitions to symbol table
  71  *
  72  * -1 is returned if the symbol already exists, and the change not made.
  73  */
  74
  75 static int addsym (sym, str_def, int_def, table, table_size)
  76      register char sym[];
  77      char   *str_def;
  78      int     int_def;
  79      hash_table table;
  80      int     table_size;
  81 {
  82         int     hash_val = hashfunct (sym, table_size);
  83         register struct hash_entry *sym_entry = table[hash_val];
  84         register struct hash_entry *new_entry;
  85         register struct hash_entry *successor;
  86
  87         while (sym_entry) {
  88                 if (!strcmp (sym, sym_entry->name)) {   /* entry already exists */
  89                         return -1;
  90                 }
  91
  92                 sym_entry = sym_entry->next;
  93         }
  94
  95         /* create new entry */
  96         new_entry = (struct hash_entry *)
  97                 flex_alloc (sizeof (struct hash_entry));
  98
  99         if (new_entry == NULL)
 100                 flexfatal (_("symbol table memory allocation failed"));
 101
 102         if ((successor = table[hash_val]) != 0) {
 103                 new_entry->next = successor;
 104                 successor->prev = new_entry;
 105         }
 106         else
 107                 new_entry->next = NULL;
 108
 109         new_entry->prev = NULL;
 110         new_entry->name = sym;
 111         new_entry->str_val = str_def;
 112         new_entry->int_val = int_def;
 113
 114         table[hash_val] = new_entry;
 115
 116         return 0;
 117 }
 118
 119
 120 /* cclinstal - save the text of a character class */
 121
 122 void    cclinstal (ccltxt, cclnum)
 123      Char    ccltxt[];
 124      int     cclnum;
 125 {
 126         /* We don't bother checking the return status because we are not
 127          * called unless the symbol is new.
 128          */
 129
 130         (void) addsym ((char *) copy_unsigned_string (ccltxt),
 131                        (char *) 0, cclnum, ccltab, CCL_HASH_SIZE);
 132 }
 133
 134
 135 /* ccllookup - lookup the number associated with character class text
 136  *
 137  * Returns 0 if there's no CCL associated with the text.
 138  */
 139
 140 int     ccllookup (ccltxt)
 141      Char    ccltxt[];
 142 {
 143         return findsym ((char *) ccltxt, ccltab, CCL_HASH_SIZE)->int_val;
 144 }
 145
 146
 147 /* findsym - find symbol in symbol table */
 148
 149 static struct hash_entry *findsym (sym, table, table_size)
 150      register const char *sym;
 151      hash_table table;
 152      int     table_size;
 153 {
 154         static struct hash_entry empty_entry = {
 155                 (struct hash_entry *) 0, (struct hash_entry *) 0,
 156                 (char *) 0, (char *) 0, 0,
 157         };
 158         register struct hash_entry *sym_entry =
 159
 160                 table[hashfunct (sym, table_size)];
 161
 162         while (sym_entry) {
 163                 if (!strcmp (sym, sym_entry->name))
 164                         return sym_entry;
 165                 sym_entry = sym_entry->next;
 166         }
 167
 168         return &empty_entry;
 169 }
 170
 171 /* hashfunct - compute the hash value for "str" and hash size "hash_size" */
 172
 173 static int hashfunct (str, hash_size)
 174      register const char *str;
 175      int     hash_size;
 176 {
 177         register int hashval;
 178         register int locstr;
 179
 180         hashval = 0;
 181         locstr = 0;
 182
 183         while (str[locstr]) {
 184                 hashval = (hashval << 1) + (unsigned char) str[locstr++];
 185                 hashval %= hash_size;
 186         }
 187
 188         return hashval;
 189 }
 190
 191
 192 /* ndinstal - install a name definition */
 193
 194 void    ndinstal (name, definition)
 195      const char *name;
 196      Char    definition[];
 197 {
 198
 199         if (addsym (copy_string (name),
 200                     (char *) copy_unsigned_string (definition), 0,
 201                     ndtbl, NAME_TABLE_HASH_SIZE))
 202                         synerr (_("name defined twice"));
 203 }
 204
 205
 206 /* ndlookup - lookup a name definition
 207  *
 208  * Returns a nil pointer if the name definition does not exist.
 209  */
 210
 211 Char   *ndlookup (nd)
 212      const char *nd;
 213 {
 214         return (Char *) findsym (nd, ndtbl, NAME_TABLE_HASH_SIZE)->str_val;
 215 }
 216
 217
 218 /* scextend - increase the maximum number of start conditions */
 219
 220 void    scextend ()
 221 {
 222         current_max_scs += MAX_SCS_INCREMENT;
 223
 224         ++num_reallocs;
 225
 226         scset = reallocate_integer_array (scset, current_max_scs);
 227         scbol = reallocate_integer_array (scbol, current_max_scs);
 228         scxclu = reallocate_integer_array (scxclu, current_max_scs);
 229         sceof = reallocate_integer_array (sceof, current_max_scs);
 230         scname = reallocate_char_ptr_array (scname, current_max_scs);
 231 }
 232
 233
 234 /* scinstal - make a start condition
 235  *
 236  * NOTE
 237  *    The start condition is "exclusive" if xcluflg is true.
 238  */
 239
 240 void    scinstal (str, xcluflg)
 241      const char *str;
 242      int     xcluflg;
 243 {
 244
 245         if (++lastsc >= current_max_scs)
 246                 scextend ();
 247
 248         scname[lastsc] = copy_string (str);
 249
 250         if (addsym (scname[lastsc], (char *) 0, lastsc,
 251                     sctbl, START_COND_HASH_SIZE))
 252                         format_pinpoint_message (_
 253                                                  ("start condition %s declared twice"),
 254 str);
 255
 256         scset[lastsc] = mkstate (SYM_EPSILON);
 257         scbol[lastsc] = mkstate (SYM_EPSILON);
 258         scxclu[lastsc] = xcluflg;
 259         sceof[lastsc] = false;
 260 }
 261
 262
 263 /* sclookup - lookup the number associated with a start condition
 264  *
 265  * Returns 0 if no such start condition.
 266  */
 267
 268 int     sclookup (str)
 269      const char *str;
 270 {
 271         return findsym (str, sctbl, START_COND_HASH_SIZE)->int_val;
 272 }