hash-list.h
Go to the documentation of this file.
1 // util/hash-list.h
2 
3 // Copyright 2009-2011 Microsoft Corporation
4 // 2013 Johns Hopkins University (author: Daniel Povey)
5 
6 // See ../../COPYING for clarification regarding multiple authors
7 //
8 // Licensed under the Apache License, Version 2.0 (the "License");
9 // you may not use this file except in compliance with the License.
10 // You may obtain a copy of the License at
11 //
12 // http://www.apache.org/licenses/LICENSE-2.0
13 //
14 // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
16 // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
17 // MERCHANTABLITY OR NON-INFRINGEMENT.
18 // See the Apache 2 License for the specific language governing permissions and
19 // limitations under the License.
20 
21 
22 #ifndef KALDI_UTIL_HASH_LIST_H_
23 #define KALDI_UTIL_HASH_LIST_H_
24 #include <vector>
25 #include <set>
26 #include <algorithm>
27 #include <limits>
28 #include <cassert>
29 #include "util/stl-utils.h"
30 
31 
32 /* This header provides utilities for a structure that's used in a decoder (but
33  is quite generic in nature so we implement and test it separately).
34  Basically it's a singly-linked list, but implemented in such a way that we
35  can quickly search for elements in the list. We give it a slightly richer
36  interface than just a hash and a list. The idea is that we want to separate
37  the hash part and the list part: basically, in the decoder, we want to have a
38  single hash for the current frame and the next frame, because by the time we
39  need to access the hash for the next frame we no longer need the hash for the
40  previous frame. So we have an operation that clears the hash but leaves the
41  list structure intact. We also control memory management inside this object,
42  to avoid repeated new's/deletes.
43 
44  See hash-list-test.cc for an example of how to use this object.
45 */
46 
47 
48 namespace kaldi {
49 
50 template<class I, class T> class HashList {
51  public:
52  struct Elem {
53  I key;
54  T val;
56  };
57 
60  HashList();
61 
65  Elem *Clear();
66 
71  const Elem *GetList() const;
72 
76  inline void Delete(Elem *e);
77 
81  inline Elem *New();
82 
87  inline Elem *Find(I key);
88 
94  inline Elem *Insert(I key, T val);
95 
103  inline void InsertMore(I key, T val);
104 
110  void SetSize(size_t sz);
111 
113  inline size_t Size() { return hash_size_; }
114 
115  ~HashList();
116  private:
117 
118  struct HashBucket {
119  size_t prev_bucket; // index to next bucket (-1 if list tail). Note:
120  // list of buckets goes in opposite direction to list of Elems.
121  Elem *last_elem; // pointer to last element in this bucket (NULL if empty)
122  inline HashBucket(size_t i, Elem *e): prev_bucket(i), last_elem(e) {}
123  };
124 
125  Elem *list_head_; // head of currently stored list.
126  size_t bucket_list_tail_; // tail of list of active hash buckets.
127 
128  size_t hash_size_; // number of hash buckets.
129 
130  std::vector<HashBucket> buckets_;
131 
132  Elem *freed_head_; // head of list of currently freed elements. [ready for
133  // allocation]
134 
135  std::vector<Elem*> allocated_; // list of allocated blocks.
136 
137  static const size_t allocate_block_size_ = 1024; // Number of Elements to
138  // allocate in one block. Must be largish so storing allocated_ doesn't
139  // become a problem.
140 };
141 
142 
143 } // end namespace kaldi
144 
145 #include "util/hash-list-inl.h"
146 
147 #endif // KALDI_UTIL_HASH_LIST_H_
This code computes Goodness of Pronunciation (GOP) and extracts phone-level pronunciation feature for...
Definition: chain.dox:20
Elem * Insert(I key, T val)
Insert inserts a new element into the hashtable/stored list.
size_t hash_size_
Definition: hash-list.h:128
Elem * freed_head_
Definition: hash-list.h:132
HashList()
Constructor takes no arguments.
Definition: hash-list-inl.h:30
std::vector< HashBucket > buckets_
Definition: hash-list.h:130
static const size_t allocate_block_size_
Definition: hash-list.h:137
size_t bucket_list_tail_
Definition: hash-list.h:126
std::vector< Elem * > allocated_
Definition: hash-list.h:135
void SetSize(size_t sz)
SetSize tells the object how many hash buckets to allocate (should typically be at least twice the nu...
Definition: hash-list-inl.h:37
const Elem * GetList() const
Gives the head of the current list to the user.
Definition: hash-list-inl.h:61
HashBucket(size_t i, Elem *e)
Definition: hash-list.h:122
Elem * Clear()
Clears the hash and gives the head of the current list to the user; ownership is transferred to the u...
Definition: hash-list-inl.h:46
Elem * New()
This should probably not be needed to be called directly by the user.
Definition: hash-list-inl.h:89
Elem * list_head_
Definition: hash-list.h:125
void InsertMore(I key, T val)
Insert inserts another element with same key into the hashtable/ stored list.
Elem * Find(I key)
Find tries to find this element in the current list using the hashtable.
Definition: hash-list-inl.h:72
void Delete(Elem *e)
Think of this like delete().
Definition: hash-list-inl.h:66
size_t Size()
Returns current number of hash buckets.
Definition: hash-list.h:113