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...
 
ElemInsert (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()

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:128
Elem * freed_head_
Definition: hash-list.h:132
size_t bucket_list_tail_
Definition: hash-list.h:126
Elem * list_head_
Definition: hash-list.h:125

◆ ~HashList()

~HashList ( )

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

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

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:132
static const size_t allocate_block_size_
Definition: hash-list.h:137
std::vector< Elem * > allocated_
Definition: hash-list.h:135
#define KALDI_WARN
Definition: kaldi-error.h:150

Member Function Documentation

◆ Clear()

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 LatticeBiglmFasterDecoder::DeleteElems(), FasterDecoder::InitDecoding(), FasterDecoder::ProcessEmitting(), OnlineFasterDecoder::ResetDecoder(), and kaldi::TestHashList().

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:130
size_t bucket_list_tail_
Definition: hash-list.h:126
Elem * list_head_
Definition: hash-list.h:125

◆ Delete()

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.

Referenced by FasterDecoder::ClearToks(), BiglmFasterDecoder::ClearToks(), LatticeBiglmFasterDecoder::DeleteElems(), FasterDecoder::ProcessEmitting(), and kaldi::TestHashList().

66  {
67  e->tail = freed_head_;
68  freed_head_ = e;
69 }
Elem * freed_head_
Definition: hash-list.h:132

◆ Find()

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.

Referenced by 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:128
std::vector< HashBucket > buckets_
Definition: hash-list.h:130
Elem * list_head_
Definition: hash-list.h:125

◆ GetList()

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 OnlineFasterDecoder::FinishTraceBack(), FasterDecoder::GetBestPath(), FasterDecoder::ProcessNonemitting(), FasterDecoder::ReachedFinal(), kaldi::TestHashList(), OnlineFasterDecoder::TracebackNFrames(), and OnlineFasterDecoder::UpdateImmortalToken().

61  {
62  return list_head_;
63 }
Elem * list_head_
Definition: hash-list.h:125

◆ Insert()

HashList< I, T >::Elem * Insert ( key,
val 
)
inline

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

Because element keys in a hashtable are unique, this operation checks whether each inserted element has a key equivalent to the one of an element already in the hashtable. If so, the element is not inserted, returning an pointer to this existing element.

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

Referenced by FasterDecoder::InitDecoding(), FasterDecoder::ProcessEmitting(), FasterDecoder::ProcessNonemitting(), OnlineFasterDecoder::ResetDecoder(), and kaldi::TestHashList().

125  {
126  size_t index = (static_cast<size_t>(key) % hash_size_);
127  HashBucket &bucket = buckets_[index];
128  // Check the element is existing or not.
129  if (bucket.last_elem != NULL) {
130  Elem *head = (bucket.prev_bucket == static_cast<size_t>(-1) ?
131  list_head_ :
132  buckets_[bucket.prev_bucket].last_elem->tail),
133  *tail = bucket.last_elem->tail;
134  for (Elem *e = head; e != tail; e = e->tail)
135  if (e->key == key) return e;
136  }
137 
138  // This is a new element. Insert it.
139  Elem *elem = New();
140  elem->key = key;
141  elem->val = val;
142  if (bucket.last_elem == NULL) { // Unoccupied bucket. Insert at
143  // head of bucket list (which is tail of regular list, they go in
144  // opposite directions).
145  if (bucket_list_tail_ == static_cast<size_t>(-1)) {
146  // list was empty so this is the first elem.
147  KALDI_ASSERT(list_head_ == NULL);
148  list_head_ = elem;
149  } else {
150  // link in to the chain of Elems
151  buckets_[bucket_list_tail_].last_elem->tail = elem;
152  }
153  elem->tail = NULL;
154  bucket.last_elem = elem;
155  bucket.prev_bucket = bucket_list_tail_;
156  bucket_list_tail_ = index;
157  } else {
158  // Already-occupied bucket. Insert at tail of list of elements within
159  // the bucket.
160  elem->tail = bucket.last_elem->tail;
161  bucket.last_elem->tail = elem;
162  bucket.last_elem = elem;
163  }
164  return elem;
165 }
size_t hash_size_
Definition: hash-list.h:128
std::vector< HashBucket > buckets_
Definition: hash-list.h:130
size_t bucket_list_tail_
Definition: hash-list.h:126
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:185
Elem * list_head_
Definition: hash-list.h:125

◆ InsertMore()

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 168 of file hash-list-inl.h.

168  {
169  size_t index = (static_cast<size_t>(key) % hash_size_);
170  HashBucket &bucket = buckets_[index];
171  Elem *elem = New();
172  elem->key = key;
173  elem->val = val;
174 
175  KALDI_ASSERT(bucket.last_elem != NULL); // assume one element is already here
176  if (bucket.last_elem->key == key) { // standard behavior: add as last element
177  elem->tail = bucket.last_elem->tail;
178  bucket.last_elem->tail = elem;
179  bucket.last_elem = elem;
180  return;
181  }
182  Elem *e = (bucket.prev_bucket == static_cast<size_t>(-1) ?
183  list_head_ : buckets_[bucket.prev_bucket].last_elem->tail);
184  // find place to insert in linked list
185  while (e != bucket.last_elem->tail && e->key != key) e = e->tail;
186  KALDI_ASSERT(e->key == key); // not found? - should not happen
187  elem->tail = e->tail;
188  e->tail = elem;
189 }
size_t hash_size_
Definition: hash-list.h:128
std::vector< HashBucket > buckets_
Definition: hash-list.h:130
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:185
Elem * list_head_
Definition: hash-list.h:125

◆ New()

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.

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:132
static const size_t allocate_block_size_
Definition: hash-list.h:137
std::vector< Elem * > allocated_
Definition: hash-list.h:135
Elem * New()
This should probably not be needed to be called directly by the user.
Definition: hash-list-inl.h:89

◆ SetSize()

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.

Referenced by FasterDecoder::FasterDecoder(), FasterDecoder::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:128
std::vector< HashBucket > buckets_
Definition: hash-list.h:130
size_t bucket_list_tail_
Definition: hash-list.h:126
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:185
Elem * list_head_
Definition: hash-list.h:125

◆ Size()

size_t Size ( )
inline

Returns current number of hash buckets.

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

Referenced by FasterDecoder::PossiblyResizeHash().

113 { return hash_size_; }
size_t hash_size_
Definition: hash-list.h:128

Member Data Documentation

◆ allocate_block_size_

const size_t allocate_block_size_ = 1024
staticprivate

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

◆ allocated_

std::vector<Elem*> allocated_
private

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

◆ bucket_list_tail_

size_t bucket_list_tail_
private

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

◆ buckets_

std::vector<HashBucket> buckets_
private

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

◆ freed_head_

Elem* freed_head_
private

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

◆ hash_size_

size_t hash_size_
private

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

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

◆ list_head_

Elem* list_head_
private

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


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