util.go

package iavl

import (
	"bytes"
	"fmt"
	"sort"
	"strconv"
)

// PrintTree prints the whole tree in an indented form.
func PrintTree(tree *ImmutableTree) {
	ndb, root := tree.ndb, tree.getRoot()
	printNode(ndb, root, 0)
}

func printNode(ndb *nodeDB, node *Node, indent int) {
	indentPrefix := ""
	for i := 0; i < indent; i++ {
		indentPrefix += "    "
	}

	if node == nil {
		fmt.Printf("%s<nil>\n", indentPrefix)
		return
	}
	if node.rightNode != nil {
		printNode(ndb, node.rightNode, indent+1)
	} else if node.rightHash != nil {
		rightNode := ndb.GetNode(node.rightHash)
		printNode(ndb, rightNode, indent+1)
	}

	hash := node._hash()
	fmt.Printf("%sh:%X\n", indentPrefix, hash)
	if node.isLeaf() {
		fmt.Printf("%s%X:%X (%v)\n", indentPrefix, node.key, node.value, node.height)
	}

	if node.leftNode != nil {
		printNode(ndb, node.leftNode, indent+1)
	} else if node.leftHash != nil {
		leftNode := ndb.GetNode(node.leftHash)
		printNode(ndb, leftNode, indent+1)
	}

}

func maxInt8(a, b int8) int8 {
	if a > b {
		return a
	}
	return b
}

func cp(bz []byte) (ret []byte) {
	ret = make([]byte, len(bz))
	copy(ret, bz)
	return ret
}

// Returns a slice of the same length (big endian)
// except incremented by one.
// Appends 0x00 if bz is all 0xFF.
// CONTRACT: len(bz) > 0
func cpIncr(bz []byte) (ret []byte) {
	ret = cp(bz)
	for i := len(bz) - 1; i >= 0; i-- {
		if ret[i] < byte(0xFF) {
			ret[i]++
			return
		}
		ret[i] = byte(0x00)
		if i == 0 {
			return append(ret, 0x00)
		}
	}
	return []byte{0x00}
}

type byteslices [][]byte

func (bz byteslices) Len() int {
	return len(bz)
}

func (bz byteslices) Less(i, j int) bool {
	switch bytes.Compare(bz[i], bz[j]) {
	case -1:
		return true
	case 0, 1:
		return false
	default:
		panic("should not happen")
	}
}

func (bz byteslices) Swap(i, j int) {
	bz[j], bz[i] = bz[i], bz[j]
}

func sortByteSlices(src [][]byte) [][]byte {
	bzz := byteslices(src)
	sort.Sort(bzz)
	return bzz
}

func PrintTreeByLevel(tree *ImmutableTree) {
	if tree == nil || tree.root == nil {
		fmt.Println("<Empty Tree>")
		return
	}
	nodes := make([]*Node, 0, tree.memoryNodeSize())
	nodes = append(nodes, tree.root)
	i := 0
	levelLastIdx := 0
	for {
		fmt.Print(string(nodes[i].key) + ":" + strconv.Itoa(int(nodes[i].version)) + ":" + strconv.Itoa(int(nodes[i].loadVersion)) + "\t")
		if left := nodes[i].leftNode; left != nil {
			nodes = append(nodes, left)
		}
		if right := nodes[i].rightNode; right != nil {
			nodes = append(nodes, right)
		}
		if i == len(nodes)-1 {
			break
		} else if i == levelLastIdx {
			fmt.Println()
			levelLastIdx = len(nodes) - 1
		}
		i++
	}
	fmt.Println()
	fmt.Println()
}