]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | ||
4 | #include "gtest/gtest.h" | |
5 | #include "common/PrioritizedQueue.h" | |
6 | ||
7 | #include <numeric> | |
8 | #include <vector> | |
9 | #include <algorithm> | |
10 | ||
11 | using std::vector; | |
12 | ||
13 | class PrioritizedQueueTest : public testing::Test | |
14 | { | |
15 | protected: | |
16 | typedef int Klass; | |
17 | typedef unsigned Item; | |
18 | typedef PrioritizedQueue<Item, Klass> PQ; | |
19 | enum { item_size = 100, }; | |
20 | vector<Item> items; | |
21 | ||
22 | void SetUp() override { | |
23 | for (int i = 0; i < item_size; i++) { | |
24 | items.push_back(Item(i)); | |
25 | } | |
26 | std::random_shuffle(items.begin(), items.end()); | |
27 | } | |
28 | void TearDown() override { | |
29 | items.clear(); | |
30 | } | |
31 | }; | |
32 | ||
33 | TEST_F(PrioritizedQueueTest, capacity) { | |
34 | const unsigned min_cost = 10; | |
35 | const unsigned max_tokens_per_subqueue = 50; | |
36 | PQ pq(max_tokens_per_subqueue, min_cost); | |
37 | EXPECT_TRUE(pq.empty()); | |
38 | EXPECT_EQ(0u, pq.length()); | |
39 | ||
40 | pq.enqueue_strict(Klass(1), 0, Item(0)); | |
41 | EXPECT_FALSE(pq.empty()); | |
42 | EXPECT_EQ(1u, pq.length()); | |
43 | ||
44 | for (int i = 0; i < 3; i++) { | |
45 | pq.enqueue(Klass(1), 0, 10, Item(0)); | |
46 | } | |
47 | for (unsigned i = 4; i > 0; i--) { | |
48 | EXPECT_FALSE(pq.empty()); | |
49 | EXPECT_EQ(i, pq.length()); | |
50 | pq.dequeue(); | |
51 | } | |
52 | EXPECT_TRUE(pq.empty()); | |
53 | EXPECT_EQ(0u, pq.length()); | |
54 | } | |
55 | ||
56 | TEST_F(PrioritizedQueueTest, strict_pq) { | |
57 | const unsigned min_cost = 1; | |
58 | const unsigned max_tokens_per_subqueue = 50; | |
59 | PQ pq(max_tokens_per_subqueue, min_cost); | |
60 | // 0 .. item_size-1 | |
61 | for (unsigned i = 0; i < item_size; i++) { | |
62 | unsigned priority = items[i]; | |
63 | pq.enqueue_strict(Klass(0), priority, items[i]); | |
64 | } | |
65 | // item_size-1 .. 0 | |
66 | for (unsigned i = item_size; i > 0; i--) { | |
67 | Item item = pq.dequeue(); | |
68 | unsigned priority = item; | |
69 | EXPECT_EQ(i - 1, priority); | |
70 | } | |
71 | } | |
72 | ||
73 | TEST_F(PrioritizedQueueTest, lowest_among_eligible_otherwise_highest) { | |
74 | // to minimize the effect of `distribute_tokens()` | |
75 | // all eligible items will be assigned with cost of min_cost | |
76 | const unsigned min_cost = 0; | |
77 | const unsigned max_tokens_per_subqueue = 100; | |
78 | PQ pq(max_tokens_per_subqueue, min_cost); | |
79 | ||
80 | #define ITEM_TO_COST(item_) (item_ % 5 ? min_cost : max_tokens_per_subqueue) | |
81 | unsigned num_low_cost = 0, num_high_cost = 0; | |
82 | for (int i = 0; i < item_size; i++) { | |
83 | const Item& item = items[i]; | |
84 | unsigned cost = ITEM_TO_COST(item); | |
85 | unsigned priority = item; | |
86 | if (cost == min_cost) { | |
87 | num_low_cost++; | |
88 | } else { | |
89 | num_high_cost++; | |
90 | } | |
91 | pq.enqueue(Klass(0), priority, cost, item); | |
92 | } | |
93 | // the token in all buckets is 0 at the beginning, so dequeue() should pick | |
94 | // the first one with the highest priority. | |
95 | unsigned highest_priority; | |
96 | { | |
97 | Item item = pq.dequeue(); | |
98 | unsigned cost = ITEM_TO_COST(item); | |
99 | unsigned priority = item; | |
100 | if (cost == min_cost) { | |
101 | num_low_cost--; | |
102 | } else { | |
103 | num_high_cost--; | |
104 | } | |
105 | EXPECT_EQ(item_size - 1u, priority); | |
106 | highest_priority = priority; | |
107 | } | |
108 | unsigned lowest_priority = 0; | |
109 | for (unsigned i = 0; i < num_low_cost; i++) { | |
110 | Item item = pq.dequeue(); | |
111 | unsigned cost = ITEM_TO_COST(item); | |
112 | unsigned priority = item; | |
113 | EXPECT_EQ(min_cost, cost); | |
114 | EXPECT_GT(priority, lowest_priority); | |
115 | lowest_priority = priority; | |
116 | } | |
117 | for (unsigned i = 0; i < num_high_cost; i++) { | |
118 | Item item = pq.dequeue(); | |
119 | unsigned cost = ITEM_TO_COST(item); | |
120 | unsigned priority = item; | |
121 | EXPECT_EQ(max_tokens_per_subqueue, cost); | |
122 | EXPECT_LT(priority, highest_priority); | |
123 | highest_priority = priority; | |
124 | } | |
125 | #undef ITEM_TO_COST | |
126 | } | |
127 | ||
128 | static const unsigned num_classes = 4; | |
129 | // just a determinitic number | |
130 | #define ITEM_TO_CLASS(item_) Klass((item_ + 43) % num_classes) | |
131 | ||
132 | TEST_F(PrioritizedQueueTest, fairness_by_class) { | |
133 | // dequeue should be fair to all classes in a certain bucket | |
134 | const unsigned min_cost = 1; | |
135 | const unsigned max_tokens_per_subqueue = 50; | |
136 | PQ pq(max_tokens_per_subqueue, min_cost); | |
137 | ||
138 | for (int i = 0; i < item_size; i++) { | |
139 | const Item& item = items[i]; | |
140 | Klass k = ITEM_TO_CLASS(item); | |
141 | unsigned priority = 0; | |
142 | unsigned cost = 1; | |
143 | pq.enqueue(k, priority, cost, item); | |
144 | } | |
145 | // just sample first 1/2 of the items | |
146 | // if i pick too small a dataset, the result won't be statisitcally | |
147 | // significant. if the sample dataset is too large, it will converge to the | |
148 | // distribution of the full set. | |
149 | vector<unsigned> num_picked_in_class(num_classes, 0u); | |
150 | for (int i = 0; i < item_size / 2; i++) { | |
151 | Item item = pq.dequeue(); | |
152 | Klass k = ITEM_TO_CLASS(item); | |
153 | num_picked_in_class[k]++; | |
154 | } | |
155 | unsigned total = std::accumulate(num_picked_in_class.begin(), | |
156 | num_picked_in_class.end(), | |
157 | 0); | |
158 | float avg = float(total) / num_classes; | |
159 | for (unsigned i = 0; i < num_classes; i++) { | |
160 | EXPECT_NEAR(avg, num_picked_in_class[i], 0.5); | |
161 | } | |
162 | } | |
163 | ||
7c673cae FG |
164 | |
165 | TEST_F(PrioritizedQueueTest, remove_by_class) { | |
166 | const unsigned min_cost = 1; | |
167 | const unsigned max_tokens_per_subqueue = 50; | |
168 | PQ pq(max_tokens_per_subqueue, min_cost); | |
169 | const Klass class_to_remove(2); | |
170 | unsigned num_to_remove = 0; | |
171 | for (int i = 0; i < item_size; i++) { | |
172 | const Item& item = items[i]; | |
173 | Klass k = ITEM_TO_CLASS(item); | |
174 | pq.enqueue(k, 0, 0, item); | |
175 | if (k == class_to_remove) { | |
176 | num_to_remove++; | |
177 | } | |
178 | } | |
179 | std::list<Item> removed; | |
180 | pq.remove_by_class(class_to_remove, &removed); | |
181 | ||
182 | // see if the removed items are expected ones. | |
183 | for (std::list<Item>::iterator it = removed.begin(); | |
184 | it != removed.end(); | |
185 | ++it) { | |
186 | const Item& item = *it; | |
187 | Klass k = ITEM_TO_CLASS(item); | |
188 | EXPECT_EQ(class_to_remove, k); | |
189 | items.erase(remove(items.begin(), items.end(), item), items.end()); | |
190 | } | |
191 | EXPECT_EQ(num_to_remove, removed.size()); | |
192 | EXPECT_EQ(item_size - num_to_remove, pq.length()); | |
193 | EXPECT_EQ(item_size - num_to_remove, items.size()); | |
194 | // see if the remainder are expeceted also. | |
195 | while (!pq.empty()) { | |
196 | const Item item = pq.dequeue(); | |
197 | Klass k = ITEM_TO_CLASS(item); | |
198 | EXPECT_NE(class_to_remove, k); | |
199 | items.erase(remove(items.begin(), items.end(), item), items.end()); | |
200 | } | |
201 | EXPECT_TRUE(items.empty()); | |
202 | } |