## root / Ganeti / HTools / PeerMap.hs @ 608efcce

History | View | Annotate | Download (1.7 kB)

1 |
{-| |
---|---|

2 |
Module abstracting the peer map implementation. |

3 | |

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

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

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

7 | |

8 |
-} |

9 | |

10 |
module Ganeti.HTools.PeerMap |

11 |
( |

12 |
PeerMap, |

13 |
Key, |

14 |
Elem, |

15 |
empty, |

16 |
create, |

17 |
accumArray, |

18 |
Ganeti.HTools.PeerMap.find, |

19 |
add, |

20 |
remove, |

21 |
maxElem |

22 |
) where |

23 | |

24 |
import Data.Maybe (fromMaybe) |

25 |
import Data.List |

26 |
import Data.Function |

27 |
import Data.Ord |

28 | |

29 |
import Ganeti.HTools.Types |

30 | |

31 |
type Key = Ndx |

32 |
type Elem = Int |

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

34 | |

35 |
empty :: PeerMap |

36 |
empty = [] |

37 | |

38 |
create :: Key -> PeerMap |

39 |
create _ = [] |

40 | |

41 |
-- | Our reverse-compare function |

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

43 |
pmCompare a b = (compare `on` snd) b a |

44 | |

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

46 |
addWith fn k v lst = |

47 |
let r = lookup k lst |

48 |
in |

49 |
case r of |

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

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

52 | |

53 |
accumArray :: (Elem -> Elem -> Elem) -> Elem -> (Key, Key) -> |

54 |
[(Key, Elem)] -> PeerMap |

55 |
accumArray fn _ _ lst = |

56 |
case lst of |

57 |
[] -> empty |

58 |
(k, v):xs -> addWith fn k v $ accumArray fn undefined undefined xs |

59 | |

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

61 |
find k c = fromMaybe 0 $ lookup k c |

62 | |

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

64 |
add k v c = addWith (\_ n -> n) k v c |

65 | |

66 |
remove :: Key -> PeerMap -> PeerMap |

67 |
remove k c = case c of |

68 |
[] -> [] |

69 |
(x@(x', _)):xs -> if k == x' then xs |

70 |
else x:(remove k xs) |

71 | |

72 |
to_list :: PeerMap -> [Elem] |

73 |
to_list c = snd $ unzip c |

74 | |

75 |
maxElem :: PeerMap -> Elem |

76 |
maxElem c = case c of |

77 |
[] -> 0 |

78 |
(_, v):_ -> v |