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 */
dvmStringInternStartup()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 */
dvmStringInternShutdown()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
lookupString(HashTable * table,u4 key,StringObject * value)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
insertString(HashTable * table,u4 key,StringObject * value)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
lookupInternedString(StringObject * strObj,bool isLiteral)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 */
dvmLookupInternedString(StringObject * strObj)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 */
dvmLookupImmortalInternedString(StringObject * strObj)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 */
dvmIsWeakInternedString(StringObject * strObj)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 */
dvmGcDetachDeadInternedStrings(int (* isUnmarkedObject)(void *))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 }
180