sorter

Documentation

Index

• Constants
• func CheckSort(index string, verbose bool) (bool, error)
• func EntryComparer(a, b interface{}) int
• func Quicksort(entries []*Entry)
• type Entry
  • func (e *Entry) Value() uint64
• type Sorter
  • func GetSorter(index, output string, maxWorkers, maxMemory int, tempDir string, ...) (*Sorter, error)
  • func (s *Sorter) CreateTape(id int, entriesPerTape int) *Tape
  • func (s *Sorter) Drain(outputBuf []*Entry)
  • func (s *Sorter) Get(index int) *Entry
  • func (s *Sorter) IsMergeCompleted() bool
  • func (s *Sorter) PopulateHeap()
  • func (s *Sorter) Start()
  • func (s *Sorter) TapesCompleted() int
• type Tape
  • func (t *Tape) IsEndOfTape() bool
  • func (t *Tape) Pop() (*Entry, bool)
  • func (t *Tape) Prefetch(position int)
  • func (t *Tape) Save()
• type Worker

Constants

const (

	// Kb - Kilobyte
	Kb = 1024
	// Mb - Megabyte
	Mb = 1024 * Kb
	// Gb - Gigabyte
	Gb = 1024 * Mb

	// StatusNotStarted - The Indexer has been created but not started
	StatusNotStarted = "Not Started"
	// StatusStarting - Indexer is starting
	StatusStarting = "Starting"
	// StatusSorting - Indexer is sorting tapes
	StatusSorting = "Sorting"
	// StatusMerging - Indexer is merging tapes
	StatusMerging = "Merging"
)

Functions

func CheckSort

func CheckSort(index string, verbose bool) (bool, error)

CheckSort - Check if an index is sorted

func EntryComparer

func EntryComparer(a, b interface{}) int

EntryComparer - Compares entries in an index

func Quicksort

func Quicksort(entries []*Entry)

Quicksort - Sort the entries

Types

type Entry

type Entry struct {
	Digest    []byte
	Offset    []byte
	TapeIndex int // Only used during merge
}

Entry - [48-bit digest][48-bit offset] = 96-bit (12 byte) entry

func (*Entry) Value

func (e *Entry) Value() uint64

Value - The numeric value of the digest

type Sorter

type Sorter struct {
	IndexPath  string
	Index      *os.File
	OutputPath string
	Output     *os.File
	Info       os.FileInfo

	MaxWorkers        int
	NumberOfEntires   int // Number of entries
	MaxMemory         int // size of buffer in bytes
	WorkerBufSize     int
	EntriesPerTape    int
	MaxPerTapeBufSize int
	MergeBufLen       int

	Tapes         []*Tape
	TapeDir       string
	NoTapeCleanup bool
	Heap          *binaryheap.Heap
	MergePercent  float64

	Workers []*Worker

	NumberOfTapes int
	Status        string
}

Sorter - An index file

func GetSorter

func GetSorter(index, output string, maxWorkers, maxMemory int, tempDir string, noTapeCleanup bool) (*Sorter, error)

GetSorter - Start the sorting process

func (*Sorter) CreateTape

func (s *Sorter) CreateTape(id int, entriesPerTape int) *Tape

CreateTape - Creates a tape and loads the entire tap into memory

func (*Sorter) Drain

func (s *Sorter) Drain(outputBuf []*Entry)

Drain - Drain buffer to file

func (*Sorter) Get

func (s *Sorter) Get(index int) *Entry

Get - Get an index entry at position

func (*Sorter) IsMergeCompleted

func (s *Sorter) IsMergeCompleted() bool

IsMergeCompleted - Returns true if all tapes have ended and heap is size 0

func (*Sorter) PopulateHeap

func (s *Sorter) PopulateHeap()

PopulateHeap - Populate the heap with lowest values from sorted tapes

func (*Sorter) Start

func (s *Sorter) Start()

Start - Sorts the index

func (*Sorter) TapesCompleted

func (s *Sorter) TapesCompleted() int

TapesCompleted - Number of tapes completed

type Tape

type Tape struct {
	ID        int
	Entries   []*Entry
	Dir       string
	FileName  string
	Len       int // Number of entires in tape file
	MergeSize int // Number of entires in merge buffer
	Position  int
}

Tape - A subsection of the index file that we can sort in-memory

func (*Tape) IsEndOfTape

func (t *Tape) IsEndOfTape() bool

IsEndOfTape - Returns true if end of tape has been reached

The file is zero indexed but the Position will
get incremented until EOF, so no Size-1.

func (*Tape) Pop

func (t *Tape) Pop() (*Entry, bool)

Pop - Pop lowest value from tape

func (*Tape) Prefetch

func (t *Tape) Prefetch(position int)

Prefetch - Prefetch t.MergeSize elements from position in tape

func (*Tape) Save

func (t *Tape) Save()

Save - Save tape to disk in dir

type Worker

type Worker struct {
	ID             int
	Queue          <-chan *Tape
	Quit           chan bool
	Wg             *sync.WaitGroup
	MaxGoRoutines  int
	TapesCompleted int
}

Worker - An instance of quicksort