main.go

package main

import (
        "bufio"
        "fmt"
        "io"
        "os"
        "reflect"
        "sort"
        "strconv"
        "strings"
)

const splitLine = "==============================================="

type chunkPages struct {
        lines []string
}

type metaPage struct {
        id         uint64
        size       uint64
        pageSize   uint64
        root       uint64
        txnID      uint64
        freelistID uint64
}

type branchPage struct {
        id       uint64
        size     uint64
        overflow int
        items    []keyID
}

type leafPage struct {
        id       uint64
        size     uint64
        overflow int
        items    []string
}

type keyID struct {
        key  string
        pgid uint64
}

func main() {
        chunks := buildChuckPages()
        res := buildPages(chunks)

        keyRootID := uint64(5983)
        // leaseRootID := uint64(6045)

        ctx := &checkCtx{
                keys: make(map[string]struct{}),
        }
        checkKeyRoot(ctx, res, keyRootID, nil)
        fmt.Println(len(ctx.keys), ctx.bytes, ctx.lastKey)
}

type checkCtx struct {
        lastKey string
        keys    map[string]struct{}
        bytes   uint64
}

func checkKeyRoot(ctx *checkCtx, pages map[uint64]interface{}, rootID uint64, stack []uint64) {
        defer func() {
                if r := recover(); r != nil {
                        fmt.Println(stack)
                        panic(r)
                }
        }()
        page := pages[rootID]
        switch page.(type) {
        case branchPage:
                p := page.(branchPage)
                checkBranchPage(p)

                stack = append(stack, p.id)
                for _, item := range p.items {
                        checkKeyRoot(ctx, pages, item.pgid, stack)
                }
        case leafPage:
                p := page.(leafPage)
                checkLeafPage(ctx, p)
        }
}

func checkBranchPage(p branchPage) {
        dupKeys := make(map[string]struct{})
        dupPgids := make(map[uint64]struct{})

        copyItems := make([]keyID, 0, len(p.items))
        for _, item := range p.items {
                copyItems = append(copyItems, keyID{
                        key:  item.key,
                        pgid: item.pgid,
                })

                if _, ok := dupKeys[item.key]; ok {
                        panic("duplicate key")
                }
                dupKeys[item.key] = struct{}{}

                if _, ok := dupPgids[item.pgid]; ok {
                        panic("duplicate key")
                }
                dupPgids[item.pgid] = struct{}{}
        }
        sort.Slice(copyItems, func(i, j int) bool {
                return copyItems[i].key < copyItems[j].key
        })

        if !reflect.DeepEqual(copyItems, p.items) {
                panic("no sorted branch")
        }
}

func checkLeafPage(ctx *checkCtx, p leafPage) {

        copyItems := make([]string, len(p.items))
        copy(copyItems, p.items)
        sort.Strings(copyItems)

        for _, item := range p.items {
                if _, ok := ctx.keys[item]; ok {
                        panic("duplicate key")
                }
                ctx.keys[item] = struct{}{}
        }

        if !reflect.DeepEqual(copyItems, p.items) {
                panic("no sorted leaf")
        }

        if ctx.lastKey != "" && strings.Compare(ctx.lastKey, p.items[0]) != -1 {
                panic(fmt.Sprintf("no sorted leaf - %v", p.id))
        }
        ctx.lastKey = p.items[len(p.items)-1]
        ctx.bytes += p.size
}

func buildPages(chunks []chunkPages) map[uint64]interface{} {
        res := make(map[uint64]interface{})
        for _, chunk := range chunks {
                // parse type
                if len(chunk.lines) < 4 {
                        continue
                }
                fileds := strings.Fields(chunk.lines[1])
                switch typStr := fileds[len(fileds)-1]; typStr {
                case "meta":
                        p := convChunkIntoMeta(chunk)
                        if old, ok := res[p.id]; ok {
                                panic(fmt.Sprintf("duplicate id=%d, old=%v", p.id, old))
                        }
                        res[p.id] = p
                case "branch":
                        p := convChunkIntoBranch(chunk)
                        if old, ok := res[p.id]; ok {
                                panic(fmt.Sprintf("duplicate id=%d, old=%v", p.id, old))
                        }
                        res[p.id] = p
                case "leaf":
                        p := convChunkIntoLeaf(chunk)
                        if old, ok := res[p.id]; ok {
                                panic(fmt.Sprintf("duplicate id=%d, old=%v", p.id, old))
                        }
                        res[p.id] = p
                default:
                        panic(fmt.Sprintf("unsupported type %s", typStr))
                }
        }
        return res
}

func convChunkIntoMeta(chunk chunkPages) metaPage {
        return metaPage{
                id:         getPgid(chunk.lines[0]),
                size:       getBytes(chunk.lines[2]),
                pageSize:   getBytes(chunk.lines[5]),
                root:       getRefPgid(chunk.lines[7]),
                freelistID: getRefPgid(chunk.lines[8]),
                txnID:      getPgid(chunk.lines[10]),
        }
}

func convChunkIntoBranch(chunk chunkPages) branchPage {
        items := make([]keyID, 0, len(chunk.lines)-6)
        for i := 6; i < len(chunk.lines); i++ {
                line := chunk.lines[i]
                if len(line) == 0 {
                        continue
                }
                items = append(items, keyID{
                        key:  getKey(line),
                        pgid: getRefPgid(line),
                })
        }
        return branchPage{
                id:       getPgid(chunk.lines[0]),
                size:     getBytes(chunk.lines[2]),
                overflow: getOverflow(chunk.lines[3]),
                items:    items,
        }
}

func convChunkIntoLeaf(chunk chunkPages) leafPage {
        items := make([]string, 0, len(chunk.lines)-6)
        for i := 6; i < len(chunk.lines); i++ {
                line := chunk.lines[i]
                if len(line) == 0 {
                        continue
                }
                items = append(items, getKey(line))
        }
        return leafPage{
                id:       getPgid(chunk.lines[0]),
                size:     getBytes(chunk.lines[2]),
                overflow: getOverflow(chunk.lines[3]),
                items:    items,
        }
}

func getBytes(strLine string) uint64 {
        fileds := strings.Fields(strLine)
        pgid, err := strconv.Atoi(fileds[len(fileds)-2])
        if err != nil {
                panic(err)
        }
        return uint64(pgid)
}

func getPgid(strLine string) uint64 {
        fileds := strings.Fields(strLine)
        pgid, err := strconv.Atoi(fileds[len(fileds)-1])
        if err != nil {
                panic(err)
        }
        return uint64(pgid)
}

func getRefPgid(strLine string) uint64 {
        fileds := strings.Fields(strLine)

        var pgid uint64
        n, err := fmt.Sscanf(fileds[len(fileds)-1], "<pgid=%d>", &pgid)
        if err != nil || n != 1 {
                panic(fmt.Sprintf("expected n=1 but got %d, err=%v, %v", n, err, fileds))
        }
        return pgid
}

func getOverflow(strLine string) int {
        fileds := strings.Fields(strLine)

        count, err := strconv.Atoi(fileds[len(fileds)-1])
        if err != nil {
                panic(err)
        }
        return count
}

func getKey(strLine string) string {
        fileds := strings.Fields(strLine)

        return string([]byte(fileds[0])[:len(fileds[0])-1])
}

func buildChuckPages() []chunkPages {
        fd, err := os.Open("./curropt")
        if err != nil {
                panic(err)
        }
        defer fd.Close()

        res := make([]chunkPages, 0)
        lines := make([]string, 0)

        r := bufio.NewReader(fd)
        for {
                str, err := r.ReadString('\n')
                if err != nil {
                        if err == io.EOF {
                                break
                        }
                        panic(err)
                }
                str = str[:len(str)-1]

                if strings.Compare(str, splitLine) == 0 {
                        newLines := make([]string, len(lines))
                        copy(newLines, lines)

                        res = append(res, chunkPages{
                                lines: newLines,
                        })

                        lines = lines[:0]
                        continue
                }
                lines = append(lines, str)
        }

        if len(lines) != 0 {
                newLines := make([]string, len(lines))
                copy(newLines, lines)

                res = append(res, chunkPages{
                        lines: newLines,
                })
        }

        return res
}