wf_hash_map_no_delete.h

Go to the documentation of this file.

/*
The MIT License (MIT)

Copyright (c) 2015 University of Central Florida's Computer Software Engineering
Scalable & Secure Systems (CSE - S3) Lab

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
#ifndef TERVEL_CONTAINER_WF_HASH_MAP_WFHM_HASHMAP_H
#define TERVEL_CONTAINER_WF_HASH_MAP_WFHM_HASHMAP_H

#include <stdlib.h>
#include <atomic>
#include <cmath>

// TODO(Steven):
//
// Document code
//
// Implement Progress Assurance.
//
// Test get_position function on keys > 64 bits
// Stronger Correctness Tests
//
namespace tervel {

namespace util {
  int round_to_next_power_of_two(uint64_t value) {
    double val = std::log2(value);
    int int_val = static_cast<int>(val);
    if (int_val < val) {
      int_val++;
    }
    return int_val;
  };
}

namespace containers {
namespace wf {
template<class Key, class Value>
struct default_functor {
  Key hash(Key k) {
    return k;
  }

  bool key_equals(Key a, Key b) {
    return a == b;
  }
};



template< class Key, class Value, class Functor = default_functor<Key, Value> >
class HashMapNoDelete {
 public:
  class ValueAccessor;

  HashMapNoDelete(uint64_t capacity, uint64_t expansion_rate = 3)
    : primary_array_size_(tervel::util::round_to_next_power_of_two(capacity))
    , primary_array_pow_(std::log2(primary_array_size_))
    , secondary_array_size_(std::pow(2, expansion_rate))
    , secondary_array_pow_(expansion_rate)
    , primary_array_(new Location[primary_array_size_]()) {

      size_.store(0);
      for (size_t i = 0; i < primary_array_size_; i++) {
         primary_array_[i].store(nullptr);
      }

   }

  ~HashMapNoDelete() {
    for (size_t i = 0; i < primary_array_size_; i++) {
      Node * temp = primary_array_[i].load();
      if (temp != nullptr) {
        delete temp;
      }
    }
  }  // ~ HashMap



  bool at(Key key, ValueAccessor &va);

  bool insert(Key key, Value value);


  size_t size() {
    return size_.load();
  };


  class ValueAccessor {
   public:
    friend class HashMapNoDelete;
    ValueAccessor()
      : value_(nullptr) {}

    ~ValueAccessor() {}

    Value* value() {
      return value_;
    };

    bool valid() {
      return (value_ != nullptr);
    };

    void reset() {
      value_ = nullptr;
    };

   private:
    void init(Value * value) {
      value_ = value;
    };

    Value * value_;
  };


  uint64_t get_position(Key &key, size_t depth);

  uint64_t max_depth();

  void print_key(Key &key);

 private:
  class Node;
  friend class Node;
  typedef std::atomic<Node *> Location;


  class Node {
   public:
    Node() {}
    virtual ~Node() {}

    virtual bool is_array() = 0;

    virtual bool is_data() = 0;
  };

  class ArrayNode : public Node {
   public:
    explicit ArrayNode(uint64_t len)
      : len_(len)
      , internal_array_(new Location[len]()) {
        for (size_t i = 0; i < len_; i++) {
          internal_array_[i].store(nullptr);
        }
      }

    ~ArrayNode() {
      for (size_t i = 0; i < len_; i++) {
        Node * temp = internal_array_[i].load();
        if (temp != nullptr) {
          delete temp;
        }
      }
    }  // ~ArrayNode


    Location *access(uint64_t pos) {
      assert(pos < len_ && pos >=0);
      return &(internal_array_[pos]);
    }

    bool is_array() {
      return true;
    }

    bool is_data() {
      return false;
    }

   private:
    uint64_t len_;
    std::unique_ptr<Location[]> internal_array_;
  };

  class DataNode : public Node {
   public:
    explicit DataNode(Key k, Value v)
      : key_(k)
      , value_(v) {}

    ~DataNode() { }

    bool is_array() {
      return false;
    }

    bool is_data() {
      return true;
    }

    Key key_;
    Value value_;
  };

  void expand_map(Location * loc, Node * &curr_value, uint64_t next_position);



  const size_t primary_array_size_;
  const size_t primary_array_pow_;
  const size_t secondary_array_size_;
  const size_t secondary_array_pow_;

  std::atomic<uint64_t> size_;

  std::unique_ptr<Location[]> primary_array_;
};  // class wf hash map


template<class Key, class Value, class Functor>
bool HashMapNoDelete<Key, Value, Functor>::
at(Key key, ValueAccessor &va) {
  Functor functor;
  key = functor.hash(key);

  size_t depth = 0;
  uint64_t position = get_position(key, depth);
  Location *loc = &(primary_array_[position]);
  Node *curr_value;

  bool op_res = false;
  while (true) {
    curr_value = loc->load();

    if (curr_value == nullptr) {
      break;
    } else if (curr_value->is_array()) {
      ArrayNode * array_node = reinterpret_cast<ArrayNode *>(curr_value);
      depth++;
      position = get_position(key, depth);
      loc = array_node->access(position);
      continue;
    } else {
      assert(curr_value->is_data());
      DataNode * data_node = reinterpret_cast<DataNode *>(curr_value);

      if (functor.key_equals(data_node->key_, key)) {
        va.init(&(data_node->value_));
        op_res = true;
      }
      break;
    }
  }  // while true

  return op_res;
}  // at


template<class Key, class Value, class Functor>
bool HashMapNoDelete<Key, Value, Functor>::
insert(Key key, Value value) {
  Functor functor;
  key = functor.hash(key);

  DataNode * new_node = new DataNode(key, value);

  size_t depth = 0;
  uint64_t position = get_position(key, depth);
  Location *loc = &(primary_array_[position]);
  Node *curr_value = loc->load();

  bool op_res;
  while (true) {

    if (curr_value == nullptr) {
      if (loc->compare_exchange_strong(curr_value, new_node)) {
        size_.fetch_add(1);
        op_res = true;
        break;
      }
    } else if (curr_value->is_array()) {
      ArrayNode * array_node = reinterpret_cast<ArrayNode *>(curr_value);
      depth++;
      position = get_position(key, depth);
      loc = array_node->access(position);
      curr_value = loc->load();
    } else {  // it is a data node
      assert(curr_value->is_data());
      DataNode * data_node = reinterpret_cast<DataNode *>(curr_value);

      if (functor.key_equals(data_node->key_, key)) {
        op_res = false;
        break;
      } else {
        // Key differs, needs to expand...
        const uint64_t next_position =  get_position(data_node->key_, depth+1);
        expand_map(loc, curr_value, next_position);
      }   // else key differs
    }  // else it is a data node
  }  // while true

  if (!op_res) {
    assert(loc->load() != new_node);
    delete new_node;
  }
  return op_res;
}  // insert


template<class Key, class Value, class Functor>
void  HashMapNoDelete<Key, Value, Functor>::
expand_map(Location * loc, Node * &curr_value, uint64_t next_position) {
  assert(curr_value->is_data());

  ArrayNode * array_node = new ArrayNode(secondary_array_size_);
  array_node->access(next_position)->store(curr_value);
  assert(array_node->is_array());

  if (loc->compare_exchange_strong(curr_value, array_node)) {
    return;
  } else {
    assert(loc->load() != array_node);
    array_node->access(next_position)->store(nullptr);
    delete array_node;
  }
}  // expand

template<class Key, class Value, class Functor>
uint64_t HashMapNoDelete<Key, Value, Functor>::
get_position(Key &key, size_t depth) {
  const uint64_t *long_array = reinterpret_cast<uint64_t *>(&key);
  const size_t max_length = sizeof(Key) / (64 / 8);

  assert(depth <= max_depth());
  if (depth == 0) {
    // We need the first 'primary_array_pow_' bits
    assert(primary_array_pow_ < 64);

    uint64_t position = long_array[0] >> (64 - primary_array_pow_);

    assert(position < primary_array_size_);
    return position;
  } else {
    const int start_bit_offset = (depth-1)*secondary_array_pow_ +
        primary_array_pow_;  // Inclusive
    const int end_bit_offset = (depth)*secondary_array_pow_ +
        primary_array_pow_;   // Not inclusive

    const size_t start_idx = start_bit_offset / 64;
    const size_t start_idx_offset = start_bit_offset % 64;
    const size_t end_idx = end_bit_offset / 64;
    const size_t end_idx_offset = end_bit_offset % 64;

    assert(start_idx == end_idx || start_idx + 1 == end_idx);
    assert(end_idx <= max_length);

    // TODO(steven): add 0 padding to fill extra bits if the bits don't
    // divide evenly.
    if (start_idx == end_idx) {
      uint64_t value = long_array[start_idx];
      value = value << start_idx_offset;
      value = value >> (64 - secondary_array_pow_);

      assert(value < secondary_array_size_);
      return value;
    } else {
      uint64_t value = long_array[start_idx];
      value = value << start_idx_offset;
      value = value >> (64 - secondary_array_pow_ + end_idx_offset);
      value = value << (end_idx_offset);


      uint64_t value2;
      if (end_idx == max_length) {
        value2 = 0;
      } else {
        value2 = long_array[end_idx];
      }
      value2 = value2 >> (64 - end_idx_offset);

      uint64_t position = (value | value2);
      assert(position < secondary_array_size_);
      return position;
    }
  }
}  // get_position

template<class Key, class Value, class Functor>
uint64_t HashMapNoDelete<Key, Value, Functor>::
max_depth() {
  uint64_t max_depth = sizeof(Key)*8;
  max_depth -= primary_array_pow_;
  max_depth = std::ceil(max_depth / secondary_array_pow_);
  max_depth++;

  return max_depth;
}

template<class Key, class Value, class Functor>
void HashMapNoDelete<Key, Value, Functor>::
print_key(Key &key) {
  size_t max_depth_ = max_depth();
  std::cout << "K(" << key << ") :";
  for (size_t i = 0; i <= max_depth_; i++) {
    uint64_t temp = get_position(key, i);
    std::cout << temp << "-";
  }
  std::cout << "\n" << std::endl;
}  // print_key

}  // namespace wf
}  // namespace containers
}  // namespace tervel

#endif  // TERVEL_CONTAINER_WF_HASH_MAP_WFHM_HASHMAP_H