diff options
Diffstat (limited to 'kaldi_io/src/kaldi/util/hash-list-inl.h')
| -rw-r--r-- | kaldi_io/src/kaldi/util/hash-list-inl.h | 183 |
1 files changed, 0 insertions, 183 deletions
diff --git a/kaldi_io/src/kaldi/util/hash-list-inl.h b/kaldi_io/src/kaldi/util/hash-list-inl.h deleted file mode 100644 index 19c2bb6..0000000 --- a/kaldi_io/src/kaldi/util/hash-list-inl.h +++ /dev/null @@ -1,183 +0,0 @@ -// 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 |