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...
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). More...
const Elem *	GetList () const
	Gives the head of the current list to the user. More...
void	Delete (Elem *e)
	Think of this like delete(). More...
Elem *	New ()
	This should probably not be needed to be called directly by the user. More...
Elem *	Find (I key)
	Find tries to find this element in the current list using the hashtable. More...
Elem *	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
Elem *	list_head_
size_t	bucket_list_tail_
size_t	hash_size_
std::vector< HashBucket >	buckets_
Elem *	freed_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.

                                                    {
  list_head_ = NULL;
  bucket_list_tail_ = static_cast<size_t>(-1);  // invalid.
  hash_size_ = 0;
  freed_head_ = NULL;
}

~HashList()

~HashList

(

)

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

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

                          {
  // 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";
  }
}

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

                                                   {
  // 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;
}

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

                                          {
  e->tail = freed_head_;
  freed_head_ = e;
}

Find()

HashList< I, T >::Elem * Find ( I  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().

                                                              {
  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.
  }
}

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

                                                                 {
  return list_head_;
}

Insert()

HashList< I, T >::Elem * Insert ( I  key, T  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().

                                                                       {
  size_t index = (static_cast<size_t>(key) % hash_size_);
  HashBucket &bucket = buckets_[index];
  // Check the element is existing or not.
  if (bucket.last_elem != NULL) {
    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;
  }

  // This is a new element. Insert it.
  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;
  }
  return elem;
}

InsertMore()

void InsertMore ( I  key, T  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.

                                            {
  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);  // assume one element is already here
  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;
}

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.

                                                        {
  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();
  }
}

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

                                                                   {
  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));
}

Size()

size_t Size ( )

inline

Returns current number of hash buckets.

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

Referenced by FasterDecoder::PossiblyResizeHash().

{ return hash_size_; }

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:

• util/hash-list.h
• util/hash-list-inl.h