Home | History | Annotate | Download | only in test 
      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  */
     31 static 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 }
     40 static 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  */
     55 static 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  */
     78 bool 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