disksort

Documentation

Overview

Package disksort implements sorting algorithms for sets of data too large to fit fully in-memory. If the number of elements becomes to large, data are paged onto the disk.

Index

• Constants
• Variables
• type Interface
  • func NewMergeSorter(opts MergeOptions) (Interface, error)
• type Iterator
• type Marshaler
• type MergeOptions

Constants

const DefaultMaxBytesInMemory = 1024 * 1024 * 256

DefaultMaxBytesInMemory is the default maximum total size of elements to keep in-memory during a merge sort.

const DefaultMaxInMemory = 32000

DefaultMaxInMemory is the default number of elements to keep in-memory during a merge sort.

Variables

var (
	// ErrAlreadyFinalized is returned from Interface#Add and Interface#Read when
	// Interface#Read has already been called, freezing the sort's inputs/outputs.
	ErrAlreadyFinalized = errors.New("sorter already finalized")
)

Types

type Interface

type Interface interface {
	// Add adds a new element to the set of data to be sorted.
	Add(i any) error

	// Iterator returns an Iterator to read each of the elements previously added
	// to the set of data to be sorted.  Once Iterator is called, no more data may
	// be added to the sorter.  This is a lower-level version of Read.  Iterator
	// and Read may only be called once.
	Iterator() (Iterator, error)

	// Read calls f on each elements previously added the set of data to be
	// sorted.  If f returns an error, it is returned immediately and f is no
	// longer called.  Once Read is called, no more data may be added to the
	// sorter.  Iterator and Read may only be called once.
	Read(f func(any) error) error
}

Interface is the standard interface for disk sorting algorithms. Each element in the set of data to be sorted is added to the sorter with Add. Once all elements are added, Read can then be called to retrieve each element sequentially in sorted order. Once Read is called, no other operations on the sorter are allowed.

func NewMergeSorter

func NewMergeSorter(opts MergeOptions) (Interface, error)

NewMergeSorter returns a new disk sorter using a mergesort algorithm.

type Iterator

type Iterator interface {
	// Next returns the next ordered element.  If none exist, an io.EOF error is
	// returned.
	Next() (any, error)

	// Close releases all of the Iterator's used resources.  Each Iterator must be
	// closed after the client's last call to Next or stray temporary files may be
	// left on disk.
	Close() error
}

An Iterator reads each element, in order, in a sorted dataset.

type Marshaler

type Marshaler interface {
	// Marshal binary encodes the given element.
	Marshal(any) ([]byte, error)

	// Unmarshal decodes the given encoding of an element.
	Unmarshal([]byte) (any, error)
}

Marshaler is an interface to functions that can binary encode/decode elements.

type MergeOptions

type MergeOptions struct {
	// Name is optionally used as part of the path for temporary file shards.
	Name string

	// Lesser is the comparison function for sorting the given elements.
	Lesser sortutil.Lesser
	// Marshaler is used for encoding/decoding elements in temporary file shards.
	Marshaler Marshaler

	// WorkDir is the directory used for writing temporary file shards.  If empty,
	// the default directory for temporary files is used.
	WorkDir string

	// MaxInMemory is the maximum number of elements to keep in-memory before
	// paging them to a temporary file shard.  If non-positive, DefaultMaxInMemory
	// is used.
	MaxInMemory int

	// MaxBytesInMemory is the maximum total size of elements to keep in-memory
	// before paging them to a temporary file shard.  An element's size is
	// determined by its `Size() int` method. If non-positive,
	// DefaultMaxBytesInMemory is used.
	MaxBytesInMemory int

	// CompressShards determines whether the temporary file shards should be
	// compressed.
	CompressShards bool
}

MergeOptions specifies how to sort elements.