PcapFileEx.Merge.Heap (pcap_file_ex v0.5.5)

View Source

Min-heap priority queue for streaming packet merge.

This module implements a priority queue optimized for merging multiple packet streams in chronological order. Each heap entry contains:

  • A packet
  • The file index (for deterministic tie-breaking)
  • The packet index within that file (for deterministic tie-breaking)

Performance

  • new/0: O(1)
  • push/2: O(N) where N is the number of files (insert and sort)
  • pop/1: O(1) (remove first element)
  • Memory: O(N files) - only one packet buffered per file

Ordering

Packets are ordered by:

  1. timestamp_precise (primary key, nanosecond precision)
  2. file_index (secondary key, deterministic)
  3. packet_index (tertiary key, deterministic)

This ensures a stable, reproducible sort even when packets have identical timestamps.

Implementation Note

This uses a sorted list rather than a true binary heap. For typical use cases with <10 files, this is simpler and performs well.

Summary

Types

heap_entry()
t()

Functions

empty?(arg1)

Checks if the heap is empty.

new()

Creates a new empty heap.

peek(list)

Returns the minimum packet without removing it.

pop(list)

Removes and returns the minimum packet from the heap.

push(heap, packet, file_index, packet_index, original_interface_id \\ nil)

Pushes a new packet onto the heap with its file and packet indices.

size(heap)

Returns the number of elements in the heap.

Types

heap_entry()

@type heap_entry() ::
  {PcapFileEx.Timestamp.t(), file_index :: non_neg_integer(),
   packet_index :: non_neg_integer(), PcapFileEx.Packet.t(),
   original_interface_id :: non_neg_integer() | nil}

t()

@type t() :: [heap_entry()]

Functions

empty?(arg1)

@spec empty?(t()) :: boolean()

Checks if the heap is empty.

Examples

iex> PcapFileEx.Merge.Heap.new() |> PcapFileEx.Merge.Heap.empty?()
true

new()

@spec new() :: t()

Creates a new empty heap.

Examples

iex> PcapFileEx.Merge.Heap.new()
[]

peek(list)

@spec peek(t()) ::
  {PcapFileEx.Packet.t(), non_neg_integer(), non_neg_integer(),
   non_neg_integer() | nil}
  | :empty

Returns the minimum packet without removing it.

Returns {packet, file_index, packet_index, original_interface_id} or :empty if the heap is empty.

Examples

{packet, file_idx, pkt_idx, orig_iface_id} = PcapFileEx.Merge.Heap.peek(heap)

pop(list)

@spec pop(t()) ::
  {PcapFileEx.Packet.t(), non_neg_integer(), non_neg_integer(),
   non_neg_integer() | nil, t()}
  | :empty

Removes and returns the minimum packet from the heap.

Returns {packet, file_index, packet_index, original_interface_id, new_heap} or :empty if the heap is empty.

Examples

{packet, file_idx, pkt_idx, orig_iface_id, new_heap} = PcapFileEx.Merge.Heap.pop(heap)

push(heap, packet, file_index, packet_index, original_interface_id \\ nil)

@spec push(
  t(),
  PcapFileEx.Packet.t(),
  non_neg_integer(),
  non_neg_integer(),
  non_neg_integer() | nil
) ::
  t()

Pushes a new packet onto the heap with its file and packet indices.

Parameters

  • heap - The heap to push onto
  • packet - The packet to add
  • file_index - Index of the file this packet came from (for tie-breaking)
  • packet_index - Index of this packet within its file (for tie-breaking)
  • original_interface_id - Original interface ID before remapping (optional, for PCAPNG)

Examples

heap = PcapFileEx.Merge.Heap.new()
heap = PcapFileEx.Merge.Heap.push(heap, packet, 0, 42, 0)

size(heap)

@spec size(t()) :: non_neg_integer()

Returns the number of elements in the heap.

Examples

iex> heap = PcapFileEx.Merge.Heap.new()
iex> PcapFileEx.Merge.Heap.size(heap)
0