4 # Copyright (C) 2011, 2012 Google Inc.
6 # This program is free software; you can redistribute it and/or modify
7 # it under the terms of the GNU General Public License as published by
8 # the Free Software Foundation; either version 2 of the License, or
9 # (at your option) any later version.
11 # This program is distributed in the hope that it will be useful, but
12 # WITHOUT ANY WARRANTY; without even the implied warranty of
13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 # General Public License for more details.
16 # You should have received a copy of the GNU General Public License
17 # along with this program; if not, write to the Free Software
18 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
22 """Script for testing ganeti.utils.algo"""
28 from ganeti import constants
29 from ganeti import compat
30 from ganeti.utils import algo
35 class TestUniqueSequence(unittest.TestCase):
36 """Test case for UniqueSequence"""
38 def _test(self, input, expected):
39 self.assertEqual(algo.UniqueSequence(input), expected)
43 self._test([1, 2, 3], [1, 2, 3])
44 self._test([1, 1, 2, 2, 3, 3], [1, 2, 3])
45 self._test([1, 2, 2, 3], [1, 2, 3])
46 self._test([1, 2, 3, 3], [1, 2, 3])
49 self._test([1, 2, 3, 1, 2, 3], [1, 2, 3])
50 self._test([1, 1, 2, 3, 3, 1, 2], [1, 2, 3])
53 self._test(["a", "a"], ["a"])
54 self._test(["a", "b"], ["a", "b"])
55 self._test(["a", "b", "a"], ["a", "b"])
58 class TestFindDuplicates(unittest.TestCase):
59 """Test case for FindDuplicates"""
61 def _Test(self, seq, expected):
62 result = algo.FindDuplicates(seq)
63 self.assertEqual(result, algo.UniqueSequence(result))
64 self.assertEqual(set(result), set(expected))
68 self._Test([1, 2, 3], [])
69 self._Test([9, 8, 8, 0, 5, 1, 7, 0, 6, 7], [8, 0, 7])
70 for exp in [[1, 2, 3], [3, 2, 1]]:
71 self._Test([1, 1, 2, 2, 3, 3], exp)
73 self._Test(["A", "a", "B"], [])
74 self._Test(["a", "A", "a", "B"], ["a"])
75 self._Test("Hello World out there!", ["e", " ", "o", "r", "t", "l"])
77 self._Test(self._Gen(False), [])
78 self._Test(self._Gen(True), range(1, 10))
89 class TestNiceSort(unittest.TestCase):
91 self.assertEqual(algo.NiceSort([]), [])
92 self.assertEqual(algo.NiceSort(["foo"]), ["foo"])
93 self.assertEqual(algo.NiceSort(["bar", ""]), ["", "bar"])
94 self.assertEqual(algo.NiceSort([",", "."]), [",", "."])
95 self.assertEqual(algo.NiceSort(["0.1", "0.2"]), ["0.1", "0.2"])
96 self.assertEqual(algo.NiceSort(["0;099", "0,099", "0.1", "0.2"]),
97 ["0,099", "0.1", "0.2", "0;099"])
99 data = ["a0", "a1", "a99", "a20", "a2", "b10", "b70", "b00", "0000"]
100 self.assertEqual(algo.NiceSort(data),
101 ["0000", "a0", "a1", "a2", "a20", "a99",
102 "b00", "b10", "b70"])
104 data = ["a0-0", "a1-0", "a99-10", "a20-3", "a0-4", "a99-3", "a09-2",
105 "Z", "a9-1", "A", "b"]
106 self.assertEqual(algo.NiceSort(data),
107 ["A", "Z", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
108 "a20-3", "a99-3", "a99-10", "b"])
109 self.assertEqual(algo.NiceSort(data, key=str.lower),
110 ["A", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
111 "a20-3", "a99-3", "a99-10", "b", "Z"])
112 self.assertEqual(algo.NiceSort(data, key=str.upper),
113 ["A", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
114 "a20-3", "a99-3", "a99-10", "b", "Z"])
116 def testLargeA(self):
118 "Eegah9ei", "xij88brTulHYAv8IEOyU", "3jTwJPtrXOY22bwL2YoW",
119 "Z8Ljf1Pf5eBfNg171wJR", "WvNJd91OoXvLzdEiEXa6", "uHXAyYYftCSG1o7qcCqe",
120 "xpIUJeVT1Rp", "KOt7vn1dWXi", "a07h8feON165N67PIE", "bH4Q7aCu3PUPjK3JtH",
121 "cPRi0lM7HLnSuWA2G9", "KVQqLPDjcPjf8T3oyzjcOsfkb",
122 "guKJkXnkULealVC8CyF1xefym", "pqF8dkU5B1cMnyZuREaSOADYx",
124 self.assertEqual(algo.NiceSort(data), [
125 "3jTwJPtrXOY22bwL2YoW", "Eegah9ei", "KOt7vn1dWXi",
126 "KVQqLPDjcPjf8T3oyzjcOsfkb", "WvNJd91OoXvLzdEiEXa6",
127 "Z8Ljf1Pf5eBfNg171wJR", "a07h8feON165N67PIE", "bH4Q7aCu3PUPjK3JtH",
128 "cPRi0lM7HLnSuWA2G9", "guKJkXnkULealVC8CyF1xefym",
129 "pqF8dkU5B1cMnyZuREaSOADYx", "uHXAyYYftCSG1o7qcCqe",
130 "xij88brTulHYAv8IEOyU", "xpIUJeVT1Rp"
133 def testLargeB(self):
135 "inst-0.0.0.0-0.0.0.0",
136 "inst-0.1.0.0-0.0.0.0",
137 "inst-0.2.0.0-0.0.0.0",
138 "inst-0.2.1.0-0.0.0.0",
139 "inst-0.2.2.0-0.0.0.0",
140 "inst-0.2.2.0-0.0.0.9",
141 "inst-0.2.2.0-0.0.3.9",
142 "inst-0.2.2.0-0.2.0.9",
143 "inst-0.2.2.0-0.9.0.9",
144 "inst-0.20.2.0-0.0.0.0",
145 "inst-0.20.2.0-0.9.0.9",
146 "inst-10.020.2.0-0.9.0.10",
147 "inst-15.020.2.0-0.9.1.00",
148 "inst-100.020.2.0-0.9.0.9",
150 # Only the last group, not converted to a number anymore, differs
151 "inst-100.020.2.0a999",
152 "inst-100.020.2.0b000",
153 "inst-100.020.2.0c10",
154 "inst-100.020.2.0c101",
155 "inst-100.020.2.0c2",
156 "inst-100.020.2.0c20",
157 "inst-100.020.2.0c3",
158 "inst-100.020.2.0c39123",
161 rnd = random.Random(16205)
164 rnd.shuffle(testdata)
165 assert testdata != data
166 self.assertEqual(algo.NiceSort(testdata), data)
169 def __init__(self, fn):
173 def __call__(self, *args):
175 return self.fn(*args)
177 def testKeyfuncA(self):
178 # Generate some random numbers
179 rnd = random.Random(21131)
180 numbers = [rnd.randint(0, 10000) for _ in range(999)]
181 assert numbers != sorted(numbers)
184 data = [hex(i) for i in numbers]
187 keyfn = self._CallCount(lambda value: str(int(value, 16)))
189 # Sort with key function converting hex to decimal
190 result = algo.NiceSort(data, key=keyfn)
192 self.assertEqual([hex(i) for i in sorted(numbers)], result)
193 self.assertEqual(data, datacopy, msg="Input data was modified in NiceSort")
194 self.assertEqual(keyfn.count, len(numbers),
195 msg="Key function was not called once per value")
198 def __init__(self, name, value):
202 def testKeyfuncB(self):
203 rnd = random.Random(27396)
206 v1 = rnd.randint(0, 5)
207 v2 = rnd.randint(0, 5)
208 data.append(self._TestData("inst-%s-%s-%s" % (v1, v2, i),
211 assert data != sorted(data, key=operator.attrgetter("name"))
213 keyfn = self._CallCount(operator.attrgetter("name"))
216 result = algo.NiceSort(data, key=keyfn)
218 self.assertEqual(result, sorted(data, key=operator.attrgetter("value")))
219 self.assertEqual(keyfn.count, len(data),
220 msg="Key function was not called once per value")
222 def testNiceSortKey(self):
223 self.assertEqual(algo.NiceSortKey(""),
224 ([None] * algo._SORTER_GROUPS) + [""])
225 self.assertEqual(algo.NiceSortKey("Hello World"),
227 ([None] * int(algo._SORTER_GROUPS - 1)) + [""])
228 self.assertEqual(algo.NiceSortKey("node1.net75.bld3.example.com"),
229 ["node", 1, ".net", 75, ".bld", 3, ".example.com",
233 class TestInvertDict(unittest.TestCase):
234 def testInvertDict(self):
235 test_dict = { "foo": 1, "bar": 2, "baz": 5 }
236 self.assertEqual(algo.InvertDict(test_dict),
237 { 1: "foo", 2: "bar", 5: "baz"})
240 class TestInsertAtPos(unittest.TestCase):
244 self.assertEqual(algo.InsertAtPos(a, 1, b), [1, 2, 3, 4, 5, 6])
245 self.assertEqual(algo.InsertAtPos(a, 0, b), b + a)
246 self.assertEqual(algo.InsertAtPos(a, len(a), b), a + b)
247 self.assertEqual(algo.InsertAtPos(a, 2, b), [1, 5, 2, 3, 4, 6])
251 def __init__(self, values):
255 return self.values.pop(0)
258 class TestRunningTimeout(unittest.TestCase):
260 self.time_fn = TimeMock([0.0, 0.3, 4.6, 6.5])
262 def testRemainingFloat(self):
263 timeout = algo.RunningTimeout(5.0, True, _time_fn=self.time_fn)
264 self.assertAlmostEqual(timeout.Remaining(), 4.7)
265 self.assertAlmostEqual(timeout.Remaining(), 0.4)
266 self.assertAlmostEqual(timeout.Remaining(), -1.5)
268 def testRemaining(self):
269 self.time_fn = TimeMock([0, 2, 4, 5, 6])
270 timeout = algo.RunningTimeout(5, True, _time_fn=self.time_fn)
271 self.assertEqual(timeout.Remaining(), 3)
272 self.assertEqual(timeout.Remaining(), 1)
273 self.assertEqual(timeout.Remaining(), 0)
274 self.assertEqual(timeout.Remaining(), -1)
276 def testRemainingNonNegative(self):
277 timeout = algo.RunningTimeout(5.0, False, _time_fn=self.time_fn)
278 self.assertAlmostEqual(timeout.Remaining(), 4.7)
279 self.assertAlmostEqual(timeout.Remaining(), 0.4)
280 self.assertEqual(timeout.Remaining(), 0.0)
282 def testNegativeTimeout(self):
283 self.assertRaises(ValueError, algo.RunningTimeout, -1.0, True)
286 class TestJoinDisjointDicts(unittest.TestCase):
288 self.non_empty_dict = {"a": 1, "b": 2}
291 def testWithEmptyDicts(self):
292 self.assertEqual(self.empty_dict, algo.JoinDisjointDicts(self.empty_dict,
294 self.assertEqual(self.non_empty_dict, algo.JoinDisjointDicts(
295 self.empty_dict, self.non_empty_dict))
296 self.assertEqual(self.non_empty_dict, algo.JoinDisjointDicts(
297 self.non_empty_dict, self.empty_dict))
299 def testNonDisjoint(self):
300 self.assertRaises(AssertionError, algo.JoinDisjointDicts,
301 self.non_empty_dict, self.non_empty_dict)
303 def testCommonCase(self):
304 dict_a = {"TEST1": 1, "TEST2": 2}
305 dict_b = {"TEST3": 3, "TEST4": 4}
307 result = dict_a.copy()
308 result.update(dict_b)
310 self.assertEqual(result, algo.JoinDisjointDicts(dict_a, dict_b))
311 self.assertEqual(result, algo.JoinDisjointDicts(dict_b, dict_a))
314 class TestSequenceToDict(unittest.TestCase):
316 self.assertEqual(algo.SequenceToDict([]), {})
317 self.assertEqual(algo.SequenceToDict({}), {})
319 def testSimple(self):
320 data = [(i, str(i), "test%s" % i) for i in range(391)]
321 self.assertEqual(algo.SequenceToDict(data),
322 dict((i, (i, str(i), "test%s" % i))
323 for i in range(391)))
325 def testCustomKey(self):
326 data = [(i, hex(i), "test%s" % i) for i in range(100)]
327 self.assertEqual(algo.SequenceToDict(data, key=compat.snd),
328 dict((hex(i), (i, hex(i), "test%s" % i))
329 for i in range(100)))
330 self.assertEqual(algo.SequenceToDict(data,
331 key=lambda (a, b, val): hash(val)),
332 dict((hash("test%s" % i), (i, hex(i), "test%s" % i))
333 for i in range(100)))
335 def testDuplicate(self):
336 self.assertRaises(ValueError, algo.SequenceToDict,
338 self.assertRaises(ValueError, algo.SequenceToDict,
339 [(i, ) for i in range(200)] + [(10, )])
342 class TestFlatToDict(unittest.TestCase):
343 def testNormal(self):
345 ("lv/xenvg", {"foo": "bar", "bar": "baz"}),
346 ("lv/xenfoo", {"foo": "bar", "baz": "blubb"}),
347 ("san/foo", {"ip": "127.0.0.1", "port": 1337}),
348 ("san/blubb/blibb", 54),
352 "xenvg": {"foo": "bar", "bar": "baz"},
353 "xenfoo": {"foo": "bar", "baz": "blubb"},
356 "foo": {"ip": "127.0.0.1", "port": 1337},
357 "blubb": {"blibb": 54},
360 self.assertEqual(algo.FlatToDict(data), reference)
362 def testUnlikeDepth(self):
364 ("san/foo", {"ip": "127.0.0.1", "port": 1337}),
365 ("san/foo/blubb", 23), # Another foo entry under san
366 ("san/blubb/blibb", 54),
368 self.assertRaises(AssertionError, algo.FlatToDict, data)
371 if __name__ == "__main__":
372 testutils.GanetiTestProgram()