root / Ganeti / HTools / PeerMap.hs @ 669d7e3d
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 |