iter_test.go

package offheap_test

import (
	"testing"

	"github.com/glycerine/offheap"
	cv "github.com/glycerine/goconvey/convey"
)

func TestIterator(t *testing.T) {

	cv.Convey("Given a table with 0,1,2 in it, the Iterator should give all three values back", t, func() {
		h := offheap.NewHashTable(8)
		cv.So(h.Population, cv.ShouldEqual, 0)
		for i := 0; i < 3; i++ {
			_, ok := h.Insert(uint64(i))
			cv.So(ok, cv.ShouldEqual, true)
			if i == 0 {
				// iterator should start with the zero value
				it := h.NewIterator()
				cv.So(it.Cur.UnHashedKey, cv.ShouldEqual, 0)
			}
		}
		cv.So(h.Population, cv.ShouldEqual, 3)

		found := []uint64{}
		for it := h.NewIterator(); it.Cur != nil; it.Next() {
			found = append(found, it.Cur.UnHashedKey)
		}
		cv.So(len(found), cv.ShouldEqual, 3)
		cv.So(found, cv.ShouldContain, 0)
		cv.So(found, cv.ShouldContain, 1)
		cv.So(found, cv.ShouldContain, 2)
	})

	cv.Convey("Given a table with 1,2,3 in it, the Iterator should give all three values back", t, func() {
		h := offheap.NewHashTable(8)
		cv.So(h.Population, cv.ShouldEqual, 0)
		for i := 1; i < 4; i++ {
			_, ok := h.Insert(uint64(i))
			cv.So(ok, cv.ShouldEqual, true)
			if i == 0 {
				// iterator should not start with the zero value, not inserted.
				it := h.NewIterator()
				cv.So(it.Cur.UnHashedKey, cv.ShouldEqual, 1)
			}
		}
		cv.So(h.Population, cv.ShouldEqual, 3)

		found := []uint64{}
		for it := h.NewIterator(); it.Cur != nil; it.Next() {
			found = append(found, it.Cur.UnHashedKey)
		}
		cv.So(len(found), cv.ShouldEqual, 3)
		cv.So(found, cv.ShouldContain, 3)
		cv.So(found, cv.ShouldContain, 1)
		cv.So(found, cv.ShouldContain, 2)
	})

	cv.Convey("Given a table with the regular 0-th slot and the special zero-location spot occupied, then the the Iterator should still give all the values back", t, func() {
		h := offheap.NewHashTable(4)
		cv.So(h.Population, cv.ShouldEqual, 0)
		for i := 0; i < 2; i++ {
			_, ok := h.Insert(uint64(i))
			cv.So(ok, cv.ShouldEqual, true)
			if i == 0 {
				// iterator should start with the zero value
				it := h.NewIterator()
				cv.So(it.Cur.UnHashedKey, cv.ShouldEqual, 0)
			}
		}
		cv.So(h.Population, cv.ShouldEqual, 2)
		cv.So(h.CellAt(0).UnHashedKey, cv.ShouldEqual, 1) // important for this test that the regular 0-th (first) cell slot be occupied.

		found := []uint64{}
		for it := h.NewIterator(); it.Cur != nil; it.Next() {
			found = append(found, it.Cur.UnHashedKey)
		}
		cv.So(len(found), cv.ShouldEqual, 2)
		cv.So(found, cv.ShouldContain, 0)
		cv.So(found, cv.ShouldContain, 1)
	})

	cv.Convey("Given a table with the regular 0-th slot *empty* and the special zero-location spot occupied, then the the Iterator should still give all the values back", t, func() {
		h := offheap.NewHashTable(8)
		cv.So(h.Population, cv.ShouldEqual, 0)
		for i := 0; i < 2; i++ {
			_, ok := h.Insert(uint64(i))
			cv.So(ok, cv.ShouldEqual, true)
			if i == 0 {
				// iterator should start with the zero value
				it := h.NewIterator()
				cv.So(it.Cur.UnHashedKey, cv.ShouldEqual, 0)
				cv.So(it.Pos, cv.ShouldEqual, -1)
			}
		}
		cv.So(h.Population, cv.ShouldEqual, 2)
		cv.So(h.CellAt(0).UnHashedKey, cv.ShouldEqual, 0) // important for this test that the regular 0-th (first) cell slot be *empty*.

		found := []uint64{}
		for it := h.NewIterator(); it.Cur != nil; it.Next() {
			found = append(found, it.Cur.UnHashedKey)
		}
		cv.So(len(found), cv.ShouldEqual, 2)
		cv.So(found, cv.ShouldContain, 0)
		cv.So(found, cv.ShouldContain, 1)
	})

	cv.Convey("Given a table with the regular 0-th slot *filled* and the special zero-location spot *empty*, then the the Iterator should still give the one value back", t, func() {
		// size 4 just happens to generate an occupation at h.Cells[0]
		h := offheap.NewHashTable(4)
		cv.So(h.Population, cv.ShouldEqual, 0)
		i := 1
		_, ok := h.Insert(uint64(i))
		cv.So(ok, cv.ShouldEqual, true)

		// iterator should start with the zero value
		it := h.NewIterator()
		cv.So(it.Cur.UnHashedKey, cv.ShouldEqual, 1)
		cv.So(it.Pos, cv.ShouldEqual, 0)

		cv.So(h.Population, cv.ShouldEqual, 1)
		cv.So(h.CellAt(0).UnHashedKey, cv.ShouldEqual, 1) // important for this test that the regular 0-th (first) cell slot be *filled*.

		found := []uint64{}
		for it := h.NewIterator(); it.Cur != nil; it.Next() {
			found = append(found, it.Cur.UnHashedKey)
		}
		cv.So(len(found), cv.ShouldEqual, 1)
		cv.So(found, cv.ShouldContain, 1)
	})

	cv.Convey("Given an empty table, an Iterator should still work fine, without crashing", t, func() {
		h := offheap.NewHashTable(4)
		cv.So(h.Population, cv.ShouldEqual, 0)

		found := []uint64{}
		for it := h.NewIterator(); it.Cur != nil; it.Next() {
			found = append(found, it.Cur.UnHashedKey)
		}
		cv.So(len(found), cv.ShouldEqual, 0)
	})

}