1 /*
2 * Copyright © 2019 Google, LLC
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 */
23
24 #include "util/u_vector.h"
25 #include "gtest/gtest.h"
26
test(uint32_t size_in_elements,uint32_t elements_to_walk,uint32_t start)27 static void test(uint32_t size_in_elements, uint32_t elements_to_walk, uint32_t start)
28 {
29 struct u_vector vector;
30 uint32_t add_counter = 0;
31 uint32_t remove_counter = 0;
32
33 ASSERT_TRUE(u_vector_init(&vector, size_in_elements, sizeof(uint64_t)));
34
35 // Override the head and tail so we can quickly test rollover
36 vector.head = vector.tail = start;
37
38 EXPECT_EQ(sizeof(uint64_t) * size_in_elements, vector.size);
39 EXPECT_EQ(0, u_vector_length(&vector));
40
41 for (uint32_t i = 0; i < size_in_elements; i++) {
42 *(uint64_t*)u_vector_add(&vector) = add_counter++;
43
44 int length = u_vector_length(&vector);
45 EXPECT_EQ(i + 1, length);
46
47 // Check the entries
48 uint32_t count = 0;
49 void* element;
50 u_vector_foreach(element, &vector)
51 {
52 EXPECT_EQ(count, *(uint64_t*)element) << "i: " << i << " count: " << count;
53 count++;
54 }
55 EXPECT_EQ(count, length);
56 }
57
58 // Remove + add
59 for (uint32_t i = 0; i < elements_to_walk; i++) {
60 u_vector_remove(&vector);
61 remove_counter++;
62 *(uint64_t*)u_vector_add(&vector) = add_counter++;
63 }
64
65 EXPECT_EQ(sizeof(uint64_t) * size_in_elements, vector.size);
66
67 // Grow the vector now
68 *(uint64_t*)u_vector_add(&vector) = add_counter++;
69 EXPECT_EQ(size_in_elements + 1, u_vector_length(&vector));
70
71 EXPECT_EQ(sizeof(uint64_t) * size_in_elements * 2, vector.size);
72
73 {
74 uint32_t count = remove_counter;
75 void* element;
76 u_vector_foreach(element, &vector)
77 {
78 EXPECT_EQ(count++, *(uint64_t*)element) << "count: " << count;
79 }
80 }
81
82 u_vector_finish(&vector);
83 }
84
TEST(Vector,Grow0)85 TEST(Vector, Grow0) { test(4, 0, 0); }
86
TEST(Vector,Grow1)87 TEST(Vector, Grow1) { test(4, 1, 0); }
88
TEST(Vector,Grow2)89 TEST(Vector, Grow2) { test(4, 2, 0); }
90
TEST(Vector,Grow3)91 TEST(Vector, Grow3) { test(4, 3, 0); }
92
TEST(Vector,Grow4)93 TEST(Vector, Grow4) { test(4, 4, 0); }
94
TEST(Vector,Grow5)95 TEST(Vector, Grow5) { test(4, 5, 0); }
96
TEST(Vector,Rollover)97 TEST(Vector, Rollover)
98 {
99 uint32_t start = (1ull << 32) - 4 * sizeof(uint64_t);
100 test(8, 4, start);
101 }
102