/* 

 * Motif

 *

 * Copyright (c) 1987-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

*/ 

/* 

 * HISTORY

*/ 

#ifdef REV_INFO

#ifndef lint

static char rcsid[] = "$TOG: UilSymNam.c /main/13 1997/09/08 11:12:50 cshi $"

#endif

#endif

#ifdef HAVE_CONFIG_H

#include <config.h>

#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;  i

    {

	int		    bucket_count;

	sym_name_entry_type  *az_name;

	bucket_count = 0;

	for (az_name = sym_az_hash_table[ i ];  

	     az_name != NULL;  

	     az_name = az_name->az_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