Package ganeti :: Package utils :: Module algo
[hide private]
[frames] | no frames]

Source Code for Module ganeti.utils.algo

  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 * r"(\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(str(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
298