GoLLRB icon indicating copy to clipboard operation
GoLLRB copied to clipboard

Panic in Delete

Open achille-roussel opened this issue 3 years ago • 1 comments

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?

achille-roussel avatar Feb 22 '22 18:02 achille-roussel