petar / gollrb Goto Github PK

Sorry, but the author of the method is Robert Sedgewick, not Roger. You can check it here: http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

What is the license and copyright of files in doc?

Content of doc directory apparently authored by Robert Sedgewick but there are no .PDF sources...

Throughout the LLRB code it is assumed the root node has been set. But there is no sensible way to create a root node for a new instance of LLRB.

By the way, the example is out of date.

Please consider assigning version numbers and tagging releases. Tags/releases
are useful for downstream package maintainers (in Debian and other distributions) to export source tarballs, automatically track new releases and to declare dependencies between packages. Read more in the Debian Upstream Guide.

Versioning provides additional benefits to encourage vendoring of a particular (e.g. latest stable) release contrary to random unreleased snapshots.

Versioning provides safety margin for situations like "ops, we've made a mistake but reverted problematic commit in master". Presumably tagged version/release is better tested/reviewed than random snapshot of "master" branch.

Thank you.

See also

• http://semver.org/
• https://en.wikipedia.org/wiki/Software_versioning

Hi Petar,

Thanks for writing this data structure.

I was giving it a drive, and the following throws a runtime panic

    func lessString(a, b interface{}) bool {
            return a.(string) < b.(string)
    }


        iofile, err := os.OpenFile("testfile.gob", os.O_RDWR|os.O_CREATE, 0666)                    
        if err != nil {                                                                                   
                panic("Could not find, or create file:  error code:" + err.String())       
        }                                                                                                 
        enc := gob.NewEncoder(iofile)                                                                     
        //dec := gob.NewDecoder(iofile)                                                                   

        tree := llrb.New(lessString)                                                                    
        tree.ReplaceOrInsert("alex")                                                                    
        errdecode := enc.Encode(tree)                                                                                                                       
        if errdecode != nil {                                                                             
                fmt.Printf("decode error:%s", err.String())                                               
        }                                                                                                 

However, if you simply encode another struct like this one

    type Test struct {
        Test string
    }

everything works fine.

Hi,

I noticed this because I've been writing an llrb, and on my own project I can't get deletion to test as correct when using top down 2-3-4 insertion (see post on golang-nuts).

I wanted to check my sanity (I've pored over the code so many times to see if I'm doing something stupid), so I inserted one of my failing deletion tests into GoLLRB and it gives equivalent behaviour (passes on bottom up 2-3 and fails catastrophically on top down 2-3-4).

func TestRandomInsertionDeletion(t *testing.T) {
    count, max := 100000, 1000
    tree := New(IntLess)
    for i := 0; i < count; i++ {
        if rand.Float64() < 0.5 {
            tree.ReplaceOrInsert(rand.Intn(max))
        }
        if rand.Float64() < 0.5 {
            tree.Delete(rand.Intn(max))
        }
    }
}

The test is obviously very vicious, but is fine with the standard 2-3 GoLLRB insertion mode.

Any ideas?

I think somebody else would find my fork useful, but I don't want to pollute the google wiki with this fork. Perhaps it's worth mentioning my fork in your README.

https://github.com/jaekwon/GoLLRB

I encountered a crash in a data processing app that makes use of GoLLRB.

panic: runtime error: invalid memory address or nil pointer dereference
at llrb/llrb.go:423 (moveRedLeft)

I found a particular sequence of data that causes the tree to become inconsistent and crash. I've attached a simple test program that reproduces the error.

Download the code file llrbcrash.go and run with:

go get github.com/petar/GoLLRB
go run llrbcrash.go

I want to iterate from a given key to the end of the tree inclusively. But there seems to be no way to get the last (tree.Max()) value as part of that iteration. I don't know what the most elegant solution would be...

• a bool param to IterRange that would change < @upper to <= @upper?
• a new IterRangeInclusive that goes @lower <= E <= @upper?
• telling me I should simply tack on tree.Max() when my IterRange chan returns a nil and I expect another element?

Here you broke compatibly by removing comparator function from New

c08868e#diff-b47232007a3b6586df5152791ce99805

Hello, is there an algorithm for fast merge of LLRB trees?

https://github.com/HuKeping/rbtree

Hi, I'm looking to use this library for a production tool, and was wondering if it's still being actively maintained?

The example code in Readme.md does not compile. I had to convert it to the following to get it to work:

package main

import (
    "fmt"
    "github.com/petar/GoLLRB/llrb"
)

type IntItem int

func IntLess(p, q interface{}) bool {
    return p.(int) < q.(int)
}


func main() {
    tree := llrb.New(IntLess)
    tree.ReplaceOrInsert(1)
    tree.ReplaceOrInsert(2)
    tree.ReplaceOrInsert(3)
    tree.ReplaceOrInsert(4)
    tree.DeleteMin()
    tree.Delete(4)
    c := tree.IterAscend()
    for {
        u := <-c
        if u == nil {
            break
        }
        fmt.Printf("%d\n", u.(int))
    }
}

I've ran into a case where the delete code path appears to panic within the llrb package:

panic: runtime error: invalid memory address or nil pointer dereference [recovered]
	panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x2 addr=0x20 pc=0x100bc7b40]

goroutine 7 [running]:
testing.tRunner.func1.2({0x100d5dd60, 0x100f44d30})
	/usr/local/go/src/testing/testing.go:1209 +0x258
testing.tRunner.func1(0x1400008d040)
	/usr/local/go/src/testing/testing.go:1212 +0x284
panic({0x100d5dd60, 0x100f44d30})
	/usr/local/go/src/runtime/panic.go:1038 +0x21c
github.com/petar/GoLLRB/llrb.flip(...)
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:417
github.com/petar/GoLLRB/llrb.moveRedRight(0x1400016fa40)
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:434 +0x30
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400016fa40, {0x100da86c0, 0x14000067f80})
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:361 +0x25c
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400017eea0, {0x100da86c0, 0x14000067f80})
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:350 +0xf4
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400018a0c0, {0x100da86c0, 0x14000067f80})
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:350 +0xf4
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140001567f0, 0x1400018bda0, {0x100da86c0, 0x14000067f80})
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:350 +0xf4
github.com/petar/GoLLRB/llrb.(*LLRB).Delete(0x140001567f0, {0x100da86c0, 0x14000067f80})
	/Users/achilleroussel/dev/pkg/mod/github.com/petar/[email protected]/llrb/llrb.go:328 +0x40

It seems that moveRedRight requires both the left and right children to exist https://github.com/petar/GoLLRB/blob/master/llrb/llrb.go#L432, but here only the right child is tested https://github.com/petar/GoLLRB/blob/master/llrb/llrb.go#L359-L362?

for i := 0; i < 1000000; i++ {
rid, _ := utils.RandInt(100000, 999999)
cnt++
tree.InsertNoReplace(NewMatchRoom(rid))
}

for i := 0; i < 1000000; i++ {
	rid, _ := utils.RandInt(100000, 999999)
	cnt++
	tree.Delete(NewMatchRoom(rid))
}