search

k-sone / critbitgo

crit-bit for golang and its applications (sorted map, IP routing table)
MIT License
45 stars 14 forks source link

fix bug of key order when key contains a zero value #1

Closed k-sone closed 8 years ago

k-sone commented 8 years ago

Test code:

package main

import (
        "bytes"
        "fmt"

        "github.com/k-sone/critbitgo"
)

func main() {
        t := critbitgo.NewTrie()
        t.Insert([]byte{1}, nil)
        t.Insert([]byte{1, 1}, nil)
        t.Insert([]byte{1, 0, 1}, nil)

        buf := bytes.NewBufferString("")
        t.Dump(buf)
        fmt.Println(buf.String())
}

Actual:

-- off=1, bit=00000001 (01)
 |-- off=1, bit=00000000 (00)
 | |-- key=[1 0 1] (010001)
 | `-- key=[1] (01)
 `-- key=[1 1] (0101)

Expected:

-- off=1, bit=00000001 (01)
 |-- key=[1] (01)
 `-- off=1, bit=00000001 (01)
   |-- key=[1 0 1] (010001)
   `-- key=[1 1] (0101)