GoogleTest Framework 例子

Google 有一款测试框架, googletest. id的doom3 BFG里面有一个不错的Hash索引实现, 采用了特殊的bucket实现形式. 通过写test的来理解是一个比较好的办法. 下面就是针对这个数据结构的测试.

Hash索引, 意思是key经过Hash函数计算之后得到一个bucket的号码, bucket中的元素是index, 这个index可以是数组的下标, key所对应的数据就存放在数组当中. 一般的实现是直接将数据存放在桶中, 数据以链表的形式存在. 这里可能的一个问题是每个链表肯定要动态申请, 这就造成很多的内存碎片. idHashIndex这个实现没有这个问题, 增加bucket的时候不需要重新申请内存.

hash和indexChain分别用来保存bucket和bucket的内容, 内容通过chain连接起来, 和链表的作用一样, 但不是链表. 下面的方法添加一对KV到系统里面.

ID_INLINE void idHashIndex::Addconst int keyconst int index ) {
    int h;

    assertindex >= );
    if hash == INVALID_INDEX ) {
        AllocatehashSizeindex >= indexSize index indexSize );
    }
    else if index >= indexSize ) {
        ResizeIndexindex );
    }

    key hashMask;
    indexChain[index] = hash[h];
    hash[h] = index;
}

这里变量名有点混淆, key实际应该是hash, 按照公式 hash = hashfunc( key ). 下面是示意图.

    ---------------------------------
    | | | | | | | |ff | | | | | | | | indexChaine array
    ---------------------------------
                   |
                   |
             ------>
             |
             |
    ------------------------------------
    | | | |index | | | | | | | | | | | | hash array
    ------------------------------------
            ^
            |
          hash
            ^
            | generatekey
          key



                     -------
                     |        |
                     V        |
    ------------------------------
    | | | | | | | |ff | |index | | | | | | indexChaine array
    ------------------------------
                         |
                         |
             ------------>
             |
             |
    ------------------------------
    | | | |index2 | | | | | | | | | | | | hash array
    ------------------------------
            ^
            |
            hash ( same hash )
             ^
             | generatekey
            key2



                   --------   -------
                   |      |   |        |
                   V      |   V        |
    ------------------------------------
    | | | | | | | |ff | |index | | |index2 | | | indexChaine array
    ------------------------------------
                                    |
                                    |
             ----------------------->
             |
             |
    ------------------------------
    | | | |index3 | | | | | | | | | | | | hash array
    ------------------------------
            ^
            |
            hash ( same hash )
             ^
             | generatekey
            key3

依次向同一个bucket中加入index, index2, index3的结果. 形成了一个chain: index3 -> index2 ->index

首先checkout googletest源码, 编译生成gtestd.lib. 将googletest的include路径和lib分别添加到doom3bfg工程的包含目录和附加库. 将启动工程的SUBSYSTEM改为CONSOLE. 还有要调换doomclassic.lib和libcmtd.lib的顺序. 先将这两个库添加到忽略依赖项中. 然后在附加依赖项中添加这两个库, doomclassic在前面.

"F:\My Documents\Visual Studio 2005\Projects\googletest-read-only\msvc\gtest\Debug\gtestd.lib";"F:\My Documents\Visual Studio 2005\Projects\DOOM-3-BFG-master\build\Win32\Debug\doomclassic.lib";libcmtd.lib;%(AdditionalDependencies)

googletest使用了_stricmp, 这个函数在doom3中被禁用, 开启这个函数, 将Str.h中的这一行注释掉.

// #define _stricmp        use_idStr_Icmp

这个模块和系统耦合太紧密了, 无法单独提取出来进行test, 改动代码的话太麻烦, 只能将test代码嵌入到整个系统中. 将入口WinMain函数替换为

#include <stdio.h>
#include <tchar.h>

#include <gtest/gtest.h>

TEST(HashIndexTestHandleNoneZeroInput)
{

    idHashIndex hi new idHashIndex(<< 141024);
    int key hi->GenerateKey(23002);

    EXPECT_EQ(23002 & ( ( << 14 ) - 1), key);
    EXPECT_EQ(69660 hi->Size());
    
    EXPECT_EQ(    hi->GetHashSize() * sizeofint ) + hi->GetIndexSize() * sizeofint ) + sizeof(*hi) , 
                hi->Size());

    EXPECT_EQ(16384hi->GetHashSize());
    EXPECT_EQ(1024hi->GetIndexSize());
    
    // test Add
    hi->Add(230022);
    hi->Add(23002 & ( ( << 14 ) - 1), 3);
    EXPECT_EQ(3hi->First(23002));
    EXPECT_EQ(2hi->Next(hi->First(23002)));
    EXPECT_EQ(0xffffffffhi->Next(2));


    // test insert index
    EXPECT_NE(hi->GenerateKey(32) , hi->GenerateKey(23002));
    hi->InsertIndex(32,2);
    // insert index 2, index 3 should be 4 now
    EXPECT_EQ(4hi->First(23002));
    EXPECT_EQ(3hi->Next(4));


    hi->Remove(230023);
    EXPECT_EQ(-1hi->Next(4));
    

    // test 赋值操作符
    idHashIndex hi2;
    hi2 = *hi
    EXPECT_EQ(4hi2.First(23002));
    EXPECT_EQ(2hi2.First(32));

    // 单个桶中元素越多, Spread值越低, 低代表分布不均匀
    hi2.Add(2300228);
    hi2.Add(23002280);
    EXPECT_EQ(50,hi2.GetSpread());
    hi2.Add(2300222);
    hi2.Add(2300223);
    EXPECT_EQ(34,hi2.GetSpread());
    hi2.Add(2300224);
    EXPECT_EQ(29,hi2.GetSpread());

    hi2.Clear(0,0);
    EXPECT_EQ(sizeofhi2 ), hi2.Size());
    
    hi->Clear(0,0);
    delete hi;
    
}

int _tmain(int argc_TCHARargv[])
{
    
    testing::InitGoogleTest(&argcargv);
    return RUN_ALL_TESTS();
}

修改了这么多, 包括构建配置和代码, 因此最好用git做两个备份, 一个备份是正常编译的, 另一个是运行test的.