cde/osf/uil/UilSymNam.c

   1 /*
   2  *  @OSF_COPYRIGHT@
   3  *  COPYRIGHT NOTICE
   4  *  Copyright (c) 1990, 1991, 1992, 1993 Open Software Foundation, Inc.
   5  *  ALL RIGHTS RESERVED (MOTIF). See the file named COPYRIGHT.MOTIF for
   6  *  the full copyright text.
   7 */
   8 /*
   9  * HISTORY
  10 */
  11 #ifdef REV_INFO
  12 #ifndef lint
  13 static char rcsid[] = "$TOG: UilSymNam.c /main/13 1997/09/08 11:12:50 cshi $"
  14 #endif
  15 #endif
  16
  17 /*
  18 *  (c) Copyright 1989, 1990, DIGITAL EQUIPMENT CORPORATION, MAYNARD, MASS. */
  19
  20 /*
  21 **++
  22 **  FACILITY:
  23 **
  24 **      User Interface Language Compiler (UIL)
  25 **
  26 **  ABSTRACT:
  27 **
  28 **      This module inserts names into the name table.
  29 **
  30 **--
  31 **/
  32
  33
  34 /*
  35 **
  36 **  INCLUDE FILES
  37 **
  38 **/
  39
  40 #include "UilDefI.h"
  41
  42 /*
  43 **
  44 **  DEFINE and MACRO DEFINITIONS
  45 **
  46 **/
  47
  48
  49 /*
  50 **
  51 **  EXTERNAL VARIABLE DECLARATIONS
  52 **
  53 **/
  54
  55
  56
  57 /*
  58 **
  59 **  GLOBAL VARIABLE DECLARATIONS
  60 **
  61 **/
  62
  63
  64
  65 /*
  66 **
  67 **  OWN VARIABLE DECLARATIONS
  68 **
  69 **/
  70
  71
  72 \f
  73 /*
  74 **++
  75 **  FUNCTIONAL DESCRIPTION:
  76 **
  77 **  This routine searches for a name entry of the same name as its parameters.
  78 **  If the entry is found, a pointer to that name node is
  79 **  returned as the value of the function.  If no entry is found, a NULL
  80 **  pointer is returned.
  81 **
  82 **  See sym_insert_name for a description of the name lookup alorithm.
  83 **
  84 **  FORMAL PARAMETERS:
  85 **
  86 **      l_length            length of the name not including the null
  87 **      c_text              pointer to a null terminated string for name
  88 **
  89 **  IMPLICIT INPUTS:
  90 **
  91 **      sym_az_hash_table   the hash table
  92 **
  93 **  IMPLICIT OUTPUTS:
  94 **
  95 **      sym_az_hash_table   may be updated with an additional name
  96 **
  97 **  FUNCTION VALUE:
  98 **
  99 **      a pointer to a name entry
 100 **
 101 **  SIDE EFFECTS:
 102 **
 103 **      none
 104 **
 105 **--
 106 **/
 107
 108 sym_name_entry_type
 109     *sym_find_name(l_length, c_text)
 110
 111 int     l_length;       /* length of name to find */
 112 char    *c_text;        /* text of the name */
 113
 114 {
 115     sym_name_entry_type *az_current_name;
 116     int                 l_hash_code;
 117     int                 l_compare_result;
 118
 119     /* obtain the hash code of for the name */
 120
 121     l_hash_code = hash_function( l_length, c_text );
 122
 123     /*
 124     **  chain along hash chain looking for symbol - exit loop under 3 condition
 125     **        1) come to the end of the chain: name not found
 126     **        2) find symbol: return this symbol
 127     **        3) find node > symbol: name not found
 128     */
 129
 130     for (az_current_name = sym_az_hash_table[ l_hash_code ];
 131          az_current_name != NULL;
 132          az_current_name = az_current_name->az_next_name_entry)
 133     {
 134         l_compare_result = _compare(c_text, az_current_name->c_text);
 135
 136         if (l_compare_result == 0)      /* c_text = current name */
 137         {
 138             /* found the name we are looking for */
 139
 140             return az_current_name;
 141         }
 142
 143         if (l_compare_result > 0)       /* c_text > current name */
 144         {
 145             /* return NULL - name should be before this spot in list */
 146
 147             return NULL;
 148         }
 149
 150     }
 151
 152     /* came to end of the list without finding the name */
 153
 154     return NULL;
 155 }
 156
 157 \f
 158 /*
 159 **++
 160 **  FUNCTIONAL DESCRIPTION:
 161 **
 162 **  This routine searches for a name entry of the same name as its parameters.
 163 **  If the entry is found, a pointer to that name node is
 164 **  returned as the value of the function.  If no entry is found, one is
 165 **  inserted.  In this case the value of the function is a pointer to
 166 **  the name entry created.
 167 **
 168 **  Name entries are linked off of a hash table.  Those
 169 **  entries that have the same hash code, are sorted according to the
 170 **  collating sequence.  Thus the algorithm involves hashing the symbol and
 171 **  then following the chain for that hash code until one of the following
 172 **  conditions is met.  1) the identifier is found, then return a pointer
 173 **  to that name entry.  2) come to the end of the chain or a name
 174 **  entry that comes later in the collating sequence than the symbol being
 175 **  searched for.  In this case the name is inserted just prior to this
 176 **  point in the chain.
 177 **
 178 **  FORMAL PARAMETERS:
 179 **
 180 **      l_length            length of the name not including the null
 181 **      c_text              pointer to a null terminated string for name
 182 **
 183 **  IMPLICIT INPUTS:
 184 **
 185 **      sym_az_hash_table   the hash table
 186 **
 187 **  IMPLICIT OUTPUTS:
 188 **
 189 **      sym_az_hash_table   may be updated with an additional name
 190 **
 191 **  FUNCTION VALUE:
 192 **
 193 **      a pointer to a name entry
 194 **
 195 **  SIDE EFFECTS:
 196 **
 197 **      may create a name entry and update the hash table
 198 **
 199 **--
 200 **/
 201
 202 sym_name_entry_type *sym_insert_name(l_length, c_text)
 203
 204 int     l_length;       /* length of name to insert */
 205 char    *c_text;        /* text of the name */
 206
 207 {
 208     sym_name_entry_type *az_previous_name;
 209     sym_name_entry_type *az_current_name;
 210     sym_name_entry_type *az_new_name;
 211     int                 l_hash_code;
 212     int                 l_compare_result;
 213
 214     /*
 215     **  algorithm keeps 2 pointers, one for the previous name and one
 216     **  for the current name.  This permits easy insertion of a new name
 217     */
 218
 219
 220     /* obtain the hash code of for the name */
 221
 222     l_hash_code = hash_function( l_length, c_text );
 223
 224     /*
 225     **  chain along hash chain looking for symbol - exit loop under 3 condition
 226     **        1) come to the end of the chain: insert new node on end
 227     **        2) find symbol: return this symbol
 228     **        3) find node > symbol: insert new node prior to current node
 229     */
 230
 231     for (az_current_name = sym_az_hash_table[ l_hash_code ],
 232          az_previous_name = NULL;
 233
 234          az_current_name != NULL;
 235
 236          az_previous_name = az_current_name,
 237          az_current_name = az_current_name->az_next_name_entry)
 238     {
 239         l_compare_result = _compare(c_text, az_current_name->c_text);
 240
 241         if (l_compare_result == 0)      /* c_text = current name */
 242         {
 243             /* found the name we are looking for */
 244
 245             return az_current_name;
 246         }
 247
 248         if (l_compare_result > 0)       /* c_text > current name */
 249         {
 250             /* exit the loop to insert just prior to current name */
 251
 252             goto insert_name;
 253         }
 254
 255     }
 256
 257 insert_name:
 258
 259     /*
 260     **  name is not in the table so it must be inserted between the
 261     **  az_previous_name and az_current_name entries.
 262     */
 263
 264     /* allocate and initialize the name entry */
 265
 266     az_new_name = (sym_name_entry_type *)
 267         sem_allocate_node (sym_k_name_entry,
 268                            sym_k_name_entry_size + l_length + 1);
 269
 270     az_new_name->header.b_type = l_length;      /* b_type holds length */
 271     az_new_name->az_object = NULL;
 272     az_new_name->az_cycle_id = 0;
 273
 274     _move( az_new_name->c_text, c_text, l_length+1 );
 275
 276     /*
 277     **  link the name entry into the hash table
 278     */
 279
 280     az_new_name->az_next_name_entry = az_current_name;
 281
 282     if (az_previous_name == NULL)
 283         sym_az_hash_table[ l_hash_code ] = az_new_name;
 284     else
 285         az_previous_name->az_next_name_entry =
 286                         (sym_name_entry_type *) az_new_name;
 287
 288     return az_new_name;
 289 }
 290
 291 \f
 292 /*
 293 **++
 294 **  FUNCTIONAL DESCRIPTION:
 295 **
 296 **      This procedure is a hashing function.  It takes a length and a
 297 **      pointer to a value.  Using this value as a string, the function
 298 **      returns an integer in the range of 0 to sym_k_hash_table_limit-1.
 299 **
 300 **  FORMAL PARAMETERS:
 301 **
 302 **      l_length            length of the value in bytes not including null
 303 **      c_value             a null terminated string
 304 **
 305 **  IMPLICIT INPUTS:
 306 **
 307 **      sym_k_hash_table_limit
 308 **
 309 **  IMPLICIT OUTPUTS:
 310 **
 311 **      none
 312 **
 313 **  FUNCTION VALUE:
 314 **
 315 **      integer (the hash code) in range 0 to sym_k_hash_table_limit-1
 316 **
 317 **  SIDE EFFECTS:
 318 **
 319 **      none
 320 **
 321 **--
 322 **/
 323
 324 int     hash_function(l_length, c_value)
 325
 326 int     l_length;
 327 char    *c_value;
 328 {
 329 #ifdef WORD64
 330 #define _shift 3
 331     static unsigned int XmConst    mask[ 8 ] =
 332                 { 0x00000000000000FF, 0x000000000000FFFF,
 333                   0x0000000000FFFFFF, 0x00000000FFFFFFFF,
 334                   0x00000000FFFFFFFF, 0x0000FFFFFFFFFFFF,
 335                   0x00FFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, };
 336 #elif defined (LONG64)
 337     #define _shift 3
 338     static long XmConst    mask[ 8 ] =
 339                 { 0x00000000000000FF, 0x000000000000FFFF,
 340                   0x0000000000FFFFFF, 0x00000000FFFFFFFF,
 341                   0x00000000FFFFFFFF, 0x0000FFFFFFFFFFFF,
 342                   0x00FFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, };
 343 #else
 344 #define _shift 2
 345     static unsigned int XmConst mask[ 4 ] =
 346                 { 0x000000FF, 0x0000FFFF, 0x00FFFFFF, 0xFFFFFFFF };
 347 #endif
 348
 349 #ifdef LONG64
 350     long                l_hash_code;
 351     long                al_value[20];
 352 #else
 353     int                 l_hash_code;
 354     int                 al_value[20];
 355 #endif
 356     int                 l_limit;
 357     int                 l_extra;
 358     int                 i;
 359
 360     l_limit = (l_length-1) >> _shift;   /* divide by wordsize */
 361     l_extra = (l_length-1) & _slm;      /* remainder from divide by wordsize */
 362
 363 #ifdef LONG64
 364     bzero((char *)al_value, sizeof(long) * 20);
 365 #else
 366     bzero((char *)al_value, sizeof(int) * 20);
 367 #endif
 368     strncpy((char *)al_value, c_value, l_length);
 369     l_hash_code = 0;
 370
 371     for (i = 0; i < l_limit; i++)
 372     {
 373         l_hash_code = l_hash_code ^ al_value[ i ];
 374     }
 375
 376     l_hash_code = l_hash_code ^ (al_value[ i ] & mask[ l_extra ]);
 377
 378     return (int)(l_hash_code % sym_k_hash_table_limit);
 379 }
 380
 381 \f
 382 #if debug_version
 383
 384 /*
 385 **++
 386 **  FUNCTIONAL DESCRIPTION:
 387 **
 388 **      This debugging routine will dump out the name entries linked
 389 **      from the hash table.
 390 **
 391 **  FORMAL PARAMETERS:
 392 **
 393 **      none
 394 **
 395 **  IMPLICIT INPUTS:
 396 **
 397 **      sym_az_hash_table
 398 **
 399 **  IMPLICIT OUTPUTS:
 400 **
 401 **      none
 402 **
 403 **  FUNCTION VALUE:
 404 **
 405 **      void
 406 **
 407 **  SIDE EFFECTS:
 408 **
 409 **      prints out the hash table
 410 **
 411 **--
 412 **/
 413
 414 void    sym_dump_hash_table()
 415 {
 416     int         i;
 417     int         total_count;
 418     int         max_length;
 419     int         empty_count;
 420
 421     total_count = 0;
 422     empty_count = 0;
 423     max_length = 0;
 424
 425     for (i=0;  i<sym_k_hash_table_limit;  i++)
 426     {
 427         int                 bucket_count;
 428         sym_name_entry_type  *az_name;
 429
 430         bucket_count = 0;
 431
 432         for (az_name = sym_az_hash_table[ i ];
 433              az_name != NULL;
 434              az_name = az_name->az_next_name_entry)
 435         {
 436             bucket_count++;
 437
 438             _debug_output("\t %s \n", az_name->c_text);
 439         }
 440
 441         total_count += bucket_count;
 442         if (bucket_count == 0)
 443             empty_count++;
 444         max_length = ( max_length > bucket_count )? max_length : bucket_count;
 445
 446         _debug_output("bucket: %d length: %d\n", i, bucket_count);
 447     }
 448
 449     _debug_output("name count: %d \n empty count: %d \n max length: %d",
 450                    total_count, empty_count, max_length );
 451 }
 452 #endif