-
Notifications
You must be signed in to change notification settings - Fork 0
/
truncindex.go
106 lines (95 loc) · 2.23 KB
/
truncindex.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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
package truncindex
import (
"errors"
"fmt"
"strings"
"sync"
"github.com/tchap/go-patricia/patricia"
)
var (
ErrNoID = errors.New("prefix can't be empty")
)
func init() {
// Change patricia max prefix per node length,
// because our len(ID) always 64
patricia.MaxPrefixPerNode = 64
}
// TruncIndex allows the retrieval of string identifiers by any of their unique prefixes.
// This is used to retrieve image and container IDs by more convenient shorthand prefixes.
type TruncIndex struct {
sync.RWMutex
trie *patricia.Trie
ids map[string]struct{}
}
func NewTruncIndex(ids []string) (idx *TruncIndex) {
idx = &TruncIndex{
ids: make(map[string]struct{}),
trie: patricia.NewTrie(),
}
for _, id := range ids {
idx.addId(id)
}
return
}
func (idx *TruncIndex) addId(id string) error {
if strings.Contains(id, " ") {
return fmt.Errorf("Illegal character: ' '")
}
if id == "" {
return ErrNoID
}
if _, exists := idx.ids[id]; exists {
return fmt.Errorf("Id already exists: '%s'", id)
}
idx.ids[id] = struct{}{}
if inserted := idx.trie.Insert(patricia.Prefix(id), struct{}{}); !inserted {
return fmt.Errorf("Failed to insert id: %s", id)
}
return nil
}
func (idx *TruncIndex) Add(id string) error {
idx.Lock()
defer idx.Unlock()
if err := idx.addId(id); err != nil {
return err
}
return nil
}
func (idx *TruncIndex) Delete(id string) error {
idx.Lock()
defer idx.Unlock()
if _, exists := idx.ids[id]; !exists || id == "" {
return fmt.Errorf("No such id: '%s'", id)
}
delete(idx.ids, id)
if deleted := idx.trie.Delete(patricia.Prefix(id)); !deleted {
return fmt.Errorf("No such id: '%s'", id)
}
return nil
}
func (idx *TruncIndex) Get(s string) (string, error) {
idx.RLock()
defer idx.RUnlock()
var (
id string
)
if s == "" {
return "", ErrNoID
}
subTreeVisitFunc := func(prefix patricia.Prefix, item patricia.Item) error {
if id != "" {
// we haven't found the ID if there are two or more IDs
id = ""
return fmt.Errorf("we've found two entries")
}
id = string(prefix)
return nil
}
if err := idx.trie.VisitSubtree(patricia.Prefix(s), subTreeVisitFunc); err != nil {
return "", fmt.Errorf("No such id: %s", s)
}
if id != "" {
return id, nil
}
return "", fmt.Errorf("No such id: %s", s)
}