aboutsummaryrefslogtreecommitdiffstats
path: root/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go
diff options
context:
space:
mode:
Diffstat (limited to 'Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go')
-rw-r--r--Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go524
1 files changed, 0 insertions, 524 deletions
diff --git a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go
deleted file mode 100644
index c60f12c20..000000000
--- a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/version.go
+++ /dev/null
@@ -1,524 +0,0 @@
-// Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com>
-// All rights reserved.
-//
-// Use of this source code is governed by a BSD-style license that can be
-// found in the LICENSE file.
-
-package leveldb
-
-import (
- "fmt"
- "sync/atomic"
- "unsafe"
-
- "github.com/syndtr/goleveldb/leveldb/iterator"
- "github.com/syndtr/goleveldb/leveldb/opt"
- "github.com/syndtr/goleveldb/leveldb/util"
-)
-
-type tSet struct {
- level int
- table *tFile
-}
-
-type version struct {
- s *session
-
- levels []tFiles
-
- // Level that should be compacted next and its compaction score.
- // Score < 1 means compaction is not strictly needed. These fields
- // are initialized by computeCompaction()
- cLevel int
- cScore float64
-
- cSeek unsafe.Pointer
-
- closing bool
- ref int
- // Succeeding version.
- next *version
-}
-
-func newVersion(s *session) *version {
- return &version{s: s}
-}
-
-func (v *version) releaseNB() {
- v.ref--
- if v.ref > 0 {
- return
- }
- if v.ref < 0 {
- panic("negative version ref")
- }
-
- nextTables := make(map[int64]bool)
- for _, tt := range v.next.levels {
- for _, t := range tt {
- num := t.fd.Num
- nextTables[num] = true
- }
- }
-
- for _, tt := range v.levels {
- for _, t := range tt {
- num := t.fd.Num
- if _, ok := nextTables[num]; !ok {
- v.s.tops.remove(t)
- }
- }
- }
-
- v.next.releaseNB()
- v.next = nil
-}
-
-func (v *version) release() {
- v.s.vmu.Lock()
- v.releaseNB()
- v.s.vmu.Unlock()
-}
-
-func (v *version) walkOverlapping(aux tFiles, ikey internalKey, f func(level int, t *tFile) bool, lf func(level int) bool) {
- ukey := ikey.ukey()
-
- // Aux level.
- if aux != nil {
- for _, t := range aux {
- if t.overlaps(v.s.icmp, ukey, ukey) {
- if !f(-1, t) {
- return
- }
- }
- }
-
- if lf != nil && !lf(-1) {
- return
- }
- }
-
- // Walk tables level-by-level.
- for level, tables := range v.levels {
- if len(tables) == 0 {
- continue
- }
-
- if level == 0 {
- // Level-0 files may overlap each other. Find all files that
- // overlap ukey.
- for _, t := range tables {
- if t.overlaps(v.s.icmp, ukey, ukey) {
- if !f(level, t) {
- return
- }
- }
- }
- } else {
- if i := tables.searchMax(v.s.icmp, ikey); i < len(tables) {
- t := tables[i]
- if v.s.icmp.uCompare(ukey, t.imin.ukey()) >= 0 {
- if !f(level, t) {
- return
- }
- }
- }
- }
-
- if lf != nil && !lf(level) {
- return
- }
- }
-}
-
-func (v *version) get(aux tFiles, ikey internalKey, ro *opt.ReadOptions, noValue bool) (value []byte, tcomp bool, err error) {
- if v.closing {
- return nil, false, ErrClosed
- }
-
- ukey := ikey.ukey()
-
- var (
- tset *tSet
- tseek bool
-
- // Level-0.
- zfound bool
- zseq uint64
- zkt keyType
- zval []byte
- )
-
- err = ErrNotFound
-
- // Since entries never hop across level, finding key/value
- // in smaller level make later levels irrelevant.
- v.walkOverlapping(aux, ikey, func(level int, t *tFile) bool {
- if level >= 0 && !tseek {
- if tset == nil {
- tset = &tSet{level, t}
- } else {
- tseek = true
- }
- }
-
- var (
- fikey, fval []byte
- ferr error
- )
- if noValue {
- fikey, ferr = v.s.tops.findKey(t, ikey, ro)
- } else {
- fikey, fval, ferr = v.s.tops.find(t, ikey, ro)
- }
-
- switch ferr {
- case nil:
- case ErrNotFound:
- return true
- default:
- err = ferr
- return false
- }
-
- if fukey, fseq, fkt, fkerr := parseInternalKey(fikey); fkerr == nil {
- if v.s.icmp.uCompare(ukey, fukey) == 0 {
- // Level <= 0 may overlaps each-other.
- if level <= 0 {
- if fseq >= zseq {
- zfound = true
- zseq = fseq
- zkt = fkt
- zval = fval
- }
- } else {
- switch fkt {
- case keyTypeVal:
- value = fval
- err = nil
- case keyTypeDel:
- default:
- panic("leveldb: invalid internalKey type")
- }
- return false
- }
- }
- } else {
- err = fkerr
- return false
- }
-
- return true
- }, func(level int) bool {
- if zfound {
- switch zkt {
- case keyTypeVal:
- value = zval
- err = nil
- case keyTypeDel:
- default:
- panic("leveldb: invalid internalKey type")
- }
- return false
- }
-
- return true
- })
-
- if tseek && tset.table.consumeSeek() <= 0 {
- tcomp = atomic.CompareAndSwapPointer(&v.cSeek, nil, unsafe.Pointer(tset))
- }
-
- return
-}
-
-func (v *version) sampleSeek(ikey internalKey) (tcomp bool) {
- var tset *tSet
-
- v.walkOverlapping(nil, ikey, func(level int, t *tFile) bool {
- if tset == nil {
- tset = &tSet{level, t}
- return true
- }
- if tset.table.consumeSeek() <= 0 {
- tcomp = atomic.CompareAndSwapPointer(&v.cSeek, nil, unsafe.Pointer(tset))
- }
- return false
- }, nil)
-
- return
-}
-
-func (v *version) getIterators(slice *util.Range, ro *opt.ReadOptions) (its []iterator.Iterator) {
- strict := opt.GetStrict(v.s.o.Options, ro, opt.StrictReader)
- for level, tables := range v.levels {
- if level == 0 {
- // Merge all level zero files together since they may overlap.
- for _, t := range tables {
- its = append(its, v.s.tops.newIterator(t, slice, ro))
- }
- } else if len(tables) != 0 {
- its = append(its, iterator.NewIndexedIterator(tables.newIndexIterator(v.s.tops, v.s.icmp, slice, ro), strict))
- }
- }
- return
-}
-
-func (v *version) newStaging() *versionStaging {
- return &versionStaging{base: v}
-}
-
-// Spawn a new version based on this version.
-func (v *version) spawn(r *sessionRecord) *version {
- staging := v.newStaging()
- staging.commit(r)
- return staging.finish()
-}
-
-func (v *version) fillRecord(r *sessionRecord) {
- for level, tables := range v.levels {
- for _, t := range tables {
- r.addTableFile(level, t)
- }
- }
-}
-
-func (v *version) tLen(level int) int {
- if level < len(v.levels) {
- return len(v.levels[level])
- }
- return 0
-}
-
-func (v *version) offsetOf(ikey internalKey) (n int64, err error) {
- for level, tables := range v.levels {
- for _, t := range tables {
- if v.s.icmp.Compare(t.imax, ikey) <= 0 {
- // Entire file is before "ikey", so just add the file size
- n += t.size
- } else if v.s.icmp.Compare(t.imin, ikey) > 0 {
- // Entire file is after "ikey", so ignore
- if level > 0 {
- // Files other than level 0 are sorted by meta->min, so
- // no further files in this level will contain data for
- // "ikey".
- break
- }
- } else {
- // "ikey" falls in the range for this table. Add the
- // approximate offset of "ikey" within the table.
- if m, err := v.s.tops.offsetOf(t, ikey); err == nil {
- n += m
- } else {
- return 0, err
- }
- }
- }
- }
-
- return
-}
-
-func (v *version) pickMemdbLevel(umin, umax []byte, maxLevel int) (level int) {
- if maxLevel > 0 {
- if len(v.levels) == 0 {
- return maxLevel
- }
- if !v.levels[0].overlaps(v.s.icmp, umin, umax, true) {
- var overlaps tFiles
- for ; level < maxLevel; level++ {
- if pLevel := level + 1; pLevel >= len(v.levels) {
- return maxLevel
- } else if v.levels[pLevel].overlaps(v.s.icmp, umin, umax, false) {
- break
- }
- if gpLevel := level + 2; gpLevel < len(v.levels) {
- overlaps = v.levels[gpLevel].getOverlaps(overlaps, v.s.icmp, umin, umax, false)
- if overlaps.size() > int64(v.s.o.GetCompactionGPOverlaps(level)) {
- break
- }
- }
- }
- }
- }
- return
-}
-
-func (v *version) computeCompaction() {
- // Precomputed best level for next compaction
- bestLevel := int(-1)
- bestScore := float64(-1)
-
- statFiles := make([]int, len(v.levels))
- statSizes := make([]string, len(v.levels))
- statScore := make([]string, len(v.levels))
- statTotSize := int64(0)
-
- for level, tables := range v.levels {
- var score float64
- size := tables.size()
- if level == 0 {
- // We treat level-0 specially by bounding the number of files
- // instead of number of bytes for two reasons:
- //
- // (1) With larger write-buffer sizes, it is nice not to do too
- // many level-0 compaction.
- //
- // (2) The files in level-0 are merged on every read and
- // therefore we wish to avoid too many files when the individual
- // file size is small (perhaps because of a small write-buffer
- // setting, or very high compression ratios, or lots of
- // overwrites/deletions).
- score = float64(len(tables)) / float64(v.s.o.GetCompactionL0Trigger())
- } else {
- score = float64(size) / float64(v.s.o.GetCompactionTotalSize(level))
- }
-
- if score > bestScore {
- bestLevel = level
- bestScore = score
- }
-
- statFiles[level] = len(tables)
- statSizes[level] = shortenb(int(size))
- statScore[level] = fmt.Sprintf("%.2f", score)
- statTotSize += size
- }
-
- v.cLevel = bestLevel
- v.cScore = bestScore
-
- v.s.logf("version@stat F·%v S·%s%v Sc·%v", statFiles, shortenb(int(statTotSize)), statSizes, statScore)
-}
-
-func (v *version) needCompaction() bool {
- return v.cScore >= 1 || atomic.LoadPointer(&v.cSeek) != nil
-}
-
-type tablesScratch struct {
- added map[int64]atRecord
- deleted map[int64]struct{}
-}
-
-type versionStaging struct {
- base *version
- levels []tablesScratch
-}
-
-func (p *versionStaging) getScratch(level int) *tablesScratch {
- if level >= len(p.levels) {
- newLevels := make([]tablesScratch, level+1)
- copy(newLevels, p.levels)
- p.levels = newLevels
- }
- return &(p.levels[level])
-}
-
-func (p *versionStaging) commit(r *sessionRecord) {
- // Deleted tables.
- for _, r := range r.deletedTables {
- scratch := p.getScratch(r.level)
- if r.level < len(p.base.levels) && len(p.base.levels[r.level]) > 0 {
- if scratch.deleted == nil {
- scratch.deleted = make(map[int64]struct{})
- }
- scratch.deleted[r.num] = struct{}{}
- }
- if scratch.added != nil {
- delete(scratch.added, r.num)
- }
- }
-
- // New tables.
- for _, r := range r.addedTables {
- scratch := p.getScratch(r.level)
- if scratch.added == nil {
- scratch.added = make(map[int64]atRecord)
- }
- scratch.added[r.num] = r
- if scratch.deleted != nil {
- delete(scratch.deleted, r.num)
- }
- }
-}
-
-func (p *versionStaging) finish() *version {
- // Build new version.
- nv := newVersion(p.base.s)
- numLevel := len(p.levels)
- if len(p.base.levels) > numLevel {
- numLevel = len(p.base.levels)
- }
- nv.levels = make([]tFiles, numLevel)
- for level := 0; level < numLevel; level++ {
- var baseTabels tFiles
- if level < len(p.base.levels) {
- baseTabels = p.base.levels[level]
- }
-
- if level < len(p.levels) {
- scratch := p.levels[level]
-
- var nt tFiles
- // Prealloc list if possible.
- if n := len(baseTabels) + len(scratch.added) - len(scratch.deleted); n > 0 {
- nt = make(tFiles, 0, n)
- }
-
- // Base tables.
- for _, t := range baseTabels {
- if _, ok := scratch.deleted[t.fd.Num]; ok {
- continue
- }
- if _, ok := scratch.added[t.fd.Num]; ok {
- continue
- }
- nt = append(nt, t)
- }
-
- // New tables.
- for _, r := range scratch.added {
- nt = append(nt, tableFileFromRecord(r))
- }
-
- if len(nt) != 0 {
- // Sort tables.
- if level == 0 {
- nt.sortByNum()
- } else {
- nt.sortByKey(p.base.s.icmp)
- }
-
- nv.levels[level] = nt
- }
- } else {
- nv.levels[level] = baseTabels
- }
- }
-
- // Trim levels.
- n := len(nv.levels)
- for ; n > 0 && nv.levels[n-1] == nil; n-- {
- }
- nv.levels = nv.levels[:n]
-
- // Compute compaction score for new version.
- nv.computeCompaction()
-
- return nv
-}
-
-type versionReleaser struct {
- v *version
- once bool
-}
-
-func (vr *versionReleaser) Release() {
- v := vr.v
- v.s.vmu.Lock()
- if !vr.once {
- v.releaseNB()
- vr.once = true
- }
- v.s.vmu.Unlock()
-}
generated by cgit (git 2.34.1) at 2024-10-20 11:54:20 +0800