/* * CDE - Common Desktop Environment * * Copyright (c) 1993-2012, The Open Group. All rights reserved. * * These libraries and programs are free software; you can * redistribute them and/or modify them under the terms of the GNU * Lesser General Public License as published by the Free Software * Foundation; either version 2 of the License, or (at your option) * any later version. * * These libraries and programs are distributed in the hope that * they will be useful, but WITHOUT ANY WARRANTY; without even the * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR * PURPOSE. See the GNU Lesser General Public License for more * details. * * You should have received a copy of the GNU Lesser General Public * License along with these librararies and programs; if not, write * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth * Floor, Boston, MA 02110-1301 USA */ /* * @OSF_COPYRIGHT@ * COPYRIGHT NOTICE * Copyright (c) 1990, 1991, 1992, 1993 Open Software Foundation, Inc. * ALL RIGHTS RESERVED (MOTIF). See the file named COPYRIGHT.MOTIF for * the full copyright text. */ /* * HISTORY */ #ifdef REV_INFO #ifndef lint static char rcsid[] = "$TOG: UilSymNam.c /main/13 1997/09/08 11:12:50 cshi $" #endif #endif /* * (c) Copyright 1989, 1990, DIGITAL EQUIPMENT CORPORATION, MAYNARD, MASS. */ /* **++ ** FACILITY: ** ** User Interface Language Compiler (UIL) ** ** ABSTRACT: ** ** This module inserts names into the name table. ** **-- **/ /* ** ** INCLUDE FILES ** **/ #include "UilDefI.h" /* ** ** DEFINE and MACRO DEFINITIONS ** **/ /* ** ** EXTERNAL VARIABLE DECLARATIONS ** **/ /* ** ** GLOBAL VARIABLE DECLARATIONS ** **/ /* ** ** OWN VARIABLE DECLARATIONS ** **/ /* **++ ** FUNCTIONAL DESCRIPTION: ** ** This routine searches for a name entry of the same name as its parameters. ** If the entry is found, a pointer to that name node is ** returned as the value of the function. If no entry is found, a NULL ** pointer is returned. ** ** See sym_insert_name for a description of the name lookup alorithm. ** ** FORMAL PARAMETERS: ** ** l_length length of the name not including the null ** c_text pointer to a null terminated string for name ** ** IMPLICIT INPUTS: ** ** sym_az_hash_table the hash table ** ** IMPLICIT OUTPUTS: ** ** sym_az_hash_table may be updated with an additional name ** ** FUNCTION VALUE: ** ** a pointer to a name entry ** ** SIDE EFFECTS: ** ** none ** **-- **/ sym_name_entry_type *sym_find_name(l_length, c_text) int l_length; /* length of name to find */ char *c_text; /* text of the name */ { sym_name_entry_type *az_current_name; int l_hash_code; int l_compare_result; /* obtain the hash code of for the name */ l_hash_code = hash_function( l_length, c_text ); /* ** chain along hash chain looking for symbol - exit loop under 3 condition ** 1) come to the end of the chain: name not found ** 2) find symbol: return this symbol ** 3) find node > symbol: name not found */ for (az_current_name = sym_az_hash_table[ l_hash_code ]; az_current_name != NULL; az_current_name = az_current_name->az_next_name_entry) { l_compare_result = _compare(c_text, az_current_name->c_text); if (l_compare_result == 0) /* c_text = current name */ { /* found the name we are looking for */ return az_current_name; } if (l_compare_result > 0) /* c_text > current name */ { /* return NULL - name should be before this spot in list */ return NULL; } } /* came to end of the list without finding the name */ return NULL; } /* **++ ** FUNCTIONAL DESCRIPTION: ** ** This routine searches for a name entry of the same name as its parameters. ** If the entry is found, a pointer to that name node is ** returned as the value of the function. If no entry is found, one is ** inserted. In this case the value of the function is a pointer to ** the name entry created. ** ** Name entries are linked off of a hash table. Those ** entries that have the same hash code, are sorted according to the ** collating sequence. Thus the algorithm involves hashing the symbol and ** then following the chain for that hash code until one of the following ** conditions is met. 1) the identifier is found, then return a pointer ** to that name entry. 2) come to the end of the chain or a name ** entry that comes later in the collating sequence than the symbol being ** searched for. In this case the name is inserted just prior to this ** point in the chain. ** ** FORMAL PARAMETERS: ** ** l_length length of the name not including the null ** c_text pointer to a null terminated string for name ** ** IMPLICIT INPUTS: ** ** sym_az_hash_table the hash table ** ** IMPLICIT OUTPUTS: ** ** sym_az_hash_table may be updated with an additional name ** ** FUNCTION VALUE: ** ** a pointer to a name entry ** ** SIDE EFFECTS: ** ** may create a name entry and update the hash table ** **-- **/ sym_name_entry_type *sym_insert_name(l_length, c_text) int l_length; /* length of name to insert */ char *c_text; /* text of the name */ { sym_name_entry_type *az_previous_name; sym_name_entry_type *az_current_name; sym_name_entry_type *az_new_name; int l_hash_code; int l_compare_result; /* ** algorithm keeps 2 pointers, one for the previous name and one ** for the current name. This permits easy insertion of a new name */ /* obtain the hash code of for the name */ l_hash_code = hash_function( l_length, c_text ); /* ** chain along hash chain looking for symbol - exit loop under 3 condition ** 1) come to the end of the chain: insert new node on end ** 2) find symbol: return this symbol ** 3) find node > symbol: insert new node prior to current node */ for (az_current_name = sym_az_hash_table[ l_hash_code ], az_previous_name = NULL; az_current_name != NULL; az_previous_name = az_current_name, az_current_name = az_current_name->az_next_name_entry) { l_compare_result = _compare(c_text, az_current_name->c_text); if (l_compare_result == 0) /* c_text = current name */ { /* found the name we are looking for */ return az_current_name; } if (l_compare_result > 0) /* c_text > current name */ { /* exit the loop to insert just prior to current name */ goto insert_name; } } insert_name: /* ** name is not in the table so it must be inserted between the ** az_previous_name and az_current_name entries. */ /* allocate and initialize the name entry */ az_new_name = (sym_name_entry_type *) sem_allocate_node (sym_k_name_entry, sym_k_name_entry_size + l_length + 1); az_new_name->header.b_type = l_length; /* b_type holds length */ az_new_name->az_object = NULL; az_new_name->az_cycle_id = 0; _move( az_new_name->c_text, c_text, l_length+1 ); /* ** link the name entry into the hash table */ az_new_name->az_next_name_entry = az_current_name; if (az_previous_name == NULL) sym_az_hash_table[ l_hash_code ] = az_new_name; else az_previous_name->az_next_name_entry = (sym_name_entry_type *) az_new_name; return az_new_name; } /* **++ ** FUNCTIONAL DESCRIPTION: ** ** This procedure is a hashing function. It takes a length and a ** pointer to a value. Using this value as a string, the function ** returns an integer in the range of 0 to sym_k_hash_table_limit-1. ** ** FORMAL PARAMETERS: ** ** l_length length of the value in bytes not including null ** c_value a null terminated string ** ** IMPLICIT INPUTS: ** ** sym_k_hash_table_limit ** ** IMPLICIT OUTPUTS: ** ** none ** ** FUNCTION VALUE: ** ** integer (the hash code) in range 0 to sym_k_hash_table_limit-1 ** ** SIDE EFFECTS: ** ** none ** **-- **/ int hash_function(l_length, c_value) int l_length; char *c_value; { #ifdef WORD64 #define _shift 3 static unsigned int XmConst mask[ 8 ] = { 0x00000000000000FF, 0x000000000000FFFF, 0x0000000000FFFFFF, 0x00000000FFFFFFFF, 0x00000000FFFFFFFF, 0x0000FFFFFFFFFFFF, 0x00FFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, }; #elif defined (LONG64) #define _shift 3 static long XmConst mask[ 8 ] = { 0x00000000000000FF, 0x000000000000FFFF, 0x0000000000FFFFFF, 0x00000000FFFFFFFF, 0x00000000FFFFFFFF, 0x0000FFFFFFFFFFFF, 0x00FFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, }; #else #define _shift 2 static unsigned int XmConst mask[ 4 ] = { 0x000000FF, 0x0000FFFF, 0x00FFFFFF, 0xFFFFFFFF }; #endif #ifdef LONG64 long l_hash_code; long al_value[20]; #else int l_hash_code; int al_value[20]; #endif int l_limit; int l_extra; int i; l_limit = (l_length-1) >> _shift; /* divide by wordsize */ l_extra = (l_length-1) & _slm; /* remainder from divide by wordsize */ #ifdef LONG64 bzero((char *)al_value, sizeof(long) * 20); #else bzero((char *)al_value, sizeof(int) * 20); #endif strncpy((char *)al_value, c_value, l_length); l_hash_code = 0; for (i = 0; i < l_limit; i++) { l_hash_code = l_hash_code ^ al_value[ i ]; } l_hash_code = l_hash_code ^ (al_value[ i ] & mask[ l_extra ]); return (int)(l_hash_code % sym_k_hash_table_limit); } #if debug_version /* **++ ** FUNCTIONAL DESCRIPTION: ** ** This debugging routine will dump out the name entries linked ** from the hash table. ** ** FORMAL PARAMETERS: ** ** none ** ** IMPLICIT INPUTS: ** ** sym_az_hash_table ** ** IMPLICIT OUTPUTS: ** ** none ** ** FUNCTION VALUE: ** ** void ** ** SIDE EFFECTS: ** ** prints out the hash table ** **-- **/ void sym_dump_hash_table() { int i; int total_count; int max_length; int empty_count; total_count = 0; empty_count = 0; max_length = 0; for (i=0; iaz_next_name_entry) { bucket_count++; _debug_output("\t %s \n", az_name->c_text); } total_count += bucket_count; if (bucket_count == 0) empty_count++; max_length = ( max_length > bucket_count )? max_length : bucket_count; _debug_output("bucket: %d length: %d\n", i, bucket_count); } _debug_output("name count: %d \n empty count: %d \n max length: %d", total_count, empty_count, max_length ); } #endif