vendor/github.com/syndtr/goleveldb/leveldb/iterator/merged_iter.go

   1 // Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com>
   2 // All rights reserved.
   3 //
   4 // Use of this source code is governed by a BSD-style license that can be
   5 // found in the LICENSE file.
   6
   7 package iterator
   8
   9 import (
  10         "github.com/syndtr/goleveldb/leveldb/comparer"
  11         "github.com/syndtr/goleveldb/leveldb/errors"
  12         "github.com/syndtr/goleveldb/leveldb/util"
  13 )
  14
  15 type dir int
  16
  17 const (
  18         dirReleased dir = iota - 1
  19         dirSOI
  20         dirEOI
  21         dirBackward
  22         dirForward
  23 )
  24
  25 type mergedIterator struct {
  26         cmp    comparer.Comparer
  27         iters  []Iterator
  28         strict bool
  29
  30         keys     [][]byte
  31         index    int
  32         dir      dir
  33         err      error
  34         errf     func(err error)
  35         releaser util.Releaser
  36 }
  37
  38 func assertKey(key []byte) []byte {
  39         if key == nil {
  40                 panic("leveldb/iterator: nil key")
  41         }
  42         return key
  43 }
  44
  45 func (i *mergedIterator) iterErr(iter Iterator) bool {
  46         if err := iter.Error(); err != nil {
  47                 if i.errf != nil {
  48                         i.errf(err)
  49                 }
  50                 if i.strict || !errors.IsCorrupted(err) {
  51                         i.err = err
  52                         return true
  53                 }
  54         }
  55         return false
  56 }
  57
  58 func (i *mergedIterator) Valid() bool {
  59         return i.err == nil && i.dir > dirEOI
  60 }
  61
  62 func (i *mergedIterator) First() bool {
  63         if i.err != nil {
  64                 return false
  65         } else if i.dir == dirReleased {
  66                 i.err = ErrIterReleased
  67                 return false
  68         }
  69
  70         for x, iter := range i.iters {
  71                 switch {
  72                 case iter.First():
  73                         i.keys[x] = assertKey(iter.Key())
  74                 case i.iterErr(iter):
  75                         return false
  76                 default:
  77                         i.keys[x] = nil
  78                 }
  79         }
  80         i.dir = dirSOI
  81         return i.next()
  82 }
  83
  84 func (i *mergedIterator) Last() bool {
  85         if i.err != nil {
  86                 return false
  87         } else if i.dir == dirReleased {
  88                 i.err = ErrIterReleased
  89                 return false
  90         }
  91
  92         for x, iter := range i.iters {
  93                 switch {
  94                 case iter.Last():
  95                         i.keys[x] = assertKey(iter.Key())
  96                 case i.iterErr(iter):
  97                         return false
  98                 default:
  99                         i.keys[x] = nil
 100                 }
 101         }
 102         i.dir = dirEOI
 103         return i.prev()
 104 }
 105
 106 func (i *mergedIterator) Seek(key []byte) bool {
 107         if i.err != nil {
 108                 return false
 109         } else if i.dir == dirReleased {
 110                 i.err = ErrIterReleased
 111                 return false
 112         }
 113
 114         for x, iter := range i.iters {
 115                 switch {
 116                 case iter.Seek(key):
 117                         i.keys[x] = assertKey(iter.Key())
 118                 case i.iterErr(iter):
 119                         return false
 120                 default:
 121                         i.keys[x] = nil
 122                 }
 123         }
 124         i.dir = dirSOI
 125         return i.next()
 126 }
 127
 128 func (i *mergedIterator) next() bool {
 129         var key []byte
 130         if i.dir == dirForward {
 131                 key = i.keys[i.index]
 132         }
 133         for x, tkey := range i.keys {
 134                 if tkey != nil && (key == nil || i.cmp.Compare(tkey, key) < 0) {
 135                         key = tkey
 136                         i.index = x
 137                 }
 138         }
 139         if key == nil {
 140                 i.dir = dirEOI
 141                 return false
 142         }
 143         i.dir = dirForward
 144         return true
 145 }
 146
 147 func (i *mergedIterator) Next() bool {
 148         if i.dir == dirEOI || i.err != nil {
 149                 return false
 150         } else if i.dir == dirReleased {
 151                 i.err = ErrIterReleased
 152                 return false
 153         }
 154
 155         switch i.dir {
 156         case dirSOI:
 157                 return i.First()
 158         case dirBackward:
 159                 key := append([]byte{}, i.keys[i.index]...)
 160                 if !i.Seek(key) {
 161                         return false
 162                 }
 163                 return i.Next()
 164         }
 165
 166         x := i.index
 167         iter := i.iters[x]
 168         switch {
 169         case iter.Next():
 170                 i.keys[x] = assertKey(iter.Key())
 171         case i.iterErr(iter):
 172                 return false
 173         default:
 174                 i.keys[x] = nil
 175         }
 176         return i.next()
 177 }
 178
 179 func (i *mergedIterator) prev() bool {
 180         var key []byte
 181         if i.dir == dirBackward {
 182                 key = i.keys[i.index]
 183         }
 184         for x, tkey := range i.keys {
 185                 if tkey != nil && (key == nil || i.cmp.Compare(tkey, key) > 0) {
 186                         key = tkey
 187                         i.index = x
 188                 }
 189         }
 190         if key == nil {
 191                 i.dir = dirSOI
 192                 return false
 193         }
 194         i.dir = dirBackward
 195         return true
 196 }
 197
 198 func (i *mergedIterator) Prev() bool {
 199         if i.dir == dirSOI || i.err != nil {
 200                 return false
 201         } else if i.dir == dirReleased {
 202                 i.err = ErrIterReleased
 203                 return false
 204         }
 205
 206         switch i.dir {
 207         case dirEOI:
 208                 return i.Last()
 209         case dirForward:
 210                 key := append([]byte{}, i.keys[i.index]...)
 211                 for x, iter := range i.iters {
 212                         if x == i.index {
 213                                 continue
 214                         }
 215                         seek := iter.Seek(key)
 216                         switch {
 217                         case seek && iter.Prev(), !seek && iter.Last():
 218                                 i.keys[x] = assertKey(iter.Key())
 219                         case i.iterErr(iter):
 220                                 return false
 221                         default:
 222                                 i.keys[x] = nil
 223                         }
 224                 }
 225         }
 226
 227         x := i.index
 228         iter := i.iters[x]
 229         switch {
 230         case iter.Prev():
 231                 i.keys[x] = assertKey(iter.Key())
 232         case i.iterErr(iter):
 233                 return false
 234         default:
 235                 i.keys[x] = nil
 236         }
 237         return i.prev()
 238 }
 239
 240 func (i *mergedIterator) Key() []byte {
 241         if i.err != nil || i.dir <= dirEOI {
 242                 return nil
 243         }
 244         return i.keys[i.index]
 245 }
 246
 247 func (i *mergedIterator) Value() []byte {
 248         if i.err != nil || i.dir <= dirEOI {
 249                 return nil
 250         }
 251         return i.iters[i.index].Value()
 252 }
 253
 254 func (i *mergedIterator) Release() {
 255         if i.dir != dirReleased {
 256                 i.dir = dirReleased
 257                 for _, iter := range i.iters {
 258                         iter.Release()
 259                 }
 260                 i.iters = nil
 261                 i.keys = nil
 262                 if i.releaser != nil {
 263                         i.releaser.Release()
 264                         i.releaser = nil
 265                 }
 266         }
 267 }
 268
 269 func (i *mergedIterator) SetReleaser(releaser util.Releaser) {
 270         if i.dir == dirReleased {
 271                 panic(util.ErrReleased)
 272         }
 273         if i.releaser != nil && releaser != nil {
 274                 panic(util.ErrHasReleaser)
 275         }
 276         i.releaser = releaser
 277 }
 278
 279 func (i *mergedIterator) Error() error {
 280         return i.err
 281 }
 282
 283 func (i *mergedIterator) SetErrorCallback(f func(err error)) {
 284         i.errf = f
 285 }
 286
 287 // NewMergedIterator returns an iterator that merges its input. Walking the
 288 // resultant iterator will return all key/value pairs of all input iterators
 289 // in strictly increasing key order, as defined by cmp.
 290 // The input's key ranges may overlap, but there are assumed to be no duplicate
 291 // keys: if iters[i] contains a key k then iters[j] will not contain that key k.
 292 // None of the iters may be nil.
 293 //
 294 // If strict is true the any 'corruption errors' (i.e errors.IsCorrupted(err) == true)
 295 // won't be ignored and will halt 'merged iterator', otherwise the iterator will
 296 // continue to the next 'input iterator'.
 297 func NewMergedIterator(iters []Iterator, cmp comparer.Comparer, strict bool) Iterator {
 298         return &mergedIterator{
 299                 iters:  iters,
 300                 cmp:    cmp,
 301                 strict: strict,
 302                 keys:   make([][]byte, len(iters)),
 303         }
 304 }