UdiTable

ts::UdiTable is a fixed-size table for tracking frequently observed keys without allowing memory use to grow with the key space. Each key has a score and an associated user-defined data object. Events for a tracked key increase its score. A new key competes with a slot selected by a rotating pointer; a losing contest weakens the selected entry, while a winning contest replaces it. Frequently observed keys therefore tend to remain in the table.

The implementation serializes table operations with one mutex. Data objects are held by std::shared_ptr, so a pointer returned by find() or process_event() remains valid after its table entry is removed or evicted.

Basic Use

Include tsutil/UdiTable.h and supply a default-constructible key and data type. The key must also support the selected hash and equality operations.

#include "tsutil/UdiTable.h"

#include <atomic>
#include <string>

struct KeyData {
  std::atomic<uint64_t> requests{0};
};

ts::UdiTable<std::string, KeyData> table(10'000);

if (auto data = table.process_event("client-id")) {
  data->requests.fetch_add(1, std::memory_order_relaxed);
}

process_event() returns an empty pointer when a new key loses its contest. The optional ProcessStatus output distinguishes an ordinary contest loss from a contest that could not find an eligible slot.

Eviction Policies

By default every occupied slot may be selected for replacement. A fourth template argument can provide a policy that temporarily protects entries. The predicate receives the stored data as a const reference and returns whether the slot may participate in a contest.

struct Data {
  std::atomic<bool> protected_entry{false};
};

struct CanEvict {
  bool operator()(Data const &data) const
  {
    return !data.protected_entry.load(std::memory_order_relaxed);
  }
};

ts::UdiTable<std::string, Data, std::hash<std::string>, CanEvict> table(1024);

The predicate runs while the table mutex is held. It should be inexpensive and must not reenter the same table. Predicate locks follow the table lock. A contest examines at most the smaller of the capacity and 1024 slots, so a table of protected entries cannot cause an unbounded scan. If no eligible slot is found, process_event() reports ProcessStatus::NO_CANDIDATE.

Diagnostics

num_slots() and slots_used() report capacity and occupancy. The contests(), contests_won(), and evictions() counters describe table activity and can be cleared with reset_metrics(). dump() snapshots the entries under the table mutex, then invokes the caller’s formatting callback after releasing it.

data_snapshot() returns shared ownership of occupied data for maintenance outside the table lock. clear() removes all entries without resetting metrics; existing shared pointers remain valid.