code.grnet.gr Git - ganeti-local/blob - test/ganeti.utils.algo_unittest.py

   1 #!/usr/bin/python
   2 #
   3
   4 # Copyright (C) 2011 Google Inc.
   5 #
   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.
  10 #
  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.
  15 #
  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
  19 # 02110-1301, USA.
  20
  21
  22 """Script for testing ganeti.utils.algo"""
  23
  24 import unittest
  25 import random
  26 import operator
  27
  28 from ganeti import constants
  29 from ganeti.utils import algo
  30
  31 import testutils
  32
  33
  34 class TestUniqueSequence(unittest.TestCase):
  35   """Test case for UniqueSequence"""
  36
  37   def _test(self, input, expected):
  38     self.assertEqual(algo.UniqueSequence(input), expected)
  39
  40   def runTest(self):
  41     # Ordered input
  42     self._test([1, 2, 3], [1, 2, 3])
  43     self._test([1, 1, 2, 2, 3, 3], [1, 2, 3])
  44     self._test([1, 2, 2, 3], [1, 2, 3])
  45     self._test([1, 2, 3, 3], [1, 2, 3])
  46
  47     # Unordered input
  48     self._test([1, 2, 3, 1, 2, 3], [1, 2, 3])
  49     self._test([1, 1, 2, 3, 3, 1, 2], [1, 2, 3])
  50
  51     # Strings
  52     self._test(["a", "a"], ["a"])
  53     self._test(["a", "b"], ["a", "b"])
  54     self._test(["a", "b", "a"], ["a", "b"])
  55
  56
  57 class TestFindDuplicates(unittest.TestCase):
  58   """Test case for FindDuplicates"""
  59
  60   def _Test(self, seq, expected):
  61     result = algo.FindDuplicates(seq)
  62     self.assertEqual(result, algo.UniqueSequence(result))
  63     self.assertEqual(set(result), set(expected))
  64
  65   def test(self):
  66     self._Test([], [])
  67     self._Test([1, 2, 3], [])
  68     self._Test([9, 8, 8, 0, 5, 1, 7, 0, 6, 7], [8, 0, 7])
  69     for exp in [[1, 2, 3], [3, 2, 1]]:
  70       self._Test([1, 1, 2, 2, 3, 3], exp)
  71
  72     self._Test(["A", "a", "B"], [])
  73     self._Test(["a", "A", "a", "B"], ["a"])
  74     self._Test("Hello World out there!", ["e", " ", "o", "r", "t", "l"])
  75
  76     self._Test(self._Gen(False), [])
  77     self._Test(self._Gen(True), range(1, 10))
  78
  79   @staticmethod
  80   def _Gen(dup):
  81     for i in range(10):
  82       yield i
  83       if dup:
  84         for _ in range(i):
  85           yield i
  86
  87
  88 class TestNiceSort(unittest.TestCase):
  89   def test(self):
  90     self.assertEqual(algo.NiceSort([]), [])
  91     self.assertEqual(algo.NiceSort(["foo"]), ["foo"])
  92     self.assertEqual(algo.NiceSort(["bar", ""]), ["", "bar"])
  93     self.assertEqual(algo.NiceSort([",", "."]), [",", "."])
  94     self.assertEqual(algo.NiceSort(["0.1", "0.2"]), ["0.1", "0.2"])
  95     self.assertEqual(algo.NiceSort(["0;099", "0,099", "0.1", "0.2"]),
  96                      ["0,099", "0.1", "0.2", "0;099"])
  97
  98     data = ["a0", "a1", "a99", "a20", "a2", "b10", "b70", "b00", "0000"]
  99     self.assertEqual(algo.NiceSort(data),
 100                      ["0000", "a0", "a1", "a2", "a20", "a99",
 101                       "b00", "b10", "b70"])
 102
 103     data = ["a0-0", "a1-0", "a99-10", "a20-3", "a0-4", "a99-3", "a09-2",
 104             "Z", "a9-1", "A", "b"]
 105     self.assertEqual(algo.NiceSort(data),
 106                      ["A", "Z", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
 107                       "a20-3", "a99-3", "a99-10", "b"])
 108     self.assertEqual(algo.NiceSort(data, key=str.lower),
 109                      ["A", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
 110                       "a20-3", "a99-3", "a99-10", "b", "Z"])
 111     self.assertEqual(algo.NiceSort(data, key=str.upper),
 112                      ["A", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
 113                       "a20-3", "a99-3", "a99-10", "b", "Z"])
 114
 115   def testLargeA(self):
 116     data = [
 117       "Eegah9ei", "xij88brTulHYAv8IEOyU", "3jTwJPtrXOY22bwL2YoW",
 118       "Z8Ljf1Pf5eBfNg171wJR", "WvNJd91OoXvLzdEiEXa6", "uHXAyYYftCSG1o7qcCqe",
 119       "xpIUJeVT1Rp", "KOt7vn1dWXi", "a07h8feON165N67PIE", "bH4Q7aCu3PUPjK3JtH",
 120       "cPRi0lM7HLnSuWA2G9", "KVQqLPDjcPjf8T3oyzjcOsfkb",
 121       "guKJkXnkULealVC8CyF1xefym", "pqF8dkU5B1cMnyZuREaSOADYx",
 122       ]
 123     self.assertEqual(algo.NiceSort(data), [
 124       "3jTwJPtrXOY22bwL2YoW", "Eegah9ei", "KOt7vn1dWXi",
 125       "KVQqLPDjcPjf8T3oyzjcOsfkb", "WvNJd91OoXvLzdEiEXa6",
 126       "Z8Ljf1Pf5eBfNg171wJR", "a07h8feON165N67PIE", "bH4Q7aCu3PUPjK3JtH",
 127       "cPRi0lM7HLnSuWA2G9", "guKJkXnkULealVC8CyF1xefym",
 128       "pqF8dkU5B1cMnyZuREaSOADYx", "uHXAyYYftCSG1o7qcCqe",
 129       "xij88brTulHYAv8IEOyU", "xpIUJeVT1Rp"
 130       ])
 131
 132   def testLargeB(self):
 133     data = [
 134       "inst-0.0.0.0-0.0.0.0",
 135       "inst-0.1.0.0-0.0.0.0",
 136       "inst-0.2.0.0-0.0.0.0",
 137       "inst-0.2.1.0-0.0.0.0",
 138       "inst-0.2.2.0-0.0.0.0",
 139       "inst-0.2.2.0-0.0.0.9",
 140       "inst-0.2.2.0-0.0.3.9",
 141       "inst-0.2.2.0-0.2.0.9",
 142       "inst-0.2.2.0-0.9.0.9",
 143       "inst-0.20.2.0-0.0.0.0",
 144       "inst-0.20.2.0-0.9.0.9",
 145       "inst-10.020.2.0-0.9.0.10",
 146       "inst-15.020.2.0-0.9.1.00",
 147       "inst-100.020.2.0-0.9.0.9",
 148
 149       # Only the last group, not converted to a number anymore, differs
 150       "inst-100.020.2.0a999",
 151       "inst-100.020.2.0b000",
 152       "inst-100.020.2.0c10",
 153       "inst-100.020.2.0c101",
 154       "inst-100.020.2.0c2",
 155       "inst-100.020.2.0c20",
 156       "inst-100.020.2.0c3",
 157       "inst-100.020.2.0c39123",
 158       ]
 159
 160     rnd = random.Random(16205)
 161     for _ in range(10):
 162       testdata = data[:]
 163       rnd.shuffle(testdata)
 164       assert testdata != data
 165       self.assertEqual(algo.NiceSort(testdata), data)
 166
 167   class _CallCount:
 168     def __init__(self, fn):
 169       self.count = 0
 170       self.fn = fn
 171
 172     def __call__(self, *args):
 173       self.count += 1
 174       return self.fn(*args)
 175
 176   def testKeyfuncA(self):
 177     # Generate some random numbers
 178     rnd = random.Random(21131)
 179     numbers = [rnd.randint(0, 10000) for _ in range(999)]
 180     assert numbers != sorted(numbers)
 181
 182     # Convert to hex
 183     data = [hex(i) for i in numbers]
 184     datacopy = data[:]
 185
 186     keyfn = self._CallCount(lambda value: str(int(value, 16)))
 187
 188     # Sort with key function converting hex to decimal
 189     result = algo.NiceSort(data, key=keyfn)
 190
 191     self.assertEqual([hex(i) for i in sorted(numbers)], result)
 192     self.assertEqual(data, datacopy, msg="Input data was modified in NiceSort")
 193     self.assertEqual(keyfn.count, len(numbers),
 194                      msg="Key function was not called once per value")
 195
 196   class _TestData:
 197     def __init__(self, name, value):
 198       self.name = name
 199       self.value = value
 200
 201   def testKeyfuncB(self):
 202     rnd = random.Random(27396)
 203     data = []
 204     for i in range(123):
 205       v1 = rnd.randint(0, 5)
 206       v2 = rnd.randint(0, 5)
 207       data.append(self._TestData("inst-%s-%s-%s" % (v1, v2, i),
 208                                  (v1, v2, i)))
 209     rnd.shuffle(data)
 210     assert data != sorted(data, key=operator.attrgetter("name"))
 211
 212     keyfn = self._CallCount(operator.attrgetter("name"))
 213
 214     # Sort by name
 215     result = algo.NiceSort(data, key=keyfn)
 216
 217     self.assertEqual(result, sorted(data, key=operator.attrgetter("value")))
 218     self.assertEqual(keyfn.count, len(data),
 219                      msg="Key function was not called once per value")
 220
 221   def testNiceSortKey(self):
 222     self.assertEqual(algo.NiceSortKey(""),
 223                      ([None] * algo._SORTER_GROUPS) + [""])
 224     self.assertEqual(algo.NiceSortKey("Hello World"),
 225                      ["Hello World"] +
 226                      ([None] * int(algo._SORTER_GROUPS - 1)) + [""])
 227     self.assertEqual(algo.NiceSortKey("node1.net75.bld3.example.com"),
 228                      ["node", 1, ".net", 75, ".bld", 3, ".example.com",
 229                       None, ""])
 230
 231
 232 class TimeMock:
 233   def __init__(self, values):
 234     self.values = values
 235
 236   def __call__(self):
 237     return self.values.pop(0)
 238
 239
 240 class TestRunningTimeout(unittest.TestCase):
 241   def setUp(self):
 242     self.time_fn = TimeMock([0.0, 0.3, 4.6, 6.5])
 243
 244   def testRemainingFloat(self):
 245     timeout = algo.RunningTimeout(5.0, True, _time_fn=self.time_fn)
 246     self.assertAlmostEqual(timeout.Remaining(), 4.7)
 247     self.assertAlmostEqual(timeout.Remaining(), 0.4)
 248     self.assertAlmostEqual(timeout.Remaining(), -1.5)
 249
 250   def testRemaining(self):
 251     self.time_fn = TimeMock([0, 2, 4, 5, 6])
 252     timeout = algo.RunningTimeout(5, True, _time_fn=self.time_fn)
 253     self.assertEqual(timeout.Remaining(), 3)
 254     self.assertEqual(timeout.Remaining(), 1)
 255     self.assertEqual(timeout.Remaining(), 0)
 256     self.assertEqual(timeout.Remaining(), -1)
 257
 258   def testRemainingNonNegative(self):
 259     timeout = algo.RunningTimeout(5.0, False, _time_fn=self.time_fn)
 260     self.assertAlmostEqual(timeout.Remaining(), 4.7)
 261     self.assertAlmostEqual(timeout.Remaining(), 0.4)
 262     self.assertEqual(timeout.Remaining(), 0.0)
 263
 264   def testNegativeTimeout(self):
 265     self.assertRaises(ValueError, algo.RunningTimeout, -1.0, True)
 266
 267
 268 if __name__ == "__main__":
 269   testutils.GanetiTestProgram()