root / src / Ganeti / HTools / PeerMap.hs @ 40960882
History | View | Annotate | Download (2.9 kB)
1 |
{-| Module abstracting the peer map implementation. |
---|---|
2 |
|
3 |
This is abstracted separately since the speed of peermap updates can |
4 |
be a significant part of the total runtime, and as such changing the |
5 |
implementation should be easy in case it's needed. |
6 |
|
7 |
-} |
8 |
|
9 |
{- |
10 |
|
11 |
Copyright (C) 2009, 2011 Google Inc. |
12 |
|
13 |
This program is free software; you can redistribute it and/or modify |
14 |
it under the terms of the GNU General Public License as published by |
15 |
the Free Software Foundation; either version 2 of the License, or |
16 |
(at your option) any later version. |
17 |
|
18 |
This program is distributed in the hope that it will be useful, but |
19 |
WITHOUT ANY WARRANTY; without even the implied warranty of |
20 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
21 |
General Public License for more details. |
22 |
|
23 |
You should have received a copy of the GNU General Public License |
24 |
along with this program; if not, write to the Free Software |
25 |
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
26 |
02110-1301, USA. |
27 |
|
28 |
-} |
29 |
|
30 |
module Ganeti.HTools.PeerMap |
31 |
( PeerMap |
32 |
, Key |
33 |
, Elem |
34 |
, empty |
35 |
, accumArray |
36 |
, Ganeti.HTools.PeerMap.find |
37 |
, add |
38 |
, remove |
39 |
, maxElem |
40 |
) where |
41 |
|
42 |
import Data.Maybe (fromMaybe) |
43 |
import Data.List |
44 |
import Data.Ord (comparing) |
45 |
|
46 |
import Ganeti.HTools.Types |
47 |
|
48 |
-- * Type definitions |
49 |
|
50 |
-- | Our key type. |
51 |
type Key = Ndx |
52 |
|
53 |
-- | Our element type. |
54 |
|
55 |
type Elem = Int |
56 |
|
57 |
-- | The definition of a peer map. |
58 |
type PeerMap = [(Key, Elem)] |
59 |
|
60 |
-- * Initialization functions |
61 |
|
62 |
-- | Create a new empty map. |
63 |
empty :: PeerMap |
64 |
empty = [] |
65 |
|
66 |
-- | Our reverse-compare function. |
67 |
pmCompare :: (Key, Elem) -> (Key, Elem) -> Ordering |
68 |
pmCompare a b = comparing snd b a |
69 |
|
70 |
-- | Add or update (via a custom function) an element. |
71 |
addWith :: (Elem -> Elem -> Elem) -> Key -> Elem -> PeerMap -> PeerMap |
72 |
addWith fn k v lst = |
73 |
case lookup k lst of |
74 |
Nothing -> insertBy pmCompare (k, v) lst |
75 |
Just o -> insertBy pmCompare (k, fn o v) (remove k lst) |
76 |
|
77 |
-- | Create a PeerMap from an association list, with possible duplicates. |
78 |
accumArray :: (Elem -> Elem -> Elem) -- ^ function used to merge the elements |
79 |
-> [(Key, Elem)] -- ^ source data |
80 |
-> PeerMap -- ^ results |
81 |
accumArray _ [] = empty |
82 |
accumArray fn ((k, v):xs) = addWith fn k v $ accumArray fn xs |
83 |
|
84 |
-- * Basic operations |
85 |
|
86 |
-- | Returns either the value for a key or zero if not found. |
87 |
find :: Key -> PeerMap -> Elem |
88 |
find k = fromMaybe 0 . lookup k |
89 |
|
90 |
-- | Add an element to a peermap, overwriting the previous value. |
91 |
add :: Key -> Elem -> PeerMap -> PeerMap |
92 |
add = addWith (flip const) |
93 |
|
94 |
-- | Remove an element from a peermap. |
95 |
remove :: Key -> PeerMap -> PeerMap |
96 |
remove _ [] = [] |
97 |
remove k ((x@(x', _)):xs) = if k == x' |
98 |
then xs |
99 |
else x:remove k xs |
100 |
|
101 |
-- | Find the maximum element. |
102 |
-- |
103 |
-- Since this is a sorted list, we just get the value at the head of |
104 |
-- the list, or zero for a null list |
105 |
maxElem :: PeerMap -> Elem |
106 |
maxElem (x:_) = snd x |
107 |
maxElem _ = 0 |