## root / htools / Ganeti / HTools / PeerMap.hs @ ebf38064

History | View | Annotate | Download (2.9 kB)

1 |
{-| Module abstracting the peer map implementation. |
---|---|

2 | |

3 |
This is abstracted separately since the speed of peermap updates can |

4 |
be a significant part of the total runtime, and as such changing the |

5 |
implementation should be easy in case it's needed. |

6 | |

7 |
-} |

8 | |

9 |
{- |

10 | |

11 |
Copyright (C) 2009, 2011 Google Inc. |

12 | |

13 |
This program is free software; you can redistribute it and/or modify |

14 |
it under the terms of the GNU General Public License as published by |

15 |
the Free Software Foundation; either version 2 of the License, or |

16 |
(at your option) any later version. |

17 | |

18 |
This program is distributed in the hope that it will be useful, but |

19 |
WITHOUT ANY WARRANTY; without even the implied warranty of |

20 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |

21 |
General Public License for more details. |

22 | |

23 |
You should have received a copy of the GNU General Public License |

24 |
along with this program; if not, write to the Free Software |

25 |
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |

26 |
02110-1301, USA. |

27 | |

28 |
-} |

29 | |

30 |
module Ganeti.HTools.PeerMap |

31 |
( PeerMap |

32 |
, Key |

33 |
, Elem |

34 |
, empty |

35 |
, accumArray |

36 |
, Ganeti.HTools.PeerMap.find |

37 |
, add |

38 |
, remove |

39 |
, maxElem |

40 |
) where |

41 | |

42 |
import Data.Maybe (fromMaybe) |

43 |
import Data.List |

44 |
import Data.Ord (comparing) |

45 | |

46 |
import Ganeti.HTools.Types |

47 | |

48 |
-- * Type definitions |

49 | |

50 |
-- | Our key type. |

51 |
type Key = Ndx |

52 | |

53 |
-- | Our element type. |

54 | |

55 |
type Elem = Int |

56 | |

57 |
-- | The definition of a peer map. |

58 |
type PeerMap = [(Key, Elem)] |

59 | |

60 |
-- * Initialization functions |

61 | |

62 |
-- | Create a new empty map. |

63 |
empty :: PeerMap |

64 |
empty = [] |

65 | |

66 |
-- | Our reverse-compare function. |

67 |
pmCompare :: (Key, Elem) -> (Key, Elem) -> Ordering |

68 |
pmCompare a b = comparing snd b a |

69 | |

70 |
-- | Add or update (via a custom function) an element. |

71 |
addWith :: (Elem -> Elem -> Elem) -> Key -> Elem -> PeerMap -> PeerMap |

72 |
addWith fn k v lst = |

73 |
case lookup k lst of |

74 |
Nothing -> insertBy pmCompare (k, v) lst |

75 |
Just o -> insertBy pmCompare (k, fn o v) (remove k lst) |

76 | |

77 |
-- | Create a PeerMap from an association list, with possible duplicates. |

78 |
accumArray :: (Elem -> Elem -> Elem) -- ^ function used to merge the elements |

79 |
-> [(Key, Elem)] -- ^ source data |

80 |
-> PeerMap -- ^ results |

81 |
accumArray _ [] = empty |

82 |
accumArray fn ((k, v):xs) = addWith fn k v $ accumArray fn xs |

83 | |

84 |
-- * Basic operations |

85 | |

86 |
-- | Returns either the value for a key or zero if not found. |

87 |
find :: Key -> PeerMap -> Elem |

88 |
find k = fromMaybe 0 . lookup k |

89 | |

90 |
-- | Add an element to a peermap, overwriting the previous value. |

91 |
add :: Key -> Elem -> PeerMap -> PeerMap |

92 |
add = addWith (flip const) |

93 | |

94 |
-- | Remove an element from a peermap. |

95 |
remove :: Key -> PeerMap -> PeerMap |

96 |
remove _ [] = [] |

97 |
remove k ((x@(x', _)):xs) = if k == x' |

98 |
then xs |

99 |
else x:remove k xs |

100 | |

101 |
-- | Find the maximum element. |

102 |
-- |

103 |
-- Since this is a sorted list, we just get the value at the head of |

104 |
-- the list, or zero for a null list |

105 |
maxElem :: PeerMap -> Elem |

106 |
maxElem (x:_) = snd x |

107 |
maxElem _ = 0 |