code.grnet.gr Git - ganeti-local/blob - lib/utils/algo.py

   1 #
   2 #
   3
   4 # Copyright (C) 2006, 2007, 2010, 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 """Utility functions with algorithms.
  22
  23 """
  24
  25 import re
  26 import time
  27 import itertools
  28
  29 from ganeti import compat
  30 from ganeti.utils import text
  31
  32
  33 _SORTER_GROUPS = 8
  34 _SORTER_RE = re.compile("^%s(.*)$" % (_SORTER_GROUPS * "(\D+|\d+)?"))
  35
  36
  37 def UniqueSequence(seq):
  38   """Returns a list with unique elements.
  39
  40   Element order is preserved.
  41
  42   @type seq: sequence
  43   @param seq: the sequence with the source elements
  44   @rtype: list
  45   @return: list of unique elements from seq
  46
  47   """
  48   seen = set()
  49   return [i for i in seq if i not in seen and not seen.add(i)]
  50
  51
  52 def JoinDisjointDicts(dict_a, dict_b):
  53   """Joins dictionaries with no conflicting keys.
  54
  55   Enforces the constraint that the two key sets must be disjoint, and then
  56   merges the two dictionaries in a new dictionary that is returned to the
  57   caller.
  58
  59   @type dict_a: dict
  60   @param dict_a: the first dictionary
  61   @type dict_b: dict
  62   @param dict_b: the second dictionary
  63   @rtype: dict
  64   @return: a new dictionary containing all the key/value pairs contained in the
  65   two dictionaries.
  66
  67   """
  68   assert not (set(dict_a) & set(dict_b)), ("Duplicate keys found while joining"
  69                                            " %s and %s" % (dict_a, dict_b))
  70   result = dict_a.copy()
  71   result.update(dict_b)
  72   return result
  73
  74
  75 def FindDuplicates(seq):
  76   """Identifies duplicates in a list.
  77
  78   Does not preserve element order.
  79
  80   @type seq: sequence
  81   @param seq: Sequence with source elements
  82   @rtype: list
  83   @return: List of duplicate elements from seq
  84
  85   """
  86   dup = set()
  87   seen = set()
  88
  89   for item in seq:
  90     if item in seen:
  91       dup.add(item)
  92     else:
  93       seen.add(item)
  94
  95   return list(dup)
  96
  97
  98 def _NiceSortTryInt(val):
  99   """Attempts to convert a string to an integer.
 100
 101   """
 102   if val and val.isdigit():
 103     return int(val)
 104   else:
 105     return val
 106
 107
 108 def NiceSortKey(value):
 109   """Extract key for sorting.
 110
 111   """
 112   return [_NiceSortTryInt(grp)
 113           for grp in _SORTER_RE.match(value).groups()]
 114
 115
 116 def NiceSort(values, key=None):
 117   """Sort a list of strings based on digit and non-digit groupings.
 118
 119   Given a list of names C{['a1', 'a10', 'a11', 'a2']} this function
 120   will sort the list in the logical order C{['a1', 'a2', 'a10',
 121   'a11']}.
 122
 123   The sort algorithm breaks each name in groups of either only-digits
 124   or no-digits. Only the first eight such groups are considered, and
 125   after that we just use what's left of the string.
 126
 127   @type values: list
 128   @param values: the names to be sorted
 129   @type key: callable or None
 130   @param key: function of one argument to extract a comparison key from each
 131     list element, must return string
 132   @rtype: list
 133   @return: a copy of the name list sorted with our algorithm
 134
 135   """
 136   if key is None:
 137     keyfunc = NiceSortKey
 138   else:
 139     keyfunc = lambda value: NiceSortKey(key(value))
 140
 141   return sorted(values, key=keyfunc)
 142
 143
 144 def InvertDict(dict_in):
 145   """Inverts the key/value mapping of a dict.
 146
 147   @param dict_in: The dict to invert
 148   @return: the inverted dict
 149
 150   """
 151   return dict(zip(dict_in.values(), dict_in.keys()))
 152
 153
 154 def InsertAtPos(src, pos, other):
 155   """Inserts C{other} at given C{pos} into C{src}.
 156
 157   @note: This function does not modify C{src} in place but returns a new copy
 158
 159   @type src: list
 160   @param src: The source list in which we want insert elements
 161   @type pos: int
 162   @param pos: The position where we want to start insert C{other}
 163   @type other: list
 164   @param other: The other list to insert into C{src}
 165   @return: A copy of C{src} with C{other} inserted at C{pos}
 166
 167   """
 168   new = src[:pos]
 169   new.extend(other)
 170   new.extend(src[pos:])
 171
 172   return new
 173
 174
 175 def SequenceToDict(seq, key=compat.fst):
 176   """Converts a sequence to a dictionary with duplicate detection.
 177
 178   @type seq: sequen
 179   @param seq: Input sequence
 180   @type key: callable
 181   @param key: Function for retrieving dictionary key from sequence element
 182   @rtype: dict
 183
 184   """
 185   keys = map(key, seq)
 186
 187   duplicates = FindDuplicates(keys)
 188   if duplicates:
 189     raise ValueError("Duplicate keys found: %s" % text.CommaJoin(duplicates))
 190
 191   assert len(keys) == len(seq)
 192
 193   return dict(zip(keys, seq))
 194
 195
 196 def _MakeFlatToDict(data):
 197   """Helper function for C{FlatToDict}.
 198
 199   This function is recursively called
 200
 201   @param data: The input data as described in C{FlatToDict}, already splitted
 202   @returns: The so far converted dict
 203
 204   """
 205   if not compat.fst(compat.fst(data)):
 206     assert len(data) == 1, \
 207       "not bottom most element, found %d elements, expected 1" % len(data)
 208     return compat.snd(compat.fst(data))
 209
 210   keyfn = lambda e: compat.fst(e).pop(0)
 211   return dict([(k, _MakeFlatToDict(list(g)))
 212                for (k, g) in itertools.groupby(sorted(data), keyfn)])
 213
 214
 215 def FlatToDict(data, field_sep="/"):
 216   """Converts a flat structure to a fully fledged dict.
 217
 218   It accept a list of tuples in the form::
 219
 220     [
 221       ("foo/bar", {"key1": "data1", "key2": "data2"}),
 222       ("foo/baz", {"key3" :"data3" }),
 223     ]
 224
 225   where the first element is the key separated by C{field_sep}.
 226
 227   This would then return::
 228
 229     {
 230       "foo": {
 231         "bar": {"key1": "data1", "key2": "data2"},
 232         "baz": {"key3" :"data3" },
 233         },
 234     }
 235
 236   @type data: list of tuple
 237   @param data: Input list to convert
 238   @type field_sep: str
 239   @param field_sep: The separator for the first field of the tuple
 240   @returns: A dict based on the input list
 241
 242   """
 243   return _MakeFlatToDict([(keys.split(field_sep), value)
 244                           for (keys, value) in data])
 245
 246
 247 class RunningTimeout(object):
 248   """Class to calculate remaining timeout when doing several operations.
 249
 250   """
 251   __slots__ = [
 252     "_allow_negative",
 253     "_start_time",
 254     "_time_fn",
 255     "_timeout",
 256     ]
 257
 258   def __init__(self, timeout, allow_negative, _time_fn=time.time):
 259     """Initializes this class.
 260
 261     @type timeout: float
 262     @param timeout: Timeout duration
 263     @type allow_negative: bool
 264     @param allow_negative: Whether to return values below zero
 265     @param _time_fn: Time function for unittests
 266
 267     """
 268     object.__init__(self)
 269
 270     if timeout is not None and timeout < 0.0:
 271       raise ValueError("Timeout must not be negative")
 272
 273     self._timeout = timeout
 274     self._allow_negative = allow_negative
 275     self._time_fn = _time_fn
 276
 277     self._start_time = None
 278
 279   def Remaining(self):
 280     """Returns the remaining timeout.
 281
 282     """
 283     if self._timeout is None:
 284       return None
 285
 286     # Get start time on first calculation
 287     if self._start_time is None:
 288       self._start_time = self._time_fn()
 289
 290     # Calculate remaining time
 291     remaining_timeout = self._start_time + self._timeout - self._time_fn()
 292
 293     if not self._allow_negative:
 294       # Ensure timeout is always >= 0
 295       return max(0.0, remaining_timeout)
 296
 297     return remaining_timeout