1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 #include "gtest/gtest.h"
5 #include "common/PrioritizedQueue.h"
13 class PrioritizedQueueTest
: public testing::Test
17 typedef unsigned Item
;
18 typedef PrioritizedQueue
<Item
, Klass
> PQ
;
19 enum { item_size
= 100, };
22 void SetUp() override
{
23 for (int i
= 0; i
< item_size
; i
++) {
24 items
.push_back(Item(i
));
26 std::random_shuffle(items
.begin(), items
.end());
28 void TearDown() override
{
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());
40 pq
.enqueue_strict(Klass(1), 0, Item(0));
41 EXPECT_FALSE(pq
.empty());
42 EXPECT_EQ(1u, pq
.length());
44 for (int i
= 0; i
< 3; i
++) {
45 pq
.enqueue(Klass(1), 0, 10, Item(0));
47 for (unsigned i
= 4; i
> 0; i
--) {
48 EXPECT_FALSE(pq
.empty());
49 EXPECT_EQ(i
, pq
.length());
52 EXPECT_TRUE(pq
.empty());
53 EXPECT_EQ(0u, pq
.length());
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
);
61 for (unsigned i
= 0; i
< item_size
; i
++) {
62 unsigned priority
= items
[i
];
63 pq
.enqueue_strict(Klass(0), priority
, items
[i
]);
66 for (unsigned i
= item_size
; i
> 0; i
--) {
67 Item item
= pq
.dequeue();
68 unsigned priority
= item
;
69 EXPECT_EQ(i
- 1, priority
);
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
);
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
) {
91 pq
.enqueue(Klass(0), priority
, cost
, item
);
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
;
97 Item item
= pq
.dequeue();
98 unsigned cost
= ITEM_TO_COST(item
);
99 unsigned priority
= item
;
100 if (cost
== min_cost
) {
105 EXPECT_EQ(item_size
- 1u, priority
);
106 highest_priority
= priority
;
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
;
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
;
128 static const unsigned num_classes
= 4;
129 // just a determinitic number
130 #define ITEM_TO_CLASS(item_) Klass((item_ + 43) % num_classes)
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
);
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;
143 pq
.enqueue(k
, priority
, cost
, item
);
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
]++;
155 unsigned total
= std::accumulate(num_picked_in_class
.begin(),
156 num_picked_in_class
.end(),
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);
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
) {
179 std::list
<Item
> removed
;
180 pq
.remove_by_class(class_to_remove
, &removed
);
182 // see if the removed items are expected ones.
183 for (std::list
<Item
>::iterator it
= removed
.begin();
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());
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());
201 EXPECT_TRUE(items
.empty());