// checkOrdering checks that the files are consistent with respect to
// increasing file numbers (for level 0 files) and increasing and non-
// overlapping internal key ranges (for level non-0 files).
func (v *version) checkOrdering(icmp db.Comparer) error {
	for level, ff := range v.files {
		if level == 0 {
			prevFileNum := uint64(0)
			for i, f := range ff {
				if i != 0 && prevFileNum >= f.fileNum {
					return fmt.Errorf("level 0 files are not in increasing fileNum order: %d, %d", prevFileNum, f.fileNum)
				}
				prevFileNum = f.fileNum
			}
		} else {
			prevLargest := internalKey(nil)
			for i, f := range ff {
				if i != 0 && icmp.Compare(prevLargest, f.smallest) >= 0 {
					return fmt.Errorf("level non-0 files are not in increasing ikey order: %q, %q", prevLargest, f.smallest)
				}
				if icmp.Compare(f.smallest, f.largest) > 0 {
					return fmt.Errorf("level non-0 file has inconsistent bounds: %q, %q", f.smallest, f.largest)
				}
				prevLargest = f.largest
			}
		}
	}
	return nil
}

// isBaseLevelForUkey reports whether it is guaranteed that there are no
// key/value pairs at c.level+2 or higher that have the user key ukey.
func (c *compaction) isBaseLevelForUkey(userCmp db.Comparer, ukey []byte) bool {
	// TODO: this can be faster if ukey is always increasing between successive
	// isBaseLevelForUkey calls and we can keep some state in between calls.
	for level := c.level + 2; level < numLevels; level++ {
		for _, f := range c.version.files[level] {
			if userCmp.Compare(ukey, f.largest.ukey()) <= 0 {
				if userCmp.Compare(ukey, f.smallest.ukey()) >= 0 {
					return false
				}
				// For levels above level 0, the files within a level are in
				// increasing ikey order, so we can break early.
				break
			}
		}
	}
	return true
}

// seek returns a blockIter positioned at the first key/value pair whose key is
// >= the given key. If there is no such key, the blockIter returned is done.
func (b block) seek(c db.Comparer, key []byte) (*blockIter, error) {
	numRestarts := int(binary.LittleEndian.Uint32(b[len(b)-4:]))
	if numRestarts == 0 {
		return nil, errors.New("leveldb/table: invalid table (block has no restart points)")
	}
	n := len(b) - 4*(1+numRestarts)
	var offset int
	if len(key) > 0 {
		// Find the index of the smallest restart point whose key is > the key
		// sought; index will be numRestarts if there is no such restart point.
		index := sort.Search(numRestarts, func(i int) bool {
			o := int(binary.LittleEndian.Uint32(b[n+4*i:]))
			// For a restart point, there are 0 bytes shared with the previous key.
			// The varint encoding of 0 occupies 1 byte.
			o++
			// Decode the key at that restart point, and compare it to the key sought.
			v1, n1 := binary.Uvarint(b[o:])
			_, n2 := binary.Uvarint(b[o+n1:])
			m := o + n1 + n2
			s := b[m : m+int(v1)]
			return c.Compare(s, key) > 0
		})
		// Since keys are strictly increasing, if index > 0 then the restart
		// point at index-1 will be the largest whose key is <= the key sought.
		// If index == 0, then all keys in this block are larger than the key
		// sought, and offset remains at zero.
		if index > 0 {
			offset = int(binary.LittleEndian.Uint32(b[n+4*(index-1):]))
		}
	}
	// Initialize the blockIter to the restart point.
	i := &blockIter{
		data: b[offset:n],
		key:  make([]byte, 0, 256),
	}
	// Iterate from that restart point to somewhere >= the key sought.
	for i.Next() && c.Compare(i.key, key) < 0 {
	}
	if i.err != nil {
		return nil, i.err
	}
	i.soi = !i.eoi
	return i, nil
}

// ikeyRange returns the minimum smallest and maximum largest internalKey for
// all the fileMetadata in f0 and f1.
func ikeyRange(icmp db.Comparer, f0, f1 []fileMetadata) (smallest, largest internalKey) {
	first := true
	for _, f := range [2][]fileMetadata{f0, f1} {
		for _, meta := range f {
			if first {
				first = false
				smallest, largest = meta.smallest, meta.largest
				continue
			}
			if icmp.Compare(meta.smallest, smallest) < 0 {
				smallest = meta.smallest
			}
			if icmp.Compare(meta.largest, largest) > 0 {
				largest = meta.largest
			}
		}
	}
	return smallest, largest
}

// internalGet looks up the first key/value pair whose (internal) key is >=
// ikey, according to the internal key ordering, and also returns whether or
// not that search was conclusive.
//
// If there is no such pair, or that pair's key and ikey do not share the same
// user key (according to ucmp), then conclusive will be false. Otherwise,
// conclusive will be true and:
//	* if that pair's key's kind is set, that pair's value will be returned,
//	* if that pair's key's kind is delete, db.ErrNotFound will be returned.
// If the returned error is non-nil then conclusive will be true.
func internalGet(t db.Iterator, ucmp db.Comparer, ukey []byte) (value []byte, conclusive bool, err error) {
	if !t.Next() {
		err = t.Close()
		return nil, err != nil, err
	}
	ikey0 := internalKey(t.Key())
	if !ikey0.valid() {
		t.Close()
		return nil, true, fmt.Errorf("leveldb: corrupt table: invalid internal key")
	}
	if ucmp.Compare(ukey, ikey0.ukey()) != 0 {
		err = t.Close()
		return nil, err != nil, err
	}
	if ikey0.kind() == internalKeyKindDelete {
		t.Close()
		return nil, true, db.ErrNotFound
	}
	return t.Value(), true, t.Close()
}

/*
本方法从v.files[level]中返回其key- ukey0 < key < ukey1 的文件
对于非0 level，是认为其db文件的用户key的范围是不会有重合的，对于level0，该假设则是不成立的
*/
func (v *version) overlaps(level int, ucmp db.Comparer, ukey0, ukey1 []byte) (ret []fileMetadata) {
loop:
	for {
		for _, meta := range v.files[level] {
			m0 := meta.smallest.ukey()
			m1 := meta.largest.ukey()
			// ukey0 is smallest, ukey1 is largest
			// 如果当前文件的最大用户key小于第一个文件的最小用户key，则跳过
			if ucmp.Compare(m1, ukey0) < 0 {
				// meta is completely before the specified range; skip it.
				continue
			}
			// 如果当前文件的最小用户key大于第一个文件的最大用户key，则也跳过
			if ucmp.Compare(m0, ukey1) > 0 {
				// meta is completely after the specified range; skip it.
				continue
			}
			// 否则则表示当前文件的用户key的范围与第一个文件的用户key的范围有重合
			// 需要将该文件返回
			ret = append(ret, meta)

			// If level == 0, check if the newly added fileMetadata has
			// expanded the range. If so, restart the search.
			if level != 0 {
				continue
			}
			// 对于level 0
			restart := false
			// 如果当前文件的最小用户key小于第一个文件的最小用户key，则将当前文件的最小用户key作为新的条件来重新搜索
			if ucmp.Compare(m0, ukey0) < 0 {
				ukey0 = m0
				restart = true
			}
			// 如果当前文件的最大用户key大于第一个文件的最大用户key，则将当前文件的最大用户key作为新的条件来重新搜索
			// 这样文件之间用户key重合的可能性就更大了
			if ucmp.Compare(m1, ukey1) > 0 {
				ukey1 = m1
				restart = true
			}
			if restart {
				ret = ret[:0]
				continue loop
			}
		}
		return ret
	}
	panic("unreachable")
}

// internalGet looks up the first key/value pair whose (internal) key is >=
// ikey, according to the internal key ordering, and also returns whether or
// not that search was conclusive.
//
// If there is no such pair, or that pair's key and ikey do not share the same
// user key (according to ucmp), then conclusive will be false. Otherwise,
// conclusive will be true and:
//    * if that pair's key's kind is set, that pair's value will be returned,
//    * if that pair's key's kind is delete, db.ErrNotFound will be returned.
// If the returned error is non-nil then conclusive will be true.
func internalGet(t db.Iterator, ucmp db.Comparer, ukey []byte) (value []byte, conclusive bool, err error) {
	if !t.Next() {
		err = t.Close()
		return nil, err != nil, err
	}
	ikey0 := internalKey(t.Key())
	if !ikey0.valid() {
		t.Close()
		return nil, true, fmt.Errorf("leveldb: corrupt table: invalid internal key")
	}
	if ucmp.Compare(ukey, ikey0.ukey()) != 0 {
		err = t.Close()
		// 在memtable中没有找到，因为用户key不匹配
		// 之后再从磁盘db文件中查找
		return nil, err != nil, err
	}
	if ikey0.kind() == internalKeyKindDelete {
		t.Close()
		// 该key对应的数据项已经被删除了，所以也没找到
		return nil, true, db.ErrNotFound
	}
	// 找到，返回value
	return t.Value(), true, t.Close()
}

// overlaps returns all elements of v.files[level] whose user key range
// intersects the inclusive range [ukey0, ukey1]. If level is non-zero then the
// user key ranges of v.files[level] are assumed to not overlap (although they
// may touch). If level is zero then that assumption cannot be made, and the
// [ukey0, ukey1] range is expanded to the union of those matching ranges so
// far and the computation is repeated until [ukey0, ukey1] stabilizes.
func (v *version) overlaps(level int, ucmp db.Comparer, ukey0, ukey1 []byte) (ret []fileMetadata) {
loop:
	for {
		for _, meta := range v.files[level] {
			m0 := meta.smallest.ukey()
			m1 := meta.largest.ukey()
			if ucmp.Compare(m1, ukey0) < 0 {
				// meta is completely before the specified range; skip it.
				continue
			}
			if ucmp.Compare(m0, ukey1) > 0 {
				// meta is completely after the specified range; skip it.
				continue
			}
			ret = append(ret, meta)

			// If level == 0, check if the newly added fileMetadata has
			// expanded the range. If so, restart the search.
			if level != 0 {
				continue
			}
			restart := false
			if ucmp.Compare(m0, ukey0) < 0 {
				ukey0 = m0
				restart = true
			}
			if ucmp.Compare(m1, ukey1) > 0 {
				ukey1 = m1
				restart = true
			}
			if restart {
				ret = ret[:0]
				continue loop
			}
		}
		return ret
	}
	panic("unreachable")
}

// get looks up the internal key ikey0 in v's tables such that ikey and ikey0
// have the same user key, and ikey0's sequence number is the highest such
// sequence number that is less than or equal to ikey's sequence number.
//
// If ikey0's kind is set, the value for that previous set action is returned.
// If ikey0's kind is delete, the db.ErrNotFound error is returned.
// If there is no such ikey0, the db.ErrNotFound error is returned.
func (v *version) get(ikey internalKey, tiFinder tableIkeyFinder, ucmp db.Comparer, ro *db.ReadOptions) ([]byte, error) {
	ukey := ikey.ukey()
	// Iterate through v's tables, calling internalGet if the table's bounds
	// might contain ikey. Due to the order in which we search the tables, and
	// the internalKeyComparer's ordering within a table, we stop after the
	// first conclusive result.

	// Search the level 0 files in decreasing fileNum order,
	// which is also decreasing sequence number order.
	icmp := internalKeyComparer{ucmp}
	for i := len(v.files[0]) - 1; i >= 0; i-- {
		f := v.files[0][i]
		// We compare user keys on the low end, as we do not want to reject a table
		// whose smallest internal key may have the same user key and a lower sequence
		// number. An internalKeyComparer sorts increasing by user key but then
		// descending by sequence number.
		if ucmp.Compare(ukey, f.smallest.ukey()) < 0 {
			continue
		}
		// We compare internal keys on the high end. It gives a tighter bound than
		// comparing user keys.
		if icmp.Compare(ikey, f.largest) > 0 {
			continue
		}
		iter, err := tiFinder.find(f.fileNum, ikey)
		if err != nil {
			return nil, fmt.Errorf("leveldb: could not open table %d: %v", f.fileNum, err)
		}
		value, conclusive, err := internalGet(iter, ucmp, ukey)
		if conclusive {
			return value, err
		}
	}

	// Search the remaining levels.
	for level := 1; level < len(v.files); level++ {
		n := len(v.files[level])
		if n == 0 {
			continue
		}
		// Find the earliest file at that level whose largest key is >= ikey.
		index := sort.Search(n, func(i int) bool {
			return icmp.Compare(v.files[level][i].largest, ikey) >= 0
		})
		if index == n {
			continue
		}
		f := v.files[level][index]
		if ucmp.Compare(ukey, f.smallest.ukey()) < 0 {
			continue
		}
		iter, err := tiFinder.find(f.fileNum, ikey)
		if err != nil {
			return nil, fmt.Errorf("leveldb: could not open table %d: %v", f.fileNum, err)
		}
		value, conclusive, err := internalGet(iter, ucmp, ukey)
		if conclusive {
			return value, err
		}
	}
	return nil, db.ErrNotFound
}

// get looks up the internal key k0 in v's tables such that k and k0 have the
// same user key, and k0's sequence number is the highest such value that is
// less than or equal to k's sequence number.
//
// If k0's kind is set, the user key for that previous set action is returned.
// If k0's kind is delete, the db.ErrNotFound error is returned.
// If there is no such k0, the db.ErrNotFound error is returned.
func (v *version) get(k internalKey, ucmp db.Comparer, ro *db.ReadOptions) ([]byte, error) {
	ukey := k.ukey()
	// get looks for k0 inside the on-disk table defined by f. Due to the order
	// in which we search the tables, and the internalKeyComparer's ordering
	// within a table, the first k0 we find is the one that we want.
	//
	// In addition to returning a []byte and an error, it returns whether or
	// not the search was conclusive: whether it found a k0, or encountered a
	// corruption error. If the search was not conclusive, we move on to the
	// next table.
	get := func(f fileMetadata) (val []byte, conclusive bool, err error) {
		b, err := open(f)
		if err != nil {
			return nil, true, err
		}
		t := b.Find(k, ro)
		if !t.Next() {
			err = t.Close()
			return nil, err != nil, err
		}
		k0 := internalKey(t.Key())
		if !k0.valid() {
			return nil, true, fmt.Errorf("leveldb: corrupt table %d: invalid internal key", f.fileNum)
		}
		if ucmp.Compare(ukey, k0.ukey()) != 0 {
			err = t.Close()
			return nil, err != nil, err
		}
		if k0.kind() == internalKeyKindDelete {
			return nil, true, db.ErrNotFound
		}
		return t.Value(), true, t.Close()
	}

	// Search the level 0 files in decreasing fileNum order,
	// which is also decreasing sequence number order.
	icmp := internalKeyComparer{ucmp}
	for i := len(v.files[0]) - 1; i >= 0; i-- {
		f := v.files[0][i]
		// We compare user keys on the low end, as we do not want to reject a table
		// whose smallest internal key may have the same user key and a lower sequence
		// number. An internalKeyComparer sorts increasing by user key but then
		// descending by sequence number.
		if ucmp.Compare(ukey, f.smallest.ukey()) < 0 {
			continue
		}
		// We compare internal keys on the high end. It gives a tighter bound than
		// comparing user keys.
		if icmp.Compare(k, f.largest) > 0 {
			continue
		}
		val, conclusive, err := get(f)
		if conclusive {
			return val, err
		}
	}

	// Search the remaining levels.
	for level := 1; level < len(v.files); level++ {
		n := len(v.files[level])
		if n == 0 {
			continue
		}
		// Find the earliest file at that level whose largest key is >= k.
		index := sort.Search(n, func(i int) bool {
			return icmp.Compare(v.files[level][i].largest, k) >= 0
		})
		if index == n {
			continue
		}
		f := v.files[level][index]
		if ucmp.Compare(ukey, f.smallest.ukey()) < 0 {
			continue
		}
		val, conclusive, err := get(f)
		if conclusive {
			return val, err
		}
	}
	return nil, db.ErrNotFound
}