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

   1 {-|
   2   Module abstracting the peer map implementation.
   3
   4 This is abstracted separately since the speed of peermap updates can
   5 be a significant part of the total runtime, and as such changing the
   6 implementation should be easy in case it's needed.
   7
   8 -}
   9
  10 module Ganeti.HTools.PeerMap
  11     (
  12      PeerMap,
  13      Key,
  14      Elem,
  15      empty,
  16      create,
  17      accumArray,
  18      Ganeti.HTools.PeerMap.find,
  19      add,
  20      remove,
  21      maxElem
  22     ) where
  23
  24 import Data.Maybe (fromMaybe)
  25 import Data.List
  26 import Data.Function
  27 import Data.Ord
  28
  29 type Key = Int
  30 type Elem = Int
  31 type PeerMap = [(Key, Elem)]
  32
  33 empty :: PeerMap
  34 empty = []
  35
  36 create :: Key -> PeerMap
  37 create _ = []
  38
  39 -- | Our reverse-compare function
  40 pmCompare :: (Key, Elem) -> (Key, Elem) -> Ordering
  41 pmCompare a b = (compare `on` snd) b a
  42
  43 addWith :: (Elem -> Elem -> Elem) -> Key -> Elem -> PeerMap -> PeerMap
  44 addWith fn k v lst =
  45     let r = lookup k lst
  46     in
  47       case r of
  48         Nothing -> insertBy pmCompare (k, v) lst
  49         Just o -> insertBy pmCompare (k, fn o v) (remove k lst)
  50
  51 accumArray :: (Elem -> Elem -> Elem) -> Elem -> (Key, Key) ->
  52               [(Key, Elem)] -> PeerMap
  53 accumArray fn _ _ lst =
  54     case lst of
  55       [] -> empty
  56       (k, v):xs -> addWith fn k v $ accumArray fn undefined undefined xs
  57
  58 find :: Key -> PeerMap -> Elem
  59 find k c = fromMaybe 0 $ lookup k c
  60
  61 add :: Key -> Elem -> PeerMap -> PeerMap
  62 add k v c = addWith (\_ n -> n) k v c
  63
  64 remove :: Key -> PeerMap -> PeerMap
  65 remove k c = case c of
  66                [] -> []
  67                (x@(x', _)):xs -> if k == x' then xs
  68                             else x:(remove k xs)
  69
  70 to_list :: PeerMap -> [Elem]
  71 to_list c = snd $ unzip c
  72
  73 maxElem :: PeerMap -> Elem
  74 maxElem c = case c of
  75               [] -> 0
  76               (_, v):_ -> v