runtime/vm/hash_map.h

// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

#ifndef VM_HASH_MAP_H_
#define VM_HASH_MAP_H_

namespace dart {

template <typename T>
class DirectChainedHashMap: public ValueObject {
 public:
  DirectChainedHashMap() : array_size_(0),
                           lists_size_(0),
                           count_(0),
                           array_(NULL),
                           lists_(NULL),
                           free_list_head_(kNil) {
    ResizeLists(kInitialSize);
    Resize(kInitialSize);
  }

  DirectChainedHashMap(const DirectChainedHashMap& other);

  void Insert(T value);

  T Lookup(T value) const;

  bool IsEmpty() const { return count_ == 0; }

 private:
  // A linked list of T values.  Stored in arrays.
  struct HashMapListElement {
    T value;
    intptr_t next;  // Index in the array of the next list element.
  };
  static const intptr_t kNil = -1;  // The end of a linked list

  // Must be a power of 2.
  static const intptr_t kInitialSize = 16;

  void Resize(intptr_t new_size);
  void ResizeLists(intptr_t new_size);
  uword Bound(uword value) const { return value & (array_size_ - 1); }

  intptr_t array_size_;
  intptr_t lists_size_;
  intptr_t count_;  // The number of values stored in the HashMap.
  HashMapListElement* array_;  // Primary store - contains the first value
  // with a given hash.  Colliding elements are stored in linked lists.
  HashMapListElement* lists_;  // The linked lists containing hash collisions.
  intptr_t free_list_head_;  // Unused elements in lists_ are on the free list.
};


template <typename T>
T DirectChainedHashMap<T>::Lookup(T value) const {
  uword hash = static_cast<uword>(value->Hashcode());
  uword pos = Bound(hash);
  if (array_[pos].value != NULL) {
    if (array_[pos].value->Equals(value)) return array_[pos].value;
    intptr_t next = array_[pos].next;
    while (next != kNil) {
      if (lists_[next].value->Equals(value)) return lists_[next].value;
      next = lists_[next].next;
    }
  }
  return NULL;
}


template <typename T>
DirectChainedHashMap<T>::DirectChainedHashMap(const DirectChainedHashMap& other)
  : ValueObject(),
    array_size_(other.array_size_),
    lists_size_(other.lists_size_),
    count_(other.count_),
    array_(Isolate::Current()->current_zone()->
           Alloc<HashMapListElement>(other.array_size_)),
    lists_(Isolate::Current()->current_zone()->
           Alloc<HashMapListElement>(other.lists_size_)),
    free_list_head_(other.free_list_head_) {
  memmove(array_, other.array_, array_size_ * sizeof(HashMapListElement));
  memmove(lists_, other.lists_, lists_size_ * sizeof(HashMapListElement));
}


template <typename T>
void DirectChainedHashMap<T>::Resize(intptr_t new_size) {
  ASSERT(new_size > count_);
  // Hashing the values into the new array has no more collisions than in the
  // old hash map, so we can use the existing lists_ array, if we are careful.

  // Make sure we have at least one free element.
  if (free_list_head_ == kNil) {
    ResizeLists(lists_size_ << 1);
  }

  HashMapListElement* new_array =
      Isolate::Current()->current_zone()->Alloc<HashMapListElement>(new_size);
  memset(new_array, 0, sizeof(HashMapListElement) * new_size);

  HashMapListElement* old_array = array_;
  intptr_t old_size = array_size_;

  intptr_t old_count = count_;
  count_ = 0;
  array_size_ = new_size;
  array_ = new_array;

  if (old_array != NULL) {
    // Iterate over all the elements in lists, rehashing them.
    for (intptr_t i = 0; i < old_size; ++i) {
      if (old_array[i].value != NULL) {
        intptr_t current = old_array[i].next;
        while (current != kNil) {
          Insert(lists_[current].value);
          intptr_t next = lists_[current].next;
          lists_[current].next = free_list_head_;
          free_list_head_ = current;
          current = next;
        }
        // Rehash the directly stored value.
        Insert(old_array[i].value);
      }
    }
  }
  USE(old_count);
  ASSERT(count_ == old_count);
}


template <typename T>
void DirectChainedHashMap<T>::ResizeLists(intptr_t new_size) {
  ASSERT(new_size > lists_size_);

  HashMapListElement* new_lists =
      Isolate::Current()->current_zone()->
      Alloc<HashMapListElement>(new_size);
  memset(new_lists, 0, sizeof(HashMapListElement) * new_size);

  HashMapListElement* old_lists = lists_;
  intptr_t old_size = lists_size_;

  lists_size_ = new_size;
  lists_ = new_lists;

  if (old_lists != NULL) {
    memmove(lists_, old_lists, old_size * sizeof(HashMapListElement));
  }
  for (intptr_t i = old_size; i < lists_size_; ++i) {
    lists_[i].next = free_list_head_;
    free_list_head_ = i;
  }
}


template <typename T>
void DirectChainedHashMap<T>::Insert(T value) {
  ASSERT(value != NULL);
  // Resizing when half of the hashtable is filled up.
  if (count_ >= array_size_ >> 1) Resize(array_size_ << 1);
  ASSERT(count_ < array_size_);
  count_++;
  uword pos = Bound(static_cast<uword>(value->Hashcode()));
  if (array_[pos].value == NULL) {
    array_[pos].value = value;
    array_[pos].next = kNil;
  } else {
    if (free_list_head_ == kNil) {
      ResizeLists(lists_size_ << 1);
    }
    intptr_t new_element_pos = free_list_head_;
    ASSERT(new_element_pos != kNil);
    free_list_head_ = lists_[free_list_head_].next;
    lists_[new_element_pos].value = value;
    lists_[new_element_pos].next = array_[pos].next;
    ASSERT(array_[pos].next == kNil || lists_[array_[pos].next].value != NULL);
    array_[pos].next = new_element_pos;
  }
}

}  // namespace dart

#endif  // VM_HASH_MAP_H_