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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
// util/hash-list-inl.h
// 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.
#ifndef KALDI_UTIL_HASH_LIST_INL_H_
#define KALDI_UTIL_HASH_LIST_INL_H_
// Do not include this file directly. It is included by fast-hash.h
namespace kaldi {
template<class I, class T> HashList<I, T>::HashList() {
list_head_ = NULL;
bucket_list_tail_ = static_cast<size_t>(-1); // invalid.
hash_size_ = 0;
freed_head_ = NULL;
}
template<class I, class T> void HashList<I, T>::SetSize(size_t size) {
hash_size_ = size;
KALDI_ASSERT(list_head_ == NULL && bucket_list_tail_ == static_cast<size_t>(-1)); // make sure empty.
if (size > buckets_.size())
buckets_.resize(size, HashBucket(0, NULL));
}
template<class I, class T>
typename HashList<I, T>::Elem* HashList<I, T>::Clear() {
// Clears the hashtable and gives ownership of the currently contained list to the
// user.
for (size_t cur_bucket = bucket_list_tail_;
cur_bucket != static_cast<size_t>(-1);
cur_bucket = buckets_[cur_bucket].prev_bucket) {
buckets_[cur_bucket].last_elem = NULL; // this is how we indicate "empty".
}
bucket_list_tail_ = static_cast<size_t>(-1);
Elem *ans = list_head_;
list_head_ = NULL;
return ans;
}
template<class I, class T>
const typename HashList<I, T>::Elem* HashList<I, T>::GetList() const {
return list_head_;
}
template<class I, class T>
inline void HashList<I, T>::Delete(Elem *e) {
e->tail = freed_head_;
freed_head_ = e;
}
template<class I, class T>
inline typename HashList<I, T>::Elem* HashList<I, T>::Find(I key) {
size_t index = (static_cast<size_t>(key) % hash_size_);
HashBucket &bucket = buckets_[index];
if (bucket.last_elem == NULL) {
return NULL; // empty bucket.
} else {
Elem *head = (bucket.prev_bucket == static_cast<size_t>(-1) ?
list_head_ :
buckets_[bucket.prev_bucket].last_elem->tail),
*tail = bucket.last_elem->tail;
for (Elem *e = head; e != tail; e = e->tail)
if (e->key == key) return e;
return NULL; // Not found.
}
}
template<class I, class T>
inline typename HashList<I, T>::Elem* HashList<I, T>::New() {
if (freed_head_) {
Elem *ans = freed_head_;
freed_head_ = freed_head_->tail;
return ans;
} else {
Elem *tmp = new Elem[allocate_block_size_];
for (size_t i = 0; i+1 < allocate_block_size_; i++)
tmp[i].tail = tmp+i+1;
tmp[allocate_block_size_-1].tail = NULL;
freed_head_ = tmp;
allocated_.push_back(tmp);
return this->New();
}
}
template<class I, class T>
HashList<I, T>::~HashList() {
// First test whether we had any memory leak within the
// HashList, i.e. things for which the user did not call Delete().
size_t num_in_list = 0, num_allocated = 0;
for (Elem *e = freed_head_; e != NULL; e = e->tail)
num_in_list++;
for (size_t i = 0; i < allocated_.size(); i++) {
num_allocated += allocate_block_size_;
delete[] allocated_[i];
}
if (num_in_list != num_allocated) {
KALDI_WARN << "Possible memory leak: " << num_in_list
<< " != " << num_allocated
<< ": you might have forgotten to call Delete on "
<< "some Elems";
}
}
template<class I, class T>
void HashList<I, T>::Insert(I key, T val) {
size_t index = (static_cast<size_t>(key) % hash_size_);
HashBucket &bucket = buckets_[index];
Elem *elem = New();
elem->key = key;
elem->val = val;
if (bucket.last_elem == NULL) { // Unoccupied bucket. Insert at
// head of bucket list (which is tail of regular list, they go in
// opposite directions).
if (bucket_list_tail_ == static_cast<size_t>(-1)) {
// list was empty so this is the first elem.
KALDI_ASSERT(list_head_ == NULL);
list_head_ = elem;
} else {
// link in to the chain of Elems
buckets_[bucket_list_tail_].last_elem->tail = elem;
}
elem->tail = NULL;
bucket.last_elem = elem;
bucket.prev_bucket = bucket_list_tail_;
bucket_list_tail_ = index;
} else {
// Already-occupied bucket. Insert at tail of list of elements within
// the bucket.
elem->tail = bucket.last_elem->tail;
bucket.last_elem->tail = elem;
bucket.last_elem = elem;
}
}
template<class I, class T>
void HashList<I, T>::InsertMore(I key, T val) {
size_t index = (static_cast<size_t>(key) % hash_size_);
HashBucket &bucket = buckets_[index];
Elem *elem = New();
elem->key = key;
elem->val = val;
KALDI_ASSERT(bucket.last_elem != NULL); // we assume there is already one element
if (bucket.last_elem->key == key) { // standard behavior: add as last element
elem->tail = bucket.last_elem->tail;
bucket.last_elem->tail = elem;
bucket.last_elem = elem;
return;
}
Elem *e = (bucket.prev_bucket == static_cast<size_t>(-1) ?
list_head_ : buckets_[bucket.prev_bucket].last_elem->tail);
// find place to insert in linked list
while (e != bucket.last_elem->tail && e->key != key) e = e->tail;
KALDI_ASSERT(e->key == key); // not found? - should not happen
elem->tail = e->tail;
e->tail = elem;
}
} // end namespace kaldi
#endif
|