Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
pointer_table.H File Reference

Pointer table with index reuse for efficient pointer management. More...

#include <tpl_dynArray.H>
#include <ah-errors.H>
#include <iostream>
Include dependency graph for pointer_table.H:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

class  Pointer_Table
 A dynamic table for managing void pointers with index recycling. More...
 

Detailed Description

Pointer table with index reuse for efficient pointer management.

This file provides Pointer_Table, a data structure that manages a dynamic collection of void pointers with automatic index recycling. When pointers are removed, their indices are tracked and reused for subsequent insertions, minimizing memory fragmentation and index growth.

Main Features

  • O(1) insertion with automatic index assignment
  • O(1) removal with index recycling
  • O(1) pointer verification by index
  • Automatic compaction when removing from the top of the heap
  • Threshold-based memory management to prevent excessive shrinking

Usage Example

Pointer_Table table(100); // Initial capacity of 100
int* p1 = new int(42);
int* p2 = new int(100);
long idx1 = table.insert_pointer(p1); // Returns 0
long idx2 = table.insert_pointer(p2); // Returns 1
table.remove_pointer(idx1); // Index 0 now available for reuse
int* p3 = new int(200);
long idx3 = table.insert_pointer(p3); // Returns 0 (reused)
// Verify a pointer matches its index
void* verified = table.verify_pointer(idx2, p2); // Returns p2
A dynamic table for managing void pointers with index recycling.

Design

The table uses a two-array approach:

  • pointer_table: Stores the actual pointers indexed by position
  • free_table: Stack of available indices for reuse

A heap_index tracks the "high water mark" - all indices below it have been used at some point. When removing the top pointer, the heap contracts automatically, releasing memory.

Author
Leandro Rabindranath Leon

Definition in file pointer_table.H.