// 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>
  inline typename HashList<I, T>::Elem* HashList<I, T>::Insert(I key, T val) {
    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;
  }
  
  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);  // 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;
  }
  
  
  }  // end namespace kaldi
  
  #endif  // KALDI_UTIL_HASH_LIST_INL_H_