diff options
Diffstat (limited to 'Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/table.go')
-rw-r--r-- | Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/table.go | 424 |
1 files changed, 424 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/table.go b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/table.go new file mode 100644 index 000000000..fdd5d2bcf --- /dev/null +++ b/Godeps/_workspace/src/github.com/syndtr/goleveldb/leveldb/table.go @@ -0,0 +1,424 @@ +// 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 ( + "sort" + "sync/atomic" + + "github.com/syndtr/goleveldb/leveldb/cache" + "github.com/syndtr/goleveldb/leveldb/comparer" + "github.com/syndtr/goleveldb/leveldb/iterator" + "github.com/syndtr/goleveldb/leveldb/opt" + "github.com/syndtr/goleveldb/leveldb/storage" + "github.com/syndtr/goleveldb/leveldb/table" + "github.com/syndtr/goleveldb/leveldb/util" +) + +// table file +type tFile struct { + file storage.File + seekLeft int32 + size uint64 + min, max iKey +} + +// test if key is after t +func (t *tFile) isAfter(key []byte, ucmp comparer.BasicComparer) bool { + return key != nil && ucmp.Compare(key, t.max.ukey()) > 0 +} + +// test if key is before t +func (t *tFile) isBefore(key []byte, ucmp comparer.BasicComparer) bool { + return key != nil && ucmp.Compare(key, t.min.ukey()) < 0 +} + +func (t *tFile) incrSeek() int32 { + return atomic.AddInt32(&t.seekLeft, -1) +} + +func newTFile(file storage.File, size uint64, min, max iKey) *tFile { + f := &tFile{ + file: file, + size: size, + min: min, + max: max, + } + + // We arrange to automatically compact this file after + // a certain number of seeks. Let's assume: + // (1) One seek costs 10ms + // (2) Writing or reading 1MB costs 10ms (100MB/s) + // (3) A compaction of 1MB does 25MB of IO: + // 1MB read from this level + // 10-12MB read from next level (boundaries may be misaligned) + // 10-12MB written to next level + // This implies that 25 seeks cost the same as the compaction + // of 1MB of data. I.e., one seek costs approximately the + // same as the compaction of 40KB of data. We are a little + // conservative and allow approximately one seek for every 16KB + // of data before triggering a compaction. + f.seekLeft = int32(size / 16384) + if f.seekLeft < 100 { + f.seekLeft = 100 + } + + return f +} + +// table files +type tFiles []*tFile + +func (tf tFiles) Len() int { return len(tf) } +func (tf tFiles) Swap(i, j int) { tf[i], tf[j] = tf[j], tf[i] } + +func (tf tFiles) lessByKey(icmp *iComparer, i, j int) bool { + a, b := tf[i], tf[j] + n := icmp.Compare(a.min, b.min) + if n == 0 { + return a.file.Num() < b.file.Num() + } + return n < 0 +} + +func (tf tFiles) lessByNum(i, j int) bool { + return tf[i].file.Num() > tf[j].file.Num() +} + +func (tf tFiles) sortByKey(icmp *iComparer) { + sort.Sort(&tFilesSortByKey{tFiles: tf, icmp: icmp}) +} + +func (tf tFiles) sortByNum() { + sort.Sort(&tFilesSortByNum{tFiles: tf}) +} + +func (tf tFiles) size() (sum uint64) { + for _, t := range tf { + sum += t.size + } + return sum +} + +func (tf tFiles) searchMin(key iKey, icmp *iComparer) int { + return sort.Search(len(tf), func(i int) bool { + return icmp.Compare(tf[i].min, key) >= 0 + }) +} + +func (tf tFiles) searchMax(key iKey, icmp *iComparer) int { + return sort.Search(len(tf), func(i int) bool { + return icmp.Compare(tf[i].max, key) >= 0 + }) +} + +func (tf tFiles) isOverlaps(min, max []byte, disjSorted bool, icmp *iComparer) bool { + if !disjSorted { + // Need to check against all files + for _, t := range tf { + if !t.isAfter(min, icmp.ucmp) && !t.isBefore(max, icmp.ucmp) { + return true + } + } + return false + } + + var idx int + if len(min) > 0 { + // Find the earliest possible internal key for min + idx = tf.searchMax(newIKey(min, kMaxSeq, tSeek), icmp) + } + + if idx >= len(tf) { + // beginning of range is after all files, so no overlap + return false + } + return !tf[idx].isBefore(max, icmp.ucmp) +} + +func (tf tFiles) getOverlaps(min, max []byte, r *tFiles, disjSorted bool, ucmp comparer.BasicComparer) { + for i := 0; i < len(tf); { + t := tf[i] + i++ + if t.isAfter(min, ucmp) || t.isBefore(max, ucmp) { + continue + } + + *r = append(*r, t) + if !disjSorted { + // Level-0 files may overlap each other. So check if the newly + // added file has expanded the range. If so, restart search. + if min != nil && ucmp.Compare(t.min.ukey(), min) < 0 { + min = t.min.ukey() + *r = nil + i = 0 + } else if max != nil && ucmp.Compare(t.max.ukey(), max) > 0 { + max = t.max.ukey() + *r = nil + i = 0 + } + } + } + + return +} + +func (tf tFiles) getRange(icmp *iComparer) (min, max iKey) { + for i, t := range tf { + if i == 0 { + min, max = t.min, t.max + continue + } + if icmp.Compare(t.min, min) < 0 { + min = t.min + } + if icmp.Compare(t.max, max) > 0 { + max = t.max + } + } + + return +} + +func (tf tFiles) newIndexIterator(tops *tOps, icmp *iComparer, slice *util.Range, ro *opt.ReadOptions) iterator.IteratorIndexer { + if slice != nil { + var start, limit int + if slice.Start != nil { + start = tf.searchMax(iKey(slice.Start), icmp) + } + if slice.Limit != nil { + limit = tf.searchMin(iKey(slice.Limit), icmp) + } else { + limit = tf.Len() + } + tf = tf[start:limit] + } + return iterator.NewArrayIndexer(&tFilesArrayIndexer{ + tFiles: tf, + tops: tops, + icmp: icmp, + slice: slice, + ro: ro, + }) +} + +type tFilesArrayIndexer struct { + tFiles + tops *tOps + icmp *iComparer + slice *util.Range + ro *opt.ReadOptions +} + +func (a *tFilesArrayIndexer) Search(key []byte) int { + return a.searchMax(iKey(key), a.icmp) +} + +func (a *tFilesArrayIndexer) Get(i int) iterator.Iterator { + if i == 0 || i == a.Len()-1 { + return a.tops.newIterator(a.tFiles[i], a.slice, a.ro) + } + return a.tops.newIterator(a.tFiles[i], nil, a.ro) +} + +type tFilesSortByKey struct { + tFiles + icmp *iComparer +} + +func (x *tFilesSortByKey) Less(i, j int) bool { + return x.lessByKey(x.icmp, i, j) +} + +type tFilesSortByNum struct { + tFiles +} + +func (x *tFilesSortByNum) Less(i, j int) bool { + return x.lessByNum(i, j) +} + +// table operations +type tOps struct { + s *session + cache cache.Cache + cacheNS cache.Namespace +} + +func newTableOps(s *session, cacheCap int) *tOps { + c := cache.NewLRUCache(cacheCap) + ns := c.GetNamespace(0) + return &tOps{s, c, ns} +} + +func (t *tOps) create() (*tWriter, error) { + file := t.s.getTableFile(t.s.allocFileNum()) + fw, err := file.Create() + if err != nil { + return nil, err + } + return &tWriter{ + t: t, + file: file, + w: fw, + tw: table.NewWriter(fw, t.s.o), + }, nil +} + +func (t *tOps) createFrom(src iterator.Iterator) (f *tFile, n int, err error) { + w, err := t.create() + if err != nil { + return f, n, err + } + + defer func() { + if err != nil { + w.drop() + } + }() + + for src.Next() { + err = w.add(src.Key(), src.Value()) + if err != nil { + return + } + } + err = src.Error() + if err != nil { + return + } + + n = w.tw.EntriesLen() + f, err = w.finish() + return +} + +func (t *tOps) lookup(f *tFile) (c cache.Object, err error) { + num := f.file.Num() + c, ok := t.cacheNS.Get(num, func() (ok bool, value interface{}, charge int, fin cache.SetFin) { + var r storage.Reader + r, err = f.file.Open() + if err != nil { + return + } + + o := t.s.o + + var cacheNS cache.Namespace + if bc := o.GetBlockCache(); bc != nil { + cacheNS = bc.GetNamespace(num) + } + + ok = true + value = table.NewReader(r, int64(f.size), cacheNS, o) + charge = 1 + fin = func() { + r.Close() + } + return + }) + if !ok && err == nil { + err = ErrClosed + } + return +} + +func (t *tOps) get(f *tFile, key []byte, ro *opt.ReadOptions) (rkey, rvalue []byte, err error) { + c, err := t.lookup(f) + if err != nil { + return nil, nil, err + } + defer c.Release() + return c.Value().(*table.Reader).Find(key, ro) +} + +func (t *tOps) offsetOf(f *tFile, key []byte) (offset uint64, err error) { + c, err := t.lookup(f) + if err != nil { + return + } + _offset, err := c.Value().(*table.Reader).OffsetOf(key) + offset = uint64(_offset) + c.Release() + return +} + +func (t *tOps) newIterator(f *tFile, slice *util.Range, ro *opt.ReadOptions) iterator.Iterator { + c, err := t.lookup(f) + if err != nil { + return iterator.NewEmptyIterator(err) + } + iter := c.Value().(*table.Reader).NewIterator(slice, ro) + iter.SetReleaser(c) + return iter +} + +func (t *tOps) remove(f *tFile) { + num := f.file.Num() + t.cacheNS.Delete(num, func(exist bool) { + if err := f.file.Remove(); err != nil { + t.s.logf("table@remove removing @%d %q", num, err) + } else { + t.s.logf("table@remove removed @%d", num) + } + if bc := t.s.o.GetBlockCache(); bc != nil { + bc.GetNamespace(num).Zap(false) + } + }) +} + +func (t *tOps) close() { + t.cache.Zap(true) +} + +type tWriter struct { + t *tOps + + file storage.File + w storage.Writer + tw *table.Writer + + first, last []byte +} + +func (w *tWriter) add(key, value []byte) error { + if w.first == nil { + w.first = append([]byte{}, key...) + } + w.last = append(w.last[:0], key...) + return w.tw.Append(key, value) +} + +func (w *tWriter) empty() bool { + return w.first == nil +} + +func (w *tWriter) finish() (f *tFile, err error) { + err = w.tw.Close() + if err != nil { + return + } + err = w.w.Sync() + if err != nil { + w.w.Close() + return + } + w.w.Close() + f = newTFile(w.file, uint64(w.tw.BytesLen()), iKey(w.first), iKey(w.last)) + return +} + +func (w *tWriter) drop() { + w.w.Close() + w.file.Remove() + w.t.s.reuseFileNum(w.file.Num()) + w.w = nil + w.file = nil + w.tw = nil + w.first = nil + w.last = nil +} |