## root / Ganeti / HTools / PeerMap.hs @ 5aa48dbe

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 |
type Key = Int |

30 |
type Elem = Int |

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

32 | |

33 |
empty :: PeerMap |

34 |
empty = [] |

35 | |

36 |
create :: Key -> PeerMap |

37 |
create _ = [] |

38 | |

39 |
-- | Our reverse-compare function |

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

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

42 | |

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

44 |
addWith fn k v lst = |

45 |
let r = lookup k lst |

46 |
in |

47 |
case r of |

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

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

50 | |

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

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

53 |
accumArray fn _ _ lst = |

54 |
case lst of |

55 |
[] -> empty |

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

57 | |

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

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

60 | |

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

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

63 | |

64 |
remove :: Key -> PeerMap -> PeerMap |

65 |
remove k c = case c of |

66 |
[] -> [] |

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

68 |
else x:(remove k xs) |

69 | |

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

71 |
to_list c = snd $ unzip c |

72 | |

73 |
maxElem :: PeerMap -> Elem |

74 |
maxElem c = case c of |

75 |
[] -> 0 |

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