queue.odin 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157
  1. package test_core_container
  2. import "base:runtime"
  3. import "core:container/queue"
  4. import "core:testing"
  5. @test
  6. test_queue :: proc(t: ^testing.T) {
  7. buf := [?]int{99, 99, 99, 99, 99}
  8. q: queue.Queue(int)
  9. testing.expect(t, queue.init_from_slice(&q, buf[:]))
  10. testing.expect_value(t, queue.reserve(&q, len(buf)), nil)
  11. queue.push_back(&q, 1)
  12. queue.push_back_elems(&q, 2, 3)
  13. queue.push_front(&q, 0)
  14. // {
  15. // data = [1, 2, 3, 99, 0],
  16. // len = 4,
  17. // offset = 4,
  18. // }
  19. testing.expect_value(t, queue.back(&q), 3)
  20. testing.expect_value(t, queue.back_ptr(&q), &buf[2])
  21. testing.expect_value(t, queue.front(&q), 0)
  22. testing.expect_value(t, queue.front_ptr(&q), &buf[4])
  23. queue.get(&q, 3)
  24. for i in 0..<4 {
  25. testing.expect_value(t, queue.get(&q, i), i)
  26. queue.set(&q, i, i)
  27. }
  28. testing.expect_value(t, queue.get_ptr(&q, 3), &buf[2])
  29. queue.consume_back(&q, 1)
  30. queue.consume_front(&q, 1)
  31. testing.expect_value(t, queue.pop_back(&q), 2)
  32. v, ok := queue.pop_back_safe(&q)
  33. testing.expect_value(t, v, 1)
  34. testing.expect_value(t, ok, true)
  35. // Test `init_with_contents`.
  36. buf2 := [?]int{99, 3, 5}
  37. queue.init_with_contents(&q, buf2[:])
  38. push_ok, push_err := queue.push_back(&q, 1)
  39. testing.expect(t, !push_ok)
  40. testing.expect_value(t, push_err, runtime.Allocator_Error.Out_Of_Memory)
  41. push_ok, push_err = queue.push_front(&q, 2)
  42. testing.expect(t, !push_ok)
  43. testing.expect_value(t, push_err, runtime.Allocator_Error.Out_Of_Memory)
  44. pop_front_v, pop_front_ok := queue.pop_front_safe(&q)
  45. testing.expect(t, pop_front_ok)
  46. testing.expect_value(t, pop_front_v, 99)
  47. // Re-initialization.
  48. queue.init(&q, 0)
  49. defer queue.destroy(&q)
  50. queue.push_back_elems(&q, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
  51. testing.expect_value(t, queue.len(q), 18)
  52. queue.push_back_elems(&q, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
  53. testing.expect_value(t, queue.len(q), 36)
  54. for i in 1..=18 {
  55. testing.expect_value(t, queue.pop_front(&q), i)
  56. }
  57. for i in 1..=18 {
  58. testing.expect_value(t, queue.pop_front(&q), i)
  59. }
  60. }
  61. @test
  62. test_queue_grow_edge_case :: proc(t: ^testing.T) {
  63. // Create a situation in which we trigger `q.offset + q.len > n` inside
  64. // `_grow` to evaluate the `copy` behavior.
  65. qq: queue.Queue(int)
  66. queue.init(&qq, 0)
  67. defer queue.destroy(&qq)
  68. queue.push_back_elems(&qq, 1, 2, 3, 4, 5, 6, 7)
  69. testing.expect_value(t, queue.pop_front(&qq), 1)
  70. testing.expect_value(t, queue.pop_front(&qq), 2)
  71. testing.expect_value(t, queue.pop_front(&qq), 3)
  72. queue.push_back(&qq, 8)
  73. queue.push_back(&qq, 9)
  74. testing.expect_value(t, qq.len, 6)
  75. testing.expect_value(t, qq.offset, 3)
  76. testing.expect_value(t, len(qq.data), 8) // value contingent on smallest dynamic array capacity on first allocation
  77. queue.reserve(&qq, 16)
  78. testing.expect_value(t, queue.len(qq), 6)
  79. for i in 4..=9 {
  80. testing.expect_value(t, queue.pop_front(&qq), i)
  81. }
  82. testing.expect_value(t, queue.len(qq), 0)
  83. // If we made it to this point without failure, the queue should have
  84. // copied the data into the right place after resizing the backing array.
  85. }
  86. @test
  87. test_queue_grow_edge_case_2 :: proc(t: ^testing.T) {
  88. // Create a situation in which we trigger `insert_from + insert_to > sz` inside `push_back_elems`
  89. // to evaluate the modified `insert_to` behavior.
  90. qq: queue.Queue(int)
  91. queue.init(&qq, 8)
  92. defer queue.destroy(&qq)
  93. queue.push_back_elems(&qq, -1, -2, -3, -4, -5, -6, -7)
  94. queue.consume_front(&qq, 3)
  95. queue.push_back_elems(&qq, -8, -9, -10)
  96. queue.push_back_elems(&qq, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  97. testing.expect_value(t, queue.len(qq), 17)
  98. for i in 4..=10 {
  99. testing.expect_value(t, queue.pop_front(&qq), -i)
  100. }
  101. for i in 1..=10 {
  102. testing.expect_value(t, queue.pop_front(&qq), i)
  103. }
  104. testing.expect_value(t, queue.len(qq), 0)
  105. }
  106. @test
  107. test_queue_shrink :: proc(t: ^testing.T) {
  108. qq: queue.Queue(int)
  109. queue.init(&qq, 8)
  110. defer queue.destroy(&qq)
  111. queue.push_back_elems(&qq, -1, -2, -3, -4, -5, -6, -7)
  112. queue.consume_front(&qq, 3)
  113. queue.push_back_elems(&qq, -8, -9, -10)
  114. queue.push_back_elems(&qq, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
  115. queue.shrink(&qq)
  116. queue.consume_front(&qq, 7)
  117. queue.shrink(&qq)
  118. for i in 1..=10 {
  119. testing.expect_value(t, queue.pop_front(&qq), i)
  120. }
  121. buf: [1]int
  122. qq_backed: queue.Queue(int)
  123. queue.init_from_slice(&qq_backed, buf[:])
  124. queue.shrink(&qq_backed)
  125. }