dnssort

Documentation

Index

• type SortResult
  • func SortUsingGraph[T dnsgraph.Graphable](records []T) SortResult[T]

Types

type SortResult

type SortResult[T dnsgraph.Graphable] struct {
	// SortedRecords is the sorted records.
	SortedRecords []T
	// UnresolvedRecords is the records that could not be resolved.
	UnresolvedRecords []T
}

SortResult is the result of a sort function.

func SortUsingGraph

func SortUsingGraph[T dnsgraph.Graphable](records []T) SortResult[T]

SortUsingGraph sorts changes based on their dependencies using a directed graph. Most changes have dependencies on other changes. Either they are depend on already (a backwards dependency) or their new state depend on another record (a forwards dependency) which can be in our change set or an existing record. A rough sketch of our sorting algorithm is as follows

while graph has nodes:

  foreach node in graph:

	  if node has no dependencies:
	    add node to sortedNodes
	    remove node from graph

return sortedNodes

The code below also accounts for the existence of cycles by tracking if any nodes were added to the sorted set in the last round.