All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
HashList< I, T > Class Template Reference

#include <hash-list.h>

Collaboration diagram for HashList< I, T >:

Classes

struct  Elem
 
struct  HashBucket
 

Public Member Functions

 HashList ()
 Constructor takes no arguments. More...
 
ElemClear ()
 Clears the hash and gives the head of the current list to the user; ownership is transferred to the user (the user must call Delete() for each element in the list, at his/her leisure). More...
 
const ElemGetList () const
 Gives the head of the current list to the user. More...
 
void Delete (Elem *e)
 Think of this like delete(). More...
 
ElemNew ()
 This should probably not be needed to be called directly by the user. More...
 
ElemFind (I key)
 Find tries to find this element in the current list using the hashtable. More...
 
void Insert (I key, T val)
 Insert inserts a new element into the hashtable/stored list. More...
 
void InsertMore (I key, T val)
 Insert inserts another element with same key into the hashtable/ stored list. More...
 
void SetSize (size_t sz)
 SetSize tells the object how many hash buckets to allocate (should typically be at least twice the number of objects we expect to go in the structure, for fastest performance). More...
 
size_t Size ()
 Returns current number of hash buckets. More...
 
 ~HashList ()
 

Private Attributes

Elemlist_head_
 
size_t bucket_list_tail_
 
size_t hash_size_
 
std::vector< HashBucketbuckets_
 
Elemfreed_head_
 
std::vector< Elem * > allocated_
 

Static Private Attributes

static const size_t allocate_block_size_ = 1024
 

Detailed Description

template<class I, class T>
class kaldi::HashList< I, T >

Definition at line 50 of file hash-list.h.

Constructor & Destructor Documentation

HashList ( )

Constructor takes no arguments.

Call SetSize to inform it of the likely size.

Definition at line 30 of file hash-list-inl.h.

30  {
31  list_head_ = NULL;
32  bucket_list_tail_ = static_cast<size_t>(-1); // invalid.
33  hash_size_ = 0;
34  freed_head_ = NULL;
35 }
size_t hash_size_
Definition: hash-list.h:130
Elem * freed_head_
Definition: hash-list.h:134
size_t bucket_list_tail_
Definition: hash-list.h:128
Elem * list_head_
Definition: hash-list.h:127
~HashList ( )

Definition at line 106 of file hash-list-inl.h.

References rnnlm::i, KALDI_WARN, and HashList< I, T >::Elem::tail.

106  {
107  // First test whether we had any memory leak within the
108  // HashList, i.e. things for which the user did not call Delete().
109  size_t num_in_list = 0, num_allocated = 0;
110  for (Elem *e = freed_head_; e != NULL; e = e->tail)
111  num_in_list++;
112  for (size_t i = 0; i < allocated_.size(); i++) {
113  num_allocated += allocate_block_size_;
114  delete[] allocated_[i];
115  }
116  if (num_in_list != num_allocated) {
117  KALDI_WARN << "Possible memory leak: " << num_in_list
118  << " != " << num_allocated
119  << ": you might have forgotten to call Delete on "
120  << "some Elems";
121  }
122 }
Elem * freed_head_
Definition: hash-list.h:134
static const size_t allocate_block_size_
Definition: hash-list.h:139
std::vector< Elem * > allocated_
Definition: hash-list.h:137
#define KALDI_WARN
Definition: kaldi-error.h:130

Member Function Documentation

HashList< I, T >::Elem * Clear ( )

Clears the hash and gives the head of the current list to the user; ownership is transferred to the user (the user must call Delete() for each element in the list, at his/her leisure).

Definition at line 46 of file hash-list-inl.h.

Referenced by NBestDecoder::Decode(), LatticeBiglmFasterDecoder::DeleteElems(), NBestDecoder::GetNBestLattice(), FasterDecoder::InitDecoding(), LatticeFasterOnlineDecoder::InitDecoding(), LatticeFasterDecoder::InitDecoding(), FasterDecoder::ProcessEmitting(), LatticeFasterOnlineDecoder::ProcessEmitting(), LatticeFasterDecoder::ProcessEmitting(), NBestDecoder::PropagateEmitting(), LatticeFasterOnlineDecoder::PruneForwardLinksFinal(), LatticeFasterDecoder::PruneForwardLinksFinal(), kaldi::TestHashList(), FasterDecoder::~FasterDecoder(), LatticeFasterDecoder::~LatticeFasterDecoder(), LatticeFasterOnlineDecoder::~LatticeFasterOnlineDecoder(), and NBestDecoder::~NBestDecoder().

46  {
47  // Clears the hashtable and gives ownership of the currently contained list
48  // to the user.
49  for (size_t cur_bucket = bucket_list_tail_;
50  cur_bucket != static_cast<size_t>(-1);
51  cur_bucket = buckets_[cur_bucket].prev_bucket) {
52  buckets_[cur_bucket].last_elem = NULL; // this is how we indicate "empty".
53  }
54  bucket_list_tail_ = static_cast<size_t>(-1);
55  Elem *ans = list_head_;
56  list_head_ = NULL;
57  return ans;
58 }
std::vector< HashBucket > buckets_
Definition: hash-list.h:132
size_t bucket_list_tail_
Definition: hash-list.h:128
Elem * list_head_
Definition: hash-list.h:127
void Delete ( Elem e)
inline

Think of this like delete().

It is to be called for each Elem in turn after you "obtained ownership" by doing Clear(). This is not the opposite of. Insert, it is the opposite of New. It's really a memory operation.

Definition at line 66 of file hash-list-inl.h.

References HashList< I, T >::Elem::tail.

Referenced by FasterDecoder::ClearToks(), BiglmFasterDecoder::ClearToks(), NBestDecoder::ClearToks(), LatticeFasterOnlineDecoder::DeleteElems(), LatticeFasterDecoder::DeleteElems(), LatticeBiglmFasterDecoder::DeleteElems(), NBestDecoder::GetNBestLattice(), FasterDecoder::ProcessEmitting(), LatticeFasterOnlineDecoder::ProcessEmitting(), LatticeFasterDecoder::ProcessEmitting(), NBestDecoder::PropagateEmitting(), and kaldi::TestHashList().

66  {
67  e->tail = freed_head_;
68  freed_head_ = e;
69 }
Elem * freed_head_
Definition: hash-list.h:134
HashList< I, T >::Elem * Find ( key)
inline

Find tries to find this element in the current list using the hashtable.

It returns NULL if not present. The Elem it returns is not owned by the user, it is part of the internal list owned by this object, but the user is free to modify the "val" element.

Definition at line 72 of file hash-list-inl.h.

References HashList< I, T >::HashBucket::last_elem, HashList< I, T >::HashBucket::prev_bucket, and HashList< I, T >::Elem::tail.

Referenced by LatticeFasterOnlineDecoder::FindOrAddToken(), LatticeFasterDecoder::FindOrAddToken(), NBestDecoder::GetNBestLattice(), FasterDecoder::ProcessEmitting(), FasterDecoder::ProcessNonemitting(), LatticeFasterOnlineDecoder::ProcessNonemitting(), LatticeFasterDecoder::ProcessNonemitting(), NBestDecoder::PropagateEmitting(), NBestDecoder::PropagateEpsilon(), and kaldi::TestHashList().

72  {
73  size_t index = (static_cast<size_t>(key) % hash_size_);
74  HashBucket &bucket = buckets_[index];
75  if (bucket.last_elem == NULL) {
76  return NULL; // empty bucket.
77  } else {
78  Elem *head = (bucket.prev_bucket == static_cast<size_t>(-1) ?
79  list_head_ :
80  buckets_[bucket.prev_bucket].last_elem->tail),
81  *tail = bucket.last_elem->tail;
82  for (Elem *e = head; e != tail; e = e->tail)
83  if (e->key == key) return e;
84  return NULL; // Not found.
85  }
86 }
size_t hash_size_
Definition: hash-list.h:130
std::vector< HashBucket > buckets_
Definition: hash-list.h:132
Elem * list_head_
Definition: hash-list.h:127
const HashList< I, T >::Elem * GetList ( ) const

Gives the head of the current list to the user.

Ownership retained in the class. Caution: in December 2013 the return type was changed to const Elem* and this function was made const. You may need to change some types of local Elem* variables to const if this produces compilation errors.

Definition at line 61 of file hash-list-inl.h.

Referenced by LatticeFasterOnlineDecoder::ComputeFinalCosts(), LatticeFasterDecoder::ComputeFinalCosts(), FasterDecoder::GetBestPath(), FasterDecoder::ProcessNonemitting(), LatticeFasterOnlineDecoder::ProcessNonemitting(), LatticeFasterDecoder::ProcessNonemitting(), NBestDecoder::PropagateEpsilon(), FasterDecoder::ReachedFinal(), NBestDecoder::ReachedFinal(), and kaldi::TestHashList().

61  {
62  return list_head_;
63 }
Elem * list_head_
Definition: hash-list.h:127
void Insert ( key,
val 
)
inline

Insert inserts a new element into the hashtable/stored list.

By calling this, the user asserts that it is not already present (e.g. Find was called and returned NULL). With current code, calling this if an element already exists will result in duplicate elements in the structure, and Find() will find the first one that was added. [but we don't guarantee this behavior].

Definition at line 126 of file hash-list-inl.h.

References KALDI_ASSERT, HashList< I, T >::Elem::key, HashList< I, T >::HashBucket::last_elem, HashList< I, T >::HashBucket::prev_bucket, HashList< I, T >::Elem::tail, and HashList< I, T >::Elem::val.

Referenced by NBestDecoder::Decode(), LatticeFasterOnlineDecoder::FindOrAddToken(), LatticeFasterDecoder::FindOrAddToken(), NBestDecoder::GetNBestLattice(), FasterDecoder::InitDecoding(), LatticeFasterOnlineDecoder::InitDecoding(), LatticeFasterDecoder::InitDecoding(), FasterDecoder::ProcessEmitting(), FasterDecoder::ProcessNonemitting(), NBestDecoder::PropagateEmitting(), NBestDecoder::PropagateEpsilon(), and kaldi::TestHashList().

126  {
127  size_t index = (static_cast<size_t>(key) % hash_size_);
128  HashBucket &bucket = buckets_[index];
129  Elem *elem = New();
130  elem->key = key;
131  elem->val = val;
132 
133  if (bucket.last_elem == NULL) { // Unoccupied bucket. Insert at
134  // head of bucket list (which is tail of regular list, they go in
135  // opposite directions).
136  if (bucket_list_tail_ == static_cast<size_t>(-1)) {
137  // list was empty so this is the first elem.
138  KALDI_ASSERT(list_head_ == NULL);
139  list_head_ = elem;
140  } else {
141  // link in to the chain of Elems
142  buckets_[bucket_list_tail_].last_elem->tail = elem;
143  }
144  elem->tail = NULL;
145  bucket.last_elem = elem;
146  bucket.prev_bucket = bucket_list_tail_;
147  bucket_list_tail_ = index;
148  } else {
149  // Already-occupied bucket. Insert at tail of list of elements within
150  // the bucket.
151  elem->tail = bucket.last_elem->tail;
152  bucket.last_elem->tail = elem;
153  bucket.last_elem = elem;
154  }
155 }
size_t hash_size_
Definition: hash-list.h:130
std::vector< HashBucket > buckets_
Definition: hash-list.h:132
size_t bucket_list_tail_
Definition: hash-list.h:128
Elem * New()
This should probably not be needed to be called directly by the user.
Definition: hash-list-inl.h:89
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
Elem * list_head_
Definition: hash-list.h:127
void InsertMore ( key,
val 
)
inline

Insert inserts another element with same key into the hashtable/ stored list.

By calling this, the user asserts that one element with that key is already present. We insert it that way, that all elements with the same key follow each other. Find() will return the first one of the elements with the same key.

Definition at line 158 of file hash-list-inl.h.

References KALDI_ASSERT, HashList< I, T >::Elem::key, HashList< I, T >::HashBucket::last_elem, HashList< I, T >::HashBucket::prev_bucket, HashList< I, T >::Elem::tail, and HashList< I, T >::Elem::val.

Referenced by NBestDecoder::TokenStore::CombineN().

158  {
159  size_t index = (static_cast<size_t>(key) % hash_size_);
160  HashBucket &bucket = buckets_[index];
161  Elem *elem = New();
162  elem->key = key;
163  elem->val = val;
164 
165  KALDI_ASSERT(bucket.last_elem != NULL); // assume one element is already here
166  if (bucket.last_elem->key == key) { // standard behavior: add as last element
167  elem->tail = bucket.last_elem->tail;
168  bucket.last_elem->tail = elem;
169  bucket.last_elem = elem;
170  return;
171  }
172  Elem *e = (bucket.prev_bucket == static_cast<size_t>(-1) ?
173  list_head_ : buckets_[bucket.prev_bucket].last_elem->tail);
174  // find place to insert in linked list
175  while (e != bucket.last_elem->tail && e->key != key) e = e->tail;
176  KALDI_ASSERT(e->key == key); // not found? - should not happen
177  elem->tail = e->tail;
178  e->tail = elem;
179 }
size_t hash_size_
Definition: hash-list.h:130
std::vector< HashBucket > buckets_
Definition: hash-list.h:132
Elem * New()
This should probably not be needed to be called directly by the user.
Definition: hash-list-inl.h:89
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
Elem * list_head_
Definition: hash-list.h:127
HashList< I, T >::Elem * New ( )
inline

This should probably not be needed to be called directly by the user.

Think of it as opposite to Delete();

Definition at line 89 of file hash-list-inl.h.

References rnnlm::i, and HashList< I, T >::Elem::tail.

89  {
90  if (freed_head_) {
91  Elem *ans = freed_head_;
93  return ans;
94  } else {
95  Elem *tmp = new Elem[allocate_block_size_];
96  for (size_t i = 0; i+1 < allocate_block_size_; i++)
97  tmp[i].tail = tmp+i+1;
98  tmp[allocate_block_size_-1].tail = NULL;
99  freed_head_ = tmp;
100  allocated_.push_back(tmp);
101  return this->New();
102  }
103 }
Elem * freed_head_
Definition: hash-list.h:134
static const size_t allocate_block_size_
Definition: hash-list.h:139
std::vector< Elem * > allocated_
Definition: hash-list.h:137
Elem * New()
This should probably not be needed to be called directly by the user.
Definition: hash-list-inl.h:89
void SetSize ( size_t  sz)

SetSize tells the object how many hash buckets to allocate (should typically be at least twice the number of objects we expect to go in the structure, for fastest performance).

It must be called while the hash is empty (e.g. after Clear() or after initializing the object, but before adding anything to the hash.

Definition at line 37 of file hash-list-inl.h.

References KALDI_ASSERT.

Referenced by FasterDecoder::FasterDecoder(), LatticeFasterDecoder::LatticeFasterDecoder(), LatticeFasterOnlineDecoder::LatticeFasterOnlineDecoder(), NBestDecoder::NBestDecoder(), FasterDecoder::PossiblyResizeHash(), LatticeFasterOnlineDecoder::PossiblyResizeHash(), LatticeFasterDecoder::PossiblyResizeHash(), NBestDecoder::PossiblyResizeHash(), and kaldi::TestHashList().

37  {
38  hash_size_ = size;
39  KALDI_ASSERT(list_head_ == NULL &&
40  bucket_list_tail_ == static_cast<size_t>(-1)); // make sure empty.
41  if (size > buckets_.size())
42  buckets_.resize(size, HashBucket(0, NULL));
43 }
size_t hash_size_
Definition: hash-list.h:130
std::vector< HashBucket > buckets_
Definition: hash-list.h:132
size_t bucket_list_tail_
Definition: hash-list.h:128
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:169
Elem * list_head_
Definition: hash-list.h:127
size_t Size ( )
inline

Member Data Documentation

const size_t allocate_block_size_ = 1024
staticprivate

Definition at line 139 of file hash-list.h.

std::vector<Elem*> allocated_
private

Definition at line 137 of file hash-list.h.

size_t bucket_list_tail_
private

Definition at line 128 of file hash-list.h.

std::vector<HashBucket> buckets_
private

Definition at line 132 of file hash-list.h.

Elem* freed_head_
private

Definition at line 134 of file hash-list.h.

size_t hash_size_
private

Definition at line 130 of file hash-list.h.

Referenced by HashList< StateId, Token * >::Size().

Elem* list_head_
private

Definition at line 127 of file hash-list.h.


The documentation for this class was generated from the following files: