1 package ridata
2
3 import (
4 "reflect"
5 "sort"
6 "testing"
7
8 "github.com/dsoprea/go-logging"
9 )
10
11 type testLruItem struct {
12 id LruKey
13 }
14
15 func (tli testLruItem) Id() LruKey {
16 return tli.id
17 }
18
19 func CreateTestLru(dropped *int) *Lru {
20 droppedCb := func(raw LruKey) (err error) {
21 id := raw.(int)
22 *dropped = id
23
24 return nil
25 }
26
27 lru := NewLru(5)
28 lru.SetDropCb(droppedCb)
29
30 tli1 := testLruItem{
31 id: 11,
32 }
33
34 _, _, err := lru.Set(tli1)
35 log.PanicIf(err)
36
37 if *dropped != 0 {
38 log.Panicf("No node should have been discarded.")
39 }
40
41 tli2 := testLruItem{
42 id: 22,
43 }
44
45 _, _, err = lru.Set(tli2)
46 log.PanicIf(err)
47
48 if *dropped != 0 {
49 log.Panicf("No node should have been discarded.")
50 }
51
52 tli3 := testLruItem{
53 id: 33,
54 }
55
56 _, _, err = lru.Set(tli3)
57 log.PanicIf(err)
58
59 if *dropped != 0 {
60 log.Panicf("No node should have been discarded.")
61 }
62
63 tli4 := testLruItem{
64 id: 44,
65 }
66
67 _, _, err = lru.Set(tli4)
68 log.PanicIf(err)
69
70 if *dropped != 0 {
71 log.Panicf("No node should have been discarded.")
72 }
73
74 size := lru.Count()
75 if size != 4 {
76 log.Panicf("LRU size not correct: (%d)", size)
77 }
78
79 return lru
80 }
81
82 func TestLru_Set(t *testing.T) {
83 defer func() {
84 if state := recover(); state != nil {
85 err := log.Wrap(state.(error))
86 log.PrintError(err)
87
88 t.Fatalf("Test failed.")
89 }
90 }()
91
92 var dropped int
93
94 lru := CreateTestLru(&dropped)
95
96 node1 := lru.top
97 node2 := node1.after
98 node3 := node2.after
99 node4 := node3.after
100
101 if node1.item.Id() != 44 {
102 t.Fatalf("First node not correct: [%v]", node1.item.Id())
103 } else if node2.item.Id() != 33 {
104 t.Fatalf("Second node not correct: [%v]", node2.item.Id())
105 } else if node3.item.Id() != 22 {
106 t.Fatalf("Third node not correct: [%v]", node3.item.Id())
107 } else if node4.item.Id() != 11 {
108 t.Fatalf("Fourth node not correct: [%v]", node4.item.Id())
109 }
110
111 if lru.bottom != node4 {
112 t.Fatalf("'bottom' node does not event fourth node.")
113 }
114
115 if node1.before != nil {
116 t.Fatalf("First node has a 'before' reference.")
117 } else if node4.after != nil {
118 t.Fatalf("Last record has a 'after' reference.")
119 }
120
121 if node4.before != node3 {
122 t.Fatalf("Fourth node 'before' node not correct.")
123 }
124 if node3.before != node2 {
125 t.Fatalf("Third node 'before' node not correct.")
126 }
127 if node2.before != node1 {
128 t.Fatalf("Second node 'before' node not correct.")
129 }
130
131
132
133 tli1 := testLruItem{
134 id: 55,
135 }
136
137 added, droppedItem, err := lru.Set(tli1)
138 log.PanicIf(err)
139
140 if added != true {
141 t.Fatalf("Value wasn't added but should've been.")
142 } else if droppedItem != nil {
143 t.Fatalf("No value should have been dropped but was: %v", droppedItem)
144 }
145
146 node55 := lru.top
147
148 if dropped != 0 {
149 t.Fatalf("No node should have been discarded.")
150 }
151
152 if len(lru.lookup) != 5 {
153 t.Fatalf("LRU not the right size.")
154 }
155
156 if lru.top.item.Id() != 55 {
157 t.Fatalf("Top value not updated.")
158 } else if lru.top.before != nil {
159 t.Fatalf("Top 'before' node not correct.")
160 } else if lru.top.after != node1 {
161 t.Fatalf("Top 'after' node not correct.")
162 } else if lru.bottom != node4 {
163 t.Fatalf("Bottom node not correct.")
164 } else if lru.bottom.before != node3 {
165 t.Fatalf("Bottom 'before' node not correct.")
166 }
167
168
169
170 tli2 := testLruItem{
171 id: 66,
172 }
173
174 added, droppedItem, err = lru.Set(tli2)
175 log.PanicIf(err)
176
177 if added != true {
178 t.Fatalf("Value wasn't added but should've been.")
179 } else if droppedItem.Id() != 11 {
180 t.Fatalf("Dropped value was not correct: %d", droppedItem.Id())
181 }
182
183 if dropped != 11 {
184 t.Fatalf("The wrong node was discarded: (%d)", dropped)
185 }
186
187 node66 := lru.top
188
189 if len(lru.lookup) != 5 {
190 t.Fatalf("LRU not the right size.")
191 }
192
193 if lru.top.item.Id() != 66 {
194 t.Fatalf("Top value not updated.")
195 } else if lru.top.before != nil {
196 t.Fatalf("Top 'before' node not correct.")
197 } else if lru.top.after != node55 {
198 t.Fatalf("Top 'after' node not correct.")
199 } else if lru.bottom != node3 {
200 t.Fatalf("Bottom node not correct.")
201 } else if lru.bottom.before != node2 {
202 t.Fatalf("Bottom 'before' node not correct.")
203 }
204
205
206
207 dropped = 0
208
209 tli3 := testLruItem{
210 id: 33,
211 }
212
213 added, droppedItem, err = lru.Set(tli3)
214 log.PanicIf(err)
215
216 if added != false {
217 t.Fatalf("Value wasn't updated but should've been.")
218 } else if droppedItem != nil {
219 t.Fatalf("Dropped value was not correct: %d", droppedItem.Id())
220 }
221
222 if dropped != 0 {
223 t.Fatalf("No node should have been discarded.")
224 }
225
226 if len(lru.lookup) != 5 {
227 t.Fatalf("LRU not the right size.")
228 }
229
230 if lru.top.item.Id() != 33 {
231 t.Fatalf("Bottom node not correct")
232 } else if lru.top.before != nil {
233 t.Fatalf("Top 'before' node not nil.")
234 } else if lru.top.after != node66 {
235 t.Fatalf("Top 'before' node not nil.")
236 }
237
238 if lru.bottom.item.Id() != 22 {
239 t.Fatalf("Bottom node not correct")
240 }
241 }
242
243 func TestLru_Count(t *testing.T) {
244 lru := NewLru(5)
245
246 if lru.Count() != 0 {
247 t.Fatalf("Count not correct when empty: (%d)", lru.Count())
248 }
249
250 tli1 := testLruItem{
251 id: 11,
252 }
253
254 _, _, err := lru.Set(tli1)
255 log.PanicIf(err)
256
257 if lru.Count() != 1 {
258 t.Fatalf("Count not correct after adding one: (%d)", lru.Count())
259 }
260
261 tli2 := testLruItem{
262 id: 22,
263 }
264
265 _, _, err = lru.Set(tli2)
266 log.PanicIf(err)
267
268 if lru.Count() != 2 {
269 t.Fatalf("Count not correct after adding two: (%d)", lru.Count())
270 }
271 }
272
273 func TestLru_IsFull(t *testing.T) {
274 lru := NewLru(2)
275
276 if lru.IsFull() != false {
277 t.Fatalf("IsFull not correct when empty.")
278 }
279
280 tli1 := testLruItem{
281 id: 11,
282 }
283
284 _, _, err := lru.Set(tli1)
285 log.PanicIf(err)
286
287 if lru.IsFull() != false {
288 t.Fatalf("IsFull not correct when with one item.")
289 }
290
291 tli2 := testLruItem{
292 id: 22,
293 }
294
295 _, _, err = lru.Set(tli2)
296 log.PanicIf(err)
297
298 if lru.IsFull() != true {
299 t.Fatalf("IsFull not correct with two items.")
300 }
301 }
302
303 func TestLru_Exists(t *testing.T) {
304 lru := NewLru(2)
305
306 if lru.Exists(22) != false {
307 t.Fatalf("Exists not correct when empty.")
308 }
309
310 tli1 := testLruItem{
311 id: 11,
312 }
313
314 _, _, err := lru.Set(tli1)
315 log.PanicIf(err)
316
317 if lru.Exists(22) != false {
318 t.Fatalf("Exists not correct when other items are present.")
319 }
320
321 tli2 := testLruItem{
322 id: 22,
323 }
324
325 _, _, err = lru.Set(tli2)
326 log.PanicIf(err)
327
328 if lru.Exists(22) != true {
329 t.Fatalf("Exists not correct when the key is present.")
330 }
331 }
332
333 func TestLru_Get(t *testing.T) {
334 lru := NewLru(2)
335
336
337
338 tli1 := testLruItem{
339 id: 11,
340 }
341
342 _, _, err := lru.Set(tli1)
343 log.PanicIf(err)
344
345 tli2 := testLruItem{
346 id: 22,
347 }
348
349 _, _, err = lru.Set(tli2)
350 log.PanicIf(err)
351
352
353
354 topId := lru.top.item.Id()
355 if topId != 22 {
356 t.Fatalf("Top-0 item not correct before touch: (%d)", topId)
357 }
358
359 secondId := lru.top.after.item.Id()
360 if secondId != 11 {
361 t.Fatalf("Top-1 item not correct before touch: (%d)", secondId)
362 }
363
364
365
366 found, _, err := lru.Get(99)
367 log.PanicIf(err)
368
369 if found != false {
370 t.Fatalf("Expected miss for unknown key.")
371 }
372
373
374
375 topId = lru.top.item.Id()
376 if topId != 22 {
377 t.Fatalf("Top-0 item not correct after intentional fault: (%d)", topId)
378 }
379
380 secondId = lru.top.after.item.Id()
381 if secondId != 11 {
382 t.Fatalf("Top-1 item not correct after intentional fault: (%d)", secondId)
383 }
384
385
386
387 found, item, err := lru.Get(11)
388 log.PanicIf(err)
389
390 if found != true {
391 t.Fatalf("Known item returned as miss (1)")
392 } else if item.Id() != 11 {
393 t.Fatalf("Known item return does not have right value (1): (%d)", item.Id())
394 }
395
396
397
398 topId = lru.top.item.Id()
399 if topId != 11 {
400 t.Fatalf("Top-0 item not correct after touch: (%d)", topId)
401 }
402
403 secondId = lru.top.after.item.Id()
404 if secondId != 22 {
405 t.Fatalf("Top-1 item not correct after touch: (%d)", secondId)
406 }
407
408
409
410
411 found, item, err = lru.Get(22)
412 log.PanicIf(err)
413
414 if found != true {
415 t.Fatalf("Known item returned as miss (2)")
416 } else if item.Id() != 22 {
417 t.Fatalf("Known item return does not have right value (2): (%d)", item.Id())
418 }
419
420
421
422 topId = lru.top.item.Id()
423 if topId != 22 {
424 t.Fatalf("Top-0 item not correct after touch 2: (%d)", topId)
425 }
426
427 secondId = lru.top.after.item.Id()
428 if secondId != 11 {
429 t.Fatalf("Top-1 item not correct after touch 2: (%d)", secondId)
430 }
431 }
432
433 func TestLru_Drop(t *testing.T) {
434 lru := NewLru(2)
435
436
437
438 tli1 := testLruItem{
439 id: 11,
440 }
441
442 _, _, err := lru.Set(tli1)
443 log.PanicIf(err)
444
445 tli2 := testLruItem{
446 id: 22,
447 }
448
449 _, _, err = lru.Set(tli2)
450 log.PanicIf(err)
451
452 if lru.Count() != 2 {
453 t.Fatalf("Count before drop not correct: (%d)", lru.Count())
454 }
455
456 found, err := lru.Drop(99)
457 log.PanicIf(err)
458
459 if found != false {
460 t.Fatalf("Dropping non-existent value did not report a miss.")
461 }
462
463 found, err = lru.Drop(11)
464 log.PanicIf(err)
465
466 if found != true {
467 t.Fatalf("Value to drop was reported as not found.")
468 }
469
470 if lru.Count() != 1 {
471 t.Fatalf("Count after drop not correct: (%d)", lru.Count())
472 }
473 }
474
475 func TestLru_Newest(t *testing.T) {
476 lru := NewLru(2)
477
478
479
480 tli1 := testLruItem{
481 id: 11,
482 }
483
484 _, _, err := lru.Set(tli1)
485 log.PanicIf(err)
486
487 tli2 := testLruItem{
488 id: 22,
489 }
490
491 _, _, err = lru.Set(tli2)
492 log.PanicIf(err)
493
494
495
496 if lru.Newest() != 22 {
497 t.Fatalf("Newest value not correct (1): (%d)", lru.Newest())
498 }
499
500 _, _, err = lru.Set(tli1)
501 log.PanicIf(err)
502
503 if lru.Newest() != 11 {
504 t.Fatalf("Newest value not correct (2): (%d)", lru.Newest())
505 }
506 }
507
508 func TestLru_Oldest(t *testing.T) {
509 lru := NewLru(2)
510
511
512
513 tli1 := testLruItem{
514 id: 11,
515 }
516
517 _, _, err := lru.Set(tli1)
518 log.PanicIf(err)
519
520 tli2 := testLruItem{
521 id: 22,
522 }
523
524 _, _, err = lru.Set(tli2)
525 log.PanicIf(err)
526
527
528
529 if lru.Oldest() != 11 {
530 t.Fatalf("Oldest value not correct (1): (%d)", lru.Oldest())
531 }
532
533 _, _, err = lru.Set(tli1)
534 log.PanicIf(err)
535
536 if lru.Oldest() != 22 {
537 t.Fatalf("Oldest value not correct (2): (%d)", lru.Oldest())
538 }
539 }
540
541 func TestLru_All(t *testing.T) {
542 lru := NewLru(2)
543
544
545
546 tli1 := testLruItem{
547 id: 11,
548 }
549
550 _, _, err := lru.Set(tli1)
551 log.PanicIf(err)
552
553 tli2 := testLruItem{
554 id: 22,
555 }
556
557 _, _, err = lru.Set(tli2)
558 log.PanicIf(err)
559
560 actualRaw := lru.All()
561
562 actual := make(sort.IntSlice, 2)
563 actual[0] = actualRaw[0].(int)
564 actual[1] = actualRaw[1].(int)
565
566 actual.Sort()
567
568 expected := sort.IntSlice{
569 11,
570 22,
571 }
572
573 expected.Sort()
574
575 if reflect.DeepEqual(actual, expected) != true {
576 t.Fatalf("All() did not return the right keys: %v != %v", actual, expected)
577 }
578 }
579
580 func TestLru_PopOldest(t *testing.T) {
581 lru := NewLru(2)
582
583
584
585 tli1 := testLruItem{
586 id: 11,
587 }
588
589 _, _, err := lru.Set(tli1)
590 log.PanicIf(err)
591
592 tli2 := testLruItem{
593 id: 22,
594 }
595
596 _, _, err = lru.Set(tli2)
597 log.PanicIf(err)
598
599 item, err := lru.PopOldest()
600 log.PanicIf(err)
601
602 if item.Id() != 11 {
603 t.Fatalf("Oldest not correct (1)")
604 }
605
606 item, err = lru.PopOldest()
607 log.PanicIf(err)
608
609 if item.Id() != 22 {
610 t.Fatalf("Oldest not correct (2)")
611 }
612
613 _, err = lru.PopOldest()
614 if err != ErrLruEmpty {
615 t.Fatalf("Expected ErrLruEmpty for empty LRU.")
616 }
617 }
618
619 func TestLru_FindPosition(t *testing.T) {
620 lru := NewLru(2)
621
622
623
624 tli1 := testLruItem{
625 id: 11,
626 }
627
628 _, _, err := lru.Set(tli1)
629 log.PanicIf(err)
630
631 p := lru.FindPosition(11)
632 if p != 0 {
633 t.Fatalf("Position not correct (1).")
634 }
635
636 tli2 := testLruItem{
637 id: 22,
638 }
639
640 _, _, err = lru.Set(tli2)
641 log.PanicIf(err)
642
643
644
645 p = lru.FindPosition(11)
646 if p != 1 {
647 t.Fatalf("Position not correct (1).")
648 }
649
650 _, _, err = lru.Set(tli1)
651 log.PanicIf(err)
652
653
654
655 p = lru.FindPosition(11)
656 if p != 0 {
657 t.Fatalf("Position not correct (3).")
658 }
659 }
660
661 func TestLru_MaxCount(t *testing.T) {
662 lru := NewLru(2)
663
664 if lru.MaxCount() != 2 {
665 t.Fatalf("MaxCount not correct (1).")
666 }
667
668 lru = NewLru(55)
669
670 if lru.MaxCount() != 55 {
671 t.Fatalf("MaxCount not correct (2).")
672 }
673 }
674
View as plain text