// ----------------------------------------------------------------------
// Copyright (c) 2016, Steven Gregory Popovitch - greg7mdp@gmail.com
// All rights reserved.
//
// Code derived from Boost libraries.
// Boost software licence reproduced below.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * The name of Steven Gregory Popovitch may not be used to
// endorse or promote products derived from this software without
// specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
// ----------------------------------------------------------------------

// ---------------------------------------------------------------------------
// Boost Software License - Version 1.0 - August 17th, 2003
//
// Permission is hereby granted, free of charge, to any person or organization
// obtaining a copy of the software and accompanying documentation covered by
// this license (the "Software") to use, reproduce, display, distribute,
// execute, and transmit the Software, and to prepare derivative works of the
// Software, and to permit third-parties to whom the Software is furnished to
// do so, all subject to the following:
//
// The copyright notices in the Software and this entire statement, including
// the above license grant, this restriction and the following disclaimer,
// must be included in all copies of the Software, in whole or in part, and
// all derivative works of the Software, unless such copies or derivative
// works are solely in the form of machine-executable object code generated by
// a source language processor.
//
// 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, TITLE AND NON-INFRINGEMENT. IN NO EVENT
// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.
// ---------------------------------------------------------------------------

//  ----------------------------------------------------------------------
//                  H A S H    F U N C T I O N S
//                  ----------------------------
//
//    Implements spp::spp_hash() and spp::hash_combine()
//  ----------------------------------------------------------------------

#if !defined(spp_utils_h_guard_)
#define spp_utils_h_guard_

#if defined(_MSC_VER)
#if (_MSC_VER >= 1600)  // vs2010 (1900 is vs2015)
#include <functional>
#define SPP_HASH_CLASS std::hash
#else
#include <hash_map>
#define SPP_HASH_CLASS stdext::hash_compare
#endif
#if (_MSC_FULL_VER < 190021730)
#define SPP_NO_CXX11_NOEXCEPT
#endif
#elif defined __clang__
#if __has_feature(cxx_noexcept) || \
    defined(SPP_CXX11)  // define SPP_CXX11 if your compiler has <functional>
#include <functional>
#define SPP_HASH_CLASS std::hash
#else
#include <tr1/functional>
#define SPP_HASH_CLASS std::tr1::hash
#endif

#if !__has_feature(cxx_noexcept)
#define SPP_NO_CXX11_NOEXCEPT
#endif
#elif defined(__GNUC__)
#if defined(__GXX_EXPERIMENTAL_CXX0X__) || (__cplusplus >= 201103L)
#include <functional>
#define SPP_HASH_CLASS std::hash

#if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100) < 40600
#define SPP_NO_CXX11_NOEXCEPT
#endif
#else
#include <tr1/unordered_map>
#define SPP_HASH_CLASS std::tr1::hash
#define SPP_NO_CXX11_NOEXCEPT
#endif
#else
#include <functional>
#define SPP_HASH_CLASS std::hash
#endif

#ifdef SPP_NO_CXX11_NOEXCEPT
#define SPP_NOEXCEPT
#else
#define SPP_NOEXCEPT noexcept
#endif

#ifdef SPP_NO_CXX11_CONSTEXPR
#define SPP_CONSTEXPR
#else
#define SPP_CONSTEXPR constexpr
#endif

#ifdef SPP_NO_CXX14_CONSTEXPR
#define SPP_CXX14_CONSTEXPR
#else
#define SPP_CXX14_CONSTEXPR constexpr
#endif

#define SPP_INLINE

#ifndef spp_
#define spp_ spp
#endif

namespace spp_ {

template <class T>
T spp_min(T a, T b) {
  return a < b ? a : b;
}
template <class T>
T spp_max(T a, T b) {
  return a >= b ? a : b;
}

template <class T>
struct spp_hash {
  SPP_INLINE size_t operator()(const T &__v) const SPP_NOEXCEPT {
    SPP_HASH_CLASS<T> hasher;
    return hasher(__v);
  }
};

template <class T>
struct spp_hash<T *> {
  static size_t spp_log2(size_t val) SPP_NOEXCEPT {
    size_t res = 0;
    while (val > 1) {
      val >>= 1;
      res++;
    }
    return res;
  }

  SPP_INLINE size_t operator()(const T *__v) const SPP_NOEXCEPT {
    static const size_t shift =
        3;  // spp_log2(1 + sizeof(T)); // T might be incomplete!
    const uintptr_t i = (const uintptr_t)__v;
    return static_cast<size_t>(i >> shift);
  }
};

// from http://burtleburtle.net/bob/hash/integer.html
// fast and efficient for power of two table sizes where we always
// consider the last bits.
// ---------------------------------------------------------------
inline size_t spp_mix_32(uint32_t a) {
  a = a ^ (a >> 4);
  a = (a ^ 0xdeadbeef) + (a << 5);
  a = a ^ (a >> 11);
  return static_cast<size_t>(a);
}

// More thorough scrambling as described in
// https://gist.github.com/badboy/6267743
// ----------------------------------------
inline size_t spp_mix_64(uint64_t a) {
  a = (~a) + (a << 21);  // a = (a << 21) - a - 1;
  a = a ^ (a >> 24);
  a = (a + (a << 3)) + (a << 8);  // a * 265
  a = a ^ (a >> 14);
  a = (a + (a << 2)) + (a << 4);  // a * 21
  a = a ^ (a >> 28);
  a = a + (a << 31);
  return static_cast<size_t>(a);
}

template <class ArgumentType, class ResultType>
struct spp_unary_function {
  typedef ArgumentType argument_type;
  typedef ResultType result_type;
};

template <>
struct spp_hash<bool> : public spp_unary_function<bool, size_t> {
  SPP_INLINE size_t operator()(bool __v) const SPP_NOEXCEPT {
    return static_cast<size_t>(__v);
  }
};

template <>
struct spp_hash<char> : public spp_unary_function<char, size_t> {
  SPP_INLINE size_t operator()(char __v) const SPP_NOEXCEPT {
    return static_cast<size_t>(__v);
  }
};

template <>
struct spp_hash<signed char> : public spp_unary_function<signed char, size_t> {
  SPP_INLINE size_t operator()(signed char __v) const SPP_NOEXCEPT {
    return static_cast<size_t>(__v);
  }
};

template <>
struct spp_hash<unsigned char>
    : public spp_unary_function<unsigned char, size_t> {
  SPP_INLINE size_t operator()(unsigned char __v) const SPP_NOEXCEPT {
    return static_cast<size_t>(__v);
  }
};

template <>
struct spp_hash<wchar_t> : public spp_unary_function<wchar_t, size_t> {
  SPP_INLINE size_t operator()(wchar_t __v) const SPP_NOEXCEPT {
    return static_cast<size_t>(__v);
  }
};

template <>
struct spp_hash<int16_t> : public spp_unary_function<int16_t, size_t> {
  SPP_INLINE size_t operator()(int16_t __v) const SPP_NOEXCEPT {
    return spp_mix_32(static_cast<uint32_t>(__v));
  }
};

template <>
struct spp_hash<uint16_t> : public spp_unary_function<uint16_t, size_t> {
  SPP_INLINE size_t operator()(uint16_t __v) const SPP_NOEXCEPT {
    return spp_mix_32(static_cast<uint32_t>(__v));
  }
};

template <>
struct spp_hash<int32_t> : public spp_unary_function<int32_t, size_t> {
  SPP_INLINE size_t operator()(int32_t __v) const SPP_NOEXCEPT {
    return spp_mix_32(static_cast<uint32_t>(__v));
  }
};

template <>
struct spp_hash<uint32_t> : public spp_unary_function<uint32_t, size_t> {
  SPP_INLINE size_t operator()(uint32_t __v) const SPP_NOEXCEPT {
    return spp_mix_32(static_cast<uint32_t>(__v));
  }
};

template <>
struct spp_hash<int64_t> : public spp_unary_function<int64_t, size_t> {
  SPP_INLINE size_t operator()(int64_t __v) const SPP_NOEXCEPT {
    return spp_mix_64(static_cast<uint64_t>(__v));
  }
};

template <>
struct spp_hash<uint64_t> : public spp_unary_function<uint64_t, size_t> {
  SPP_INLINE size_t operator()(uint64_t __v) const SPP_NOEXCEPT {
    return spp_mix_64(static_cast<uint64_t>(__v));
  }
};

template <>
struct spp_hash<float> : public spp_unary_function<float, size_t> {
  SPP_INLINE size_t operator()(float __v) const SPP_NOEXCEPT {
    // -0.0 and 0.0 should return same hash
    uint32_t *as_int = reinterpret_cast<uint32_t *>(&__v);
    return (__v == 0) ? static_cast<size_t>(0) : spp_mix_32(*as_int);
  }
};

template <>
struct spp_hash<double> : public spp_unary_function<double, size_t> {
  SPP_INLINE size_t operator()(double __v) const SPP_NOEXCEPT {
    // -0.0 and 0.0 should return same hash
    uint64_t *as_int = reinterpret_cast<uint64_t *>(&__v);
    return (__v == 0) ? static_cast<size_t>(0) : spp_mix_64(*as_int);
  }
};

template <class T, int sz>
struct Combiner {
  inline void operator()(T &seed, T value);
};

template <class T>
struct Combiner<T, 4> {
  inline void operator()(T &seed, T value) {
    seed ^= value + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
};

template <class T>
struct Combiner<T, 8> {
  inline void operator()(T &seed, T value) {
    seed ^= value + T(0xc6a4a7935bd1e995) + (seed << 6) + (seed >> 2);
  }
};

template <class T>
inline void hash_combine(std::size_t &seed, T const &v) {
  spp_::spp_hash<T> hasher;
  Combiner<std::size_t, sizeof(std::size_t)> combiner;

  combiner(seed, hasher(v));
}

static inline uint32_t s_spp_popcount_default(uint32_t i) SPP_NOEXCEPT {
  i = i - ((i >> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
  return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

static inline uint32_t s_spp_popcount_default(uint64_t x) SPP_NOEXCEPT {
  const uint64_t m1 = uint64_t(0x5555555555555555);  // binary: 0101...
  const uint64_t m2 = uint64_t(0x3333333333333333);  // binary: 00110011..
  const uint64_t m4 =
      uint64_t(0x0f0f0f0f0f0f0f0f);  // binary:  4 zeros,  4 ones ...
  const uint64_t h01 = uint64_t(
      0x0101010101010101);  // the sum of 256 to the power of 0,1,2,3...

  x -= (x >> 1) & m1;              // put count of each 2 bits into those 2 bits
  x = (x & m2) + ((x >> 2) & m2);  // put count of each 4 bits into those 4 bits
  x = (x + (x >> 4)) & m4;         // put count of each 8 bits into those 8 bits
  return (x * h01) >>
         56;  // returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24)+...
}

#ifdef __APPLE__
static inline uint32_t count_trailing_zeroes(size_t v) SPP_NOEXCEPT {
  size_t x = (v & -v) - 1;
  // sadly sizeof() required to build on macos
  return sizeof(size_t) == 8 ? s_spp_popcount_default((uint64_t)x)
                             : s_spp_popcount_default((uint32_t)x);
}

static inline uint32_t s_popcount(size_t v) SPP_NOEXCEPT {
  // sadly sizeof() required to build on macos
  return sizeof(size_t) == 8 ? s_spp_popcount_default((uint64_t)v)
                             : s_spp_popcount_default((uint32_t)v);
}
#else
static inline uint32_t count_trailing_zeroes(size_t v) SPP_NOEXCEPT {
  return s_spp_popcount_default((v & -(intptr_t)v) - 1);
}

static inline uint32_t s_popcount(size_t v) SPP_NOEXCEPT {
  return s_spp_popcount_default(v);
}
#endif

// -----------------------------------------------------------
// -----------------------------------------------------------
template <class T>
class libc_allocator {
 public:
  typedef T value_type;
  typedef T *pointer;
  typedef ptrdiff_t difference_type;
  typedef const T *const_pointer;
  typedef size_t size_type;

  libc_allocator() {}
  libc_allocator(const libc_allocator &) {}

  template <class U>
  libc_allocator(const libc_allocator<U> &) {}

  libc_allocator &operator=(const libc_allocator &) { return *this; }

  template <class U>
  libc_allocator &operator=(const libc_allocator<U> &) {
    return *this;
  }

#ifndef SPP_NO_CXX11_RVALUE_REFERENCES
  libc_allocator(libc_allocator &&) {}
  libc_allocator &operator=(libc_allocator &&) { return *this; }
#endif

  pointer allocate(size_t n, const_pointer /* unused */ = 0) {
    pointer res = static_cast<pointer>(malloc(n * sizeof(T)));
    if (!res) throw std::bad_alloc();
    return res;
  }

  void deallocate(pointer p, size_t /* unused */) { free(p); }

  pointer reallocate(pointer p, size_t new_size) {
    pointer res = static_cast<pointer>(realloc(p, new_size * sizeof(T)));
    if (!res) throw std::bad_alloc();
    return res;
  }

  // extra API to match spp_allocator interface
  pointer reallocate(pointer p, size_t /* old_size */, size_t new_size) {
    return static_cast<pointer>(realloc(p, new_size * sizeof(T)));
  }

  size_type max_size() const {
    return static_cast<size_type>(-1) / sizeof(value_type);
  }

  void construct(pointer p, const value_type &val) { new (p) value_type(val); }

  void destroy(pointer p) { p->~value_type(); }

  template <class U>
  struct rebind {
    typedef spp_::libc_allocator<U> other;
  };
};

// forward declaration
// -------------------
template <class T>
class spp_allocator;

}  // namespace spp_

template <class T>
inline bool operator==(const spp_::libc_allocator<T> &,
                       const spp_::libc_allocator<T> &) {
  return true;
}

template <class T>
inline bool operator!=(const spp_::libc_allocator<T> &,
                       const spp_::libc_allocator<T> &) {
  return false;
}

#endif  // spp_utils_h_guard_
