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