hashtable.c

This is a java virtual machine implement in c

/*0001*//*
/*0002./ * Copyright (c) 1998-2001 Sun Microsystems, Inc. All Rights Reserved.
/*0003./ *
/*0004./ * This software is the confidential and proprietary information of Sun
/*0005./ * Microsystems, Inc. ("Confidential Information").  You shall not
/*0006./ * disclose such Confidential Information and shall use it only in
/*0007./ * accordance with the terms of the license agreement you entered into
/*0008./ * with Sun.
/*0009./ *
/*0010./ * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF THE
/*0011./ * SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
/*0012./ * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
/*0013./ * PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR ANY DAMAGES
/*0014./ * SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR DISTRIBUTING
/*0015./ * THIS SOFTWARE OR ITS DERIVATIVES.
/*0016./ *
/*0017./ */
/*0018*/
/*0019*//*=========================================================================
/*0020./ * SYSTEM:    KVM
/*0021./ * SUBSYSTEM: Internal hashtables
/*0022./ * FILE:      hashtable.c
/*0023./ * OVERVIEW:  Maintains all the hashtables in the system:
/*0024./ *               ClassTable:        Mapping from char* to name
/*0025./ *               InternStringTable: Mapping from char* to String
/*0026./ *               UTFStringTable:    Mapping from char* to unique char*
/*0027./ *            
/*0028./ * AUTHOR:    Frank Yellin
/*0029./ * NOTE:      See hashtable.h for further information.
/*0030./ *=======================================================================*/
/*0031*/
/*0032*//*=========================================================================
/*0033./ * Include files
/*0034./ *=======================================================================*/
/*0035*/
/*0036*/#include <global.h>
/*0037*/
/*0038*//*=========================================================================
/*0039./ * Global variables
/*0040./ *=======================================================================*/
/*0041*/
/*0042*/#if ROMIZING
/*0043*/extern
/*0044*/#endif
/*0045*/HASHTABLE InternStringTable;    /* char* to String */
/*0046*/
/*0047*/#if ROMIZING
/*0048*/extern
/*0049*/#endif
/*0050*/HASHTABLE UTFStringTable;       /* char* to unique instance */
/*0051*/
/*0052*/#if ROMIZING
/*0053*/extern
/*0054*/#endif
/*0055*/HASHTABLE ClassTable;           /* package/base to CLASS */
/*0056*/
/*0057*//*=========================================================================
/*0058./ * Hashtable creation and deletion
/*0059./ *=======================================================================*/
/*0060*/
/*0061*//*=========================================================================
/*0062./ * FUNCTION:      createHashTable
/*0063./ * OVERVIEW:      Creates a hashtable, assigns it to a location, and 
/*0064./ *                registers that location as a root for GC.
/*0065./ * INTERFACE:
/*0066./ *   parameters:  tablePtr:  Address of variable holding location
/*0067./ *                bucketCount: Size of hashtable
/*0068./ *   returns:     no value, but as a side effect, puts the newly created
/*0069./ *                hashtable into *tablePtr
/*0070./ *=======================================================================*/
/*0071*/
/*0072*/void
/*0073*/createHashTable(HASHTABLE *tablePtr, int bucketCount) { 
/*0074*/    int objectSize = SIZEOF_HASHTABLE(bucketCount);
/*0075*/    HASHTABLE table = (HASHTABLE)callocPermanentObject(objectSize);
/*0076*/    table->bucketCount = bucketCount;
/*0077*/    *tablePtr = table;
/*0078*/}
/*0079*/
/*0080*//*=========================================================================
/*0081./ * FUNCTION:      InitializeHashTable
/*0082./ * OVERVIEW:      Called at startup to create system hashtables.
/*0083./ * INTERFACE:
/*0084./ *   parameters:  <none>
/*0085./ *   returns:     <nothing>
/*0086./ *=======================================================================*/
/*0087*/
/*0088*/void InitializeHashtables() { 
/*0089*/    if (!ROMIZING) { 
/*0090*/        createHashTable(&UTFStringTable, UTF_TABLE_SIZE);
/*0091*/        createHashTable(&InternStringTable, INTERN_TABLE_SIZE);
/*0092*/        createHashTable(&ClassTable, CLASS_TABLE_SIZE);
/*0093*/    }
/*0094*/}
/*0095*/
/*0096*//*=========================================================================
/*0097./ * FUNCTION:      finalizeROMHashTable
/*0098./ * OVERVIEW:      Return a ROM hashtable back to its "virgin" state.
/*0099./ * INTERFACE:
/*0100./ *   parameters:  table:  The hashtable
/*0101./ *                nextOffset:  Offset of the "next" field within each
/*0102./ *                entry of the hashtable.
/*0103./ *
/*0104./ * This code assumes that the non ROM entries are at the beginning of each
/*0105./ * chain, and that the ROM entries are at the end.  Hence, it can scan
/*0106./ * each chain, and just pop off the non-ROM entries until it reaches the end
/*0107./ * or a ROM entry.
/*0108./ *=======================================================================*/
/*0109*/
/*0110*/#if ROMIZING
/*0111*/
/*0112*/void finalizeROMHashTable(HASHTABLE table, int nextOffset) 
/*0113*/{
/*0114*/    int bucketCount = table->bucketCount;
/*0115*/    int i;
/*0116*/    for (i = 0; i < bucketCount; i++) {
/*0117*/        void *p = table->bucket[i];
/*0118*/        while (p != NULL && inAnyHeap(p)) { 
/*0119*/            /* Move to the next bucket */
/*0120*/            p = *(void **)((char *)p + nextOffset);
/*0121*/        }
/*0122*/        table->bucket[i] = p;
/*0123*/    }
/*0124*/}
/*0125*/
/*0126*/#endif /* ROMIZING */
/*0127*/
/*0128*/void FinalizeHashtables() { 
/*0129*/    if (!ROMIZING) { 
/*0130*/        UTFStringTable = NULL;
/*0131*/        InternStringTable = NULL;
/*0132*/        ClassTable = NULL;
/*0133*/    }
/*0134*/}
/*0135*/
/*0136*//*=========================================================================
/*0137./ * Functions on hashtables
/*0138./ *=======================================================================*/
/*0139*/
/*0140*//*=========================================================================
/*0141./ * FUNCTION:      stringHash
/*0142./ * OVERVIEW:      Returns a hash value for a C string
/*0143./ * INTERFACE:
/*0144./ *   parameters:  s:    pointer to a string
/*0145./ *                len:  length of string, in bytes
/*0146./ *   returns:     a hash value
/*0147./ *=======================================================================*/
/*0148*/
/*0149*/static unsigned int
/*0150*/stringHash(const char *s, int length)
/*0151*/{
/*0152*/    unsigned raw_hash = 0;
/*0153*/    while (--length >= 0) { 
/*0154*/        int c = *s++;
/*0155*/        /* raw_hash = raw_hash * 37 + c; */
/*0156*/        raw_hash =   (((raw_hash << 3) + raw_hash)  << 2) + raw_hash  + c;
/*0157*/    }
/*0158*/    return raw_hash;
/*0159*/}
/*0160*/
/*0161*//*=========================================================================
/*0162./ * FUNCTION:      getUString, getUStringX
/*0163./ * OVERVIEW:      Returns a unique instance of a given C string
/*0164./ * INTERFACE:
/*0165./ *   parameters:  string:       Pointer to an array of characters
/*0166./ *                stringLength: Length of string (implicit for getUString)
/*0167./ *   returns:     A unique instance.  If strcmp(x,y)==0, then
/*0168./ *                 getUString(x) == getUString(y), and
/*0169./ *                 strcmp(UStringInfo(getUString(x)), x) == 0.
/*0170./ * 
/*0171./ * Note that getUString actually allows "string"s with embedded NULLs.
/*0172./ * Two arrays of characters are equal only if they have the same length 
/*0173./ * and the same characters.
/*0174./ *=======================================================================*/
/*0175*/
/*0176*/UString
/*0177*/getUString(const char* string) { 
/*0181*/    return getUStringX(&string, 0, strlen(string));
/*0182*/}
/*0183*/
/*0184*/UString
/*0185*/getUStringX(CONST_CHAR_HANDLE nameH, int offset, int stringLength)
/*0186*/{
/*0187*/    const char *start = unhand(nameH);
/*0188*/    const char *string = start + offset; 
/*0189*/    HASHTABLE table = UTFStringTable;
/*0190*/    /* The bucket in the hash table */
/*0191*/    int index =  stringHash(string, stringLength) % table->bucketCount;
/*0192*/    UTF_HASH_ENTRY *bucketPtr = (UTF_HASH_ENTRY *)&table->bucket[index];
/*0193*/    UTF_HASH_ENTRY bucket;
/*0194*/    /* Search the bucket for the corresponding string. */
/*0195*/    for (bucket = *bucketPtr; bucket != NULL; bucket = bucket->next) { 
/*0196*/        const char *key = bucket->string;
/*0197*/        int length = bucket->length;
/*0198*/        if (length == stringLength) { 
/*0199*/            if ((key == string) ||
/*0200*/                (key[0] == string[0] && memcmp(key, string, length) == 0)) {
/*0201*/            if (EXCESSIVE_GARBAGE_COLLECTION && !ASYNCHRONOUS_NATIVE_FUNCTIONS){
/*0202*/                /* We'd garbage collect if it weren't found. . . */
/*0203*/                garbageCollect(0);
/*0204*/            } 
/*0205*/                return bucket;
/*0206*/            }
/*0207*/        }
/*0208*/    }
/*0209*/
/*0210*/    /* We have to create a new bucket.  Note that the string is embedded
/*0211./     * into the bucket.  We always append a '\0' to the string so that if
/*0212./     * the thing we were passed is a C String, it will continue to be a C
/*0213./     * String */
/*0214*/    bucket = (UTF_HASH_ENTRY)callocPermanentObject(
/*0215*/                 SIZEOF_UTF_HASH_ENTRY(stringLength));
/*0216*/
/*0217*/    /* Install the new item into the hash table.
/*0218./     * The allocation above may cause string to no longer be valid 
/*0219./     */
/*0220*/    
/*0221*/    bucket->next = *bucketPtr;
/*0222*/    memcpy((char *)bucket->string, unhand(nameH) + offset, stringLength);
/*0223*/    bucket->string[stringLength] = '\0';
/*0224*/    /* Give the item a key that uniquely represents it.  On purpose, we assign
/*0225./     * a key that makes it easy for us to find the right bucket.
/*0226./     * (key % table->bucketCount) = index.
/*0227./     */
/*0228*/    if (bucket->next == NULL) { 
/*0229*/        bucket->key = table->bucketCount + index;
/*0230*/    } else {