Graphe non hiérarchique
Reliez librement vos noeuds via des branches nommées (Token, string, etc.), avec support des cycles.
CppUtils::Container::MeshNetwork est conçu pour la création de graphes non hiérarchiques (qu’ils possèdent ou non une racine unique), où les noeuds se connectent via des branches nommées, tolèrent des cycles sans fuite mémoire, se manipulent en toute sécurité entre threads et supportent la pagination sur disque (MeshPager).
Ce modèle offre une grande flexibilité mais induit un surcoût structurel (allocations de liens, tables de branches, support du multithreading).
Exemple de graphe représentable avec MeshNetwork :
graph LR
R1["Root 1"] -->|"next"| A["Node A"]
R1 -->|"next"| B["Node B"]
R2["Root 2"] -->|"next"| C["Node C"]
R2 -->|"link"| B
R3["Root 3"] -->|"next"| D["Node D"]
A <-->|"link"| E["Node E"]
A -->|"branch"| B
B <-->|"link"| F["Node F"]
B -->|"next"| D
C -->|"branch"| B
C -->|"branch"| G["Node G"]
D -->|"next"| C
D -->|"branch"| H["Node H"]
E -->|"next"| F
F -->|"next"| G
G -->|"next"| D
G -->|"link"| E
H -->|"link"| F
H -->|"next"| A
classDef root fill:#2563eb,stroke:#93c5fd,stroke-width:2px,color:#ffffff
class R1,R2,R3 root
Ce guide est un tutoriel pas à pas conçu pour vous apprendre à déclarer un maillage, connecter ses branches, manipuler ses noeuds en toute sécurité entre threads et activer la persistance paginée sur disque.
Graphe non hiérarchique
Reliez librement vos noeuds via des branches nommées (Token, string, etc.), avec support des cycles.
Destruction RAII
Libération immédiate des sous-graphes détachés, même en présence de cycles.
Concurrence sans deadlock
Verrouillage de chaque noeud via les verrous RAII pour des accès concurrents sûrs.
Pagination sur disque
Sérialisation, enregistrement et chargement progressifs sur disque via MeshPager pour préserver la RAM.
Un pointeur de noeud s’instancie en spécifiant le type de clé des branches (ici CppUtils::Type::Token) et le type de valeur portée par chaque noeud (ici std::string) :
Les exemples de ce guide utilisent le littéral ""_token (issu de using namespace CppUtils::String::Literals;).
// Définition du type de noeud manipulé (clés Token, valeurs std::string)using NodePtr = CppUtils::Container::MeshNodePtr<CppUtils::Type::Token, std::string>;
// Création d'un noeud racine du grapheauto root = NodePtr::makeRoot("Root");
// Création de noeuds libres (non encore rattachés à une racine)auto nodeA = NodePtr::make("Node A");auto nodeB = NodePtr::make("Node B");graph LR
Root["Root (racine)"]
A["Node A (libre)"]
B["Node B (libre)"]
classDef root fill:#2563eb,stroke:#93c5fd,stroke-width:2px,color:#ffffff
class Root root
style A stroke-dasharray: 5 5
style B stroke-dasharray: 5 5
Utilisez les opérateurs dédiés pour relier ou détacher des noeuds :
>>)L’opérateur >> relie un noeud enfant à une branche du parent. Il supporte deux formes :
branch >> node attache node à branch et retourne node ;parent["a"_token] >> child["b"_token] attache child à parent["a"_token] et retourne la branche child["b"_token], ce qui permet d’enchaîner plusieurs niveaux en une seule expression :// Attachement des noeuds sous des branches nomméesroot["branch"_token] >> nodeA;nodeA["sub"_token] >> nodeB;
// Équivalent en une seule expression chaînéeroot["branch"_token] >> nodeA["sub"_token] >> nodeB;
// Chaînage direct à l'instanciationauto nodeC = root["other"_token] >> NodePtr::make("Node C");graph LR
Root["Root"] -->|"branch"| A["Node A"]
A -->|"sub"| B["Node B"]
Root -->|"other"| C["Node C"]
classDef root fill:#2563eb,stroke:#93c5fd,stroke-width:2px,color:#ffffff
class Root root
-)L’opérateur - supprime un lien vers un noeud sans altérer les autres noeuds présents sur la même branche :
// Retrait de nodeA de la branche "branch"root["branch"_token] - nodeA;Tant que vous conservez un MeshNodePtr local sur le noeud détaché (nodeA), il reste valide en mémoire avec ses enfants (nodeB) et peut être rattaché. En revanche, un noeud ou un groupe de noeuds (y compris cyclique) qui n’est plus rattaché à aucune racine et n’a plus de variable locale est libéré immédiatement en RAII :
// 1. nodeA reste valide via la variable locale et garde son enfant nodeBroot["branch"_token] >> nodeA;
// 2. Sous-graphe cyclique sans variable locale conservée : libéré dès le détachement{ auto tempA = root["temp"_token] >> NodePtr::make("Temp A"); auto tempB = tempA["next"_token] >> NodePtr::make("Temp B"); tempB["back"_token] >> tempA; // Cycle interne} // tempA et tempB sortent du scope, mais restent en vie tant que root les référence
root["temp"_token].clear(); // Plus aucune racine ni variable locale : tempA et tempB sont détruits immédiatement (malgré le cycle)flowchart LR
subgraph Kept ["1. Variable locale conservée en mémoire"]
Root["Root"] -->|"branch"| NA["Node A"] -->|"sub"| NB["Node B"]
end
subgraph Freed ["2. Sans racine ni variable locale, détruit en RAII"]
TA["Temp A"] -->|"next"| TB["Temp B"]
TB -->|"back"| TA
end
NB ~~~ TA
classDef root fill:#2563eb,stroke:#93c5fd,stroke-width:2px,color:#ffffff
classDef freed stroke:#ef4444,stroke-dasharray: 5 5
class Root root
class TA,TB freed
Pour détacher l’ensemble des noeuds d’une branche en un seul appel, utilisez clear() :
root["branch"_token].clear();Pour détacher toutes les branches sortantes du noeud d’un coup :
root.clearBranches();&)L’opérateur & crée deux liaisons réciproques en une seule instruction. Chaque crochet désigne la branche sortante du noeud qui le précède, et l’attachement démarre automatiquement depuis le noeud déjà relié à une racine :
// Au moins l'un des noeuds doit être une racine ou déjà rattaché à une racineauto nodeA = NodePtr::makeRoot("Node A");auto nodeB = NodePtr::make("Node B");
// nodeA["toB"] -> nodeB et nodeB["toA"] -> nodeA// (les deux clés peuvent aussi être identiques)nodeA["toB"_token] & nodeB["toA"_token];graph LR
A["Node A"] -->|"toB"| B["Node B"]
B -->|"toA"| A
classDef root fill:#2563eb,stroke:#93c5fd,stroke-width:2px,color:#ffffff
class A root
Fonctionnellement, & équivaut à enchaîner deux >> en une seule instruction :
// Équivalent fonctionnel en unidirectionnelnodeA["toB"_token] >> nodeB;nodeB["toA"_token] >> nodeA;/)L’opérateur / rompt simultanément les deux directions d’une connexion croisée. Comme pour &, chaque crochet indique la branche sortante à nettoyer sur chacun des deux noeuds :
// Retire nodeB de nodeA["toB"] et nodeA de nodeB["toA"]nodeA["toB"_token] / nodeB["toA"_token];Fonctionnellement, / équivaut à enchaîner deux - en une seule instruction :
nodeA["toB"_token] - nodeB;nodeB["toA"_token] - nodeA;Chaque noeud encapsule sa valeur dans un conteneur thread-safe :
// Acquisition d'un accesseur en lecture partagée sur la valeurif (auto valueAccessor = nodeA.getValue()){ // La valeur est verrouillée en lecture partagée pendant tout ce bloc std::println("Valeur courante : {}", valueAccessor.value());} // valueAccessor est détruit ici et relâche le verrou
// Modification thread-safe de la valeur (uniquement possible une fois le verrou libéré)nodeA.setValue("Node A v2");Il est essentiel de distinguer deux types de comparaison :
nodeA == nodeB) : Retourne un bool indiquant si les deux pointeurs font référence au même noeud physique en mémoire, peu importe sa valeur.nodeA.getValue().value() == nodeB.getValue().value()) : Compare la charge utile des noeuds.auto node1 = NodePtr::makeRoot("Value");auto node2 = NodePtr::makeRoot("Value");auto alias1 = node1;
assert(node1 == alias1); // Vrai : même adresse mémoireassert(node1 != node2); // Vrai : deux instances distinctesassert(node1.getValue().value() == node2.getValue().value()); // Vrai : même contenu "Value"MeshNodePtr s’intègre nativement avec les concepts et algorithmes de la bibliothèque standard C++ (ranges, vues, itérateurs).
[] et at())Il existe deux manières d’accéder à une branche d’un noeud, selon que vous souhaitiez créer ou modifier la branche (node[key]) ou l’interroger sans exception (node.at(key)) :
| Appel | Sur node non-const | Sur node const | Si la clé est absente |
|---|---|---|---|
node[key] | Retourne une branche modifiable (verrou exclusif) | Retourne une branche en lecture seule (verrou partagé) | Crée la branche en non-const ; lance std::out_of_range en const |
node.at(key) | Retourne un std::expected (branche en lecture seule, verrou partagé, ou erreur std::string_view) | Identique | Ne crée pas et ne lance jamais d’exception (std::unexpected<std::string_view>) |
Sur une branche, l’accès indexé branch[i] (ainsi que front() et back()) retourne également un std::expected<MeshNodePtr, std::string_view>.
Vérification d’existence préalable (clé de branche et présence d’un noeud) :
if (root.contains("branch"_token)){ auto branch = root["branch"_token]; std::println("Nombre de noeuds : {}", std::ranges::size(branch)); std::println("Contient nodeA : {}", branch.contains(nodeA));}Accès sécurisé sans risque d’exception (recommandé en lecture) :
if (auto branch = root.at("branch"_token)){ if (auto firstNode = branch->front()) { std::println("Premier noeud trouvé : {}", firstNode->getValue().value()); }}Compter les liens d’une branche sans la créer si elle est absente :
const auto linkCount = root.at("branch"_token).transform([](const auto& branch) { return std::ranges::size(branch);}).value_or(0uz);Une branche se parcourt comme n’importe quelle collection C++ standard :
std::random_access_iterator).Branch maintient un verrou RAII sur le vecteur de liens (std::vector<Link>) pendant toute la durée de la boucle ou de l’expression : aucun lien ne peut donc être ajouté ou retiré de cette branche pendant le parcours.WeakPtr plutôt qu’un pointeur fort. Ce choix évite les fuites mémoire sur les cycles du graphe et permet à un autre thread ou à MeshPager de supprimer ou décharger un noeud cible sans verrouiller tout le graphe. Si la cible a disparu ou été déchargée entre-temps, l’itérateur renvoie un MeshNodePtr vide (d’où la vérification if (child)).Vous pouvez parcourir directement les enfants avec une simple boucle for :
for (const auto& child : root["branch"_token]){ if (child) { std::println("Noeud : {}", child.getValue().value()); }}Les branches étant compatibles avec les algorithmes de std::ranges, vous pouvez vérifier une condition sur leurs éléments en une seule expression :
const auto hasNodeA = std::ranges::any_of(root["branch"_token], [](const auto& node) { return node and node.getValue().value() == "Node A";});Elles se composent également avec les vues de std::views, par exemple pour filtrer les noeuds valides puis inverser l’ordre de parcours :
for (const auto& validChild : root["branch"_token] | std::views::filter([](const auto& node) { return static_cast<bool>(node); }) | std::views::reverse){ std::println("Noeud valide : {}", validChild.getValue().value());}Enfin, grâce au support de std::random_access_iterator, vous pouvez manipuler les itérateurs directement (comme calculer un index par soustraction) :
auto branch = root["branch"_token];if (auto it = std::ranges::find_if(branch, [](const auto& node) { return node and node.getValue().value() == "Node A"; }); it != std::ranges::end(branch)){ std::println("Trouvé à l'index {}", it - std::ranges::begin(branch));}getBranches())Lorsque les clés de branches ne sont pas connues à l’avance, utilisez getBranches() pour parcourir l’ensemble des branches sortantes d’un noeud.
Dans la boucle ci-dessous, links est de type SafeShared<std::vector<Link>> (un pointeur partagé thread-safe vers le vecteur de liens de la branche), dont la méthode .sharedAccess() fournit un accès en lecture seule :
for (const auto& [branchKey, links] : node.getBranches().value()){ std::println("Branche '{}' : {} lien(s)", branchKey, links->sharedAccess()->size());}L’architecture interne de MeshNode repose sur une synchronisation sans verrou global, articulée autour de trois niveaux indépendants de CppUtils::Thread::SharedLocker :
SharedLocker<Value>) : getValue() et setValue() ne verrouillent que la charge utile, sans bloquer les branches.SharedLocker<Branches>) : getBranches() ne verrouille que l’index des clés de branches.SharedLocker<std::vector<Link>>) : chaque clé possède son propre verrou de vecteur. Un proxy Branch sur "branchA" n’empêche ni d’accéder à la valeur du noeud, ni de modifier "branchB" depuis un autre thread.Un accesseur ne verrouille donc jamais tout le noeud, mais uniquement la ressource ciblée.
flowchart TD
subgraph MeshNode ["Structure interne d'un MeshNode"]
ValLock["SharedLocker<Value> (Donnée)"]
BranchMapLock["SharedLocker<Branches> (Index des branches)"]
BranchALock["SharedLocker<vector<Link>> (Branche A)"]
BranchBLock["SharedLocker<vector<Link>> (Branche B)"]
BranchMapLock --> BranchALock
BranchMapLock --> BranchBLock
end
Reader1["Thread 1 (getValue / sharedAccess)"] --> ValLock
Writer["Thread 2 (setValue / uniqueAccess)"] -. Exclusif .-> ValLock
Reader2["Thread 3 (node['A'])"] --> BranchALock
WriterB["Thread 4 (node['B'] >> x)"] -. Exclusif .-> BranchBLock
En pratique, un thread peut ainsi modifier la valeur d’un noeud (ou une de ses branches) pendant qu’un autre thread manipule une autre branche ou lit la valeur du même noeud, sans blocage mutuel.
MeshPager)Lorsque votre graphe doit persister entre deux exécutions d’un programme, ou lorsqu’il devient trop volumineux pour tenir entièrement en mémoire vive (plusieurs millions de noeuds), CppUtils fournit CppUtils::FileSystem::MeshPager.
track)MeshPager ne suit pas vos noeuds automatiquement : après avoir importé CppUtils.FileSystem.MeshPager et ouvert un répertoire de stockage, vous devez enregistrer chaque noeud avec pager.track(noeud). Cela lui attribue un identifiant persistant (std::size_t).
Enregistrer un noeud avec track() ne l’écrit toutefois pas immédiatement sur disque : tant qu’il reste dans le cache du pager, il demeure en RAM. La sauvegarde sur disque ne se déclenche que lorsqu’un noeud sort d’une fenêtre de focus et est déchargé de la RAM, ou lorsque le MeshPager est détruit :
using namespace CppUtils::Type::Literals;using MeshPager = CppUtils::FileSystem::MeshPager<CppUtils::Type::Token, std::string>;using PagedNode = MeshPager::MeshNodePtr; // Équivalent à CppUtils::Container::MeshNodePtr<CppUtils::Type::Token, std::string, MeshPager::Policy>
const auto saveDirectory = std::filesystem::path{"./save"};auto pager = MeshPager{saveDirectory};
auto root = PagedNode::makeRoot("Root");auto nodeA = root["next"_token] >> PagedNode::make("Node A");auto nodeB = nodeA["next"_token] >> PagedNode::make("Node B");auto nodeC = nodeB["next"_token] >> PagedNode::make("Node C");auto nodeD = nodeC["next"_token] >> PagedNode::make("Node D");auto nodeE = nodeD["next"_token] >> PagedNode::make("Node E");
// Enregistrement des noeuds dans le pagerpager.track(root);pager.track(nodeA);pager.track(nodeB);pager.track(nodeC);pager.track(nodeD);pager.track(nodeE);acquireFocusPlutôt que de garder tout le graphe en RAM, pager.acquireFocus(noeud, rayon) crée une fenêtre RAII (ScopedFocus) qui maintient en mémoire les noeuds à distance <= rayon et décharge automatiquement les autres sur disque :
{ auto focus = pager.acquireFocus(root, 1uz); // 'root' et son voisin direct 'nodeA' restent en RAM. // 'nodeB', 'nodeC', 'nodeD' et 'nodeE' (à distance >= 2) sont déchargés sur disque tout en conservant leurs liens persistants.} // À la destruction de 'focus' (puis de 'pager'), les noeuds restants sont déchargés sur disque.Si noeud n’est pas encore suivi par le pager, acquireFocus() appelle automatiquement track(noeud) avant d’activer la fenêtre.
Plusieurs ScopedFocus peuvent coexister en même temps, qu’ils se chevauchent (fenêtre glissante lors d’un parcours) ou qu’ils soient totalement disjoints pour garder plusieurs zones distinctes en RAM. L’union de leurs rayons détermine l’ensemble des noeuds maintenus en RAM, tandis que les autres restent sur disque.
{ auto focusA = pager.acquireFocus(nodeA, 1uz); auto focusB = pager.acquireFocus(nodeB, 1uz);}{ auto focusA = pager.acquireFocus(nodeA, 1uz); auto focusD = pager.acquireFocus(nodeD, 1uz);}addFocus, removeFocus)Si vous avez besoin d’un contrôle manuel sans garde RAII (par exemple pour attacher un focus à un événement plutôt qu’à un bloc), utilisez addFocus(nodeId, distance) et removeFocus(nodeId, distance) :
// Gérer la durée de vie d'un focus manuellement (sans scope RAII)const auto idA = nodeA.getId();pager.addFocus(idA, 1uz);// ...pager.removeFocus(idA, 1uz);loadNode, unloadNode)Si vous souhaitez contrôler manuellement la présence des noeuds en RAM sans utiliser de focus, MeshPager fournit deux fonctions complémentaires : loadNode(nodeId) pour charger un noeud depuis le disque vers la RAM, et unloadNode(nodeId) pour le sérialiser sur disque et libérer immédiatement la RAM :
auto root = pager.loadNode(rootId); // Charge root depuis le disquepager.unloadNode(rootId); // Sauvegarde root sur disque et le libère de la RAMloadNode() et unloadNode() fonctionnent sur n’importe quel noeud à partir de son identifiant, pas uniquement sur une racine : chaque noeud est stocké et indexé indépendamment par son nodeId.
auto root = pager.loadNode(rootId);auto nodeA = root["next"_token].front().value(); // Charge nodeA à la voléeUne fois un noeud chargé avec loadNode(), chaque accès à l’une de ses branches recharge automatiquement depuis le disque les noeuds cibles qui ne sont pas encore en RAM, et il en va de même pour les sauts suivants vers d’autres noeuds du graphe.
MeshPager attribue des identifiants séquentiels à partir de 1uz (0uz étant réservé aux noeuds non suivis ou invalides) et ne maintient pas de catalogue des racines. Deux bonnes pratiques permettent de retrouver facilement vos points d’entrée au lancement suivant :
1uz : dans un répertoire neuf, enregistrez en premier un noeud racine dédié qui reçoit automatiquement l’ID 1uz et relie vos différentes racines ou branches du graphe. Au redémarrage, il suffit d’appeler pager.loadNode(1uz) pour tout retrouver.pager.track(root) (ou root.getId()) dans un fichier de configuration applicatif (ou dans un IndexedStorage distinct, placé dans un autre répertoire que celui du pager) pour les relire au démarrage.removeNode)Deux mécanismes permettent de supprimer des noeuds du disque, selon votre besoin :
ScopedFocus). Un simple appel à unloadNode() ne déclenche pas cette suppression : il se contente d’écrire le noeud sur disque et de le retirer de la RAM.removeNode(nodeId)) : indispensable pour supprimer un noeud racine (jamais supprimé automatiquement, même sans parent) ou pour supprimer immédiatement un noeud précis de la RAM, de l’index des liens et du disque (notamment sans utiliser de focus, ou sans attendre la fin d’un ScopedFocus).{ auto focus = pager.acquireFocus(root, 1uz); root["next"_token] - nodeA;} // À la sortie du focus, nodeA (et nodeB s'il n'est plus rattaché) sont supprimés du disque
// Ou suppression explicite d'un noeud par son IDpager.removeNode(rootId);Pour sauvegarder un noeud sur disque lorsqu’il est déchargé de la RAM (et le reconstruire lors d’un rechargement), MeshPager<Key, Value> doit convertir ses clés de branches (Key) et ses valeurs (Value) en flux binaire via CppUtils::Type::Binary::Serializer.
Les types suivants sont pris en charge nativement, sans code supplémentaire :
int, double, bool, etc.), enum et structures POD simples (std::is_trivially_copyable_v<T>).std::stringstd::vector<T>, dès lors que T est lui-même sérialisable.std::unordered_map<Key, Value>, dès lors que Key et Value sont eux-mêmes sérialisables.Pour étendre la sérialisation binaire à vos propres types utilisateur (par exemple une structure contenant des std::string ou d’autres membres non triviaux), spécialisez CppUtils::Type::Binary::Serializer :
struct UserAccount{ std::string name; std::uint64_t score = 0;};
template<>struct CppUtils::Type::Binary::Serializer<UserAccount> final{ static auto serialize(const UserAccount& user, auto& target) -> void { CppUtils::Type::serialize(user.name, target); CppUtils::Type::serialize(user.score, target); }
[[nodiscard]] static auto deserialize(auto& source, UserAccount& user) -> std::expected<void, std::string_view> { if (auto result = CppUtils::Type::deserialize(source, user.name); not result) return result; if (auto result = CppUtils::Type::deserialize(source, user.score); not result) return result; return {}; }
[[nodiscard]] static auto deserialize(auto& source) -> std::expected<UserAccount, std::string_view> { auto user = UserAccount{}; if (auto result = deserialize(source, user); not result) return std::unexpected{result.error()}; return user; }};Une fois cette spécialisation définie, vous pouvez directement instancier MeshPager<std::string, UserAccount> : le pager sérialise et recharge automatiquement vos objets UserAccount sur disque sans configuration supplémentaire.