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
 222 class TimeMock:
 223   def __init__(self, values):
 224     self.values = values
 225
 226   def __call__(self):
 227     return self.values.pop(0)
 228
 229
 230 class TestRunningTimeout(unittest.TestCase):
 231   def setUp(self):
 232     self.time_fn = TimeMock([0.0, 0.3, 4.6, 6.5])
 233
 234   def testRemainingFloat(self):
 235     timeout = algo.RunningTimeout(5.0, True, _time_fn=self.time_fn)
 236     self.assertAlmostEqual(timeout.Remaining(), 4.7)
 237     self.assertAlmostEqual(timeout.Remaining(), 0.4)
 238     self.assertAlmostEqual(timeout.Remaining(), -1.5)
 239
 240   def testRemaining(self):
 241     self.time_fn = TimeMock([0, 2, 4, 5, 6])
 242     timeout = algo.RunningTimeout(5, True, _time_fn=self.time_fn)
 243     self.assertEqual(timeout.Remaining(), 3)
 244     self.assertEqual(timeout.Remaining(), 1)
 245     self.assertEqual(timeout.Remaining(), 0)
 246     self.assertEqual(timeout.Remaining(), -1)
 247
 248   def testRemainingNonNegative(self):
 249     timeout = algo.RunningTimeout(5.0, False, _time_fn=self.time_fn)
 250     self.assertAlmostEqual(timeout.Remaining(), 4.7)
 251     self.assertAlmostEqual(timeout.Remaining(), 0.4)
 252     self.assertEqual(timeout.Remaining(), 0.0)
 253
 254   def testNegativeTimeout(self):
 255     self.assertRaises(ValueError, algo.RunningTimeout, -1.0, True)
 256
 257
 258 if __name__ == "__main__":
 259   testutils.GanetiTestProgram()