OLD | NEW |
1 // Copyright 2015 The Chromium Authors. All rights reserved. | 1 // Copyright 2015 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 package memory | 5 package memory |
6 | 6 |
7 import ( | 7 import ( |
8 "bytes" | 8 "bytes" |
9 "fmt" | 9 "fmt" |
10 "sort" | 10 "sort" |
11 | 11 |
12 » rds "github.com/luci/gae/service/rawdatastore" | 12 » ds "github.com/luci/gae/service/datastore" |
13 "github.com/luci/gkvlite" | 13 "github.com/luci/gkvlite" |
14 ) | 14 ) |
15 | 15 |
16 var indexCreationDeterministic = false | 16 var indexCreationDeterministic = false |
17 | 17 |
18 type qIndexSlice []*qIndex | 18 type qIndexSlice []*qIndex |
19 | 19 |
20 func (s qIndexSlice) Len() int { return len(s) } | 20 func (s qIndexSlice) Len() int { return len(s) } |
21 func (s qIndexSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] } | 21 func (s qIndexSlice) Swap(i, j int) { s[i], s[j] = s[j], s[i] } |
22 func (s qIndexSlice) Less(i, j int) bool { return s[i].Less(s[j]) } | 22 func (s qIndexSlice) Less(i, j int) bool { return s[i].Less(s[j]) } |
23 | 23 |
24 func defaultIndicies(kind string, pmap rds.PropertyMap) []*qIndex { | 24 func defaultIndicies(kind string, pmap ds.PropertyMap) []*qIndex { |
25 ret := make(qIndexSlice, 0, 2*len(pmap)+1) | 25 ret := make(qIndexSlice, 0, 2*len(pmap)+1) |
26 ret = append(ret, &qIndex{kind, false, nil}) | 26 ret = append(ret, &qIndex{kind, false, nil}) |
27 for name, pvals := range pmap { | 27 for name, pvals := range pmap { |
28 needsIndex := false | 28 needsIndex := false |
29 for _, v := range pvals { | 29 for _, v := range pvals { |
30 » » » if v.IndexSetting() == rds.ShouldIndex { | 30 » » » if v.IndexSetting() == ds.ShouldIndex { |
31 needsIndex = true | 31 needsIndex = true |
32 break | 32 break |
33 } | 33 } |
34 } | 34 } |
35 if !needsIndex { | 35 if !needsIndex { |
36 continue | 36 continue |
37 } | 37 } |
38 ret = append(ret, &qIndex{kind, false, []qSortBy{{name, qASC}}}) | 38 ret = append(ret, &qIndex{kind, false, []qSortBy{{name, qASC}}}) |
39 ret = append(ret, &qIndex{kind, false, []qSortBy{{name, qDEC}}}) | 39 ret = append(ret, &qIndex{kind, false, []qSortBy{{name, qDEC}}}) |
40 } | 40 } |
41 if indexCreationDeterministic { | 41 if indexCreationDeterministic { |
42 sort.Sort(ret) | 42 sort.Sort(ret) |
43 } | 43 } |
44 return ret | 44 return ret |
45 } | 45 } |
46 | 46 |
47 func indexEntriesWithBuiltins(k rds.Key, pm rds.PropertyMap, complexIdxs []*qInd
ex) *memStore { | 47 func indexEntriesWithBuiltins(k ds.Key, pm ds.PropertyMap, complexIdxs []*qIndex
) *memStore { |
48 sip := partiallySerialize(pm) | 48 sip := partiallySerialize(pm) |
49 return sip.indexEntries(k, append(defaultIndicies(k.Kind(), pm), complex
Idxs...)) | 49 return sip.indexEntries(k, append(defaultIndicies(k.Kind(), pm), complex
Idxs...)) |
50 } | 50 } |
51 | 51 |
52 // serializedPvals is all of the serialized DSProperty values in qASC order. | 52 // serializedPvals is all of the serialized DSProperty values in qASC order. |
53 type serializedPvals [][]byte | 53 type serializedPvals [][]byte |
54 | 54 |
55 func (s serializedPvals) Len() int { return len(s) } | 55 func (s serializedPvals) Len() int { return len(s) } |
56 func (s serializedPvals) Swap(i, j int) { s[i], s[j] = s[j], s[i] } | 56 func (s serializedPvals) Swap(i, j int) { s[i], s[j] = s[j], s[i] } |
57 func (s serializedPvals) Less(i, j int) bool { return bytes.Compare(s[i], s[j])
< 0 } | 57 func (s serializedPvals) Less(i, j int) bool { return bytes.Compare(s[i], s[j])
< 0 } |
58 | 58 |
59 // prop name -> [<serialized DSProperty>, ...] | 59 // prop name -> [<serialized DSProperty>, ...] |
60 type serializedIndexablePmap map[string]serializedPvals | 60 type serializedIndexablePmap map[string]serializedPvals |
61 | 61 |
62 func partiallySerialize(pm rds.PropertyMap) (ret serializedIndexablePmap) { | 62 func partiallySerialize(pm ds.PropertyMap) (ret serializedIndexablePmap) { |
63 if len(pm) == 0 { | 63 if len(pm) == 0 { |
64 return | 64 return |
65 } | 65 } |
66 | 66 |
67 buf := &bytes.Buffer{} | 67 buf := &bytes.Buffer{} |
68 ret = make(serializedIndexablePmap, len(pm)) | 68 ret = make(serializedIndexablePmap, len(pm)) |
69 for k, vals := range pm { | 69 for k, vals := range pm { |
70 newVals := make(serializedPvals, 0, len(vals)) | 70 newVals := make(serializedPvals, 0, len(vals)) |
71 for _, v := range vals { | 71 for _, v := range vals { |
72 » » » if v.IndexSetting() == rds.NoIndex { | 72 » » » if v.IndexSetting() == ds.NoIndex { |
73 continue | 73 continue |
74 } | 74 } |
75 buf.Reset() | 75 buf.Reset() |
76 » » » v.Write(buf, rds.WithoutContext) | 76 » » » v.Write(buf, ds.WithoutContext) |
77 newVal := make([]byte, buf.Len()) | 77 newVal := make([]byte, buf.Len()) |
78 copy(newVal, buf.Bytes()) | 78 copy(newVal, buf.Bytes()) |
79 newVals = append(newVals, newVal) | 79 newVals = append(newVals, newVal) |
80 } | 80 } |
81 if len(newVals) > 0 { | 81 if len(newVals) > 0 { |
82 sort.Sort(newVals) | 82 sort.Sort(newVals) |
83 ret[k] = newVals | 83 ret[k] = newVals |
84 } | 84 } |
85 } | 85 } |
86 return | 86 return |
(...skipping 81 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
168 if pv, ok := sip[sb.prop]; ok { | 168 if pv, ok := sip[sb.prop]; ok { |
169 m.buf.propVec = append(m.buf.propVec, pv) | 169 m.buf.propVec = append(m.buf.propVec, pv) |
170 m.buf.orders = append(m.buf.orders, sb.dir) | 170 m.buf.orders = append(m.buf.orders, sb.dir) |
171 } else { | 171 } else { |
172 return indexRowGen{}, false | 172 return indexRowGen{}, false |
173 } | 173 } |
174 } | 174 } |
175 return m.buf, true | 175 return m.buf, true |
176 } | 176 } |
177 | 177 |
178 func (sip serializedIndexablePmap) indexEntries(k rds.Key, idxs []*qIndex) *memS
tore { | 178 func (sip serializedIndexablePmap) indexEntries(k ds.Key, idxs []*qIndex) *memSt
ore { |
179 ret := newMemStore() | 179 ret := newMemStore() |
180 idxColl := ret.SetCollection("idx", nil) | 180 idxColl := ret.SetCollection("idx", nil) |
181 // getIdxEnts retrieves an index collection or adds it if it's not there
. | 181 // getIdxEnts retrieves an index collection or adds it if it's not there
. |
182 getIdxEnts := func(qi *qIndex) *memCollection { | 182 getIdxEnts := func(qi *qIndex) *memCollection { |
183 buf := &bytes.Buffer{} | 183 buf := &bytes.Buffer{} |
184 qi.WriteBinary(buf) | 184 qi.WriteBinary(buf) |
185 b := buf.Bytes() | 185 b := buf.Bytes() |
186 idxColl.Set(b, []byte{}) | 186 idxColl.Set(b, []byte{}) |
187 return ret.SetCollection(fmt.Sprintf("idx:%s:%s", k.Namespace(),
b), nil) | 187 return ret.SetCollection(fmt.Sprintf("idx:%s:%s", k.Namespace(),
b), nil) |
188 } | 188 } |
189 | 189 |
190 buf := &bytes.Buffer{} | 190 buf := &bytes.Buffer{} |
191 » rds.WriteKey(buf, rds.WithoutContext, k) | 191 » ds.WriteKey(buf, ds.WithoutContext, k) |
192 keyData := buf.Bytes() | 192 keyData := buf.Bytes() |
193 | 193 |
194 walkPermutations := func(prefix []byte, irg indexRowGen, ents *memCollec
tion) { | 194 walkPermutations := func(prefix []byte, irg indexRowGen, ents *memCollec
tion) { |
195 prev := []byte{} // intentionally make a non-nil slice, gkvlite
hates nil. | 195 prev := []byte{} // intentionally make a non-nil slice, gkvlite
hates nil. |
196 irg.permute(func(data []byte) { | 196 irg.permute(func(data []byte) { |
197 buf := bytes.NewBuffer(make([]byte, 0, len(prefix)+len(d
ata)+len(keyData))) | 197 buf := bytes.NewBuffer(make([]byte, 0, len(prefix)+len(d
ata)+len(keyData))) |
198 buf.Write(prefix) | 198 buf.Write(prefix) |
199 buf.Write(data) | 199 buf.Write(data) |
200 buf.Write(keyData) | 200 buf.Write(keyData) |
201 ents.Set(buf.Bytes(), prev) | 201 ents.Set(buf.Bytes(), prev) |
202 prev = data | 202 prev = data |
203 }) | 203 }) |
204 } | 204 } |
205 | 205 |
206 mtch := matcher{} | 206 mtch := matcher{} |
207 for _, idx := range idxs { | 207 for _, idx := range idxs { |
208 if irg, ok := mtch.match(idx, sip); ok { | 208 if irg, ok := mtch.match(idx, sip); ok { |
209 idxEnts := getIdxEnts(idx) | 209 idxEnts := getIdxEnts(idx) |
210 if len(irg.propVec) == 0 { | 210 if len(irg.propVec) == 0 { |
211 idxEnts.Set(keyData, []byte{}) // propless index
, e.g. kind -> key = nil | 211 idxEnts.Set(keyData, []byte{}) // propless index
, e.g. kind -> key = nil |
212 } else if idx.ancestor { | 212 } else if idx.ancestor { |
213 for ancKey := k; ancKey != nil; ancKey = ancKey.
Parent() { | 213 for ancKey := k; ancKey != nil; ancKey = ancKey.
Parent() { |
214 buf := &bytes.Buffer{} | 214 buf := &bytes.Buffer{} |
215 » » » » » rds.WriteKey(buf, rds.WithoutContext, an
cKey) | 215 » » » » » ds.WriteKey(buf, ds.WithoutContext, ancK
ey) |
216 walkPermutations(buf.Bytes(), irg, idxEn
ts) | 216 walkPermutations(buf.Bytes(), irg, idxEn
ts) |
217 } | 217 } |
218 } else { | 218 } else { |
219 walkPermutations(nil, irg, idxEnts) | 219 walkPermutations(nil, irg, idxEnts) |
220 } | 220 } |
221 } | 221 } |
222 } | 222 } |
223 | 223 |
224 return ret | 224 return ret |
225 } | 225 } |
226 | 226 |
227 func updateIndicies(store *memStore, key rds.Key, oldEnt, newEnt rds.PropertyMap
) { | 227 func updateIndicies(store *memStore, key ds.Key, oldEnt, newEnt ds.PropertyMap)
{ |
228 idxColl := store.GetCollection("idx") | 228 idxColl := store.GetCollection("idx") |
229 if idxColl == nil { | 229 if idxColl == nil { |
230 idxColl = store.SetCollection("idx", nil) | 230 idxColl = store.SetCollection("idx", nil) |
231 } | 231 } |
232 | 232 |
233 // load all current complex query index definitions. | 233 // load all current complex query index definitions. |
234 compIdx := []*qIndex{} | 234 compIdx := []*qIndex{} |
235 idxColl.VisitItemsAscend(complexQueryPrefix, false, func(i *gkvlite.Item
) bool { | 235 idxColl.VisitItemsAscend(complexQueryPrefix, false, func(i *gkvlite.Item
) bool { |
236 if !bytes.HasPrefix(i.Key, complexQueryPrefix) { | 236 if !bytes.HasPrefix(i.Key, complexQueryPrefix) { |
237 return false | 237 return false |
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
280 coll.Set(k, nv) | 280 coll.Set(k, nv) |
281 } | 281 } |
282 }) | 282 }) |
283 default: | 283 default: |
284 panic("impossible") | 284 panic("impossible") |
285 } | 285 } |
286 // TODO(riannucci): remove entries from idxColl and remove index
collections | 286 // TODO(riannucci): remove entries from idxColl and remove index
collections |
287 // when there are no index entries for that index any more. | 287 // when there are no index entries for that index any more. |
288 }) | 288 }) |
289 } | 289 } |
OLD | NEW |