name.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 566 行 · 第 1/2 页

/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  WHEN YOU FIGURE OUT WHAT THIS FILE DOES, PLEASE
*               DESCRIBE IT HERE!
*
****************************************************************************/


#include "plusplus.h"

#include <stdio.h>
#include <limits.h>

#include "errdefns.h"
#include "memmgr.h"
#include "name.h"
#include "carve.h"
#include "initdefs.h"
#include "stats.h"
#include "pcheader.h"
#include "toggle.h"
#ifndef NDEBUG
#include "pragdefn.h"
#endif

#pragma pack(1);
typedef struct name NAME;
struct name {
    NAME                *next;
    uint_16             xhash;
    name_hash_t         hash;
    char                name[1];
};
#pragma pack();

#define NAME_TABLE_HASH NAME_HASH

static NAME *hashTable[ NAME_TABLE_HASH ];

static name_dummy_index_t nameDummyIndex;
static unsigned long nameCount;

static NAME **nameTranslateTable;

static struct {
    unsigned            no_creates_allowed : 1; // name list is frozen
} nameFlags;

ExtraRptCtr( ctr_names );
ExtraRptCtr( ctr_dummy_names );
ExtraRptCtr( ctr_chains );
ExtraRptCtr( ctr_searches );
ExtraRptCtr( ctr_probes );
ExtraRptCtr( ctr_hashes );
ExtraRptCtr( ctr_length );
ExtraRptCtr( ctr_memcmp );
ExtraRptCtr( ctr_memcmp_fail );
ExtraRptCtr( ctr_max_length );

unsigned const NameCmpMask[5] = {
    0x00000000,
    0x000000ff,
    0x0000ffff,
    0x00ffffff,
    0xffffffff,
};

int NameMemCmp( char const *t1, char const *t2, unsigned len )
/************************************************************/
{
    unsigned *s1 = (unsigned*) t1;
    unsigned *s2 = (unsigned*) t2;
    unsigned mask;
    int diff;

    // can only check for one null byte since the common length
    // may access invalid memory with the other string
    DbgAssert( t2[len-1] == 0 );
    if( len > sizeof( unsigned ) ) {
        do {
            diff = *s1 - *s2;
            if( diff != 0 ) {
                return( diff );
            }
            ++s1;
            ++s2;
            len -= sizeof( unsigned );
        } while( len > sizeof( unsigned ) );
    }
    mask = NameCmpMask[ len ];
    return( ( *s1 & mask ) - ( *s2 & mask ) );
}

unsigned NameCalcHashLen( char const *id, size_t len )
/**********************************************/
{
    unsigned *s = (unsigned*) id;
    unsigned mask;
    unsigned c;
    unsigned g;
    unsigned h;

    ExtraRptIncrementCtr( ctr_hashes );
    /* modelled on hashpjw from the Dragon book */
    /* should not be used in mangled names so that it can change in patches */
    h = len;
    c = len;
    if( len > sizeof( unsigned ) ) {
        do {
            c ^= *s;
            h = ( h << 4 ) + c;
            g = h & ~0x0ffffff;
            h ^= g;
            h ^= g >> (4+4+4+4+4);
            ++s;
            len -= sizeof( unsigned );
        } while( len > sizeof( unsigned ) );
    }
    mask = NameCmpMask[ len ];
    c ^= *s & mask;
    h = ( h << 4 ) + c;
    g = h & ~0x0ffffff;
    h ^= g;
    h ^= g >> (4+4+4+4+4);
    g = h & ~0x0fff;
    h ^= g;
    h ^= g >> (4+4+4);
    h ^= h >> (2+4);
    DbgAssert(( h % NAME_HASH ) == h );
    return( h );
}

static char *nameAdd( NAME **head, unsigned bucket, unsigned xhash,
                      char *id, size_t len )
{
    NAME *name;

#ifdef XTRA_RPT
    if( *head == NULL ) {
        ExtraRptIncrementCtr( ctr_chains );
    }
#endif
    ExtraRptIncrementCtr( ctr_names );
    DbgVerify( ! nameFlags.no_creates_allowed
             , "name create occurred during precompiled header processing" );
    name = CPermAlloc( sizeof( NAME ) + len );
    memcpy( name->name, id, len + 1 );
    name->xhash = xhash;
    name->hash = bucket;
    name->next = *head;
    *head = name;
    ++nameCount;
    return( name->name );
}


char *NameCreateLen( char *id, unsigned len )
/*******************************************/
{
    unsigned xhash;
    unsigned bucket;
    size_t cmp_len;
    NAME *name;
    NAME **head;
    NAME **prev;

    ExtraRptIncrementCtr( ctr_searches );
    xhash = NameCalcHashLen( id, len );
#if NAME_TABLE_HASH != NAME_HASH
    bucket = xhash % NAME_TABLE_HASH;
#else
    bucket = xhash;
#endif
    // xhash cannot overflow a uint_16 ( 0x0fff + 0x00ff <= 0x1fff )
    xhash += (uint_8) len;
    head = &(hashTable[ bucket ]);
    prev = head;
    cmp_len = len + 1;
    ExtraRptZeroCtr( ctr_length );
    for( name = *prev; ; name = *prev ) {
        ExtraRptIncrementCtr( ctr_probes );
        ExtraRptIncrementCtr( ctr_length );
        if( name == NULL ) break;
        if( name->xhash == xhash ) {
            ExtraRptIncrementCtr( ctr_memcmp );
            if( NameMemCmp( name->name, id, cmp_len ) == 0 ) {
                /* move name to front of list in hash table */
                *prev = name->next;
                name->next = *head;
                *head = name;
                return( name->name );
            }
            ExtraRptIncrementCtr( ctr_memcmp_fail );
        }
        prev = &(name->next);
    }
    ExtraRptMaximum( ctr_length, ctr_max_length );
    return( nameAdd( head, bucket, xhash, id, len ) );
}


char *NameCreateNoLen( char *id )
/*******************************/
{
    size_t len;
    name_dummy_index_t ni;
    unsigned xhash;
    unsigned bucket;
    NAME **head;

    len = strlen( id );
    if( id[0] != NAME_DUMMY_PREFIX_0 ) {
        return( NameCreateLen( id, len ) );
    }
    // everybody uses the same 'name' so the hash doesn't have to be generated
    // from the name contents
    ni = nameDummyIndex++;
    xhash = ni % NAME_TABLE_HASH;
    bucket = xhash;
    head = &(hashTable[ bucket ]);
    return( nameAdd( head, bucket, xhash, id, len ) );
}

name_dummy_index_t NameNextDummyIndex( void )
/*******************************************/
{
    return( nameDummyIndex++ );
}

char *NameDummy( void )
/*********************/
{
    name_dummy_index_t ni;
    unsigned xhash;
    unsigned bucket;
    size_t len;
    NAME **head;
    char buff[ 1 + 1 + sizeof( ni ) * 3 + 1 ];

    ExtraRptIncrementCtr( ctr_dummy_names );
    ni = nameDummyIndex++;
    xhash = ni % NAME_TABLE_HASH;
    bucket = xhash;
    buff[0] = NAME_DUMMY_PREFIX_0;
    buff[1] = NAME_DUMMY_PREFIX_1;
    // the contents of the name don't have to be different just the address
    // but for debugging it is handy to have unique contents
#ifndef NDEBUG
    ultoa( ni, &buff[2], 10 );
    len = strlen( buff );
#else
    buff[2] = '0';
    buff[3] = '\0';
    len = 3;
#endif
    head = &(hashTable[ bucket ]);
    return( nameAdd( head, bucket, xhash, buff, len ) );
}