Árboles, hashes y otras estructuras

Las listas son geniales para recorrer, pero lentas para buscar. El kernel provee estructuras optimizadas —árboles equilibrados, tablas hash, arrays dispersos— todas con el mismo diseño intrusivo. Conocerlas te deja elegir la estructura correcta en vez de reinventarla.

Árboles rojo-negro

Cuando necesitas datos ordenados con inserción, borrado y búsqueda en O(log n), el kernel usa árboles rojo-negro (self-balancing). Igual que las listas, son intrusivos: embebes un struct rb_node:

#include <linux/rbtree.h>

struct evento {
    u64 timestamp;
    struct rb_node nodo;    // el nodo del árbol, embebido
};
static struct rb_root arbol = RB_ROOT;

Los usa el planificador (nivel 25) para ordenar tareas, el gestor de memoria para las regiones virtuales, y cualquier sitio que necesite orden con búsqueda rápida. Insertar requiere escribir la comparación (dónde va cada nodo), pero el reequilibrado lo hace el kernel.

Tablas hash

Para búsqueda por clave en O(1) medio, las hash tables del kernel (DECLARE_HASHTABLE) enlazan objetos en cubetas, otra vez de forma intrusiva:

#include <linux/hashtable.h>
DECLARE_HASHTABLE(mi_tabla, 8);     // 2^8 = 256 cubetas

struct entrada {
    int clave;
    struct hlist_node nodo;         // nodo de hash, embebido
};
hash_add(mi_tabla, &e->nodo, e->clave);

xarray e idr: enteros → punteros

Un patrón constante en el kernel: “tengo un ID entero, quiero el objeto asociado” (un descriptor de archivo → su struct file, un PID → su task). El xarray (y el más antiguo idr) resuelven esto eficientemente, incluso para IDs dispersos:

#include <linux/xarray.h>
DEFINE_XARRAY(mis_objetos);
xa_store(&mis_objetos, id, objeto, GFP_KERNEL);
void *obj = xa_load(&mis_objetos, id);