/*
|
Copyright 2017 The Kubernetes Authors.
|
|
Licensed under the Apache License, Version 2.0 (the "License");
|
you may not use this file except in compliance with the License.
|
You may obtain a copy of the License at
|
|
http://www.apache.org/licenses/LICENSE-2.0
|
|
Unless required by applicable law or agreed to in writing, software
|
distributed under the License is distributed on an "AS IS" BASIS,
|
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
See the License for the specific language governing permissions and
|
limitations under the License.
|
*/
|
|
package cache
|
|
import (
|
"sync"
|
"testing"
|
"time"
|
)
|
|
func testHeapObjectKeyFunc(obj interface{}) (string, error) {
|
return obj.(testHeapObject).name, nil
|
}
|
|
type testHeapObject struct {
|
name string
|
val interface{}
|
}
|
|
func mkHeapObj(name string, val interface{}) testHeapObject {
|
return testHeapObject{name: name, val: val}
|
}
|
|
func compareInts(val1 interface{}, val2 interface{}) bool {
|
first := val1.(testHeapObject).val.(int)
|
second := val2.(testHeapObject).val.(int)
|
return first < second
|
}
|
|
// TestHeapBasic tests Heap invariant and synchronization.
|
func TestHeapBasic(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
var wg sync.WaitGroup
|
wg.Add(2)
|
const amount = 500
|
var i, u int
|
// Insert items in the heap in opposite orders in two go routines.
|
go func() {
|
for i = amount; i > 0; i-- {
|
h.Add(mkHeapObj(string([]rune{'a', rune(i)}), i))
|
}
|
wg.Done()
|
}()
|
go func() {
|
for u = 0; u < amount; u++ {
|
h.Add(mkHeapObj(string([]rune{'b', rune(u)}), u+1))
|
}
|
wg.Done()
|
}()
|
// Wait for the two go routines to finish.
|
wg.Wait()
|
// Make sure that the numbers are popped in ascending order.
|
prevNum := 0
|
for i := 0; i < amount*2; i++ {
|
obj, err := h.Pop()
|
num := obj.(testHeapObject).val.(int)
|
// All the items must be sorted.
|
if err != nil || prevNum > num {
|
t.Errorf("got %v out of order, last was %v", obj, prevNum)
|
}
|
prevNum = num
|
}
|
}
|
|
// Tests Heap.Add and ensures that heap invariant is preserved after adding items.
|
func TestHeap_Add(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
h.Add(mkHeapObj("foo", 10))
|
h.Add(mkHeapObj("bar", 1))
|
h.Add(mkHeapObj("baz", 11))
|
h.Add(mkHeapObj("zab", 30))
|
h.Add(mkHeapObj("foo", 13)) // This updates "foo".
|
|
item, err := h.Pop()
|
if e, a := 1, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
item, err = h.Pop()
|
if e, a := 11, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
h.Delete(mkHeapObj("baz", 11)) // Nothing is deleted.
|
h.Add(mkHeapObj("foo", 14)) // foo is updated.
|
item, err = h.Pop()
|
if e, a := 14, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
item, err = h.Pop()
|
if e, a := 30, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
}
|
|
// TestHeap_BulkAdd tests Heap.BulkAdd functionality and ensures that all the
|
// items given to BulkAdd are added to the queue before Pop reads them.
|
func TestHeap_BulkAdd(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
const amount = 500
|
// Insert items in the heap in opposite orders in a go routine.
|
go func() {
|
l := []interface{}{}
|
for i := amount; i > 0; i-- {
|
l = append(l, mkHeapObj(string([]rune{'a', rune(i)}), i))
|
}
|
h.BulkAdd(l)
|
}()
|
prevNum := -1
|
for i := 0; i < amount; i++ {
|
obj, err := h.Pop()
|
num := obj.(testHeapObject).val.(int)
|
// All the items must be sorted.
|
if err != nil || prevNum >= num {
|
t.Errorf("got %v out of order, last was %v", obj, prevNum)
|
}
|
prevNum = num
|
}
|
}
|
|
// TestHeapEmptyPop tests that pop returns properly after heap is closed.
|
func TestHeapEmptyPop(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
go func() {
|
time.Sleep(1 * time.Second)
|
h.Close()
|
}()
|
_, err := h.Pop()
|
if err == nil || err.Error() != closedMsg {
|
t.Errorf("pop should have returned heap closed error: %v", err)
|
}
|
}
|
|
// TestHeap_AddIfNotPresent tests Heap.AddIfNotPresent and ensures that heap
|
// invariant is preserved after adding items.
|
func TestHeap_AddIfNotPresent(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
h.AddIfNotPresent(mkHeapObj("foo", 10))
|
h.AddIfNotPresent(mkHeapObj("bar", 1))
|
h.AddIfNotPresent(mkHeapObj("baz", 11))
|
h.AddIfNotPresent(mkHeapObj("zab", 30))
|
h.AddIfNotPresent(mkHeapObj("foo", 13)) // This is not added.
|
|
if len := len(h.data.items); len != 4 {
|
t.Errorf("unexpected number of items: %d", len)
|
}
|
if val := h.data.items["foo"].obj.(testHeapObject).val; val != 10 {
|
t.Errorf("unexpected value: %d", val)
|
}
|
item, err := h.Pop()
|
if e, a := 1, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
item, err = h.Pop()
|
if e, a := 10, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
// bar is already popped. Let's add another one.
|
h.AddIfNotPresent(mkHeapObj("bar", 14))
|
item, err = h.Pop()
|
if e, a := 11, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
item, err = h.Pop()
|
if e, a := 14, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
}
|
|
// TestHeap_Delete tests Heap.Delete and ensures that heap invariant is
|
// preserved after deleting items.
|
func TestHeap_Delete(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
h.Add(mkHeapObj("foo", 10))
|
h.Add(mkHeapObj("bar", 1))
|
h.Add(mkHeapObj("bal", 31))
|
h.Add(mkHeapObj("baz", 11))
|
|
// Delete head. Delete should work with "key" and doesn't care about the value.
|
if err := h.Delete(mkHeapObj("bar", 200)); err != nil {
|
t.Fatalf("Failed to delete head.")
|
}
|
item, err := h.Pop()
|
if e, a := 10, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
h.Add(mkHeapObj("zab", 30))
|
h.Add(mkHeapObj("faz", 30))
|
len := h.data.Len()
|
// Delete non-existing item.
|
if err = h.Delete(mkHeapObj("non-existent", 10)); err == nil || len != h.data.Len() {
|
t.Fatalf("Didn't expect any item removal")
|
}
|
// Delete tail.
|
if err = h.Delete(mkHeapObj("bal", 31)); err != nil {
|
t.Fatalf("Failed to delete tail.")
|
}
|
// Delete one of the items with value 30.
|
if err = h.Delete(mkHeapObj("zab", 30)); err != nil {
|
t.Fatalf("Failed to delete item.")
|
}
|
item, err = h.Pop()
|
if e, a := 11, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
item, err = h.Pop()
|
if e, a := 30, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
if h.data.Len() != 0 {
|
t.Fatalf("expected an empty heap.")
|
}
|
}
|
|
// TestHeap_Update tests Heap.Update and ensures that heap invariant is
|
// preserved after adding items.
|
func TestHeap_Update(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
h.Add(mkHeapObj("foo", 10))
|
h.Add(mkHeapObj("bar", 1))
|
h.Add(mkHeapObj("bal", 31))
|
h.Add(mkHeapObj("baz", 11))
|
|
// Update an item to a value that should push it to the head.
|
h.Update(mkHeapObj("baz", 0))
|
if h.data.queue[0] != "baz" || h.data.items["baz"].index != 0 {
|
t.Fatalf("expected baz to be at the head")
|
}
|
item, err := h.Pop()
|
if e, a := 0, item.(testHeapObject).val; err != nil || a != e {
|
t.Fatalf("expected %d, got %d", e, a)
|
}
|
// Update bar to push it farther back in the queue.
|
h.Update(mkHeapObj("bar", 100))
|
if h.data.queue[0] != "foo" || h.data.items["foo"].index != 0 {
|
t.Fatalf("expected foo to be at the head")
|
}
|
}
|
|
// TestHeap_Get tests Heap.Get.
|
func TestHeap_Get(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
h.Add(mkHeapObj("foo", 10))
|
h.Add(mkHeapObj("bar", 1))
|
h.Add(mkHeapObj("bal", 31))
|
h.Add(mkHeapObj("baz", 11))
|
|
// Get works with the key.
|
obj, exists, err := h.Get(mkHeapObj("baz", 0))
|
if err != nil || exists == false || obj.(testHeapObject).val != 11 {
|
t.Fatalf("unexpected error in getting element")
|
}
|
// Get non-existing object.
|
_, exists, err = h.Get(mkHeapObj("non-existing", 0))
|
if err != nil || exists == true {
|
t.Fatalf("didn't expect to get any object")
|
}
|
}
|
|
// TestHeap_GetByKey tests Heap.GetByKey and is very similar to TestHeap_Get.
|
func TestHeap_GetByKey(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
h.Add(mkHeapObj("foo", 10))
|
h.Add(mkHeapObj("bar", 1))
|
h.Add(mkHeapObj("bal", 31))
|
h.Add(mkHeapObj("baz", 11))
|
|
obj, exists, err := h.GetByKey("baz")
|
if err != nil || exists == false || obj.(testHeapObject).val != 11 {
|
t.Fatalf("unexpected error in getting element")
|
}
|
// Get non-existing object.
|
_, exists, err = h.GetByKey("non-existing")
|
if err != nil || exists == true {
|
t.Fatalf("didn't expect to get any object")
|
}
|
}
|
|
// TestHeap_Close tests Heap.Close and Heap.IsClosed functions.
|
func TestHeap_Close(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
h.Add(mkHeapObj("foo", 10))
|
h.Add(mkHeapObj("bar", 1))
|
|
if h.IsClosed() {
|
t.Fatalf("didn't expect heap to be closed")
|
}
|
h.Close()
|
if !h.IsClosed() {
|
t.Fatalf("expect heap to be closed")
|
}
|
}
|
|
// TestHeap_List tests Heap.List function.
|
func TestHeap_List(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
list := h.List()
|
if len(list) != 0 {
|
t.Errorf("expected an empty list")
|
}
|
|
items := map[string]int{
|
"foo": 10,
|
"bar": 1,
|
"bal": 30,
|
"baz": 11,
|
"faz": 30,
|
}
|
for k, v := range items {
|
h.Add(mkHeapObj(k, v))
|
}
|
list = h.List()
|
if len(list) != len(items) {
|
t.Errorf("expected %d items, got %d", len(items), len(list))
|
}
|
for _, obj := range list {
|
heapObj := obj.(testHeapObject)
|
v, ok := items[heapObj.name]
|
if !ok || v != heapObj.val {
|
t.Errorf("unexpected item in the list: %v", heapObj)
|
}
|
}
|
}
|
|
// TestHeap_ListKeys tests Heap.ListKeys function. Scenario is the same as
|
// TestHeap_list.
|
func TestHeap_ListKeys(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
list := h.ListKeys()
|
if len(list) != 0 {
|
t.Errorf("expected an empty list")
|
}
|
|
items := map[string]int{
|
"foo": 10,
|
"bar": 1,
|
"bal": 30,
|
"baz": 11,
|
"faz": 30,
|
}
|
for k, v := range items {
|
h.Add(mkHeapObj(k, v))
|
}
|
list = h.ListKeys()
|
if len(list) != len(items) {
|
t.Errorf("expected %d items, got %d", len(items), len(list))
|
}
|
for _, key := range list {
|
_, ok := items[key]
|
if !ok {
|
t.Errorf("unexpected item in the list: %v", key)
|
}
|
}
|
}
|
|
// TestHeapAddAfterClose tests that heap returns an error if anything is added
|
// after it is closed.
|
func TestHeapAddAfterClose(t *testing.T) {
|
h := NewHeap(testHeapObjectKeyFunc, compareInts)
|
h.Close()
|
if err := h.Add(mkHeapObj("test", 1)); err == nil || err.Error() != closedMsg {
|
t.Errorf("expected heap closed error")
|
}
|
if err := h.AddIfNotPresent(mkHeapObj("test", 1)); err == nil || err.Error() != closedMsg {
|
t.Errorf("expected heap closed error")
|
}
|
if err := h.BulkAdd([]interface{}{mkHeapObj("test", 1)}); err == nil || err.Error() != closedMsg {
|
t.Errorf("expected heap closed error")
|
}
|
}
|
