dnssort

Documentation

Index

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

Types

type SortResult

type SortResult[T dnsgraph.Graphable] struct {
	SortedRecords     []T
	UnresolvedRecords []T
}

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.