1 {-| Module abstracting the peer map implementation.
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.
11 Copyright (C) 2009, 2011 Google Inc.
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.
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.
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
30 module Ganeti.HTools.PeerMap
36 , Ganeti.HTools.PeerMap.find
42 import Data.Maybe (fromMaybe)
44 import Data.Ord (comparing)
46 import Ganeti.HTools.Types
53 -- | Our element type.
57 -- | The definition of a peer map.
58 type PeerMap = [(Key, Elem)]
60 -- * Initialization functions
62 -- | Create a new empty map.
66 -- | Our reverse-compare function.
67 pmCompare :: (Key, Elem) -> (Key, Elem) -> Ordering
68 pmCompare a b = comparing snd b a
70 -- | Add or update (via a custom function) an element.
71 addWith :: (Elem -> Elem -> Elem) -> Key -> Elem -> PeerMap -> PeerMap
74 Nothing -> insertBy pmCompare (k, v) lst
75 Just o -> insertBy pmCompare (k, fn o v) (remove k lst)
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
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
90 -- | Add an element to a peermap, overwriting the previous value.
91 add :: Key -> Elem -> PeerMap -> PeerMap
92 add = addWith (flip const)
94 -- | Remove an element from a peermap.
95 remove :: Key -> PeerMap -> PeerMap
97 remove k ((x@(x', _)):xs) = if k == x'
101 -- | Find the maximum element.
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