Statistics
| Branch: | Tag: | Revision:

root / src / Ganeti / HTools / PeerMap.hs @ 7ec2f76b

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