forked from Workiva/go-datastructures
-
Notifications
You must be signed in to change notification settings - Fork 0
/
interface.go
69 lines (57 loc) · 2.49 KB
/
interface.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
Copyright 2014 Workiva, LLC
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
/*
Package palm implements parallel architecture-friendly latch-free
modifications (PALM). Details can be found here:
http://cs.unc.edu/~sewall/palm.pdf
The primary purpose of the tree is to efficiently batch operations
in such a way that locks are not required. This is most beneficial
for in-memory indices. Otherwise, the operations have typical B-tree
time complexities.
You primarily see the benefits of multithreading in availability and
bulk operations.
Benchmarks:
BenchmarkReadAndWrites-8 3000 483140 ns/op
BenchmarkSimultaneousReadsAndWrites-8 300 4418123 ns/op
BenchmarkBulkAdd-8 300 5569750 ns/op
BenchmarkAdd-8 500000 2478 ns/op
BenchmarkBulkAddToExisting-8 100 20552674 ns/op
BenchmarkGet-8 2000000 629 ns/op
BenchmarkBulkGet-8 5000 223249 ns/op
BenchmarkDelete-8 500000 2421 ns/op
BenchmarkBulkDelete-8 500 2790461 ns/op
BenchmarkFindQuery-8 1000000 1166 ns/op
BenchmarkExecuteQuery-8 10000 1290732 ns/op
*/
package palm
import "github.com/Workiva/go-datastructures/common"
// BTree is the interface returned from this package's constructor.
type BTree interface {
// Insert will insert the provided keys into the tree.
Insert(...common.Comparator)
// Delete will remove the provided keys from the tree. If no
// matching key is found, this is a no-op.
Delete(...common.Comparator)
// Get will return a key matching the associated provided
// key if it exists.
Get(...common.Comparator) common.Comparators
// Len returns the number of items in the tree.
Len() uint64
// Query will return a list of Comparators that fall within the
// provided start and stop Comparators. Start is inclusive while
// stop is exclusive, ie [start, stop).
Query(start, stop common.Comparator) common.Comparators
// Dispose will clean up any resources used by this tree. This
// must be called to prevent a memory leak.
Dispose()
}