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