tpl_olhash.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  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 TPL_OLHASH_H
# define TPL_OLHASH_H
 
# include <iostream>
# include <cstddef>
# include <cstdint>
# include <primes.H>
# include <dlink.H>
# include <ahDry.H>
# include <hash-dry.H>
# include <hashDry.H>
# include <hash-fct.H>
# include <ah-errors.H>
# include <ah-concepts.H>
 
using namespace Primes;
 
using namespace Aleph;
 
# ifdef N
# define NBACKUP N
# undef N
# endif
 
# ifdef M
# define MBACKUP M
# undef M
# endif
 
namespace Aleph
{
 
  template <typename Key, class Cmp = Aleph::equal_to<Key>>
    requires EqualityComparator<Cmp, Key>
  class OLhashTable
    : public OhashCommon<OLhashTable<Key, Cmp>, Key>,
      public GenericTraverse<OLhashTable<Key, Cmp>>,
      public LocateFunctions<OLhashTable<Key, Cmp>, Key>,
      public FunctionalMethods<OLhashTable<Key, Cmp>, Key>,
      public EqualToMethod<OLhashTable<Key, Cmp>>,
      public StlAlephIterator<OLhashTable<Key, Cmp>>
  {
    friend class OhashCommon<OLhashTable<Key, Cmp>, Key>;
 
   public:
 
    using Key_Type = Key;
 
    using Item_Type = Key;
 
    using Hash_Fct = std::function<size_t(const Key &)>;
 
    using Hash_Fct_Ptr = size_t (*)(const Key &);
 
    enum Status
    {
      EMPTY, BUSY, DELETED
    };
 
    struct Bucket
    {
      Key key;
      char status = EMPTY;
 
      Bucket() noexcept: status(EMPTY) {}
      void reset() noexcept { status = EMPTY; }
    };
 
    [[nodiscard]] static Bucket *key_to_bucket(Key *rec) noexcept
    {
      // Note: cannot be constexpr due to reinterpret_cast
      const auto base = reinterpret_cast<std::uintptr_t>(rec);
      const auto offset = offsetof(Bucket, key);
      return reinterpret_cast<Bucket *>(base - offset);
    }
 
    Bucket *table = nullptr;
    size_t N = 0;
 
   protected:
 
    size_t len;
    float lower_alpha;
    float upper_alpha;
    Cmp cmp;
 
   private:
 
    Hash_Fct hash_fct;
    bool with_resize;
 
    [[nodiscard]] bool is_valid_bucket(Bucket *bucket) const noexcept
    {
      if (table == nullptr)
        return false;
 
      const auto begin = reinterpret_cast<std::uintptr_t>(&table[0]);
      const auto end   = reinterpret_cast<std::uintptr_t>(&table[len]);
      const auto addr  = reinterpret_cast<std::uintptr_t>(bucket);
 
      if (addr < begin or addr >= end)
        return false;
 
      const auto offset_with_base =
        static_cast<std::ptrdiff_t>(addr - begin);
 
      return offset_with_base % sizeof(*bucket) == 0;
    }
 
   public:
 
    [[nodiscard]] constexpr const Cmp &get_compare() const noexcept { return cmp; }
 
    [[nodiscard]] constexpr Cmp &get_compare() noexcept { return cmp; }
 
   public:
 
    OLhashTable(const size_t l, Hash_Fct hash_f, Cmp cmp_f,
                const float l_alpha, const float u_alpha, const bool resize)
      : table(nullptr), N(0), len(Primes::next_prime(l)),
        lower_alpha(l_alpha), upper_alpha(u_alpha), cmp(cmp_f),
        hash_fct(hash_f), with_resize(resize)
    {
      table = new Bucket[len];
    }
 
    OLhashTable(size_t len, Hash_Fct hash_fct, Hash_Fct, Cmp cmp,
                float lower_alpha, float upper_alpha, bool with_resize)
      : OLhashTable(len, hash_fct, cmp, lower_alpha, upper_alpha, with_resize) {}
 
    using Base = OhashCommon<OLhashTable<Key, Cmp>, Key>;
 
    using Base::contains;
 
    OLhashTable(size_t len = Primes::DefaultPrime,
                Hash_Fct_Ptr hash_fct = Aleph::dft_hash_ptr_fct<Key>,
                Cmp cmp = Cmp(),
                float lower_alpha = hash_default_lower_alpha,
                float upper_alpha = 0.70f,
                bool with_resize = true)
      : OLhashTable(len, Hash_Fct(hash_fct), cmp,
                    lower_alpha, upper_alpha, with_resize) {}
 
    OLhashTable(size_t len, Hash_Fct_Ptr hash_fct, Hash_Fct_Ptr,
                Cmp cmp, float lower_alpha, float upper_alpha, bool with_resize)
      : OLhashTable(len, Hash_Fct(hash_fct), cmp,
                    lower_alpha, upper_alpha, with_resize) {}
 
    OLhashTable(size_t len, Hash_Fct hash_fct, Hash_Fct_Ptr, Cmp cmp,
                float lower_alpha, float upper_alpha, bool with_resize)
      : OLhashTable(len, hash_fct, cmp,
                    lower_alpha, upper_alpha, with_resize) {}
 
    Special_Ctors(OLhashTable, Key);
 
    ~OLhashTable()
    {
      if (table != nullptr)
        delete[] table;
    }
 
    void swap(OLhashTable &other) noexcept
    {
      std::swap(table, other.table);
      std::swap(N, other.N);
      std::swap(len, other.len);
      std::swap(cmp, other.cmp);
      std::swap(hash_fct, other.hash_fct);
      std::swap(lower_alpha, other.lower_alpha);
      std::swap(upper_alpha, other.upper_alpha);
      std::swap(with_resize, other.with_resize);
    }
 
    OLhashTable(const OLhashTable &other)
      : OLhashTable(other.len, other.hash_fct, other.cmp,
                    other.lower_alpha, other.upper_alpha, other.with_resize)
    {
      this->copy_from_table(other);
    }
 
    OLhashTable(OLhashTable &&other) noexcept: OLhashTable(other)
    {
      swap(other);
    }
 
    OLhashTable &operator=(const OLhashTable &other)
    {
      if (this == &other)
        return *this;
 
      if (len > other.N)
        this->clean_table();
      else
        {
          auto *new_table = new Bucket[other.len];
          delete[] table;
          table = new_table;
          N = 0;
          len = other.len;
          hash_fct = other.hash_fct;
          cmp = other.cmp;
          lower_alpha = other.lower_alpha;
          upper_alpha = other.upper_alpha;
        }
 
      this->copy_from_table(other);
 
      return *this;
    }
 
    OLhashTable &operator=(OLhashTable &&other) noexcept
    {
      swap(other);
      return *this;
    }
 
    [[nodiscard]] Key *search(const Key &key) const noexcept
    {
      size_t i = hash_fct(key) % len;
      for (size_t c = 0; c < len; ++c)
        {
          // Prefetch next bucket for better cache performance
          __builtin_prefetch(&table[(i + 1 < len) ? i + 1 : 0], 0, 1);
 
          if (table[i].status == EMPTY) [[unlikely]]
            return nullptr;
 
          if (table[i].status == BUSY and cmp(table[i].key, key)) [[likely]]
            return &table[i].key;
 
          if (++i == len)
            i = 0;
        }
 
      return nullptr; // Key not found
    }
 
   protected:
 
    Bucket *allocate_bucket(const Key &key) noexcept
    {
      Bucket * first_deleted = nullptr;
      size_t i = hash_fct(key) % len;
 
      for (size_t c = 0; c < len; ++c)
        {
          // Prefetch next bucket for better cache performance
          __builtin_prefetch(&table[(i + 1 < len) ? i + 1 : 0], 0, 1);
 
          auto & b = table[i];
          if (b.status == EMPTY) [[likely]]
            {
              Bucket *bucket = first_deleted != nullptr ? first_deleted : &b;
              bucket->status = BUSY;
              ++N;
              return bucket;
            }
          if (b.status == BUSY)
            {
              if (cmp(key, b.key)) [[unlikely]]
                  return nullptr;  // Duplicate
            }
          else // DELETED
            {
              if (first_deleted == nullptr)
                first_deleted = &b;
            }
 
          if (++i == len)
            i = 0;
        }
 
      if (first_deleted != nullptr) [[unlikely]]
        {
          first_deleted->status = BUSY;
          ++N;
          return first_deleted;
        }
 
      return nullptr;
    }
 
    // Allocate a new bucket for storing key. It always returns a
    // pointer to the bucket entry into the table. If the key is
    // already inserted in the table, then second value is true,
    // otherwise, not allocation is done, and false is returned as second
    std::tuple<Bucket *, bool> hard_allocate_bucket(const Key &key) noexcept
    {
      Bucket * first_deleted = nullptr;
      size_t i = hash_fct(key) % len;
 
      for (size_t c = 0; c < len; ++c)
        {
          // Prefetch next bucket for better cache performance
          __builtin_prefetch(&table[(i + 1 < len) ? i + 1 : 0], 0, 1);
 
          auto & b = table[i];
          if (b.status == EMPTY) [[likely]]
            {
              Bucket *bucket = first_deleted != nullptr ? first_deleted : &b;
              bucket->status = BUSY;
              ++N;
              return {bucket, false};
            }
          else if (b.status == BUSY)
            {
              if (cmp(key, b.key))
                return {&b, true};  // Found existing
            }
          else // DELETED
            {
              if (first_deleted == nullptr)
                first_deleted = &b;
            }
 
          if (++i == len)
            i = 0;
        }
 
      if (first_deleted != nullptr) [[unlikely]]
        {
          first_deleted->status = BUSY;
          ++N;
          return {first_deleted, false};
        }
 
      return {nullptr, false};
    }
 
    [[nodiscard]] size_t prev_index(const size_t i) const noexcept
    {
      return (i == 0) ? len - 1 : i - 1;
    }
 
    [[nodiscard]] size_t next_index(const size_t i) const noexcept
    {
      return (i + 1 == len) ? 0 : i + 1;
    }
 
    void cleanup_deleted_chain(size_t idx) noexcept
    {
      // If next bucket is not EMPTY, we must keep this as DELETED
      if (table[next_index(idx)].status != EMPTY)
        return;
 
      // Next is EMPTY, so we can mark this as EMPTY
      table[idx].status = EMPTY;
 
      // Propagate backwards: any DELETED bucket whose next is now EMPTY
      // can also become EMPTY
      size_t prev = prev_index(idx);
      size_t count = 0;
      while (table[prev].status == DELETED and count < len)
        {
          table[prev].status = EMPTY;
          prev = prev_index(prev);
          ++count;
        }
    }
 
    void deallocate_bucket(Bucket *bucket)
    {
      ah_invalid_argument_if(not is_valid_bucket(bucket))
        << "record address is not inside table's range";
 
      ah_domain_error_if(bucket->status != BUSY)
        << "Bucket containing record is not busy";
 
      --N;
      const auto idx = static_cast<size_t>(bucket - &table[0]);
      table[idx].status = DELETED;
      cleanup_deleted_chain(idx);
    }
 
   public:
 
    void remove(const Key &key)
    {
      size_t i = hash_fct(key) % len;
      for (size_t c = 0; c < len; ++c)
        {
          // Prefetch next bucket for better cache performance
          __builtin_prefetch(&table[(i + 1 < len) ? i + 1 : 0], 0, 1);
 
          if (table[i].status == EMPTY) [[unlikely]]
            ah_domain_error() << "Key not in hash table";
 
          if (table[i].status == BUSY and cmp(table[i].key, key)) [[likely]]
            {
              table[i].status = DELETED;
              --N;
              cleanup_deleted_chain(i);
              return;
            }
 
          if (++i == len)
            i = 0;
        }
 
      ah_domain_error() << "Key not in hash table";
    }
 
   OHASH_COMMON(OLhashTable);
 
    using Stats = typename OhashCommon<OLhashTable<Key, Cmp>, Key>::Stats;
 
    [[nodiscard]] Stats stats() const
    {
      DynArray<size_t> lens;
      size_t num_busy = 0;
      size_t num_deleted = 0;
      size_t num_empty = 0;
      size_t max_len = std::numeric_limits<size_t>::min();
      for (size_t i = 0; i < len; ++i)
        switch (table[i].status)
          {
            case BUSY:
              {
                ++num_busy;
                const Key &key = table[i].key;
                size_t i = hash_fct(key) % len;
                size_t count = 1;
 
                while (true)
                  {
                    if (table[i].status == BUSY and cmp(table[i].key, key))
                      break;
                    ++count;
                    if (++i == len)
                      i = 0;
                  }
 
                max_len = std::max(max_len, count);
                update_stat_len(lens, count);
                break;
              }
            case EMPTY:
              ++num_empty;
            update_stat_len(lens, 0);
            break;
            case DELETED:
              ++num_deleted;
            break;
          }
 
      float avg = 0;
      float sum = 0;
      for (size_t i = 0; i < lens.size(); ++i)
        {
          avg += lens(i) * i;
          sum += lens(i);
        }
 
      avg /= sum;
      float var = 0;
      for (size_t i = 0; i < lens.size(); ++i)
        {
          const float s = i - avg;
          var += lens(i) * s * s;
        }
      var /= sum;
 
      Stats stats;
      stats.num_busy = num_busy;
      stats.num_deleted = num_deleted;
      stats.num_empty = num_empty;
      std::swap(lens, stats.lens);
      stats.avg = avg;
      stats.var = var;
      stats.max_len = max_len;
 
      return stats;
    }
  };
 
  template <typename Key, class Cmp = Aleph::equal_to<Key>>
  using SetOLhash = OLhashTable<Key, Cmp>;
 
}
# endif // TPL_OLHASH_H