heap_test.go

Documentation: k8s.io/client-go/tools/cache

     1  /*
     2  Copyright 2017 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package cache
    18  
    19  import (
    20  	"sync"
    21  	"testing"
    22  	"time"
    23  )
    24  
    25  func testHeapObjectKeyFunc(obj interface{}) (string, error) {
    26  	return obj.(testHeapObject).name, nil
    27  }
    28  
    29  type testHeapObject struct {
    30  	name string
    31  	val  interface{}
    32  }
    33  
    34  func mkHeapObj(name string, val interface{}) testHeapObject {
    35  	return testHeapObject{name: name, val: val}
    36  }
    37  
    38  func compareInts(val1 interface{}, val2 interface{}) bool {
    39  	first := val1.(testHeapObject).val.(int)
    40  	second := val2.(testHeapObject).val.(int)
    41  	return first < second
    42  }
    43  
    44  // TestHeapBasic tests Heap invariant and synchronization.
    45  func TestHeapBasic(t *testing.T) {
    46  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
    47  	var wg sync.WaitGroup
    48  	wg.Add(2)
    49  	const amount = 500
    50  	var i, u int
    51  	// Insert items in the heap in opposite orders in two go routines.
    52  	go func() {
    53  		for i = amount; i > 0; i-- {
    54  			h.Add(mkHeapObj(string([]rune{'a', rune(i)}), i))
    55  		}
    56  		wg.Done()
    57  	}()
    58  	go func() {
    59  		for u = 0; u < amount; u++ {
    60  			h.Add(mkHeapObj(string([]rune{'b', rune(u)}), u+1))
    61  		}
    62  		wg.Done()
    63  	}()
    64  	// Wait for the two go routines to finish.
    65  	wg.Wait()
    66  	// Make sure that the numbers are popped in ascending order.
    67  	prevNum := 0
    68  	for i := 0; i < amount*2; i++ {
    69  		obj, err := h.Pop()
    70  		num := obj.(testHeapObject).val.(int)
    71  		// All the items must be sorted.
    72  		if err != nil || prevNum > num {
    73  			t.Errorf("got %v out of order, last was %v", obj, prevNum)
    74  		}
    75  		prevNum = num
    76  	}
    77  }
    78  
    79  // Tests Heap.Add and ensures that heap invariant is preserved after adding items.
    80  func TestHeap_Add(t *testing.T) {
    81  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
    82  	h.Add(mkHeapObj("foo", 10))
    83  	h.Add(mkHeapObj("bar", 1))
    84  	h.Add(mkHeapObj("baz", 11))
    85  	h.Add(mkHeapObj("zab", 30))
    86  	h.Add(mkHeapObj("foo", 13)) // This updates "foo".
    87  
    88  	item, err := h.Pop()
    89  	if e, a := 1, item.(testHeapObject).val; err != nil || a != e {
    90  		t.Fatalf("expected %d, got %d", e, a)
    91  	}
    92  	item, err = h.Pop()
    93  	if e, a := 11, item.(testHeapObject).val; err != nil || a != e {
    94  		t.Fatalf("expected %d, got %d", e, a)
    95  	}
    96  	h.Delete(mkHeapObj("baz", 11)) // Nothing is deleted.
    97  	h.Add(mkHeapObj("foo", 14))    // foo is updated.
    98  	item, err = h.Pop()
    99  	if e, a := 14, item.(testHeapObject).val; err != nil || a != e {
   100  		t.Fatalf("expected %d, got %d", e, a)
   101  	}
   102  	item, err = h.Pop()
   103  	if e, a := 30, item.(testHeapObject).val; err != nil || a != e {
   104  		t.Fatalf("expected %d, got %d", e, a)
   105  	}
   106  }
   107  
   108  // TestHeap_BulkAdd tests Heap.BulkAdd functionality and ensures that all the
   109  // items given to BulkAdd are added to the queue before Pop reads them.
   110  func TestHeap_BulkAdd(t *testing.T) {
   111  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   112  	const amount = 500
   113  	// Insert items in the heap in opposite orders in a go routine.
   114  	go func() {
   115  		l := []interface{}{}
   116  		for i := amount; i > 0; i-- {
   117  			l = append(l, mkHeapObj(string([]rune{'a', rune(i)}), i))
   118  		}
   119  		h.BulkAdd(l)
   120  	}()
   121  	prevNum := -1
   122  	for i := 0; i < amount; i++ {
   123  		obj, err := h.Pop()
   124  		num := obj.(testHeapObject).val.(int)
   125  		// All the items must be sorted.
   126  		if err != nil || prevNum >= num {
   127  			t.Errorf("got %v out of order, last was %v", obj, prevNum)
   128  		}
   129  		prevNum = num
   130  	}
   131  }
   132  
   133  // TestHeapEmptyPop tests that pop returns properly after heap is closed.
   134  func TestHeapEmptyPop(t *testing.T) {
   135  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   136  	go func() {
   137  		time.Sleep(1 * time.Second)
   138  		h.Close()
   139  	}()
   140  	_, err := h.Pop()
   141  	if err == nil || err.Error() != closedMsg {
   142  		t.Errorf("pop should have returned heap closed error: %v", err)
   143  	}
   144  }
   145  
   146  // TestHeap_AddIfNotPresent tests Heap.AddIfNotPresent and ensures that heap
   147  // invariant is preserved after adding items.
   148  func TestHeap_AddIfNotPresent(t *testing.T) {
   149  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   150  	h.AddIfNotPresent(mkHeapObj("foo", 10))
   151  	h.AddIfNotPresent(mkHeapObj("bar", 1))
   152  	h.AddIfNotPresent(mkHeapObj("baz", 11))
   153  	h.AddIfNotPresent(mkHeapObj("zab", 30))
   154  	h.AddIfNotPresent(mkHeapObj("foo", 13)) // This is not added.
   155  
   156  	if len := len(h.data.items); len != 4 {
   157  		t.Errorf("unexpected number of items: %d", len)
   158  	}
   159  	if val := h.data.items["foo"].obj.(testHeapObject).val; val != 10 {
   160  		t.Errorf("unexpected value: %d", val)
   161  	}
   162  	item, err := h.Pop()
   163  	if e, a := 1, item.(testHeapObject).val; err != nil || a != e {
   164  		t.Fatalf("expected %d, got %d", e, a)
   165  	}
   166  	item, err = h.Pop()
   167  	if e, a := 10, item.(testHeapObject).val; err != nil || a != e {
   168  		t.Fatalf("expected %d, got %d", e, a)
   169  	}
   170  	// bar is already popped. Let's add another one.
   171  	h.AddIfNotPresent(mkHeapObj("bar", 14))
   172  	item, err = h.Pop()
   173  	if e, a := 11, item.(testHeapObject).val; err != nil || a != e {
   174  		t.Fatalf("expected %d, got %d", e, a)
   175  	}
   176  	item, err = h.Pop()
   177  	if e, a := 14, item.(testHeapObject).val; err != nil || a != e {
   178  		t.Fatalf("expected %d, got %d", e, a)
   179  	}
   180  }
   181  
   182  // TestHeap_Delete tests Heap.Delete and ensures that heap invariant is
   183  // preserved after deleting items.
   184  func TestHeap_Delete(t *testing.T) {
   185  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   186  	h.Add(mkHeapObj("foo", 10))
   187  	h.Add(mkHeapObj("bar", 1))
   188  	h.Add(mkHeapObj("bal", 31))
   189  	h.Add(mkHeapObj("baz", 11))
   190  
   191  	// Delete head. Delete should work with "key" and doesn't care about the value.
   192  	if err := h.Delete(mkHeapObj("bar", 200)); err != nil {
   193  		t.Fatalf("Failed to delete head.")
   194  	}
   195  	item, err := h.Pop()
   196  	if e, a := 10, item.(testHeapObject).val; err != nil || a != e {
   197  		t.Fatalf("expected %d, got %d", e, a)
   198  	}
   199  	h.Add(mkHeapObj("zab", 30))
   200  	h.Add(mkHeapObj("faz", 30))
   201  	len := h.data.Len()
   202  	// Delete non-existing item.
   203  	if err = h.Delete(mkHeapObj("non-existent", 10)); err == nil || len != h.data.Len() {
   204  		t.Fatalf("Didn't expect any item removal")
   205  	}
   206  	// Delete tail.
   207  	if err = h.Delete(mkHeapObj("bal", 31)); err != nil {
   208  		t.Fatalf("Failed to delete tail.")
   209  	}
   210  	// Delete one of the items with value 30.
   211  	if err = h.Delete(mkHeapObj("zab", 30)); err != nil {
   212  		t.Fatalf("Failed to delete item.")
   213  	}
   214  	item, err = h.Pop()
   215  	if e, a := 11, item.(testHeapObject).val; err != nil || a != e {
   216  		t.Fatalf("expected %d, got %d", e, a)
   217  	}
   218  	item, err = h.Pop()
   219  	if e, a := 30, item.(testHeapObject).val; err != nil || a != e {
   220  		t.Fatalf("expected %d, got %d", e, a)
   221  	}
   222  	if h.data.Len() != 0 {
   223  		t.Fatalf("expected an empty heap.")
   224  	}
   225  }
   226  
   227  // TestHeap_Update tests Heap.Update and ensures that heap invariant is
   228  // preserved after adding items.
   229  func TestHeap_Update(t *testing.T) {
   230  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   231  	h.Add(mkHeapObj("foo", 10))
   232  	h.Add(mkHeapObj("bar", 1))
   233  	h.Add(mkHeapObj("bal", 31))
   234  	h.Add(mkHeapObj("baz", 11))
   235  
   236  	// Update an item to a value that should push it to the head.
   237  	h.Update(mkHeapObj("baz", 0))
   238  	if h.data.queue[0] != "baz" || h.data.items["baz"].index != 0 {
   239  		t.Fatalf("expected baz to be at the head")
   240  	}
   241  	item, err := h.Pop()
   242  	if e, a := 0, item.(testHeapObject).val; err != nil || a != e {
   243  		t.Fatalf("expected %d, got %d", e, a)
   244  	}
   245  	// Update bar to push it farther back in the queue.
   246  	h.Update(mkHeapObj("bar", 100))
   247  	if h.data.queue[0] != "foo" || h.data.items["foo"].index != 0 {
   248  		t.Fatalf("expected foo to be at the head")
   249  	}
   250  }
   251  
   252  // TestHeap_Get tests Heap.Get.
   253  func TestHeap_Get(t *testing.T) {
   254  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   255  	h.Add(mkHeapObj("foo", 10))
   256  	h.Add(mkHeapObj("bar", 1))
   257  	h.Add(mkHeapObj("bal", 31))
   258  	h.Add(mkHeapObj("baz", 11))
   259  
   260  	// Get works with the key.
   261  	obj, exists, err := h.Get(mkHeapObj("baz", 0))
   262  	if err != nil || exists == false || obj.(testHeapObject).val != 11 {
   263  		t.Fatalf("unexpected error in getting element")
   264  	}
   265  	// Get non-existing object.
   266  	_, exists, err = h.Get(mkHeapObj("non-existing", 0))
   267  	if err != nil || exists {
   268  		t.Fatalf("didn't expect to get any object")
   269  	}
   270  }
   271  
   272  // TestHeap_GetByKey tests Heap.GetByKey and is very similar to TestHeap_Get.
   273  func TestHeap_GetByKey(t *testing.T) {
   274  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   275  	h.Add(mkHeapObj("foo", 10))
   276  	h.Add(mkHeapObj("bar", 1))
   277  	h.Add(mkHeapObj("bal", 31))
   278  	h.Add(mkHeapObj("baz", 11))
   279  
   280  	obj, exists, err := h.GetByKey("baz")
   281  	if err != nil || exists == false || obj.(testHeapObject).val != 11 {
   282  		t.Fatalf("unexpected error in getting element")
   283  	}
   284  	// Get non-existing object.
   285  	_, exists, err = h.GetByKey("non-existing")
   286  	if err != nil || exists {
   287  		t.Fatalf("didn't expect to get any object")
   288  	}
   289  }
   290  
   291  // TestHeap_Close tests Heap.Close and Heap.IsClosed functions.
   292  func TestHeap_Close(t *testing.T) {
   293  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   294  	h.Add(mkHeapObj("foo", 10))
   295  	h.Add(mkHeapObj("bar", 1))
   296  
   297  	if h.IsClosed() {
   298  		t.Fatalf("didn't expect heap to be closed")
   299  	}
   300  	h.Close()
   301  	if !h.IsClosed() {
   302  		t.Fatalf("expect heap to be closed")
   303  	}
   304  }
   305  
   306  // TestHeap_List tests Heap.List function.
   307  func TestHeap_List(t *testing.T) {
   308  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   309  	list := h.List()
   310  	if len(list) != 0 {
   311  		t.Errorf("expected an empty list")
   312  	}
   313  
   314  	items := map[string]int{
   315  		"foo": 10,
   316  		"bar": 1,
   317  		"bal": 30,
   318  		"baz": 11,
   319  		"faz": 30,
   320  	}
   321  	for k, v := range items {
   322  		h.Add(mkHeapObj(k, v))
   323  	}
   324  	list = h.List()
   325  	if len(list) != len(items) {
   326  		t.Errorf("expected %d items, got %d", len(items), len(list))
   327  	}
   328  	for _, obj := range list {
   329  		heapObj := obj.(testHeapObject)
   330  		v, ok := items[heapObj.name]
   331  		if !ok || v != heapObj.val {
   332  			t.Errorf("unexpected item in the list: %v", heapObj)
   333  		}
   334  	}
   335  }
   336  
   337  // TestHeap_ListKeys tests Heap.ListKeys function. Scenario is the same as
   338  // TestHeap_list.
   339  func TestHeap_ListKeys(t *testing.T) {
   340  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   341  	list := h.ListKeys()
   342  	if len(list) != 0 {
   343  		t.Errorf("expected an empty list")
   344  	}
   345  
   346  	items := map[string]int{
   347  		"foo": 10,
   348  		"bar": 1,
   349  		"bal": 30,
   350  		"baz": 11,
   351  		"faz": 30,
   352  	}
   353  	for k, v := range items {
   354  		h.Add(mkHeapObj(k, v))
   355  	}
   356  	list = h.ListKeys()
   357  	if len(list) != len(items) {
   358  		t.Errorf("expected %d items, got %d", len(items), len(list))
   359  	}
   360  	for _, key := range list {
   361  		_, ok := items[key]
   362  		if !ok {
   363  			t.Errorf("unexpected item in the list: %v", key)
   364  		}
   365  	}
   366  }
   367  
   368  // TestHeapAddAfterClose tests that heap returns an error if anything is added
   369  // after it is closed.
   370  func TestHeapAddAfterClose(t *testing.T) {
   371  	h := NewHeap(testHeapObjectKeyFunc, compareInts)
   372  	h.Close()
   373  	if err := h.Add(mkHeapObj("test", 1)); err == nil || err.Error() != closedMsg {
   374  		t.Errorf("expected heap closed error")
   375  	}
   376  	if err := h.AddIfNotPresent(mkHeapObj("test", 1)); err == nil || err.Error() != closedMsg {
   377  		t.Errorf("expected heap closed error")
   378  	}
   379  	if err := h.BulkAdd([]interface{}{mkHeapObj("test", 1)}); err == nil || err.Error() != closedMsg {
   380  		t.Errorf("expected heap closed error")
   381  	}
   382  }
   383
View as plain text