root / Ganeti / HTools / PeerMap.hs @ 234d8af0
History | View | Annotate | Download (1.7 kB)
1 | e4f08c46 | Iustin Pop | {-| |
---|---|---|---|
2 | e4f08c46 | Iustin Pop | Module abstracting the peer map implementation. |
3 | e4f08c46 | Iustin Pop | |
4 | e4f08c46 | Iustin Pop | This is abstracted separately since the speed of peermap updates can |
5 | e4f08c46 | Iustin Pop | be a significant part of the total runtime, and as such changing the |
6 | e4f08c46 | Iustin Pop | implementation should be easy in case it's needed. |
7 | e4f08c46 | Iustin Pop | |
8 | e4f08c46 | Iustin Pop | -} |
9 | e4f08c46 | Iustin Pop | |
10 | 669d7e3d | Iustin Pop | module Ganeti.HTools.PeerMap |
11 | 669d7e3d | Iustin Pop | ( |
12 | 669d7e3d | Iustin Pop | PeerMap, |
13 | 669d7e3d | Iustin Pop | Key, |
14 | 669d7e3d | Iustin Pop | Elem, |
15 | 669d7e3d | Iustin Pop | empty, |
16 | 669d7e3d | Iustin Pop | create, |
17 | 669d7e3d | Iustin Pop | accumArray, |
18 | 669d7e3d | Iustin Pop | Ganeti.HTools.PeerMap.find, |
19 | 669d7e3d | Iustin Pop | add, |
20 | 669d7e3d | Iustin Pop | remove, |
21 | 669d7e3d | Iustin Pop | maxElem |
22 | 669d7e3d | Iustin Pop | ) where |
23 | e4f08c46 | Iustin Pop | |
24 | e4f08c46 | Iustin Pop | import Data.Maybe (fromMaybe) |
25 | e4f08c46 | Iustin Pop | import Data.List |
26 | e4f08c46 | Iustin Pop | import Data.Function |
27 | e4f08c46 | Iustin Pop | import Data.Ord |
28 | e4f08c46 | Iustin Pop | |
29 | e4f08c46 | Iustin Pop | type Key = Int |
30 | e4f08c46 | Iustin Pop | type Elem = Int |
31 | e4f08c46 | Iustin Pop | type PeerMap = [(Key, Elem)] |
32 | e4f08c46 | Iustin Pop | |
33 | e4f08c46 | Iustin Pop | empty :: PeerMap |
34 | e4f08c46 | Iustin Pop | empty = [] |
35 | e4f08c46 | Iustin Pop | |
36 | e4f08c46 | Iustin Pop | create :: Key -> PeerMap |
37 | e4f08c46 | Iustin Pop | create _ = [] |
38 | e4f08c46 | Iustin Pop | |
39 | e4f08c46 | Iustin Pop | -- | Our reverse-compare function |
40 | e4f08c46 | Iustin Pop | pmCompare :: (Key, Elem) -> (Key, Elem) -> Ordering |
41 | e4f08c46 | Iustin Pop | pmCompare a b = (compare `on` snd) b a |
42 | e4f08c46 | Iustin Pop | |
43 | e4f08c46 | Iustin Pop | addWith :: (Elem -> Elem -> Elem) -> Key -> Elem -> PeerMap -> PeerMap |
44 | e4f08c46 | Iustin Pop | addWith fn k v lst = |
45 | e4f08c46 | Iustin Pop | let r = lookup k lst |
46 | e4f08c46 | Iustin Pop | in |
47 | e4f08c46 | Iustin Pop | case r of |
48 | e4f08c46 | Iustin Pop | Nothing -> insertBy pmCompare (k, v) lst |
49 | e4f08c46 | Iustin Pop | Just o -> insertBy pmCompare (k, fn o v) (remove k lst) |
50 | e4f08c46 | Iustin Pop | |
51 | e4f08c46 | Iustin Pop | accumArray :: (Elem -> Elem -> Elem) -> Elem -> (Key, Key) -> |
52 | e4f08c46 | Iustin Pop | [(Key, Elem)] -> PeerMap |
53 | e4f08c46 | Iustin Pop | accumArray fn _ _ lst = |
54 | e4f08c46 | Iustin Pop | case lst of |
55 | e4f08c46 | Iustin Pop | [] -> empty |
56 | e4f08c46 | Iustin Pop | (k, v):xs -> addWith fn k v $ accumArray fn undefined undefined xs |
57 | e4f08c46 | Iustin Pop | |
58 | e4f08c46 | Iustin Pop | find :: Key -> PeerMap -> Elem |
59 | e4f08c46 | Iustin Pop | find k c = fromMaybe 0 $ lookup k c |
60 | e4f08c46 | Iustin Pop | |
61 | e4f08c46 | Iustin Pop | add :: Key -> Elem -> PeerMap -> PeerMap |
62 | e4f08c46 | Iustin Pop | add k v c = addWith (\_ n -> n) k v c |
63 | e4f08c46 | Iustin Pop | |
64 | e4f08c46 | Iustin Pop | remove :: Key -> PeerMap -> PeerMap |
65 | e4f08c46 | Iustin Pop | remove k c = case c of |
66 | e4f08c46 | Iustin Pop | [] -> [] |
67 | e4f08c46 | Iustin Pop | (x@(x', _)):xs -> if k == x' then xs |
68 | e4f08c46 | Iustin Pop | else x:(remove k xs) |
69 | e4f08c46 | Iustin Pop | |
70 | e4f08c46 | Iustin Pop | to_list :: PeerMap -> [Elem] |
71 | e4f08c46 | Iustin Pop | to_list c = snd $ unzip c |
72 | e4f08c46 | Iustin Pop | |
73 | e4f08c46 | Iustin Pop | maxElem :: PeerMap -> Elem |
74 | e4f08c46 | Iustin Pop | maxElem c = case c of |
75 | e4f08c46 | Iustin Pop | [] -> 0 |
76 | e4f08c46 | Iustin Pop | (_, v):_ -> v |