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/*
18 * Test the hash table functions.
19 */
20#include "Dalvik.h"
21
22#include <stdlib.h>
23
24#ifndef NDEBUG
25
26#define kNumTestEntries 14
27
28/*
29 * Test foreach.
30 */
31static int printFunc(void* data, void* arg)
32{
33    //printf("  '%s'\n", (const char*) data);
34    // (should verify strings)
35
36    int* count = (int*) arg;
37    (*count)++;
38    return 0;
39}
40static void dumpForeach(HashTable* pTab)
41{
42    int count = 0;
43
44    //printf("Print from foreach:\n");
45    dvmHashForeach(pTab, printFunc, &count);
46    if (count != kNumTestEntries) {
47        ALOGE("TestHash foreach test failed");
48        assert(false);
49    }
50}
51
52/*
53 * Test iterator.
54 */
55static void dumpIterator(HashTable* pTab)
56{
57    int count = 0;
58
59    //printf("Print from iterator:\n");
60    HashIter iter;
61    for (dvmHashIterBegin(pTab, &iter); !dvmHashIterDone(&iter);
62        dvmHashIterNext(&iter))
63    {
64        //const char* str = (const char*) dvmHashIterData(&iter);
65        //printf("  '%s'\n", str);
66        // (should verify strings)
67        count++;
68    }
69    if (count != kNumTestEntries) {
70        ALOGE("TestHash iterator test failed");
71        assert(false);
72    }
73}
74
75/*
76 * Some quick hash table tests.
77 */
78bool dvmTestHash()
79{
80    HashTable* pTab;
81    char tmpStr[64];
82    const char* str;
83    u4 hash;
84    int i;
85
86    ALOGV("TestHash BEGIN");
87
88    pTab = dvmHashTableCreate(dvmHashSize(12), free);
89    if (pTab == NULL)
90        return false;
91
92    dvmHashTableLock(pTab);
93
94    /* add some entries */
95    for (i = 0; i < kNumTestEntries; i++) {
96        sprintf(tmpStr, "entry %d", i);
97        hash = dvmComputeUtf8Hash(tmpStr);
98        dvmHashTableLookup(pTab, hash, strdup(tmpStr),
99            (HashCompareFunc) strcmp, true);
100    }
101
102    dvmHashTableUnlock(pTab);
103
104    /* make sure we can find all entries */
105    for (i = 0; i < kNumTestEntries; i++) {
106        sprintf(tmpStr, "entry %d", i);
107        hash = dvmComputeUtf8Hash(tmpStr);
108        str = (const char*) dvmHashTableLookup(pTab, hash, tmpStr,
109                (HashCompareFunc) strcmp, false);
110        if (str == NULL) {
111            ALOGE("TestHash: failure: could not find '%s'", tmpStr);
112            /* return false */
113        }
114    }
115
116    /* make sure it behaves correctly when entry not found and !doAdd */
117    sprintf(tmpStr, "entry %d", 17);
118    hash = dvmComputeUtf8Hash(tmpStr);
119    str = (const char*) dvmHashTableLookup(pTab, hash, tmpStr,
120            (HashCompareFunc) strcmp, false);
121    if (str == NULL) {
122        /* good */
123    } else {
124        ALOGE("TestHash found nonexistent string (improper add?)");
125    }
126
127    dumpForeach(pTab);
128    dumpIterator(pTab);
129
130    /* make sure they all get freed */
131    dvmHashTableFree(pTab);
132
133
134    /*
135     * Round 2: verify probing & tombstones.
136     */
137    pTab = dvmHashTableCreate(dvmHashSize(2), free);
138    if (pTab == NULL)
139        return false;
140
141    hash = 0;
142
143    /* two entries, same hash, different values */
144    const char* str1;
145    str1 = (char*) dvmHashTableLookup(pTab, hash, strdup("one"),
146            (HashCompareFunc) strcmp, true);
147    assert(str1 != NULL);
148    str = (const char*) dvmHashTableLookup(pTab, hash, strdup("two"),
149            (HashCompareFunc) strcmp, true);
150
151    /* remove the first one */
152    if (!dvmHashTableRemove(pTab, hash, (void*)str1))
153        ALOGE("TestHash failed to delete item");
154    else
155        free((void*)str1);     // "Remove" doesn't call the free func
156
157    /* make sure iterator doesn't included deleted entries */
158    int count = 0;
159    HashIter iter;
160    for (dvmHashIterBegin(pTab, &iter); !dvmHashIterDone(&iter);
161        dvmHashIterNext(&iter))
162    {
163        count++;
164    }
165    if (count != 1) {
166        ALOGE("TestHash wrong number of entries (%d)", count);
167    }
168
169    /* see if we can find them */
170    str = (const char*) dvmHashTableLookup(pTab, hash, (void*)"one",
171            (HashCompareFunc) strcmp,false);
172    if (str != NULL)
173        ALOGE("TestHash deleted entry has returned!");
174    str = (const char*) dvmHashTableLookup(pTab, hash, (void*)"two",
175            (HashCompareFunc) strcmp,false);
176    if (str == NULL)
177        ALOGE("TestHash entry vanished");
178
179    /* force a table realloc to exercise tombstone removal */
180    for (i = 0; i < 20; i++) {
181        sprintf(tmpStr, "entry %d", i);
182        str = (const char*) dvmHashTableLookup(pTab, hash, strdup(tmpStr),
183                (HashCompareFunc) strcmp, true);
184        assert(str != NULL);
185    }
186
187    dvmHashTableFree(pTab);
188    ALOGV("TestHash END");
189
190    return true;
191}
192
193#endif /*NDEBUG*/
194