btree

package module
v1.3.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Apr 20, 2022 License: MIT Imports: 1 Imported by: 249

README

btree

GoDoc

An efficient B-tree implementation in Go.

Features

  • Support for Generics (Go 1.18+).
  • Map and Set types for ordered key-value maps and sets,
  • Fast bulk loading for pre-ordered data using the Load() method.
  • Copy() method with copy-on-write support.
  • Thread-safe operations.
  • Path hinting optimization for operations with nearby keys.

Using

To start using this package, install Go and run:

$ go get github.com/tidwall/btree

B-tree types

This package includes the following types of B-trees:

  • btree.Map: A fast B-tree for storing ordered key value pairs. Go 1.18+
  • btree.Set: Like Map, but only for storing keys. Go 1.18+
  • btree.Generic: A feature-rich B-tree for storing data using a custom comparator. Go 1.18+
  • btree.BTree: Like Generic but uses the interface{} type for data. Backwards compatible. Go 1.16+
btree.Map
// Basic
Set(key, value)    // insert or replace an item
Get(key, value)    // get an existing item
Delete(key)        // delete an item
Len()              // return the number of items in the map

// Iteration
Scan(iter)         // scan items in ascending order
Reverse(iter)      // scan items in descending order
Ascend(key, iter)  // scan items in ascending order that are >= to key
Descend(key, iter) // scan items in descending order that are <= to key.
Iter()             // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)       // returns the item at index
DeleteAt(index)    // deletes the item at index

// Bulk-loading
Load(key, value)   // load presorted items into tree
Example
package main

import (
	"fmt"
	"github.com/tidwall/btree"
)

func main() {
	// create a map
	var users btree.Map[string, string]

	// add some users
	users.Set("user:4", "Andrea")
	users.Set("user:6", "Andy")
	users.Set("user:2", "Andy")
	users.Set("user:1", "Jane")
	users.Set("user:5", "Janet")
	users.Set("user:3", "Steve")

	// Iterate over the maps and print each user
	users.Scan(func(key, value string) bool {
		fmt.Printf("%s %s\n", key, value)
		return true
	})
	fmt.Printf("\n")

	// Delete a couple
	users.Delete("user:5")
	users.Delete("user:1")

	// print the map again
	users.Scan(func(key, value string) bool {
		fmt.Printf("%s %s\n", key, value)
		return true
	})
	fmt.Printf("\n")

	// Output:
	// user:1 Jane
	// user:2 Andy
	// user:3 Steve
	// user:4 Andrea
	// user:5 Janet
	// user:6 Andy
	//
	// user:2 Andy
	// user:3 Steve
	// user:4 Andrea
	// user:6 Andy
}
btree.Set
// Basic
Insert(key)        // insert an item
Contains(key)      // test if item exists
Delete(key)        // delete an item
Len()              // return the number of items in the set

// Iteration
Scan(iter)         // scan items in ascending order
Reverse(iter)      // scan items in descending order
Ascend(key, iter)  // scan items in ascending order that are >= to key
Descend(key, iter) // scan items in descending order that are <= to key.
Iter()             // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)       // returns the item at index
DeleteAt(index)    // deletes the item at index

// Bulk-loading
Load(key)          // load presorted item into tree
Example
package main

import (
	"fmt"
	"github.com/tidwall/btree"
)

func main() {
	// create a set
	var names btree.Set[string]

	// add some names
	names.Insert("Jane")
	names.Insert("Andrea")
	names.Insert("Steve")
	names.Insert("Andy")
	names.Insert("Janet")
	names.Insert("Andy")

	// Iterate over the maps and print each user
	names.Scan(func(key string) bool {
		fmt.Printf("%s\n", key)
		return true
	})
	fmt.Printf("\n")

	// Delete a couple
	names.Delete("Steve")
	names.Delete("Andy")

	// print the map again
	names.Scan(func(key string) bool {
		fmt.Printf("%s\n", key)
		return true
	})
	fmt.Printf("\n")

	// Output:
	// Andrea
	// Andy
	// Jane
	// Janet
	// Steve
	//
	// Andrea
	// Jane
	// Janet
}
btree.Generic
// Basic
Set(item)               // insert or replace an item
Get(item)               // get an existing item
Delete(item)            // delete an item
Len()                   // return the number of items in the btree

// Iteration
Scan(iter)              // scan items in ascending order
Reverse(iter)           // scan items in descending order
Ascend(key, iter)       // scan items in ascending order that are >= to key
Descend(key, iter)      // scan items in descending order that are <= to key.
Iter()                  // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)            // returns the item at index
DeleteAt(index)         // deletes the item at index

// Bulk-loading
Load(item)              // load presorted items into tree

// Path hinting
SetHint(item, *hint)    // insert or replace an existing item
GetHint(item, *hint)    // get an existing item
DeleteHint(item, *hint) // delete an item

// Copy-on-write
Copy()                  // copy the btree
Example
package main

import (
	"fmt"

	"github.com/tidwall/btree"
)

type Item struct {
	Key, Val string
}

// byKeys is a comparison function that compares item keys and returns true
// when a is less than b.
func byKeys(a, b Item) bool {
	return a.Key < b.Key
}

// byVals is a comparison function that compares item values and returns true
// when a is less than b.
func byVals(a, b Item) bool {
	if a.Val < b.Val {
		return true
	}
	if a.Val > b.Val {
		return false
	}
	// Both vals are equal so we should fall though
	// and let the key comparison take over.
	return byKeys(a, b)
}

func main() {
	// Create a tree for keys and a tree for values.
	// The "keys" tree will be sorted on the Keys field.
	// The "values" tree will be sorted on the Values field.
	keys := btree.NewGeneric[Item](byKeys)
	vals := btree.NewGeneric[Item](byVals)

	// Create some items.
	users := []Item{
		Item{Key: "user:1", Val: "Jane"},
		Item{Key: "user:2", Val: "Andy"},
		Item{Key: "user:3", Val: "Steve"},
		Item{Key: "user:4", Val: "Andrea"},
		Item{Key: "user:5", Val: "Janet"},
		Item{Key: "user:6", Val: "Andy"},
	}

	// Insert each user into both trees
	for _, user := range users {
		keys.Set(user)
		vals.Set(user)
	}

	// Iterate over each user in the key tree
	keys.Scan(func(item Item) bool {
		fmt.Printf("%s %s\n", item.Key, item.Val)
		return true
	})
	fmt.Printf("\n")

	// Iterate over each user in the val tree
	vals.Scan(func(item Item) bool {
		fmt.Printf("%s %s\n", item.Key, item.Val)
		return true
	})

	// Output:
	// user:1 Jane
	// user:2 Andy
	// user:3 Steve
	// user:4 Andrea
	// user:5 Janet
	// user:6 Andy
	//
	// user:4 Andrea
	// user:2 Andy
	// user:6 Andy
	// user:1 Jane
	// user:5 Janet
	// user:3 Steve
}
btree.BTree
// Basic
Set(item)               // insert or replace an item
Get(item)               // get an existing item
Delete(item)            // delete an item
Len()                   // return the number of items in the btree

// Iteration
Scan(iter)              // scan items in ascending order
Reverse(iter)           // scan items in descending order
Ascend(key, iter)       // scan items in ascending order that are >= to key
Descend(key, iter)      // scan items in descending order that are <= to key.
Iter()                  // returns a read-only iterator for for-loops.

// Array-like operations
GetAt(index)            // returns the item at index
DeleteAt(index)         // deletes the item at index

// Bulk-loading
Load(item)              // load presorted items into tree

// Path hinting
SetHint(item, *hint)    // insert or replace an existing item
GetHint(item, *hint)    // get an existing item
DeleteHint(item, *hint) // delete an item

// Copy-on-write
Copy()                  // copy the btree
Example
package main

import (
	"fmt"

	"github.com/tidwall/btree"
)

type Item struct {
	Key, Val string
}

// byKeys is a comparison function that compares item keys and returns true
// when a is less than b.
func byKeys(a, b interface{}) bool {
	i1, i2 := a.(*Item), b.(*Item)
	return i1.Key < i2.Key
}

// byVals is a comparison function that compares item values and returns true
// when a is less than b.
func byVals(a, b interface{}) bool {
	i1, i2 := a.(*Item), b.(*Item)
	if i1.Val < i2.Val {
		return true
	}
	if i1.Val > i2.Val {
		return false
	}
	// Both vals are equal so we should fall though
	// and let the key comparison take over.
	return byKeys(a, b)
}

func main() {
	// Create a tree for keys and a tree for values.
	// The "keys" tree will be sorted on the Keys field.
	// The "values" tree will be sorted on the Values field.
	keys := btree.New(byKeys)
	vals := btree.New(byVals)

	// Create some items.
	users := []*Item{
		&Item{Key: "user:1", Val: "Jane"},
		&Item{Key: "user:2", Val: "Andy"},
		&Item{Key: "user:3", Val: "Steve"},
		&Item{Key: "user:4", Val: "Andrea"},
		&Item{Key: "user:5", Val: "Janet"},
		&Item{Key: "user:6", Val: "Andy"},
	}

	// Insert each user into both trees
	for _, user := range users {
		keys.Set(user)
		vals.Set(user)
	}

	// Iterate over each user in the key tree
	keys.Ascend(nil, func(item interface{}) bool {
		kvi := item.(*Item)
		fmt.Printf("%s %s\n", kvi.Key, kvi.Val)
		return true
	})

	fmt.Printf("\n")
	// Iterate over each user in the val tree
	vals.Ascend(nil, func(item interface{}) bool {
		kvi := item.(*Item)
		fmt.Printf("%s %s\n", kvi.Key, kvi.Val)
		return true
	})

	// Output:
	// user:1 Jane
	// user:2 Andy
	// user:3 Steve
	// user:4 Andrea
	// user:5 Janet
	// user:6 Andy
	//
	// user:4 Andrea
	// user:2 Andy
	// user:6 Andy
	// user:1 Jane
	// user:5 Janet
	// user:3 Steve
}

Performance

This implementation was designed with performance in mind.

  • google: The google/btree package (without generics)
  • tidwall: The tidwall/btree package (without generics)
  • tidwall(G): The tidwall/btree package (generics using the btree.Generic type)
  • tidwall(M): The tidwall/btree package (generics using the btree.Map type)
  • go-arr: A simple Go array

The following benchmarks were run on my 2019 Macbook Pro (2.4 GHz 8-Core Intel Core i9) using Go Development version 1.18 (beta1). The items are simple 8-byte ints.

** sequential set **
google:     set-seq        1,000,000 ops in 156ms, 6,426,724/sec, 155 ns/op, 39.0 MB, 40 bytes/op
tidwall:    set-seq        1,000,000 ops in 135ms, 7,380,627/sec, 135 ns/op, 23.5 MB, 24 bytes/op
tidwall(G): set-seq        1,000,000 ops in 78ms, 12,881,995/sec, 77 ns/op, 8.2 MB, 8 bytes/op
tidwall(M): set-seq        1,000,000 ops in 46ms, 21,892,141/sec, 45 ns/op, 8.2 MB, 8 bytes/op
tidwall:    set-seq-hint   1,000,000 ops in 73ms, 13,789,017/sec, 72 ns/op, 23.5 MB, 24 bytes/op
tidwall(G): set-seq-hint   1,000,000 ops in 48ms, 20,969,431/sec, 47 ns/op, 8.2 MB, 8 bytes/op
tidwall:    load-seq       1,000,000 ops in 45ms, 22,452,523/sec, 44 ns/op, 23.5 MB, 24 bytes/op
tidwall(G): load-seq       1,000,000 ops in 22ms, 46,242,274/sec, 21 ns/op, 8.2 MB, 8 bytes/op
tidwall(M): load-seq       1,000,000 ops in 13ms, 74,371,903/sec, 13 ns/op, 8.2 MB, 8 bytes/op
go-arr:     append         1,000,000 ops in 21ms, 47,141,875/sec, 21 ns/op, 8.1 MB, 8 bytes/op

** sequential get **
google:     get-seq        1,000,000 ops in 119ms, 8,389,459/sec, 119 ns/op
tidwall:    get-seq        1,000,000 ops in 110ms, 9,068,759/sec, 110 ns/op
tidwall(G): get-seq        1,000,000 ops in 78ms, 12,813,135/sec, 78 ns/op
tidwall(M): get-seq        1,000,000 ops in 62ms, 16,053,728/sec, 62 ns/op
tidwall:    get-seq-hint   1,000,000 ops in 64ms, 15,509,696/sec, 64 ns/op
tidwall(G): get-seq-hint   1,000,000 ops in 41ms, 24,144,951/sec, 41 ns/op

** random set **
google:     set-rand       1,000,000 ops in 563ms, 1,777,592/sec, 562 ns/op, 29.7 MB, 31 bytes/op
tidwall:    set-rand       1,000,000 ops in 542ms, 1,844,397/sec, 542 ns/op, 29.6 MB, 31 bytes/op
tidwall(G): set-rand       1,000,000 ops in 234ms, 4,271,764/sec, 234 ns/op, 11.2 MB, 11 bytes/op
tidwall(M): set-rand       1,000,000 ops in 189ms, 5,292,236/sec, 188 ns/op, 11.2 MB, 11 bytes/op
tidwall:    set-rand-hint  1,000,000 ops in 602ms, 1,659,852/sec, 602 ns/op, 29.6 MB, 31 bytes/op
tidwall(G): set-rand-hint  1,000,000 ops in 278ms, 3,595,435/sec, 278 ns/op, 11.2 MB, 11 bytes/op
tidwall:    set-after-copy 1,000,000 ops in 679ms, 1,471,954/sec, 679 ns/op
tidwall(G): set-after-copy 1,000,000 ops in 238ms, 4,196,854/sec, 238 ns/op
tidwall:    load-rand      1,000,000 ops in 532ms, 1,880,877/sec, 531 ns/op, 29.6 MB, 31 bytes/op
tidwall(G): load-rand      1,000,000 ops in 232ms, 4,316,475/sec, 231 ns/op, 11.2 MB, 11 bytes/op
tidwall(M): load-rand      1,000,000 ops in 209ms, 4,790,169/sec, 208 ns/op, 11.2 MB, 11 bytes/op

** random get **
google:     get-rand       1,000,000 ops in 807ms, 1,238,703/sec, 807 ns/op
tidwall:    get-rand       1,000,000 ops in 812ms, 1,231,551/sec, 811 ns/op
tidwall(G): get-rand       1,000,000 ops in 255ms, 3,914,819/sec, 255 ns/op
tidwall(M): get-rand       1,000,000 ops in 190ms, 5,249,966/sec, 190 ns/op
tidwall:    get-rand-hint  1,000,000 ops in 876ms, 1,141,313/sec, 876 ns/op
tidwall(G): get-rand-hint  1,000,000 ops in 258ms, 3,877,775/sec, 257 ns/op

** range **
google:     ascend        1,000,000 ops in 26ms, 39,101,882/sec, 25 ns/op
tidwall:    ascend        1,000,000 ops in 20ms, 50,223,988/sec, 19 ns/op
tidwall(G): iter          1,000,000 ops in 8ms, 119,155,937/sec, 8 ns/op
tidwall(G): scan          1,000,000 ops in 6ms, 168,275,407/sec, 5 ns/op
tidwall(G): walk          1,000,000 ops in 5ms, 186,941,046/sec, 5 ns/op
go-arr:     for-loop      1,000,000 ops in 4ms, 272,234,997/sec, 3 ns/op

You can find the benchmark utility at tidwall/btree-benchmark

Contact

Josh Baker @tidwall

License

Source code is available under the MIT License.

Documentation

Overview

Copyright 2020 Joshua J Baker. All rights reserved. Use of this source code is governed by an MIT-style license that can be found in the LICENSE file.

Copyright 2020 Joshua J Baker. All rights reserved. Use of this source code is governed by an MIT-style license that can be found in the LICENSE file.

Copyright 2020 Joshua J Baker. All rights reserved. Use of this source code is governed by an MIT-style license that can be found in the LICENSE file.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BTree 

type BTree struct {
	// contains filtered or unexported fields
}

func New 

func New(less func(a, b any) bool) *BTree

New returns a new BTree

func NewNonConcurrent added in v0.6.0 

func NewNonConcurrent(less func(a, b any) bool) *BTree

NewNonConcurrent returns a new BTree which is not safe for concurrent write operations by multiple goroutines.

This is useful for when you do not need the BTree to manage the locking, but would rather do it yourself.

func (*BTree) Ascend 

func (tr *BTree) Ascend(pivot any, iter func(item any) bool)

Ascend the tree within the range [pivot, last] Pass nil for pivot to scan all item in ascending order Return false to stop iterating

func (*BTree) Copy added in v0.4.0 

func (tr *BTree) Copy() *BTree

Copy the tree. This is a copy-on-write operation and is very fast because it only performs a shadowed copy.

func (*BTree) Delete 

func (tr *BTree) Delete(key any) (prev any)

Delete an item for a key. Returns the deleted value or nil if the key was not found.

func (*BTree) DeleteAt added in v0.5.0 

func (tr *BTree) DeleteAt(index int) any

DeleteAt deletes the item at index. Return nil if the tree is empty or the index is out of bounds.

func (*BTree) DeleteHint added in v0.2.0 

func (tr *BTree) DeleteHint(key any, hint *PathHint) (prev any)

DeleteHint deletes a value for a key using a path hint Returns the deleted value or nil if the key was not found.

func (*BTree) Descend 

func (tr *BTree) Descend(pivot any, iter func(item any) bool)

Descend the tree within the range [pivot, first] Pass nil for pivot to scan all item in descending order Return false to stop iterating

func (*BTree) Get 

func (tr *BTree) Get(key any) any

Get a value for key. Returns nil if the key was not found.

func (*BTree) GetAt added in v0.5.0 

func (tr *BTree) GetAt(index int) any

GetAt returns the value at index. Return nil if the tree is empty or the index is out of bounds.

func (*BTree) GetHint added in v0.2.0 

func (tr *BTree) GetHint(key any, hint *PathHint) (value any)

GetHint gets a value for key using a path hint. Returns nil if the item was not found.

func (*BTree) Height added in v0.2.0 

func (tr *BTree) Height() int

Height returns the height of the tree. Returns zero if tree has no items.

func (*BTree) Iter added in v1.1.0 

func (tr *BTree) Iter() Iter

Iter returns a read-only iterator. The Release method must be called finished with iterator.

func (*BTree) Len 

func (tr *BTree) Len() int

Len returns the number of items in the tree

func (*BTree) Less added in v0.2.1 

func (tr *BTree) Less(a, b any) bool

Less is a convenience function that performs a comparison of two items using the same "less" function provided to New.

func (*BTree) Load added in v0.2.0 

func (tr *BTree) Load(item any) (prev any)

Load is for bulk loading pre-sorted items If the load replaces and existing item then the value for the replaced item is returned.

func (*BTree) Max 

func (tr *BTree) Max() any

Max returns the maximum item in tree. Returns nil if the tree has no items.

func (*BTree) Min 

func (tr *BTree) Min() any

Min returns the minimum item in tree. Returns nil if the tree has no items.

func (*BTree) PopMax added in v0.2.0 

func (tr *BTree) PopMax() any

PopMax removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*BTree) PopMin added in v0.2.0 

func (tr *BTree) PopMin() any

PopMin removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*BTree) Set added in v0.2.0 

func (tr *BTree) Set(item any) (prev any)

Set or replace a value for a key Returns the value for the replaced item or nil if the key was not found.

func (*BTree) SetHint added in v0.2.0 

func (tr *BTree) SetHint(item any, hint *PathHint) (prev any)

SetHint sets or replace a value for a key using a path hint Returns the value for the replaced item or nil if the key was not found.

func (*BTree) Walk added in v0.2.0 

func (tr *BTree) Walk(iter func(items []any))

Walk iterates over all items in tree, in order. The items param will contain one or more items.

type Generic added in v1.2.0 

type Generic[T any] struct {
	// contains filtered or unexported fields
}

func NewGeneric added in v1.2.0 

func NewGeneric[T any](less func(a, b T) bool) *Generic[T]

New returns a new BTree

func NewGenericOptions added in v1.2.0 

func NewGenericOptions[T any](less func(a, b T) bool, opts Options) *Generic[T]

func (*Generic[T]) Ascend added in v1.2.0 

func (tr *Generic[T]) Ascend(pivot T, iter func(item T) bool)

Ascend the tree within the range [pivot, last] Pass nil for pivot to scan all item in ascending order Return false to stop iterating

func (*Generic[T]) Copy added in v1.2.0 

func (tr *Generic[T]) Copy() *Generic[T]

Copy the tree. This is a copy-on-write operation and is very fast because it only performs a shadowed copy.

func (*Generic[T]) Delete added in v1.2.0 

func (tr *Generic[T]) Delete(key T) (T, bool)

Delete a value for a key and returns the deleted value. Returns false if there was no value by that key found.

func (*Generic[T]) DeleteAt added in v1.2.0 

func (tr *Generic[T]) DeleteAt(index int) (T, bool)

DeleteAt deletes the item at index. Return nil if the tree is empty or the index is out of bounds.

func (*Generic[T]) DeleteHint added in v1.2.0 

func (tr *Generic[T]) DeleteHint(key T, hint *PathHint) (T, bool)

DeleteHint deletes a value for a key using a path hint and returns the deleted value. Returns false if there was no value by that key found.

func (*Generic[T]) Descend added in v1.2.0 

func (tr *Generic[T]) Descend(pivot T, iter func(item T) bool)

Descend the tree within the range [pivot, first] Pass nil for pivot to scan all item in descending order Return false to stop iterating

func (*Generic[T]) Get added in v1.2.0 

func (tr *Generic[T]) Get(key T) (T, bool)

Get a value for key

func (*Generic[T]) GetAt added in v1.2.0 

func (tr *Generic[T]) GetAt(index int) (T, bool)

GetAt returns the value at index. Return nil if the tree is empty or the index is out of bounds.

func (*Generic[T]) GetHint added in v1.2.0 

func (tr *Generic[T]) GetHint(key T, hint *PathHint) (T, bool)

GetHint gets a value for key using a path hint

func (*Generic[T]) Height added in v1.2.0 

func (tr *Generic[T]) Height() int

Height returns the height of the tree. Returns zero if tree has no items.

func (*Generic[T]) Items added in v1.2.0 

func (tr *Generic[T]) Items() []T

Items returns all the items in order.

func (*Generic[T]) Iter added in v1.2.0 

func (tr *Generic[T]) Iter() GenericIter[T]

Iter returns a read-only iterator. The Release method must be called finished with iterator.

func (*Generic[T]) Len added in v1.2.0 

func (tr *Generic[T]) Len() int

Len returns the number of items in the tree

func (*Generic[T]) Less added in v1.2.0 

func (tr *Generic[T]) Less(a, b T) bool

Less is a convenience function that performs a comparison of two items using the same "less" function provided to New.

func (*Generic[T]) Load added in v1.2.0 

func (tr *Generic[T]) Load(item T) (T, bool)

Load is for bulk loading pre-sorted items

func (*Generic[T]) Max added in v1.2.0 

func (tr *Generic[T]) Max() (T, bool)

Max returns the maximum item in tree. Returns nil if the tree has no items.

func (*Generic[T]) Min added in v1.2.0 

func (tr *Generic[T]) Min() (T, bool)

Min returns the minimum item in tree. Returns nil if the treex has no items.

func (*Generic[T]) PopMax added in v1.2.0 

func (tr *Generic[T]) PopMax() (T, bool)

PopMax removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*Generic[T]) PopMin added in v1.2.0 

func (tr *Generic[T]) PopMin() (T, bool)

PopMin removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*Generic[T]) Reverse added in v1.2.0 

func (tr *Generic[T]) Reverse(iter func(item T) bool)

func (*Generic[T]) Scan added in v1.2.0 

func (tr *Generic[T]) Scan(iter func(item T) bool)

func (*Generic[T]) Set added in v1.2.0 

func (tr *Generic[T]) Set(item T) (T, bool)

Set or replace a value for a key

func (*Generic[T]) SetHint added in v1.2.0 

func (tr *Generic[T]) SetHint(item T, hint *PathHint) (prev T, replaced bool)

SetHint sets or replace a value for a key using a path hint

func (*Generic[T]) Walk added in v1.2.0 

func (tr *Generic[T]) Walk(iter func(item []T) bool)

Walk iterates over all items in tree, in order. The items param will contain one or more items.

type GenericIter added in v1.2.0 

type GenericIter[T any] struct {
	// contains filtered or unexported fields
}

Iter represents an iterator

func (*GenericIter[T]) First added in v1.2.0 

func (iter *GenericIter[T]) First() bool

First moves iterator to first item in tree. Returns false if the tree is empty.

func (*GenericIter[T]) Item added in v1.2.0 

func (iter *GenericIter[T]) Item() T

Item returns the current iterator item.

func (*GenericIter[T]) Last added in v1.2.0 

func (iter *GenericIter[T]) Last() bool

Last moves iterator to last item in tree. Returns false if the tree is empty.

func (*GenericIter[T]) Next added in v1.2.0 

func (iter *GenericIter[T]) Next() bool

Next moves iterator to the next item in iterator. Returns false if the tree is empty or the iterator is at the end of the tree.

func (*GenericIter[T]) Prev added in v1.2.0 

func (iter *GenericIter[T]) Prev() bool

Prev moves iterator to the previous item in iterator. Returns false if the tree is empty or the iterator is at the beginning of the tree.

func (*GenericIter[T]) Release added in v1.2.0 

func (iter *GenericIter[T]) Release()

Release the iterator.

func (*GenericIter[T]) Seek added in v1.2.0 

func (iter *GenericIter[T]) Seek(key T) bool

Seek to item greater-or-equal-to key. Returns false if there was no item found.

type Iter added in v1.1.0 

type Iter struct {
	// contains filtered or unexported fields
}

func (*Iter) First added in v1.1.0 

func (iter *Iter) First() bool

First moves iterator to first item in tree. Returns false if the tree is empty.

func (*Iter) Item added in v1.1.0 

func (iter *Iter) Item() any

Item returns the current iterator item.

func (*Iter) Last added in v1.1.0 

func (iter *Iter) Last() bool

Last moves iterator to last item in tree. Returns false if the tree is empty.

func (*Iter) Next added in v1.1.0 

func (iter *Iter) Next() bool

Next moves iterator to the next item in iterator. Returns false if the tree is empty or the iterator is at the end of the tree.

func (*Iter) Prev added in v1.1.0 

func (iter *Iter) Prev() bool

Prev moves iterator to the previous item in iterator. Returns false if the tree is empty or the iterator is at the beginning of the tree.

func (*Iter) Release added in v1.1.0 

func (iter *Iter) Release()

First moves iterator to first item in tree. Returns false if the tree is empty.

func (*Iter) Seek added in v1.1.0 

func (iter *Iter) Seek(key any) bool

Seek to item greater-or-equal-to key. Returns false if there was no item found.

type Map added in v1.2.0 

type Map[K ordered, V any] struct {
	// contains filtered or unexported fields
}

func (*Map[K, V]) Ascend added in v1.2.0 

func (tr *Map[K, V]) Ascend(pivot K, iter func(key K, value V) bool)

Ascend the tree within the range [pivot, last] Pass nil for pivot to scan all item in ascending order Return false to stop iterating

func (*Map[K, V]) Copy added in v1.3.0 

func (tr *Map[K, V]) Copy() *Map[K, V]

func (*Map[K, V]) Delete added in v1.2.0 

func (tr *Map[K, V]) Delete(key K) (V, bool)

Delete a value for a key and returns the deleted value. Returns false if there was no value by that key found.

func (*Map[K, V]) DeleteAt added in v1.2.0 

func (tr *Map[K, V]) DeleteAt(index int) (K, V, bool)

DeleteAt deletes the item at index. Return nil if the tree is empty or the index is out of bounds.

func (*Map[K, V]) Descend added in v1.2.0 

func (tr *Map[K, V]) Descend(pivot K, iter func(key K, value V) bool)

Descend the tree within the range [pivot, first] Pass nil for pivot to scan all item in descending order Return false to stop iterating

func (*Map[K, V]) Get added in v1.2.0 

func (tr *Map[K, V]) Get(key K) (V, bool)

Get a value for key

func (*Map[K, V]) GetAt added in v1.2.0 

func (tr *Map[K, V]) GetAt(index int) (K, V, bool)

GetAt returns the value at index. Return nil if the tree is empty or the index is out of bounds.

func (*Map[K, V]) Height added in v1.2.0 

func (tr *Map[K, V]) Height() int

Height returns the height of the tree. Returns zero if tree has no items.

func (*Map[K, V]) Iter added in v1.2.0 

func (tr *Map[K, V]) Iter() MapIter[K, V]

Iter returns a read-only iterator.

func (*Map[K, V]) KeyValues added in v1.2.0 

func (tr *Map[K, V]) KeyValues() ([]K, []V)

KeyValues returns all the keys and values in order.

func (*Map[K, V]) Keys added in v1.2.0 

func (tr *Map[K, V]) Keys() []K

Keys returns all the keys in order.

func (*Map[K, V]) Len added in v1.2.0 

func (tr *Map[K, V]) Len() int

Len returns the number of items in the tree

func (*Map[K, V]) Load added in v1.2.0 

func (tr *Map[K, V]) Load(key K, value V) (V, bool)

Load is for bulk loading pre-sorted items

func (*Map[K, V]) Max added in v1.2.0 

func (tr *Map[K, V]) Max() (K, V, bool)

Max returns the maximum item in tree. Returns nil if the tree has no items.

func (*Map[K, V]) Min added in v1.2.0 

func (tr *Map[K, V]) Min() (K, V, bool)

Min returns the minimum item in tree. Returns nil if the treex has no items.

func (*Map[K, V]) PopMax added in v1.2.0 

func (tr *Map[K, V]) PopMax() (K, V, bool)

PopMax removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*Map[K, V]) PopMin added in v1.2.0 

func (tr *Map[K, V]) PopMin() (K, V, bool)

PopMin removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*Map[K, V]) Reverse added in v1.2.0 

func (tr *Map[K, V]) Reverse(iter func(key K, value V) bool)

func (*Map[K, V]) Scan added in v1.2.0 

func (tr *Map[K, V]) Scan(iter func(key K, value V) bool)

func (*Map[K, V]) Set added in v1.2.0 

func (tr *Map[K, V]) Set(key K, value V) (V, bool)

Set or replace a value for a key

func (*Map[K, V]) Values added in v1.2.0 

func (tr *Map[K, V]) Values() []V

Values returns all the values in order.

type MapIter added in v1.2.0 

type MapIter[K ordered, V any] struct {
	// contains filtered or unexported fields
}

MapIter represents an iterator for btree.Map

func (*MapIter[K, V]) First added in v1.2.0 

func (iter *MapIter[K, V]) First() bool

First moves iterator to first item in tree. Returns false if the tree is empty.

func (*MapIter[K, V]) Key added in v1.2.0 

func (iter *MapIter[K, V]) Key() K

Key returns the current iterator item key.

func (*MapIter[K, V]) Last added in v1.2.0 

func (iter *MapIter[K, V]) Last() bool

Last moves iterator to last item in tree. Returns false if the tree is empty.

func (*MapIter[K, V]) Next added in v1.2.0 

func (iter *MapIter[K, V]) Next() bool

Next moves iterator to the next item in iterator. Returns false if the tree is empty or the iterator is at the end of the tree.

func (*MapIter[K, V]) Prev added in v1.2.0 

func (iter *MapIter[K, V]) Prev() bool

Prev moves iterator to the previous item in iterator. Returns false if the tree is empty or the iterator is at the beginning of the tree.

func (*MapIter[K, V]) Seek added in v1.2.0 

func (iter *MapIter[K, V]) Seek(key K) bool

Seek to item greater-or-equal-to key. Returns false if there was no item found.

func (*MapIter[K, V]) Value added in v1.2.0 

func (iter *MapIter[K, V]) Value() V

Value returns the current iterator item value.

type Options added in v1.2.0 

type Options struct {
	NoLocks bool
}

Options for passing to New when creating a new BTree.

type PathHint added in v0.2.2 

type PathHint struct {
	// contains filtered or unexported fields
}

PathHint is a utility type used with the *Hint() functions. Hints provide faster operations for clustered keys.

type Set added in v1.2.0 

type Set[K ordered] struct {
	// contains filtered or unexported fields
}

func (*Set[K]) Ascend added in v1.2.0 

func (tr *Set[K]) Ascend(pivot K, iter func(key K) bool)

Ascend the tree within the range [pivot, last] Pass nil for pivot to scan all item in ascending order Return false to stop iterating

func (*Set[K]) Contains added in v1.2.0 

func (tr *Set[K]) Contains(key K) bool

Get a value for key

func (*Set[K]) Copy added in v1.3.0 

func (tr *Set[K]) Copy() *Set[K]

Copy

func (*Set[K]) Delete added in v1.2.0 

func (tr *Set[K]) Delete(key K)

Delete an item

func (*Set[K]) DeleteAt added in v1.2.0 

func (tr *Set[K]) DeleteAt(index int) (K, bool)

DeleteAt deletes the item at index. Return nil if the tree is empty or the index is out of bounds.

func (*Set[K]) Descend added in v1.2.0 

func (tr *Set[K]) Descend(pivot K, iter func(key K) bool)

Descend the tree within the range [pivot, first] Pass nil for pivot to scan all item in descending order Return false to stop iterating

func (*Set[K]) GetAt added in v1.2.0 

func (tr *Set[K]) GetAt(index int) (K, bool)

GetAt returns the value at index. Return nil if the tree is empty or the index is out of bounds.

func (*Set[K]) Height added in v1.2.0 

func (tr *Set[K]) Height() int

Height returns the height of the tree. Returns zero if tree has no items.

func (*Set[K]) Insert added in v1.2.0 

func (tr *Set[K]) Insert(key K)

Insert an item

func (*Set[K]) Iter added in v1.2.0 

func (tr *Set[K]) Iter() SetIter[K]

Iter returns a read-only iterator.

func (*Set[K]) Keys added in v1.3.0 

func (tr *Set[K]) Keys() []K

Keys returns all the keys in order.

func (*Set[K]) Len added in v1.2.0 

func (tr *Set[K]) Len() int

Len returns the number of items in the tree

func (*Set[K]) Load added in v1.2.0 

func (tr *Set[K]) Load(key K)

Load is for bulk loading pre-sorted items

func (*Set[K]) Max added in v1.2.0 

func (tr *Set[K]) Max() (K, bool)

Max returns the maximum item in tree. Returns nil if the tree has no items.

func (*Set[K]) Min added in v1.2.0 

func (tr *Set[K]) Min() (K, bool)

Min returns the minimum item in tree. Returns nil if the treex has no items.

func (*Set[K]) PopMax added in v1.2.0 

func (tr *Set[K]) PopMax() (K, bool)

PopMax removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*Set[K]) PopMin added in v1.2.0 

func (tr *Set[K]) PopMin() (K, bool)

PopMin removes the minimum item in tree and returns it. Returns nil if the tree has no items.

func (*Set[K]) Reverse added in v1.2.0 

func (tr *Set[K]) Reverse(iter func(key K) bool)

func (*Set[K]) Scan added in v1.2.0 

func (tr *Set[K]) Scan(iter func(key K) bool)

type SetIter added in v1.2.0 

type SetIter[K ordered] struct {
	// contains filtered or unexported fields
}

SetIter represents an iterator for btree.Set

func (*SetIter[K]) First added in v1.2.0 

func (iter *SetIter[K]) First() bool

First moves iterator to first item in tree. Returns false if the tree is empty.

func (*SetIter[K]) Key added in v1.2.0 

func (iter *SetIter[K]) Key() K

Key returns the current iterator item key.

func (*SetIter[K]) Last added in v1.2.0 

func (iter *SetIter[K]) Last() bool

Last moves iterator to last item in tree. Returns false if the tree is empty.

func (*SetIter[K]) Next added in v1.2.0 

func (iter *SetIter[K]) Next() bool

Next moves iterator to the next item in iterator. Returns false if the tree is empty or the iterator is at the end of the tree.

func (*SetIter[K]) Prev added in v1.2.0 

func (iter *SetIter[K]) Prev() bool

Prev moves iterator to the previous item in iterator. Returns false if the tree is empty or the iterator is at the beginning of the tree.

func (*SetIter[K]) Seek added in v1.2.0 

func (iter *SetIter[K]) Seek(key K) bool

Seek to item greater-or-equal-to key. Returns false if there was no item found.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.