vm/Intern.cpp

   1 /*
   2  * Copyright (C) 2008 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 /*
  17  * String interning.
  18  */
  19 #include "Dalvik.h"
  20
  21 #include <stddef.h>
  22
  23 /*
  24  * Prep string interning.
  25  */
  26 bool dvmStringInternStartup()
  27 {
  28     dvmInitMutex(&gDvm.internLock);
  29     gDvm.internedStrings = dvmHashTableCreate(256, NULL);
  30     if (gDvm.internedStrings == NULL)
  31         return false;
  32     gDvm.literalStrings = dvmHashTableCreate(256, NULL);
  33     if (gDvm.literalStrings == NULL)
  34         return false;
  35     return true;
  36 }
  37
  38 /*
  39  * Chuck the intern list.
  40  *
  41  * The contents of the list are StringObjects that live on the GC heap.
  42  */
  43 void dvmStringInternShutdown()
  44 {
  45     if (gDvm.internedStrings != NULL || gDvm.literalStrings != NULL) {
  46         dvmDestroyMutex(&gDvm.internLock);
  47     }
  48     dvmHashTableFree(gDvm.internedStrings);
  49     gDvm.internedStrings = NULL;
  50     dvmHashTableFree(gDvm.literalStrings);
  51     gDvm.literalStrings = NULL;
  52 }
  53
  54 static StringObject* lookupString(HashTable* table, u4 key, StringObject* value)
  55 {
  56     void* entry = dvmHashTableLookup(table, key, (void*)value,
  57                                      dvmHashcmpStrings, false);
  58     return (StringObject*)entry;
  59 }
  60
  61 static StringObject* insertString(HashTable* table, u4 key, StringObject* value)
  62 {
  63     if (dvmIsNonMovingObject(value) == false) {
  64         value = (StringObject*)dvmCloneObject(value, ALLOC_NON_MOVING);
  65     }
  66     void* entry = dvmHashTableLookup(table, key, (void*)value,
  67                                      dvmHashcmpStrings, true);
  68     return (StringObject*)entry;
  69 }
  70
  71 static StringObject* lookupInternedString(StringObject* strObj, bool isLiteral)
  72 {
  73     StringObject* found;
  74
  75     assert(strObj != NULL);
  76     u4 key = dvmComputeStringHash(strObj);
  77     dvmLockMutex(&gDvm.internLock);
  78     if (isLiteral) {
  79         /*
  80          * Check the literal table for a match.
  81          */
  82         StringObject* literal = lookupString(gDvm.literalStrings, key, strObj);
  83         if (literal != NULL) {
  84             /*
  85              * A match was found in the literal table, the easy case.
  86              */
  87             found = literal;
  88         } else {
  89             /*
  90              * There is no match in the literal table, check the
  91              * interned string table.
  92              */
  93             StringObject* interned = lookupString(gDvm.internedStrings, key, strObj);
  94             if (interned != NULL) {
  95                 /*
  96                  * A match was found in the interned table.  Move the
  97                  * matching string to the literal table.
  98                  */
  99                 dvmHashTableRemove(gDvm.internedStrings, key, interned);
 100                 found = insertString(gDvm.literalStrings, key, interned);
 101                 assert(found == interned);
 102             } else {
 103                 /*
 104                  * No match in the literal table or the interned
 105                  * table.  Insert into the literal table.
 106                  */
 107                 found = insertString(gDvm.literalStrings, key, strObj);
 108                 assert(found == strObj);
 109             }
 110         }
 111     } else {
 112         /*
 113          * Check the literal table for a match.
 114          */
 115         found = lookupString(gDvm.literalStrings, key, strObj);
 116         if (found == NULL) {
 117             /*
 118              * No match was found in the literal table.  Insert into
 119              * the intern table if it does not already exist.
 120              */
 121             found = insertString(gDvm.internedStrings, key, strObj);
 122         }
 123     }
 124     assert(found != NULL);
 125     dvmUnlockMutex(&gDvm.internLock);
 126     return found;
 127 }
 128
 129 /*
 130  * Find an entry in the interned string table.
 131  *
 132  * If the string doesn't already exist, the StringObject is added to
 133  * the table.  Otherwise, the existing entry is returned.
 134  */
 135 StringObject* dvmLookupInternedString(StringObject* strObj)
 136 {
 137     return lookupInternedString(strObj, false);
 138 }
 139
 140 /*
 141  * Same as dvmLookupInternedString(), but guarantees that the
 142  * returned string is a literal.
 143  */
 144 StringObject* dvmLookupImmortalInternedString(StringObject* strObj)
 145 {
 146     return lookupInternedString(strObj, true);
 147 }
 148
 149 /*
 150  * Returns true if the object is a weak interned string.  Any string
 151  * interned by the user is weak.
 152  */
 153 bool dvmIsWeakInternedString(StringObject* strObj)
 154 {
 155     assert(strObj != NULL);
 156     if (gDvm.internedStrings == NULL) {
 157         return false;
 158     }
 159     dvmLockMutex(&gDvm.internLock);
 160     u4 key = dvmComputeStringHash(strObj);
 161     StringObject* found = lookupString(gDvm.internedStrings, key, strObj);
 162     dvmUnlockMutex(&gDvm.internLock);
 163     return found == strObj;
 164 }
 165
 166 /*
 167  * Clear white references from the intern table.
 168  */
 169 void dvmGcDetachDeadInternedStrings(int (*isUnmarkedObject)(void *))
 170 {
 171     /* It's possible for a GC to happen before dvmStringInternStartup()
 172      * is called.
 173      */
 174     if (gDvm.internedStrings != NULL) {
 175         dvmLockMutex(&gDvm.internLock);
 176         dvmHashForeachRemove(gDvm.internedStrings, isUnmarkedObject);
 177         dvmUnlockMutex(&gDvm.internLock);
 178     }
 179 }