Statistics
| Branch: | Tag: | Revision:

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

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