code.grnet.gr Git - ganeti-local/blob - htools/Ganeti/HTools/PeerMap.hs

   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