Tuesday, November 19, 2013

Better testing reveals broken delete...

The latest commit on GitHub has an updated test implementation. It's a big improvement over what I had before because it uses Go's map type as a reference implementation. First I created an interface "TreeLike" that defines the basic operations on a tree:

type Treelike interface {
Insert(uint64, interface{})
Fetch(uint64) interface{}
Iterate() chan uint64

I know Iterate() is basically useless, it's still a work in progress. TreeLike is already implemented by Btree. Now I make a struct that implements checking. 

type BtreeTest struct {
test *testing.T
tree Treelike 
reference map[uint64] interface{}

The class contains a test so that I can testing.T.Fail() when a problem is detected. The TreeLike is kept in sync with the map[] by implementing methods that operate on both structures. This is the implementation of Insert():

func (self *BtreeTest) Insert(key uint64, value interface{}) {
self.reference[key] = value
self.tree.Insert(key, value)

The Insert() function does no checking. The Delete() function does:

func (self *BtreeTest) Delete(key uint64) {
delete(self.reference, key)
verify := self.tree.Fetch(key) 
if (verify != nil) {

The struct BtreeTest itself implements TreeLike so any code that requires TreeLike can be easily instrumented to be testing code. Thanks to that I found a serious bug in Delete(). My delete function fails to delete values that are not stored in leaf nodes. I'm fixing it. 

No comments:

Post a Comment