khenaidoo | 2672188 | 2021-08-11 17:42:52 -0400 | [diff] [blame] | 1 | // Copyright 2017 The etcd Authors |
| 2 | // |
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | // you may not use this file except in compliance with the License. |
| 5 | // You may obtain a copy of the License at |
| 6 | // |
| 7 | // http://www.apache.org/licenses/LICENSE-2.0 |
| 8 | // |
| 9 | // Unless required by applicable law or agreed to in writing, software |
| 10 | // distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | // See the License for the specific language governing permissions and |
| 13 | // limitations under the License. |
| 14 | |
| 15 | package backend |
| 16 | |
| 17 | import ( |
| 18 | "bytes" |
| 19 | "sort" |
| 20 | ) |
| 21 | |
| 22 | // txBuffer handles functionality shared between txWriteBuffer and txReadBuffer. |
| 23 | type txBuffer struct { |
| 24 | buckets map[string]*bucketBuffer |
| 25 | } |
| 26 | |
| 27 | func (txb *txBuffer) reset() { |
| 28 | for k, v := range txb.buckets { |
| 29 | if v.used == 0 { |
| 30 | // demote |
| 31 | delete(txb.buckets, k) |
| 32 | } |
| 33 | v.used = 0 |
| 34 | } |
| 35 | } |
| 36 | |
| 37 | // txWriteBuffer buffers writes of pending updates that have not yet committed. |
| 38 | type txWriteBuffer struct { |
| 39 | txBuffer |
| 40 | seq bool |
| 41 | } |
| 42 | |
| 43 | func (txw *txWriteBuffer) put(bucket, k, v []byte) { |
| 44 | txw.seq = false |
| 45 | txw.putSeq(bucket, k, v) |
| 46 | } |
| 47 | |
| 48 | func (txw *txWriteBuffer) putSeq(bucket, k, v []byte) { |
| 49 | b, ok := txw.buckets[string(bucket)] |
| 50 | if !ok { |
| 51 | b = newBucketBuffer() |
| 52 | txw.buckets[string(bucket)] = b |
| 53 | } |
| 54 | b.add(k, v) |
| 55 | } |
| 56 | |
| 57 | func (txw *txWriteBuffer) writeback(txr *txReadBuffer) { |
| 58 | for k, wb := range txw.buckets { |
| 59 | rb, ok := txr.buckets[k] |
| 60 | if !ok { |
| 61 | delete(txw.buckets, k) |
| 62 | txr.buckets[k] = wb |
| 63 | continue |
| 64 | } |
| 65 | if !txw.seq && wb.used > 1 { |
| 66 | // assume no duplicate keys |
| 67 | sort.Sort(wb) |
| 68 | } |
| 69 | rb.merge(wb) |
| 70 | } |
| 71 | txw.reset() |
| 72 | } |
| 73 | |
| 74 | // txReadBuffer accesses buffered updates. |
| 75 | type txReadBuffer struct{ txBuffer } |
| 76 | |
| 77 | func (txr *txReadBuffer) Range(bucketName, key, endKey []byte, limit int64) ([][]byte, [][]byte) { |
| 78 | if b := txr.buckets[string(bucketName)]; b != nil { |
| 79 | return b.Range(key, endKey, limit) |
| 80 | } |
| 81 | return nil, nil |
| 82 | } |
| 83 | |
| 84 | func (txr *txReadBuffer) ForEach(bucketName []byte, visitor func(k, v []byte) error) error { |
| 85 | if b := txr.buckets[string(bucketName)]; b != nil { |
| 86 | return b.ForEach(visitor) |
| 87 | } |
| 88 | return nil |
| 89 | } |
| 90 | |
| 91 | type kv struct { |
| 92 | key []byte |
| 93 | val []byte |
| 94 | } |
| 95 | |
| 96 | // bucketBuffer buffers key-value pairs that are pending commit. |
| 97 | type bucketBuffer struct { |
| 98 | buf []kv |
| 99 | // used tracks number of elements in use so buf can be reused without reallocation. |
| 100 | used int |
| 101 | } |
| 102 | |
| 103 | func newBucketBuffer() *bucketBuffer { |
| 104 | return &bucketBuffer{buf: make([]kv, 512), used: 0} |
| 105 | } |
| 106 | |
| 107 | func (bb *bucketBuffer) Range(key, endKey []byte, limit int64) (keys [][]byte, vals [][]byte) { |
| 108 | f := func(i int) bool { return bytes.Compare(bb.buf[i].key, key) >= 0 } |
| 109 | idx := sort.Search(bb.used, f) |
| 110 | if idx < 0 { |
| 111 | return nil, nil |
| 112 | } |
| 113 | if len(endKey) == 0 { |
| 114 | if bytes.Equal(key, bb.buf[idx].key) { |
| 115 | keys = append(keys, bb.buf[idx].key) |
| 116 | vals = append(vals, bb.buf[idx].val) |
| 117 | } |
| 118 | return keys, vals |
| 119 | } |
| 120 | if bytes.Compare(endKey, bb.buf[idx].key) <= 0 { |
| 121 | return nil, nil |
| 122 | } |
| 123 | for i := idx; i < bb.used && int64(len(keys)) < limit; i++ { |
| 124 | if bytes.Compare(endKey, bb.buf[i].key) <= 0 { |
| 125 | break |
| 126 | } |
| 127 | keys = append(keys, bb.buf[i].key) |
| 128 | vals = append(vals, bb.buf[i].val) |
| 129 | } |
| 130 | return keys, vals |
| 131 | } |
| 132 | |
| 133 | func (bb *bucketBuffer) ForEach(visitor func(k, v []byte) error) error { |
| 134 | for i := 0; i < bb.used; i++ { |
| 135 | if err := visitor(bb.buf[i].key, bb.buf[i].val); err != nil { |
| 136 | return err |
| 137 | } |
| 138 | } |
| 139 | return nil |
| 140 | } |
| 141 | |
| 142 | func (bb *bucketBuffer) add(k, v []byte) { |
| 143 | bb.buf[bb.used].key, bb.buf[bb.used].val = k, v |
| 144 | bb.used++ |
| 145 | if bb.used == len(bb.buf) { |
| 146 | buf := make([]kv, (3*len(bb.buf))/2) |
| 147 | copy(buf, bb.buf) |
| 148 | bb.buf = buf |
| 149 | } |
| 150 | } |
| 151 | |
| 152 | // merge merges data from bb into bbsrc. |
| 153 | func (bb *bucketBuffer) merge(bbsrc *bucketBuffer) { |
| 154 | for i := 0; i < bbsrc.used; i++ { |
| 155 | bb.add(bbsrc.buf[i].key, bbsrc.buf[i].val) |
| 156 | } |
| 157 | if bb.used == bbsrc.used { |
| 158 | return |
| 159 | } |
| 160 | if bytes.Compare(bb.buf[(bb.used-bbsrc.used)-1].key, bbsrc.buf[0].key) < 0 { |
| 161 | return |
| 162 | } |
| 163 | |
| 164 | sort.Stable(bb) |
| 165 | |
| 166 | // remove duplicates, using only newest update |
| 167 | widx := 0 |
| 168 | for ridx := 1; ridx < bb.used; ridx++ { |
| 169 | if !bytes.Equal(bb.buf[ridx].key, bb.buf[widx].key) { |
| 170 | widx++ |
| 171 | } |
| 172 | bb.buf[widx] = bb.buf[ridx] |
| 173 | } |
| 174 | bb.used = widx + 1 |
| 175 | } |
| 176 | |
| 177 | func (bb *bucketBuffer) Len() int { return bb.used } |
| 178 | func (bb *bucketBuffer) Less(i, j int) bool { |
| 179 | return bytes.Compare(bb.buf[i].key, bb.buf[j].key) < 0 |
| 180 | } |
| 181 | func (bb *bucketBuffer) Swap(i, j int) { bb.buf[i], bb.buf[j] = bb.buf[j], bb.buf[i] } |