root / Ganeti / HTools / PeerMap.hs @ 71e13e48
History | View | Annotate | Download (1.9 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 |
( PeerMap |
12 |
, Key |
13 |
, Elem |
14 |
, empty |
15 |
, accumArray |
16 |
, Ganeti.HTools.PeerMap.find |
17 |
, add |
18 |
, remove |
19 |
, maxElem |
20 |
) where |
21 |
|
22 |
import Data.Maybe (fromMaybe) |
23 |
import Data.List |
24 |
import Data.Function |
25 |
import Data.Ord |
26 |
|
27 |
import Ganeti.HTools.Types |
28 |
|
29 |
type Key = Ndx |
30 |
type Elem = Int |
31 |
type PeerMap = [(Key, Elem)] |
32 |
|
33 |
-- | Create a new empty map |
34 |
empty :: PeerMap |
35 |
empty = [] |
36 |
|
37 |
-- | Our reverse-compare function |
38 |
pmCompare :: (Key, Elem) -> (Key, Elem) -> Ordering |
39 |
pmCompare a b = (compare `on` snd) b a |
40 |
|
41 |
-- | Add or update (via a custom function) an element |
42 |
addWith :: (Elem -> Elem -> Elem) -> Key -> Elem -> PeerMap -> PeerMap |
43 |
addWith fn k v lst = |
44 |
let r = lookup k lst |
45 |
in |
46 |
case r of |
47 |
Nothing -> insertBy pmCompare (k, v) lst |
48 |
Just o -> insertBy pmCompare (k, fn o v) (remove k lst) |
49 |
|
50 |
-- | Create a PeerMap from an association list, with possible duplicates |
51 |
accumArray :: (Elem -> Elem -> Elem) -- ^ function used to merge the elements |
52 |
-> [(Key, Elem)] -- ^ source data |
53 |
-> PeerMap -- ^ results |
54 |
accumArray fn lst = |
55 |
case lst of |
56 |
[] -> empty |
57 |
(k, v):xs -> addWith fn k v $ accumArray fn xs |
58 |
|
59 |
find :: Key -> PeerMap -> Elem |
60 |
find k c = fromMaybe 0 $ lookup k c |
61 |
|
62 |
add :: Key -> Elem -> PeerMap -> PeerMap |
63 |
add k v c = addWith (flip const) k v c |
64 |
|
65 |
remove :: Key -> PeerMap -> PeerMap |
66 |
remove k c = case c of |
67 |
[] -> [] |
68 |
(x@(x', _)):xs -> if k == x' then xs |
69 |
else x:(remove k xs) |
70 |
|
71 |
-- | Find the maximum element. Since this is a sorted list, we just |
72 |
-- get the first one |
73 |
maxElem :: PeerMap -> Elem |
74 |
maxElem c = if null c then 0 else snd . head $ c |