pointer_table.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 POINTER_TABLE_H
# define POINTER_TABLE_H
 
# include <tpl_dynArray.H>
# include <ah-errors.H>
# include <iostream>
 
class Pointer_Table
{
public:
  static constexpr long Null_Index = -1;
 
private:
  DynArray<void *> pointer_table;  
  DynArray<long> free_table;       
  long num_pointers;               
  long heap_index;                 
  long threshold_size;             
 
  long allocate_above_heap()
  {
    if (free_table.size() == 0)
      return Null_Index;
 
    long ret_val = free_table[free_table.size() - 1];
 
    assert(ret_val >= 0 and ret_val < heap_index);
    assert(pointer_table[ret_val] == nullptr);
 
    free_table.cut(free_table.size() - 1);
 
    return ret_val;
  }
 
  void insert_in_free_table(long i)
  {
    assert(i >= 0 and i < heap_index);
 
    pointer_table[i] = nullptr;
    free_table[free_table.size()] = i;
  }
 
  void cleanup_free_table(long new_heap_index)
  {
    if (free_table.size() == 0)
      return;
 
    // Remove all indices >= new_heap_index from free_table
    // We need to compact the free_table, keeping only valid indices
    long write_pos = 0;
    for (long read_pos = 0; read_pos < static_cast<long>(free_table.size()); ++read_pos)
      {
        if (free_table[read_pos] < new_heap_index)
          {
            if (write_pos != read_pos)
              free_table[write_pos] = free_table[read_pos];
            ++write_pos;
          }
      }
 
    if (write_pos < static_cast<long>(free_table.size()))
      free_table.cut(write_pos);
  }
 
  bool is_valid_index(long i) const noexcept
  {
    return i >= 0 and i < heap_index;
  }
 
  bool pointer_matches_with_index(long i, const void *ptr) const noexcept
  {
    assert(is_valid_index(i));
    return pointer_table(i) == ptr;
  }
 
  bool invariant() const
  {
    // Basic count check
    if (num_pointers < 0)
      return false;
 
    // When empty
    if (num_pointers == 0)
      return heap_index == 0 and free_table.size() == 0;
 
    // Non-empty: top of heap must be non-null
    if (heap_index <= 0 or pointer_table(heap_index - 1) == nullptr)
      return false;
 
    // Verify count consistency
    if (num_pointers != heap_index - static_cast<long>(free_table.size()))
      return false;
 
    // Verify all free_table indices are valid and point to nullptr
    for (size_t j = 0; j < free_table.size(); ++j)
      {
        long idx = free_table(j);
        if (idx < 0 or idx >= heap_index)
          return false;
        if (pointer_table(idx) != nullptr)
          return false;
      }
 
    return true;
  }
 
public:
  Pointer_Table(size_t initial_size = 0)
    : pointer_table(initial_size), free_table(0),
      num_pointers(0), heap_index(0), threshold_size(static_cast<long>(initial_size))
  {
    // DynArray initializes to default (nullptr for pointers)
    // No explicit initialization loop needed
  }
 
  long size() const noexcept { return pointer_table.size(); }
 
  long busies() const noexcept { return num_pointers; }
 
  long frees() const noexcept { return free_table.size(); }
 
  long get_heap_index() const noexcept { return heap_index; }
 
  long get_threshold() const noexcept { return threshold_size; }
 
  bool is_empty() const noexcept { return num_pointers == 0; }
 
  long insert_pointer(void *ptr)
  {
    assert(invariant());
 
    long ret_val = allocate_above_heap();
 
    if (ret_val == Null_Index)
      ret_val = heap_index++;
 
    pointer_table[ret_val] = ptr;
    ++num_pointers;
 
    assert(invariant());
 
    return ret_val;
  }
 
  void remove_pointer(long i)
  {
    assert(invariant());
 
    if (not is_valid_index(i))
      ah_range_error_if(true) << "index " << i << " out of range [0, "
                              << heap_index << ")";
 
    if (pointer_table[i] == nullptr)
      ah_domain_error_if(true) << "index " << i << " is not busy (already free)";
 
    if (i == heap_index - 1)
      {
        // Removing from top of heap - contract the heap
        pointer_table[heap_index - 1] = nullptr;
 
        // Find new heap top (first non-null from the top)
        while (heap_index > 0 and pointer_table[heap_index - 1] == nullptr)
          --heap_index;
 
        // CRITICAL FIX: Remove invalid indices from free_table
        cleanup_free_table(heap_index);
      }
    else
      insert_in_free_table(i);
 
    // Shrink pointer_table if below threshold
    if (heap_index <= threshold_size and pointer_table.size() > static_cast<size_t>(threshold_size))
      pointer_table.cut(threshold_size > 0 ? threshold_size : 0);
 
    --num_pointers;
 
    assert(invariant());
  }
 
  void * get_pointer(long i) const
  {
    if (not is_valid_index(i))
      ah_range_error_if(true) << "index " << i << " out of range [0, "
                              << heap_index << ")";
    return pointer_table(i);
  }
 
  void * verify_pointer(long i, void *ptr) const
  {
    if (not is_valid_index(i))
      ah_range_error_if(true) << "index " << i << " out of range [0, "
                              << heap_index << ")";
 
    if (not pointer_matches_with_index(i, ptr))
      ah_domain_error_if(true) << "pointer at index " << i
                               << " does not match expected value";
 
    return ptr;
  }
 
  void clear()
  {
    pointer_table.cut(threshold_size > 0 ? threshold_size : 0);
    free_table.cut(0);
    num_pointers = 0;
    heap_index = 0;
 
    assert(invariant());
  }
 
# ifdef DEBUG
  void print_parameters() const
  {
    std::cout << "Number of pointers = " << num_pointers << '\n'
              << "Pointer table size = " << pointer_table.size() << '\n'
              << "Free table size    = " << free_table.size() << '\n'
              << "Threshold          = " << threshold_size << '\n'
              << "Heap index         = " << heap_index << '\n';
    if (heap_index > 0)
      std::cout << "pointer_table[" << heap_index - 1 << "]= "
                << pointer_table(heap_index - 1) << '\n';
  }
 
  bool check_invariant() const { return invariant(); }
# endif
};
 
 
# endif // POINTER_TABLE_H