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   
 28   
 29  _SORTER_GROUPS = 8 
 30  _SORTER_RE = re.compile("^%s(.*)$" % (_SORTER_GROUPS * "(\D+|\d+)?")) 
 31  _SORTER_DIGIT = re.compile("^\d+$") 
 32   
 33   
 34 -def UniqueSequence(seq): 
 35    """Returns a list with unique elements. 
 36   
 37    Element order is preserved. 
 38   
 39    @type seq: sequence 
 40    @param seq: the sequence with the source elements 
 41    @rtype: list 
 42    @return: list of unique elements from seq 
 43   
 44    """ 
 45    seen = set() 
 46    return [i for i in seq if i not in seen and not seen.add(i)] 
 47   
 48   
 49 -def FindDuplicates(seq): 
 50    """Identifies duplicates in a list. 
 51   
 52    Does not preserve element order. 
 53   
 54    @type seq: sequence 
 55    @param seq: Sequence with source elements 
 56    @rtype: list 
 57    @return: List of duplicate elements from seq 
 58   
 59    """ 
 60    dup = set() 
 61    seen = set() 
 62   
 63    for item in seq: 
 64      if item in seen: 
 65        dup.add(item) 
 66      else: 
 67        seen.add(item) 
 68   
 69    return list(dup) 
 70   
 71   
 72 -def _NiceSortTryInt(val): 
 73    """Attempts to convert a string to an integer. 
 74   
 75    """ 
 76    if val and _SORTER_DIGIT.match(val): 
 77      return int(val) 
 78    else: 
 79      return val 
 80   
 81   
 82 -def NiceSortKey(value): 
 83    """Extract key for sorting. 
 84   
 85    """ 
 86    return [_NiceSortTryInt(grp) 
 87            for grp in _SORTER_RE.match(value).groups()] 
 88   
 89   
 90 -def NiceSort(values, key=None): 
 91    """Sort a list of strings based on digit and non-digit groupings. 
 92   
 93    Given a list of names C{['a1', 'a10', 'a11', 'a2']} this function 
 94    will sort the list in the logical order C{['a1', 'a2', 'a10', 
 95    'a11']}. 
 96   
 97    The sort algorithm breaks each name in groups of either only-digits 
 98    or no-digits. Only the first eight such groups are considered, and 
 99    after that we just use what's left of the string. 
100   
101    @type values: list 
102    @param values: the names to be sorted 
103    @type key: callable or None 
104    @param key: function of one argument to extract a comparison key from each 
105      list element, must return string 
106    @rtype: list 
107    @return: a copy of the name list sorted with our algorithm 
108   
109    """ 
110    if key is None: 
111      keyfunc = NiceSortKey 
112    else: 
113      keyfunc = lambda value: NiceSortKey(key(value)) 
114   
115    return sorted(values, key=keyfunc) 
116   
117   
118 -def InvertDict(dict_in): 
119    """Inverts the key/value mapping of a dict. 
120   
121    @param dict_in: The dict to invert 
122    @return: the inverted dict 
123   
124    """ 
125    return dict(zip(dict_in.values(), dict_in.keys())) 
126   
127   
128 -class RunningTimeout(object): 
129    """Class to calculate remaining timeout when doing several operations. 
130   
131    """ 
132    __slots__ = [ 
133      "_allow_negative", 
134      "_start_time", 
135      "_time_fn", 
136      "_timeout", 
137      ] 
138   
139 -  def __init__(self, timeout, allow_negative, _time_fn=time.time): 
140      """Initializes this class. 
141   
142      @type timeout: float 
143      @param timeout: Timeout duration 
144      @type allow_negative: bool 
145      @param allow_negative: Whether to return values below zero 
146      @param _time_fn: Time function for unittests 
147   
148      """ 
149      object.__init__(self) 
150   
151      if timeout is not None and timeout < 0.0: 
152        raise ValueError("Timeout must not be negative") 
153   
154      self._timeout = timeout 
155      self._allow_negative = allow_negative 
156      self._time_fn = _time_fn 
157   
158      self._start_time = None 
159   
160 -  def Remaining(self): 
161      """Returns the remaining timeout. 
162   
163      """ 
164      if self._timeout is None: 
165        return None 
166   
167      # Get start time on first calculation 
168      if self._start_time is None: 
169        self._start_time = self._time_fn() 
170   
171      # Calculate remaining time 
172      remaining_timeout = self._start_time + self._timeout - self._time_fn() 
173   
174      if not self._allow_negative: 
175        # Ensure timeout is always >= 0 
176        return max(0.0, remaining_timeout) 
177   
178      return remaining_timeout 
179