hash-list-test.cc
2.86 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
// util/hash-list-test.cc
// Copyright 2009-2011 Microsoft Corporation
// 2013 Johns Hopkins University (author: Daniel Povey)
// See ../../COPYING for clarification regarding multiple authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.
#include "util/hash-list.h"
#include <map> // for baseline.
#include <cstdlib>
#include <iostream>
namespace kaldi {
template<class Int, class T> void TestHashList() {
typedef typename HashList<Int, T>::Elem Elem;
HashList<Int, T> hash;
hash.SetSize(200); // must be called before use.
std::map<Int, T> m1;
for (size_t j = 0; j < 50; j++) {
Int key = Rand() % 200;
T val = Rand() % 50;
m1[key] = val;
Elem *e = hash.Find(key);
if (e) e->val = val;
else hash.Insert(key, val);
}
std::map<Int, T> m2;
for (int i = 0; i < 100; i++) {
m2.clear();
for (typename std::map<Int, T>::const_iterator iter = m1.begin();
iter != m1.end();
iter++) {
m2[iter->first + 1] = iter->second;
}
std::swap(m1, m2);
Elem *h = hash.Clear(), *tmp;
hash.SetSize(100 + Rand() % 100); // note, SetSize is relatively cheap
// operation as long as we are not increasing the size more than it's ever
// previously been increased to.
for (; h != NULL; h = tmp) {
hash.Insert(h->key + 1, h->val);
tmp = h->tail;
hash.Delete(h); // think of this like calling delete.
}
// Now make sure h and m2 are the same.
const Elem *list = hash.GetList();
size_t count = 0;
for (; list != NULL; list = list->tail, count++) {
KALDI_ASSERT(m1[list->key] == list->val);
}
for (size_t j = 0; j < 10; j++) {
Int key = Rand() % 200;
bool found_m1 = (m1.find(key) != m1.end());
if (found_m1) m1[key];
Elem *e = hash.Find(key);
KALDI_ASSERT((e != NULL) == found_m1);
if (found_m1)
KALDI_ASSERT(m1[key] == e->val);
}
KALDI_ASSERT(m1.size() == count);
}
}
} // end namespace kaldi
int main() {
using namespace kaldi;
for (size_t i = 0;i < 3;i++) {
TestHashList<int, unsigned int>();
TestHashList<unsigned int, int>();
TestHashList<int16, int32>();
TestHashList<int16, int32>();
TestHashList<char, unsigned char>();
TestHashList<unsigned char, int>();
}
std::cout << "Test OK.\n";
}