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