Statistics
| Branch: | Tag: | Revision:

root / src / Ganeti / HTools / PeerMap.hs @ 6d3d13ab

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