/
smallindex.go
152 lines (131 loc) · 3.91 KB
/
smallindex.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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// Copyright (C) 2018 The Syncthing Authors.
//
// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this file,
// You can obtain one at https://mozilla.org/MPL/2.0/.
package db
import (
"encoding/binary"
"sort"
"github.com/syncthing/syncthing/lib/db/backend"
"github.com/syncthing/syncthing/lib/sync"
)
// A smallIndex is an in memory bidirectional []byte to uint32 map. It gives
// fast lookups in both directions and persists to the database. Don't use for
// storing more items than fit comfortably in RAM.
type smallIndex struct {
db backend.Backend
prefix []byte
id2val map[uint32]string
val2id map[string]uint32
nextID uint32
mut sync.Mutex
}
func newSmallIndex(db backend.Backend, prefix []byte) *smallIndex {
idx := &smallIndex{
db: db,
prefix: prefix,
id2val: make(map[uint32]string),
val2id: make(map[string]uint32),
mut: sync.NewMutex(),
}
idx.load()
return idx
}
// load iterates over the prefix space in the database and populates the in
// memory maps.
func (i *smallIndex) load() {
it, err := i.db.NewPrefixIterator(i.prefix)
if err != nil {
panic("loading small index: " + err.Error())
}
defer it.Release()
for it.Next() {
val := string(it.Value())
id := binary.BigEndian.Uint32(it.Key()[len(i.prefix):])
if val != "" {
// Empty value means the entry has been deleted.
i.id2val[id] = val
i.val2id[val] = id
}
if id >= i.nextID {
i.nextID = id + 1
}
}
}
// ID returns the index number for the given byte slice, allocating a new one
// and persisting this to the database if necessary.
func (i *smallIndex) ID(val []byte) (uint32, error) {
i.mut.Lock()
// intentionally avoiding defer here as we want this call to be as fast as
// possible in the general case (folder ID already exists). The map lookup
// with the conversion of []byte to string is compiler optimized to not
// copy the []byte, which is why we don't assign it to a temp variable
// here.
if id, ok := i.val2id[string(val)]; ok {
i.mut.Unlock()
return id, nil
}
id := i.nextID
i.nextID++
valStr := string(val)
i.val2id[valStr] = id
i.id2val[id] = valStr
key := make([]byte, len(i.prefix)+8) // prefix plus uint32 id
copy(key, i.prefix)
binary.BigEndian.PutUint32(key[len(i.prefix):], id)
if err := i.db.Put(key, val); err != nil {
i.mut.Unlock()
return 0, err
}
i.mut.Unlock()
return id, nil
}
// Val returns the value for the given index number, or (nil, false) if there
// is no such index number.
func (i *smallIndex) Val(id uint32) ([]byte, bool) {
i.mut.Lock()
val, ok := i.id2val[id]
i.mut.Unlock()
if !ok {
return nil, false
}
return []byte(val), true
}
func (i *smallIndex) Delete(val []byte) error {
i.mut.Lock()
defer i.mut.Unlock()
// Check the reverse mapping to get the ID for the value.
if id, ok := i.val2id[string(val)]; ok {
// Generate the corresponding database key.
key := make([]byte, len(i.prefix)+8) // prefix plus uint32 id
copy(key, i.prefix)
binary.BigEndian.PutUint32(key[len(i.prefix):], id)
// Put an empty value into the database. This indicates that the
// entry does not exist any more and prevents the ID from being
// reused in the future.
if err := i.db.Put(key, []byte{}); err != nil {
return err
}
// Delete reverse mapping.
delete(i.id2val, id)
}
// Delete forward mapping.
delete(i.val2id, string(val))
return nil
}
// Values returns the set of values in the index
func (i *smallIndex) Values() []string {
// In principle this method should return [][]byte because all the other
// methods deal in []byte keys. However, in practice, where it's used
// wants a []string and it's easier to just create that here rather than
// having to convert both here and there...
i.mut.Lock()
vals := make([]string, 0, len(i.val2id))
for val := range i.val2id {
vals = append(vals, val)
}
i.mut.Unlock()
sort.Strings(vals)
return vals
}