1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
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
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
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
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
109 """Extract key for sorting.
110
111 """
112 return [_NiceSortTryInt(grp)
113 for grp in _SORTER_RE.match(value).groups()]
114
115
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
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
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
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
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
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
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
287 if self._start_time is None:
288 self._start_time = self._time_fn()
289
290
291 remaining_timeout = self._start_time + self._timeout - self._time_fn()
292
293 if not self._allow_negative:
294
295 return max(0.0, remaining_timeout)
296
297 return remaining_timeout
298