cde/osf/uil/UilSymNam.c

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