hashDry.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 HASHDRY_H
# define HASHDRY_H
 
# include <aleph.H>
# include <tpl_dynArray.H>
# include <ah-errors.H>
 
template <class HashTbl, typename Key>
class OhashCommon
{
  HashTbl * me() { return static_cast<HashTbl*>(this); }
 
  const HashTbl * const_me() const { return static_cast<const HashTbl*>(this); }
 
public:
 
  [[nodiscard]] constexpr float get_lower_alpha() const noexcept { return const_me()->lower_alpha; }
 
  [[nodiscard]] constexpr float get_upper_alpha() const noexcept { return const_me()->upper_alpha; }
 
  void copy_from_table(const HashTbl & other)
  {
    assert(me()->N == 0 and me()->len >= other.N);
    for (long i = 0, c = 0; c < other.N; ++i)
      {
        auto & bucket = other.table[i];
        if (bucket.status != HashTbl::BUSY)
          continue;
 
        (void)me()->insert(bucket.key);
        ++c;
      }
    assert(me()->N == other.N);
  }
 
  void clean_table()
  {
    for (long i = 0; i < me()->len; ++i)
      me()->table[i].reset();
    me()->N = 0;
  }
 
  void check_resize_before_insert()
  {
    // Keep at least one EMPTY bucket as a sentinel.
    if (me()->with_resize and me()->N >= me()->len - 1)
      me()->resize(Primes::next_prime(2 * me()->len));
  }
 
  [[nodiscard]] Key * insert(const Key & key)
  {
    check_resize_before_insert();
    auto bucket = me()->allocate_bucket(key);
    if (bucket == nullptr)
      return nullptr;
 
    bucket->key = key;
 
    return me()->test_resize(bucket, key);
  }
 
  [[nodiscard]] Key * insert(Key && key)
  {
    check_resize_before_insert();
    auto bucket = me()->allocate_bucket(key);
    if (bucket == nullptr)
      return nullptr;
 
    std::swap(bucket->key, key);
 
    return me()->test_resize(bucket, bucket->key);
  }
 
  [[nodiscard]] Key * search_or_insert(const Key & key)
  {
    check_resize_before_insert();
    auto r = me()->hard_allocate_bucket(key);
    auto bucket = get<0>(r);
    if (bucket == nullptr)
      return nullptr;
    if (get<1>(r))
      return &bucket->key;
 
    bucket->key = key;
 
    return me()->test_resize(bucket, bucket->key);
  }
 
  [[nodiscard]] Key * search_or_insert(Key && key)
  {
    check_resize_before_insert();
    auto r = me()->hard_allocate_bucket(key);
    auto bucket = get<0>(r);
    if (bucket == nullptr)
      return nullptr;
    if (get<1>(r))
      return &bucket->key;
 
    std::swap(bucket->key, key);
 
    return me()->test_resize(bucket, bucket->key);
  }
 
  [[nodiscard]] std::pair<Key*, bool> contains_or_insert(const Key & key)
  {
    check_resize_before_insert();
    auto r = me()->hard_allocate_bucket(key);
    auto bucket = get<0>(r);
    if (bucket == nullptr)
      return { nullptr, false };
    if (get<1>(r))
      return { &bucket->key, true };
 
    bucket->key = key;
    auto key_ptr = me()->test_resize(bucket, bucket->key);
 
    return { key_ptr, false };
  }
 
  [[nodiscard]] std::pair<Key*, bool> contains_or_insert(Key && key)
  {
    check_resize_before_insert();
    auto r = me()->hard_allocate_bucket(key);
    auto bucket = get<0>(r);
    if (bucket == nullptr)
      return { nullptr, false };
    if (get<1>(r))
      return { &bucket->key, true };
 
    std::swap(bucket->key, key);
    auto key_ptr = me()->test_resize(bucket, bucket->key);
 
    return { key_ptr, false };
  }
 
  [[nodiscard]] Key * append(const Key & key)
  {
    return this->insert(key);
  }
 
  [[nodiscard]] Key * append(Key && key)
  {
    return this->insert(std::move(key));
  }
 
  [[nodiscard]] constexpr bool has(const Key & key) const noexcept
  {
    return const_me()->search(key) != nullptr;
  }
 
  [[nodiscard]] constexpr bool contains(const Key & key) const noexcept { return has(key); }
 
  [[nodiscard]] Key & find(const Key & key)
  {
    auto key_ptr = me()->search(key);
    ah_domain_error_if(key_ptr == nullptr)
      << "Key not found in hash";
 
    return *key_ptr;
  }
 
  [[nodiscard]] const Key & find(const Key & key) const
  {
    return const_cast<OhashCommon*>(this)->find(key);
  }
 
  const Key & operator [] (const Key & key) const
  {
    return find(key);
  }
 
  const Key & operator [] (const Key & key)
  {
    return *search_or_insert(key);
  }
 
  void remove_ptr(Key * key)
  {
    auto bucket = HashTbl::key_to_bucket(key);
    me()->deallocate_bucket(bucket);
 
    if (me()->with_resize and me()->current_alpha() < me()->lower_alpha)
      resize(Primes::next_prime(me()->len/2 + 1));
  }
 
  size_t resize(size_t new_size)
  {
    assert(me()->len > 0);
 
    if (new_size == 0 or new_size == me()->len)
      return me()->len;
 
    // new_size must leave at least one EMPTY bucket as sentinel
    ah_overflow_error_if(me()->N >= new_size)
      << "New size is not enough for current number of entries";
 
    auto * new_table = new typename HashTbl::Bucket[new_size];
    typename HashTbl::Bucket * old_table = me()->table;
    const size_t old_len = me()->len;
 
    int old_N = me()->N;
 
    me()->table = new_table;
    me()->len   = new_size;
    me()->N     = 0;
 
    for (int i = 0, c = 0; i < old_len and c < old_N; ++i)
      if (old_table[i].status == HashTbl::BUSY)
        {
          Key & key = old_table[i].key;
          auto bucket = me()->allocate_bucket(key);
          std::swap(bucket->key, key);
          ++c;
        }
 
    assert(old_N == me()->N);
 
    delete [] old_table;
 
    return me()->len;
  }
 
  void rehash()
  {
    auto new_table = new typename HashTbl::Bucket [me()->len];
    auto old_table = me()->table;
 
    int old_N = me()->N;
 
    me()->table = new_table;
    me()->N     = 0;
 
    for (int i = 0, c = 0; i < me()->len and c < old_N; ++i)
      if (old_table[i].status == HashTbl::BUSY)
        {
          Key & key = old_table[i].key;
          auto bucket = me()->allocate_bucket(key);
          std::swap(bucket->key, key);
          ++c;
        }
 
    assert(old_N == me()->N);
 
    delete [] old_table;
  }
 
  void empty()
  {
    delete [] me()->table;
    me()->N = 0;
    me()->len = Primes::DefaultPrime;
    me()->table = new typename HashTbl::Bucket [me()->len];
  }
 
  void clear() { empty(); }
 
  [[nodiscard]] constexpr size_t size() const noexcept { return const_me()->N; }
 
  [[nodiscard]] constexpr bool is_empty() const noexcept { return const_me()->N == 0; }
 
  [[nodiscard]] constexpr size_t capacity() const noexcept { return const_me()->len; }
 
  class Iterator
  {
    HashTbl * table_ptr = nullptr;  
    long curr_idx          = 0;     
    long ordinal           = 0;     
 
    [[nodiscard]] bool check() const noexcept
    {
      assert(table_ptr != nullptr);
      return curr_idx >= 0 and curr_idx < static_cast<long>(table_ptr->len) and
        ordinal >= -1 and ordinal <= static_cast<long>(table_ptr->size());
    }
 
    void locate_next_available_entry_ne() noexcept
    {
      assert(check());
      if (++ordinal == table_ptr->size())
        return;
 
      while (table_ptr->table[++curr_idx].status != HashTbl::BUSY);
    }
 
    void locate_prev_available_entry_ne()
    {
      assert(check());
      if (--ordinal == -1)
        return;
 
      while (table_ptr->table[--curr_idx].status != HashTbl::BUSY);
    }
 
    void locate_next_available_entry()
    {
      ah_overflow_error_if(ordinal >= table_ptr->size())
        << "Iterator next() overflow";
      locate_next_available_entry_ne();
    }
 
    void locate_prev_available_entry()
    {
      ah_underflow_error_if(ordinal <= -1)
        << "Iterator next() underflow";
      locate_prev_available_entry_ne();
    }
 
  public:
 
    void reset_first() noexcept
    {
      assert(table_ptr != nullptr);
      curr_idx = 0;
      ordinal = -1;
      if (table_ptr->is_empty())
        {
          curr_idx = table_ptr->len;
          ordinal = 0;
          return;
        }
 
      while (table_ptr->table[curr_idx].status != HashTbl::BUSY)
        ++curr_idx;
 
      ordinal = 0;
      assert(check());
    }
 
    void reset_last() noexcept
    {
      assert(table_ptr != nullptr);
      if (table_ptr->is_empty())
        {
          curr_idx = -1;
          ordinal = -1;
          return;
        }
 
      curr_idx = table_ptr->len - 1;
      while (table_ptr->table[curr_idx].status != HashTbl::BUSY)
        --curr_idx;
 
      ordinal = table_ptr->size() - 1;
      assert(check());
    }
 
    void end() noexcept
    {
      put_itor_at_the_end(*this);
    }
 
    [[nodiscard]] constexpr long get_pos() const noexcept { return ordinal; }
 
    Key & get_curr_ne() noexcept
    {
      assert(table_ptr->table[curr_idx].status == HashTbl::BUSY);
      return table_ptr->table[curr_idx].key;
    }
 
    const Key & get_curr_ne() const noexcept
    {
      return const_cast<Iterator*>(this)->get_curr_ne();
    }
 
    Key & get_curr()
    {
      ah_overflow_error_if(ordinal == table_ptr->size())
        << "O hash::Iterator next() overflow";
 
      ah_underflow_error_if(ordinal == -1)
        << "O hash::Iterator next() underflow";
 
      assert(check());
 
      return get_curr_ne();
    }
 
    const Key & get_curr() const
    {
      return const_cast<Iterator*>(this)->get_curr();
    }
 
    bool has_curr() const noexcept
    {
      assert(table_ptr != nullptr);
      if (table_ptr->is_empty())
        return false;
      return ordinal >= 0 and ordinal < table_ptr->size();
    }
 
    [[nodiscard]] constexpr bool is_last() const noexcept { return ordinal == table_ptr->size() - 1; }
 
    void next() { locate_next_available_entry(); }
 
    void next_ne() noexcept { locate_next_available_entry_ne(); }
 
    void prev_ne() { locate_prev_available_entry_ne(); }
 
    void prev() { locate_prev_available_entry(); }
 
    Iterator() noexcept = default;
 
    Iterator(const HashTbl & table) noexcept
      : table_ptr(&const_cast<HashTbl&>(table)), curr_idx(0), ordinal(-1)
    {
      reset_first();
    }
 
    void del()
    {
      ah_overflow_error_if(not has_curr())
        << "Overflow in del() of iterator";
 
      table_ptr->deallocate_bucket(&table_ptr->table[curr_idx]);
      if (table_ptr->size() == 0)
        return;
 
      while (table_ptr->table[++curr_idx].status != HashTbl::BUSY);
    }
  };
 
  [[nodiscard]] DynList<Key> keys() const
  {
    return const_me()->template maps<Key> ([] (const Key & key) { return key; });
  }
 
  [[nodiscard]] auto items() const { return keys(); }
 
  struct Stats
  {
    size_t num_busy = 0;     
    size_t num_deleted = 0;  
    size_t num_empty = 0;    
    DynArray<size_t> lens;   
    float avg = 0;           
    float var = 0;           
    size_t max_len = 0;      
 
    Stats() : max_len(std::numeric_limits<size_t>::min())
    {
      assert(lens.size() == 0);
    }
  };
 
  void print_stats(const Stats & stats) const
  {
    std::cout << "M             = " << this->capacity() << '\n'
              << "N             = " << this->size() << '\n'
              << "busy slots    = " << stats.num_busy << '\n'
              << "deleted slots = " << stats.num_deleted << '\n'
              << "empty slots   = " << stats.num_empty << '\n'
              << "alpha         = " << const_me()->current_alpha() << '\n'
              << "max length    = " << stats.max_len << '\n';
    for (size_t i = 0; i < stats.lens.size(); ++i)
      std::cout << "    " << i << " = " << stats.lens(i) << '\n';
  }
 
  [[nodiscard]] constexpr float current_alpha() const noexcept 
  {
    return 1.0f*const_me()->N/const_me()->len; 
  }
};
 
 
template <class HashTbl>
class HashStats
{
  HashTbl * me() { return static_cast<HashTbl*>(this); }
 
  const HashTbl * const_me() const { return static_cast<const HashTbl*>(this); }
 
  float  lower_alpha;          
  float  upper_alpha;          
  size_t busy_slots_counter = 0;  
  size_t N = 0;                
 
public:
 
  struct Stats
  {
    float avg;              
    float var;              
    DynArray<size_t> lens;  
  };
 
private:
 
  static void update_stat_len(DynArray<size_t> & lens, size_t i)
  {
    if (lens.exist(i))
      lens(i) += 1;
    else
      lens.touch(i) = 1;
  }
 
public:
 
  Stats stats() const
  {
    DynArray<size_t> lens;
    for (int i = 0; i < const_me()->capacity(); ++i)
      {
        Dlink & list = const_me()->table[i];
        size_t count = 0;
        for (typename HashTbl::BucketItor it(list); it.has_curr(); 
             it.next(), ++count)
          ;
 
        update_stat_len(lens, count);
      }
 
    float avg = 0, 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)
      {
        float s = i - avg;
        var += lens(i)*s*s;
      }
    var /= sum;
 
    Stats stats;
    stats.avg = avg;
    stats.var = var;
    std::swap(lens, stats.lens);
 
    return stats;
  }
 
  void print_stats(const Stats & stats) const
  {
    std::cout << "M          = " << const_me()->capacity() << '\n'
         << "N          = " << const_me()->size() << '\n'
         << "busy slots = " << busy_slots_counter << '\n'
         << "Average    = " << stats.avg << '\n'
         << "Desv       = " << sqrt(stats.var) << '\n'
         << "alpha      = " << (1.0*const_me()->size())/const_me()->capacity() 
         << '\n';
    for (size_t i = 0; i < stats.lens.size(); ++i)
      std::cout << "    " << i << " = " << stats.lens(i) << '\n';
  }
 
  void set_upper_alpha(float _upper_alpha)
  {
    ah_domain_error_if(_upper_alpha <= lower_alpha)
      << "upper_alpha lower than lower_alpha";
 
    upper_alpha = _upper_alpha;
  }
 
  void set_lower_alpha(float _lower_alpha)
  {
    ah_domain_error_if(_lower_alpha >= upper_alpha)
      << "lower_alpha greater than upper_alpha";
 
    lower_alpha = _lower_alpha;
  }
 
  [[nodiscard]] constexpr float get_lower_alpha() const noexcept { return lower_alpha; }
 
  [[nodiscard]] constexpr float get_upper_alpha() const noexcept { return upper_alpha; }
};
 
 
# endif // HASHDRY_H