root / lib / utils / algo.py @ 31d3b918
History | View | Annotate | Download (7.8 kB)
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 |
#pylint: disable=W0142
|
99 |
# (use of *-magic in argument list)
|
100 |
def GetRepeatedKeys(*dicts): |
101 |
"""Return the set of keys defined multiple times in the given dicts.
|
102 |
|
103 |
>>> GetRepeatedKeys({"foo": 1, "bar": 2},
|
104 |
... {"foo": 5, "baz": 7}
|
105 |
... )
|
106 |
set("foo")
|
107 |
|
108 |
@type dicts: dict
|
109 |
@param dicts: The dictionaries to check for duplicate keys.
|
110 |
@rtype: set
|
111 |
@return: Keys used more than once across all dicts
|
112 |
|
113 |
"""
|
114 |
if len(dicts) < 2: |
115 |
return set() |
116 |
|
117 |
keys = [] |
118 |
for dictionary in dicts: |
119 |
keys.extend(dictionary) |
120 |
|
121 |
return set(FindDuplicates(keys)) |
122 |
|
123 |
|
124 |
def _NiceSortTryInt(val): |
125 |
"""Attempts to convert a string to an integer.
|
126 |
|
127 |
"""
|
128 |
if val and val.isdigit(): |
129 |
return int(val) |
130 |
else:
|
131 |
return val
|
132 |
|
133 |
|
134 |
def NiceSortKey(value): |
135 |
"""Extract key for sorting.
|
136 |
|
137 |
"""
|
138 |
return [_NiceSortTryInt(grp)
|
139 |
for grp in _SORTER_RE.match(value).groups()] |
140 |
|
141 |
|
142 |
def NiceSort(values, key=None): |
143 |
"""Sort a list of strings based on digit and non-digit groupings.
|
144 |
|
145 |
Given a list of names C{['a1', 'a10', 'a11', 'a2']} this function
|
146 |
will sort the list in the logical order C{['a1', 'a2', 'a10',
|
147 |
'a11']}.
|
148 |
|
149 |
The sort algorithm breaks each name in groups of either only-digits
|
150 |
or no-digits. Only the first eight such groups are considered, and
|
151 |
after that we just use what's left of the string.
|
152 |
|
153 |
@type values: list
|
154 |
@param values: the names to be sorted
|
155 |
@type key: callable or None
|
156 |
@param key: function of one argument to extract a comparison key from each
|
157 |
list element, must return string
|
158 |
@rtype: list
|
159 |
@return: a copy of the name list sorted with our algorithm
|
160 |
|
161 |
"""
|
162 |
if key is None: |
163 |
keyfunc = NiceSortKey |
164 |
else:
|
165 |
keyfunc = lambda value: NiceSortKey(key(value))
|
166 |
|
167 |
return sorted(values, key=keyfunc) |
168 |
|
169 |
|
170 |
def InvertDict(dict_in): |
171 |
"""Inverts the key/value mapping of a dict.
|
172 |
|
173 |
@param dict_in: The dict to invert
|
174 |
@return: the inverted dict
|
175 |
|
176 |
"""
|
177 |
return dict(zip(dict_in.values(), dict_in.keys())) |
178 |
|
179 |
|
180 |
def InsertAtPos(src, pos, other): |
181 |
"""Inserts C{other} at given C{pos} into C{src}.
|
182 |
|
183 |
@note: This function does not modify C{src} in place but returns a new copy
|
184 |
|
185 |
@type src: list
|
186 |
@param src: The source list in which we want insert elements
|
187 |
@type pos: int
|
188 |
@param pos: The position where we want to start insert C{other}
|
189 |
@type other: list
|
190 |
@param other: The other list to insert into C{src}
|
191 |
@return: A copy of C{src} with C{other} inserted at C{pos}
|
192 |
|
193 |
"""
|
194 |
new = src[:pos] |
195 |
new.extend(other) |
196 |
new.extend(src[pos:]) |
197 |
|
198 |
return new
|
199 |
|
200 |
|
201 |
def SequenceToDict(seq, key=compat.fst): |
202 |
"""Converts a sequence to a dictionary with duplicate detection.
|
203 |
|
204 |
@type seq: sequen
|
205 |
@param seq: Input sequence
|
206 |
@type key: callable
|
207 |
@param key: Function for retrieving dictionary key from sequence element
|
208 |
@rtype: dict
|
209 |
|
210 |
"""
|
211 |
keys = map(key, seq)
|
212 |
|
213 |
duplicates = FindDuplicates(keys) |
214 |
if duplicates:
|
215 |
raise ValueError("Duplicate keys found: %s" % text.CommaJoin(duplicates)) |
216 |
|
217 |
assert len(keys) == len(seq) |
218 |
|
219 |
return dict(zip(keys, seq)) |
220 |
|
221 |
|
222 |
def _MakeFlatToDict(data): |
223 |
"""Helper function for C{FlatToDict}.
|
224 |
|
225 |
This function is recursively called
|
226 |
|
227 |
@param data: The input data as described in C{FlatToDict}, already splitted
|
228 |
@returns: The so far converted dict
|
229 |
|
230 |
"""
|
231 |
if not compat.fst(compat.fst(data)): |
232 |
assert len(data) == 1, \ |
233 |
"not bottom most element, found %d elements, expected 1" % len(data) |
234 |
return compat.snd(compat.fst(data))
|
235 |
|
236 |
keyfn = lambda e: compat.fst(e).pop(0) |
237 |
return dict([(k, _MakeFlatToDict(list(g))) |
238 |
for (k, g) in itertools.groupby(sorted(data), keyfn)]) |
239 |
|
240 |
|
241 |
def FlatToDict(data, field_sep="/"): |
242 |
"""Converts a flat structure to a fully fledged dict.
|
243 |
|
244 |
It accept a list of tuples in the form::
|
245 |
|
246 |
[
|
247 |
("foo/bar", {"key1": "data1", "key2": "data2"}),
|
248 |
("foo/baz", {"key3" :"data3" }),
|
249 |
]
|
250 |
|
251 |
where the first element is the key separated by C{field_sep}.
|
252 |
|
253 |
This would then return::
|
254 |
|
255 |
{
|
256 |
"foo": {
|
257 |
"bar": {"key1": "data1", "key2": "data2"},
|
258 |
"baz": {"key3" :"data3" },
|
259 |
},
|
260 |
}
|
261 |
|
262 |
@type data: list of tuple
|
263 |
@param data: Input list to convert
|
264 |
@type field_sep: str
|
265 |
@param field_sep: The separator for the first field of the tuple
|
266 |
@returns: A dict based on the input list
|
267 |
|
268 |
"""
|
269 |
return _MakeFlatToDict([(keys.split(field_sep), value)
|
270 |
for (keys, value) in data]) |
271 |
|
272 |
|
273 |
class RunningTimeout(object): |
274 |
"""Class to calculate remaining timeout when doing several operations.
|
275 |
|
276 |
"""
|
277 |
__slots__ = [ |
278 |
"_allow_negative",
|
279 |
"_start_time",
|
280 |
"_time_fn",
|
281 |
"_timeout",
|
282 |
] |
283 |
|
284 |
def __init__(self, timeout, allow_negative, _time_fn=time.time): |
285 |
"""Initializes this class.
|
286 |
|
287 |
@type timeout: float
|
288 |
@param timeout: Timeout duration
|
289 |
@type allow_negative: bool
|
290 |
@param allow_negative: Whether to return values below zero
|
291 |
@param _time_fn: Time function for unittests
|
292 |
|
293 |
"""
|
294 |
object.__init__(self) |
295 |
|
296 |
if timeout is not None and timeout < 0.0: |
297 |
raise ValueError("Timeout must not be negative") |
298 |
|
299 |
self._timeout = timeout
|
300 |
self._allow_negative = allow_negative
|
301 |
self._time_fn = _time_fn
|
302 |
|
303 |
self._start_time = None |
304 |
|
305 |
def Remaining(self): |
306 |
"""Returns the remaining timeout.
|
307 |
|
308 |
"""
|
309 |
if self._timeout is None: |
310 |
return None |
311 |
|
312 |
# Get start time on first calculation
|
313 |
if self._start_time is None: |
314 |
self._start_time = self._time_fn() |
315 |
|
316 |
# Calculate remaining time
|
317 |
remaining_timeout = self._start_time + self._timeout - self._time_fn() |
318 |
|
319 |
if not self._allow_negative: |
320 |
# Ensure timeout is always >= 0
|
321 |
return max(0.0, remaining_timeout) |
322 |
|
323 |
return remaining_timeout
|