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