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 */
26bool 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 */
43void 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
54static 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
61static 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
71static 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 */
135StringObject* 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 */
144StringObject* 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 */
153bool 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 */
169void 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