Skip to main content

trie.go

trie.go - Overview​

This file implements a Trie data structure that supports adding, deleting, and retrieving IDs based on prefix matches, including the ability to ignore certain bytes in the prefix during matching.

Detailed Documentation​

type node​

type node struct {
	children map[byte]*node
	ignore   *node
	ids      []uint64
}

Represents a node in the Trie.

  • children: A map of child nodes, keyed by byte value.
  • ignore: A pointer to a child node that represents an ignored byte.
  • ids: A slice of uint64 IDs associated with this node.

node.isEmpty​

func (n *node) isEmpty() bool

Purpose: Checks if a node is empty (has no children, IDs, or ignore node).

Returns: true if the node is empty, false otherwise.

newNode​

func newNode() *node

Purpose: Creates a new node with initialized children map and ids slice.

Returns: A pointer to the new node.

type Trie​

type Trie struct {
	root *node
}

Represents the Trie data structure.

  • root: The root node of the Trie.

NewTrie​

func NewTrie() *Trie

Purpose: Creates a new Trie with an initialized root node.

Returns: A pointer to the new Trie.

parseIgnoreBytes​

func parseIgnoreBytes(ig string) ([]bool, error)

Purpose: Parses a string representing ignored byte indices into a boolean slice.

Parameters:

  • ig: A comma-separated string of indices or ranges (e.g., "3, 5-8, 10").

Returns:

  • []bool: A slice where out[i] == true indicates that the byte at index i should be ignored.
  • error: An error if the input string is invalid.

Trie.Add​

func (t *Trie) Add(prefix []byte, id uint64)

Purpose: Adds an ID to the Trie for a given prefix. It creates a pb.Match and calls AddMatch.

Parameters:

  • prefix: The prefix to associate with the ID.
  • id: The ID to add.

Trie.AddMatch​

func (t *Trie) AddMatch(m pb.Match, id uint64) error

Purpose: Adds an ID to the Trie based on a pb.Match which can include ignored bytes.

Parameters:

  • m: A pb.Match struct containing the prefix and ignore byte information.
  • id: The ID to add.

Returns:

  • error: An error if parsing the ignore bytes fails.

Trie.fix​

func (t *Trie) fix(m pb.Match, id uint64, op int) error

Purpose: Internal function to add or delete an ID from the Trie.

Parameters:

  • m: A pb.Match struct containing the prefix and ignore byte information.
  • id: The ID to add or delete.
  • op: An integer representing the operation to perform (set for add, del for delete).

Returns:

  • error: An error if parsing the ignore bytes fails.

Trie.Get​

func (t *Trie) Get(key []byte) map[uint64]struct{}

Purpose: Retrieves all IDs matching a given key (prefix).

Parameters:

  • key: The key to search for.

Returns:

  • map[uint64]struct{}: A map of unique IDs that match the key.

Trie.get​

func (t *Trie) get(curNode *node, key []byte) map[uint64]struct{}

Purpose: Recursive helper function for Get to traverse the Trie and collect matching IDs.

Parameters:

  • curNode: The current node being visited.
  • key: The remaining key to search for.

Returns:

  • map[uint64]struct{}: A map of unique IDs that match the key.

removeEmpty​

func removeEmpty(curNode *node) bool

Purpose: Recursively removes empty nodes from the Trie.

Parameters:

  • curNode: The current node being checked.

Returns:

  • bool: true if the current node was empty and removed, false otherwise.

Trie.Delete​

func (t *Trie) Delete(prefix []byte, id uint64) error

Purpose: Deletes an ID from the Trie for a given prefix.

Parameters:

  • prefix: The prefix associated with the ID to delete.
  • id: The ID to delete.

Returns:

  • error: An error, if any.

Trie.DeleteMatch​

func (t *Trie) DeleteMatch(m pb.Match, id uint64) error

Purpose: Deletes an ID from the Trie based on a pb.Match including possible ignored bytes.

Parameters:

  • m: A pb.Match struct containing the prefix and ignore byte information.
  • id: The ID to delete.

Returns:

  • error: An error, if any.

numNodes​

func numNodes(curNode *node) int

Purpose: Recursively counts the number of nodes in the Trie.

Parameters:

  • curNode: The current node being visited.

Returns:

  • int: The total number of nodes in the Trie.

Code Examples​

None

Getting Started Relevance​