sorter

package

v1.0.3 Latest Latest Go to latest Published: Jul 19, 2020 License: GPL-3.0 Imports: 10 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/moloch--/leakdb

Links

Open Source Insights

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)
type Tape
type Worker

Constants ¶

View Source

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"
)

Variables ¶

This section is empty.

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

Source Files ¶

View all Source files

sorter.go

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL