1. API et ABI du noyau
1.1 Les red-black trees augmentés
Un red-black tree est un arbre binaire de recherche équilibré. L'objectif est d'y ranger un ensemble de valeurs (qui peuvent être modifiées) de façon ordonnée en permettant alors d'effectuer des opérations de recherche rapide. En effet, les opérations d'insertion, de suppression et de recherche s'exécutent dans le pire cas en O(log(N)) (cf. Kernel Corner 97). Ce type d'arbre est abondamment employé dans le noyau pour la recherche des structures de données qui peuvent être associées à des valeurs spécifiques. Il suffit alors de ranger dans cet arbre les structures avec leur valeur comme clé. Bien que répondant à de nombreux types de recherches effectuées par le noyau, ce type d'arbre atteint vite ses limites lorsque des recherches plus sophistiquées sont nécessaires.
Un red-black tree augmenté est une amélioration du red-black tree qui vise à couvrir un plus grand nombre de cas d'utilisation. Ils servent...
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première