hashtable.c

Nucleus_2_kvm_Hello 是kvm移植到Nucleus系统的源代码。。。好东西啊

/*
 * Copyright (c) 1998-2001 Sun Microsystems, Inc. All Rights Reserved.
 *
 * This software is the confidential and proprietary information of Sun
 * Microsystems, Inc. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Sun.
 *
 * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
 * SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 * PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES
 * SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
 * THIS SOFTWARE OR ITS DERIVATIVES.
 *
 * Use is subject to license terms.
 */

/*=========================================================================
 * SYSTEM:    KVM
 * SUBSYSTEM: Internal hashtables
 * FILE:      hashtable.c
 * OVERVIEW:  Maintains all the hashtables in the system:
 *               ClassTable:        Mapping from char* to name
 *               InternStringTable: Mapping from char* to String
 *               UTFStringTable:    Mapping from char* to unique char*
 *            
 * AUTHOR:    Frank Yellin
 * NOTE:      See hashtable.h for further information.
 *=======================================================================*/

/*=========================================================================
 * Include files
 *=======================================================================*/

#include "global.h"

/*=========================================================================
 * Global variables
 *=======================================================================*/

#if ROMIZING
extern
#endif
HASHTABLE InternStringTable;    /* char* to String */

#if ROMIZING
extern
#endif
HASHTABLE UTFStringTable;       /* char* to unique instance */

#if ROMIZING
extern
#endif
HASHTABLE ClassTable;           /* package/base to CLASS */

/*=========================================================================
 * Hashtable creation and deletion
 *=======================================================================*/

/*=========================================================================
 * FUNCTION:      createHashTable
 * OVERVIEW:      Creates a hashtable, assigns it to a location, and 
 *                registers that location as a root for GC.
 * INTERFACE:
 *   parameters:  tablePtr:  Address of variable holding location
 *                bucketCount: Size of hashtable
 *   returns:     no value, but as a side effect, puts the newly created
 *                hashtable into *tablePtr
 *=======================================================================*/

void
createHashTable(HASHTABLE *tablePtr, int bucketCount) { 
    int objectSize = SIZEOF_HASHTABLE(bucketCount);
    HASHTABLE table = (HASHTABLE)callocPermanentObject(objectSize);
    table->bucketCount = bucketCount;
    *tablePtr = table;
}

/*=========================================================================
 * FUNCTION:      InitializeHashTable
 * OVERVIEW:      Called at startup to create system hashtables.
 * INTERFACE:
 *   parameters:  <none>
 *   returns:     <nothing>
 *=======================================================================*/

void InitializeHashtables() { 
    if (!ROMIZING) { 
        createHashTable(&UTFStringTable, UTF_TABLE_SIZE);
        createHashTable(&InternStringTable, INTERN_TABLE_SIZE);
        createHashTable(&ClassTable, CLASS_TABLE_SIZE);
    }
}

/*=========================================================================
 * FUNCTION:      finalizeROMHashTable
 * OVERVIEW:      Return a ROM hashtable back to its "virgin" state.
 * INTERFACE:
 *   parameters:  table:  The hashtable
 *                nextOffset:  Offset of the "next" field within each
 *                entry of the hashtable.
 *
 * This code assumes that the non ROM entries are at the beginning of each
 * chain, and that the ROM entries are at the end.  Hence, it can scan
 * each chain, and just pop off the non-ROM entries until it reaches the end
 * or a ROM entry.
 *=======================================================================*/

#if ROMIZING

void finalizeROMHashTable(HASHTABLE table, int nextOffset) 
{
    int bucketCount = table->bucketCount;
    int i;
    for (i = 0; i < bucketCount; i++) {
        void *p = table->bucket[i];
        while (p != NULL && inAnyHeap(p)) { 
            /* Move to the next bucket */
            p = *(void **)((char *)p + nextOffset);
        }
        table->bucket[i] = p;
    }
}

#endif /* ROMIZING */

void FinalizeHashtables() { 
    if (!ROMIZING) { 
        UTFStringTable = NULL;
        InternStringTable = NULL;
        ClassTable = NULL;
    }
}

/*=========================================================================
 * Functions on hashtables
 *=======================================================================*/

/*=========================================================================
 * FUNCTION:      stringHash
 * OVERVIEW:      Returns a hash value for a C string
 * INTERFACE:
 *   parameters:  s:    pointer to a string
 *                len:  length of string, in bytes
 *   returns:     a hash value
 *=======================================================================*/

static unsigned int
stringHash(const char *s, int length)
{
    unsigned raw_hash = 0;
    while (--length >= 0) { 
        int c = *s++;
        /* raw_hash = raw_hash * 37 + c; */
        raw_hash =   (((raw_hash << 3) + raw_hash)  << 2) + raw_hash  + c;
    }
    return raw_hash;
}

/*=========================================================================
 * FUNCTION:      getUString, getUStringX
 * OVERVIEW:      Returns a unique instance of a given C string
 * INTERFACE:
 *   parameters:  string:       Pointer to an array of characters
 *                stringLength: Length of string (implicit for getUString)
 *   returns:     A unique instance.  If strcmp(x,y)==0, then
 *                 getUString(x) == getUString(y), and
 *                 strcmp(UStringInfo(getUString(x)), x) == 0.
 * 
 * Note that getUString actually allows "string"s with embedded NULLs.
 * Two arrays of characters are equal only if they have the same length 
 * and the same characters.
 *=======================================================================*/

UString
getUString(const char* string) { 
    if (INCLUDEDEBUGCODE && inCurrentHeap(string)) { 
        fatalError(KVM_MSG_BAD_CALL_TO_GETUSTRING);
    }
    return getUStringX(&string, 0, strlen(string));
}

UString
getUStringX(CONST_CHAR_HANDLE nameH, int offset, int stringLength)
{
    const char *start = unhand(nameH);
    const char *string = start + offset; 
    HASHTABLE table = UTFStringTable;
    /* The bucket in the hash table */
    int index =  stringHash(string, stringLength) % table->bucketCount;
    UTF_HASH_ENTRY *bucketPtr = (UTF_HASH_ENTRY *)&table->bucket[index];
    UTF_HASH_ENTRY bucket;
    /* Search the bucket for the corresponding string. */
    for (bucket = *bucketPtr; bucket != NULL; bucket = bucket->next) { 
        const char *key = bucket->string;
        int length = bucket->length;
        if (length == stringLength) { 
            if ((key == string) ||
                (key[0] == string[0] && memcmp(key, string, length) == 0)) {
#if EXCESSIVE_GARBAGE_COLLECTION && !ASYNCHRONOUS_NATIVE_FUNCTIONS
                    if (excessivegc) {
                        /* We'd garbage collect if it weren't found. . . */
                        garbageCollect(0);
                    }
#endif /* EXCESSIVE_GARBAGE_COLLECTION && !ASYNCHRONOUS_NATIVE_FUNCTIONS */
                return bucket;
            }
        }
    }

    /* We have to create a new bucket.  Note that the string is embedded
     * into the bucket.  We always append a '\0' to the string so that if
     * the thing we were passed is a C String, it will continue to be a C
     * String */
    bucket = (UTF_HASH_ENTRY)callocPermanentObject(
                 SIZEOF_UTF_HASH_ENTRY(stringLength));

    /* Install the new item into the hash table.
     * The allocation above may cause string to no longer be valid 
     */
    
    bucket->next = *bucketPtr;
    memcpy((char *)bucket->string, unhand(nameH) + offset, stringLength);
    bucket->string[stringLength] = '\0';
    /* Give the item a key that uniquely represents it.  On purpose, we assign
     * a key that makes it easy for us to find the right bucket.
     * (key % table->bucketCount) = index.
     */
    if (bucket->next == NULL) { 
        bucket->key = table->bucketCount + index;
    } else { 
        unsigned long nextKey = table->bucketCount + bucket->next->key;
        if (nextKey >= 0x10000) { 
            fatalError(KVM_MSG_TOO_MANY_NAMETABLE_KEYS);
        }
        bucket->key = (unsigned short)nextKey;
    }

    bucket->length = stringLength;
    *bucketPtr = bucket;

    /* Increment the count, in case we need this information */
    table->count++;

    /* Return the string */
    return bucket;
}

/*=========================================================================
 * FUNCTION:      internString
 * OVERVIEW:      Returns a unique Java String that corresponds to a
 *                particular char* C string
 * INTERFACE:
 *   parameters:  string:  A C string
 *   returns:     A unique Java String, such that if strcmp(x,y) == 0, then
 *                internString(x) == internString(y).
 *=======================================================================*/

INTERNED_STRING_INSTANCE
internString(const char *utf8string, int length)
{ 
    HASHTABLE table = InternStringTable;
    unsigned int hash = stringHash(utf8string, length);
    unsigned int index = hash % table->bucketCount;
    unsigned int utfLength = utfStringLength(utf8string, length);

    INTERNED_STRING_INSTANCE string, *stringPtr;

    stringPtr = (INTERNED_STRING_INSTANCE *)&table->bucket[index];
    
    for (string = *stringPtr; string != NULL; string = string->next) { 
        if (string->length == utfLength) { 
            SHORTARRAY chars = string->array;
            int offset = string->offset;
            const char *p = utf8string;
            unsigned int i;
            for (i = 0; i < utfLength; i++) { 
                short unichar = utf2unicode(&p);
                if (unichar != chars->sdata[offset + i]) { 
                    /* We want to do "continue  <outerLoop>", but this is C */;
                    goto continueOuterLoop;
                }
            }
#if EXCESSIVE_GARBAGE_COLLECTION && !ASYNCHRONOUS_NATIVE_FUNCTIONS
            if (excessivegc) {
                /* We might garbage collect, so we do  */
                garbageCollect(0);
            }
#endif /* EXCESSIVE_GARBAGE_COLLECTION && !ASYNCHRONOUS_NATIVE_FUNCTIONS */
            return string;
        }
    continueOuterLoop:
        ;
    }

    
    string = instantiateInternedString(utf8string, length);
    string->next = *stringPtr;
    *stringPtr = string;
    return string;
}

/*=========================================================================
 * Conversion operations
 *=======================================================================*/

/*=========================================================================
 * FUNCTION:      utf2unicode
 * OVERVIEW:      Converts UTF8 string to unicode char.
 *
 *   parameters:  utfstring_ptr: pointer to a UTF8 string. Set to point 
 *                to the next UTF8 char upon return.
 *   returns      unicode char
 *=======================================================================*/

short utf2unicode(const char **utfstring_ptr) {
    unsigned char *ptr = (unsigned char *)(*utfstring_ptr);
    unsigned char ch, ch2, ch3;
    int length = 1;     /* default length */