Program Listing for File compare_and_hash_utils.h

↰ Return to documentation for file (include/shad/data_structures/compare_and_hash_utils.h)

//===------------------------------------------------------------*- C++ -*-===//
//
//                                     SHAD
//
//      The Scalable High-performance Algorithms and Data Structure Library
//
//===----------------------------------------------------------------------===//
//
// Copyright 2018 Battelle Memorial Institute
//
// 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
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations
// under the License.
//
//===----------------------------------------------------------------------===//

#ifndef INCLUDE_SHAD_DATA_STRUCTURES_COMPARE_AND_HASH_UTILS_H_
#define INCLUDE_SHAD_DATA_STRUCTURES_COMPARE_AND_HASH_UTILS_H_

#include <algorithm>
#include <cstdint>
#include <cstring>
#include <functional>
#include <type_traits>
#include <vector>

#include "shad/core/type_traits.h"

namespace shad {

template <typename KeyTy>
class MemCmp {
 public:
  bool operator()(const KeyTy *first, const KeyTy *second) const {
    return std::memcmp(first, second, sizeof(KeyTy));
  }
};

template <typename KeyTy>
class MemCmp<std::vector<KeyTy>> {
 public:
  bool operator()(const std::vector<KeyTy> *first,
                  const std::vector<KeyTy> *sec) const {
    return !std::equal(first->begin(), first->end(), sec->begin());
  }
};

template <typename KeyTy>
uint64_t HashFunction(const KeyTy &key, uint8_t seed) {
  constexpr size_t keyWords = sizeof(KeyTy) / sizeof(uint8_t);

  uint8_t const *const key_uint8 = reinterpret_cast<uint8_t const *const>(&key);

  uint64_t hash = 0;
  for (size_t i = 0; i < keyWords; ++i) {
    hash += key_uint8[i] + seed;  // NOLINT
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }
  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);
  return hash;
}

template <typename KeyTy>
uint64_t HashFunction(const std::vector<KeyTy> &key, uint8_t seed) {
  uint16_t const *const key_uint16 =
      reinterpret_cast<uint16_t const *const>(key.data());

  uint64_t hash = 0;
  size_t keyWords = (sizeof(KeyTy) * key.size()) / sizeof(uint16_t);

  for (size_t i = 0; i < keyWords; ++i) {
    hash += key_uint16[i] + seed;
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }
  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);
  return hash;
}

template <typename Key, bool=is_std_hashable<Key>::value>
struct hash {
  size_t operator()(const Key &k) const noexcept { return hasher(k); }
  std::hash<Key> hasher;
};

template <typename Key>
struct hash<Key, false> {
  size_t operator()(const Key &k) const noexcept {
    return shad::HashFunction(k, 0u);
  }
};

}  // namespace shad

#endif  // INCLUDE_SHAD_DATA_STRUCTURES_COMPARE_AND_HASH_UTILS_H_