\section{Client Lists}
\begin{code}
{-# LANGUAGE NamedFieldPuns #-}
{-# LANGUAGE Safe #-}
module Network.Tox.DHT.ClientList where
import Control.Applicative ((<$>), (<*>))
import Control.Monad (join)
import Data.List (sort)
import Data.Map (Map)
import qualified Data.Map as Map
import Test.QuickCheck.Arbitrary (Arbitrary, arbitrary,
arbitrarySizedNatural)
import Test.QuickCheck.Gen (Gen)
import qualified Test.QuickCheck.Gen as Gen
import Network.Tox.Crypto.Key (PublicKey)
import Network.Tox.DHT.ClientNode (ClientNode)
import qualified Network.Tox.DHT.ClientNode as ClientNode
import Network.Tox.DHT.Distance (Distance)
import qualified Network.Tox.DHT.Distance as Distance
import Network.Tox.NodeInfo.NodeInfo (NodeInfo)
import qualified Network.Tox.NodeInfo.NodeInfo as NodeInfo
import Network.Tox.Time (Timestamp)
\end{code}
A Client List of \textit{maximum size} \texttt{k} with a given public key as
\textit{base key} is an ordered set of at most \texttt{k} nodes close to the
base key. The elements are sorted by \href{#distance}{distance} from the base
key. Thus, the first (smallest) element of the set is the closest one to the
base key in that set, the last (greatest) element is the furthest away. The
maximum size and base key are constant throughout the lifetime of a Client
List.
\begin{code}
data ClientList = ClientList
{ baseKey :: PublicKey
, maxSize :: Int
, nodes :: ClientNodes
}
deriving (Eq, Read, Show)
type ClientNodes = Map Distance ClientNode
nodeInfos :: ClientList -> [NodeInfo]
nodeInfos = map ClientNode.nodeInfo . Map.elems . nodes
empty :: PublicKey -> Int -> ClientList
empty publicKey size = ClientList
{ baseKey = publicKey
, maxSize = size
, nodes = Map.empty
}
isEmpty :: ClientList -> Bool
isEmpty = Map.null . nodes
updateClientNodes :: (ClientNodes -> ClientNodes) -> ClientList -> ClientList
updateClientNodes f clientList@ClientList{ nodes } =
clientList{nodes = f nodes}
lookup :: PublicKey -> ClientList -> Maybe NodeInfo
lookup publicKey _cl@ClientList{ baseKey, nodes } =
ClientNode.nodeInfo <$> Distance.xorDistance publicKey baseKey `Map.lookup` nodes
\end{code}
A Client List is \textit{full} when the number of nodes it contains is the
maximum size of the list.
A node is \textit{viable} for entry if the Client List is not \textit{full} or the
node's public key has a lower distance from the base key than the current entry
with the greatest distance.
If a node is \textit{viable} and the Client List is \textit{full}, the entry
with the greatest distance from the base key is removed to keep the size below
the maximum configured size.
Adding a node whose key already exists will result in an update of the Node
Info in the Client List. Removing a node for which no Node Info exists in the
Client List has no effect. Thus, removing a node twice is permitted and has the
same effect as removing it once.
\begin{code}
full :: ClientList -> Bool
full ClientList{ nodes, maxSize } =
Map.size nodes >= maxSize
addNode :: Timestamp -> NodeInfo -> ClientList -> ClientList
addNode time nodeInfo clientList@ClientList{ baseKey, maxSize } =
(`updateClientNodes` clientList) $
mapTake maxSize
. Map.insert
(Distance.xorDistance (NodeInfo.publicKey nodeInfo) baseKey)
(ClientNode.newNode time nodeInfo)
where
mapTake :: Int -> Map k a -> Map k a
mapTake n = Map.fromDistinctAscList . take n . Map.toAscList
removeNode :: PublicKey -> ClientList -> ClientList
removeNode publicKey clientList =
(`updateClientNodes` clientList) .
Map.delete . Distance.xorDistance publicKey $ baseKey clientList
viable :: NodeInfo -> ClientList -> Bool
viable nodeInfo ClientList{ baseKey, maxSize, nodes } =
let key = Distance.xorDistance (NodeInfo.publicKey nodeInfo) baseKey
in (key `elem`) . take maxSize . sort $ key : Map.keys nodes
\end{code}
The iteration order of a Client List is in order of distance from the base
key. I.e. the first node seen in iteration is the closest, and the last node
is the furthest away in terms of the distance metric.
\begin{code}
foldNodes :: (a -> NodeInfo -> a) -> a -> ClientList -> a
foldNodes f x = foldl f x . nodeInfos
closeNodes :: PublicKey -> ClientList -> [ (Distance, NodeInfo) ]
closeNodes publicKey ClientList{ baseKey, nodes } =
Map.toAscList . fmap ClientNode.nodeInfo $
Map.mapKeys (Distance.rebaseDistance baseKey publicKey) nodes
genClientList :: PublicKey -> Int -> Gen ClientList
genClientList publicKey size =
foldl (flip $ uncurry addNode) (empty publicKey size) <$> Gen.listOf arbitrary
instance Arbitrary ClientList where
arbitrary = join $ genClientList <$> arbitrary <*> arbitrarySizedNatural
\end{code}