1/*
2Copyright 2017 The Kubernetes Authors.
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8    http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15*/
16
17package cache
18
19import (
20	"sync"
21	"testing"
22	"time"
23)
24
25func testHeapObjectKeyFunc(obj interface{}) (string, error) {
26	return obj.(testHeapObject).name, nil
27}
28
29type testHeapObject struct {
30	name string
31	val  interface{}
32}
33
34func mkHeapObj(name string, val interface{}) testHeapObject {
35	return testHeapObject{name: name, val: val}
36}
37
38func 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.
45func 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.
80func 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.
110func 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.
134func 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.
148func 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.
184func 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.
229func 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.
253func 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 == true {
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.
273func 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 == true {
287		t.Fatalf("didn't expect to get any object")
288	}
289}
290
291// TestHeap_Close tests Heap.Close and Heap.IsClosed functions.
292func 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.
307func 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.
339func 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.
370func 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