/* * @OPENGROUP_COPYRIGHT@ * COPYRIGHT NOTICE * Copyright (c) 1990, 1991, 1992, 1993 Open Software Foundation, Inc. * Copyright (c) 1996, 1997, 1998, 1999, 2000 The Open Group * ALL RIGHTS RESERVED (MOTIF). See the file named COPYRIGHT.MOTIF for * the full copyright text. * * This software is subject to an open license. It may only be * used on, with or for operating systems which are themselves open * source systems. You must contact The Open Group for a license * allowing distribution and sublicensing of this software on, with, * or for operating systems which are not Open Source programs. * * See http://www.opengroup.org/openmotif/license for full * details of the license agreement. Any use, reproduction, or * distribution of the program constitutes recipient's acceptance of * this agreement. * * EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, THE PROGRAM IS * PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * KIND, EITHER EXPRESS OR IMPLIED INCLUDING, WITHOUT LIMITATION, ANY * WARRANTIES OR CONDITIONS OF TITLE, NON-INFRINGEMENT, MERCHANTABILITY * OR FITNESS FOR A PARTICULAR PURPOSE * * EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, NEITHER RECIPIENT * NOR ANY CONTRIBUTORS SHALL HAVE ANY LIABILITY FOR ANY DIRECT, * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING WITHOUT LIMITATION LOST PROFITS), HOWEVER CAUSED * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN * ANY WAY OUT OF THE USE OR DISTRIBUTION OF THE PROGRAM OR THE * EXERCISE OF ANY RIGHTS GRANTED HEREUNDER, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGES. */ /* * 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