realloc y el crecimiento: duplicar, mover y perder el puntero

El arreglo que crece es la estructura de datos más usada de la informática y la que más veces se implementa mal en C. Su corrección depende de un invariante de tres campos, su rendimiento depende de una decisión aritmética que parece arbitraria y no lo es, y su seguridad depende de entender que realloc no es una operación que modifica un bloque sino una que puede sustituirlo. Esta lección deduce el factor de crecimiento desde el análisis amortizado, examina las condiciones exactas bajo las que el bloque se mueve, y disecciona el error de una sola línea que convierte un fallo de reserva recuperable en una fuga irreparable.

Longitud y capacidad son dos números distintos

Un arreglo dinámico correcto guarda tres cosas: el bloque, cuántos elementos contiene y cuántos caben. Confundir los dos últimos es el origen de la mitad de los errores de esta estructura, porque son magnitudes con semánticas opuestas: la longitud es un hecho sobre los datos, la capacidad es una decisión sobre la memoria.

#include <stdlib.h>
#include <string.h>

typedef struct {
    int    *datos;
    size_t  longitud;    // elementos validos
    size_t  capacidad;   // elementos que caben sin reasignar
} Vector;

// Invariante: longitud no supera a capacidad, y si capacidad vale
// cero entonces datos es nullptr.

De ese invariante se deriva toda la implementación. Insertar comprueba si queda sitio y, solo si no queda, invoca la política de crecimiento; leer valida contra la longitud, nunca contra la capacidad; y liberar devuelve el bloque una sola vez, dejando la estructura en un estado que vuelve a satisfacer el invariante.

bool vector_insertar(Vector *v, int valor) {
    if (v->longitud == v->capacidad &&
        !vector_reservar(v, v->longitud + 1))
        return false;                    // el vector queda intacto

    v->datos[v->longitud++] = valor;
    return true;
}

void vector_destruir(Vector *v) {
    free(v->datos);
    *v = (Vector){ 0 };                  // el invariante se sigue cumpliendo
}

Fíjate en que la inserción devuelve un valor booleano en vez de abortar. Esa decisión es la que hace posible que el fallo de reserva sea recuperable, y es también la que obliga a que la función de crecimiento no destruya nada cuando fracasa: el llamante tiene derecho a seguir usando el vector después de un false.

Por qué se multiplica y no se suma

Supón que amplías la capacidad en una unidad cada vez que se llena. Cada ampliación puede requerir copiar todos los elementos ya presentes, así que insertar n elementos cuesta en el peor caso 1 + 2 + ... + n copias, es decir, del orden de n al cuadrado. Para un millón de elementos son medio billón de copias: el arreglo deja de ser utilizable por una decisión de una línea.

Multiplicar la capacidad por un factor constante k cambia la naturaleza del problema. Las reasignaciones ocurren en tamaños que forman una progresión geométrica decreciente hacia atrás, y el total de elementos copiados hasta llegar a n es la suma de esa progresión, acotada por n dividido entre k menos uno. Con k igual a dos se copia como mucho una vez por elemento: el coste amortizado de insertar es constante, aunque el coste de la inserción concreta que dispara la copia sea lineal.

static bool vector_reservar(Vector *v, size_t minima) {
    if (minima <= v->capacidad) return true;

    size_t nueva = v->capacidad ? v->capacidad + v->capacidad / 2 : 8;
    if (nueva < minima) nueva = minima;

    int *tmp = realloc(v->datos, nueva * sizeof *v->datos);
    if (!tmp) return false;          // el vector sigue intacto y usable

    v->datos     = tmp;
    v->capacidad = nueva;
    return true;
}

El factor exacto no es indiferente, y aquí aparece el argumento más elegante de todo el tema. Con k igual a dos, cada bloque nuevo es estrictamente mayor que la suma de todos los bloques que ya liberaste, porque una potencia de dos supera a la suma de todas las anteriores. El asignador nunca puede reutilizar el hueco que dejaste atrás, ni siquiera fusionándolo entero, y el arreglo va dejando un rastro de memoria libre inservible a medida que avanza por el montón. Con un factor menor que la razón áurea, aproximadamente uno coma seis uno ocho, la suma de los bloques liberados acaba alcanzando al bloque siguiente y la reutilización se vuelve posible. Por eso varias bibliotecas serias eligen uno coma cinco: sacrifican una copia amortizada adicional a cambio de un montón que no se fragmenta.

Cuándo realloc mueve el bloque

La firma de realloc esconde una disyuntiva que la documentación enuncia en una línea y que casi nadie interioriza: la función puede devolver la misma dirección o puede devolver otra distinta, y tu código debe ser correcto en ambos casos sin poder distinguirlos de antemano.

Amplía en el sitio, devolviendo la misma dirección, cuando el asignador puede satisfacer el nuevo tamaño sin tocar los datos. Eso ocurre si el crecimiento cabe en el redondeo que ya se había concedido, si el bloque contiguo posterior está libre y basta con absorberlo, o si el bloque es el último del montón y basta con desplazar el fin del segmento de datos. Reduciendo el tamaño casi siempre puede: parte el bloque y libera la cola.

Mueve, devolviendo una dirección nueva, cuando ninguna de esas condiciones se cumple. Entonces reserva un bloque nuevo, copia los bytes del contenido antiguo hasta el menor de los dos tamaños y libera el original. Los bloques obtenidos con mmap son un caso aparte: sobre Linux el asignador puede recurrir a mremap, que reasigna el mapeo virtual sin copiar un solo byte de datos físicos.

flowchart TD
A[realloc con puntero y tamano nuevo] --> B[Puntero nulo, equivale a malloc]
A --> C[Cabe en el redondeo actual]
A --> D[El bloque contiguo esta libre]
A --> E[Ninguna de las anteriores]
C --> F[Devuelve la MISMA direccion]
D --> F
E --> G[Reserva, copia con memcpy y libera el original]
G --> H[Devuelve una direccion DISTINTA]
E --> I[Si falla devuelve nulo y el bloque original sigue vivo]
style F fill:#a6e3a1,color:#11111b
style H fill:#f9e2af,color:#11111b
style I fill:#f38ba8,color:#11111b

La consecuencia práctica es severa y va más allá del puntero base. En cuanto realloc devuelve un valor no nulo, el bloque anterior deja de existir a efectos del lenguaje, y toda dirección derivada de él queda colgante: los punteros a elementos interiores que hubieras guardado, los iteradores, las direcciones almacenadas en otras estructuras. Guardar índices en vez de punteros no es una preferencia estilística, es la única forma de sobrevivir a una reasignación.

El bug de una línea que borra tu memoria

La forma corta y natural de escribir la reasignación es también la incorrecta:

// INCORRECTO: si realloc falla, v->datos pasa a ser nulo
// y la direccion del bloque original se pierde para siempre.
v->datos = realloc(v->datos, nueva * sizeof *v->datos);
if (!v->datos) return false;

El razonamiento es directo. Cuando realloc fracasa devuelve nulo y, por contrato, no libera ni modifica el bloque original, que sigue reservado y sigue conteniendo tus datos. Pero acabas de sobrescribir con nulo la única variable que guardaba su dirección. La memoria queda reservada y ya no es accesible: una fuga en su definición más pura, provocada precisamente por la ruta de error que creías estar gestionando. Y no es solo una fuga, es una pérdida de datos: el vector se queda con capacidad y longitud que ya no describen nada.

La corrección cabe en una variable temporal, y el patrón merece grabarse tal cual: reasignas a una temporal, compruebas la temporal, y solo entonces publicas los tres campos de la estructura de forma consistente.

int *tmp = realloc(v->datos, nueva * sizeof *v->datos);
if (!tmp) return false;      // v sigue siendo un vector valido
v->datos     = tmp;
v->capacidad = nueva;

La regla general que subyace es la de la actualización atómica del estado: mientras la operación puede fallar, no se toca ningún campo observable de la estructura; cuando ya no puede fallar, se actualizan todos de golpe. Aplicada de forma sistemática, esa disciplina da lo que en el resto de la ingeniería se llama garantía fuerte de excepción: o la operación tiene éxito o el objeto queda exactamente como estaba. En C no hay excepciones, pero la propiedad es igual de valiosa y bastante más fácil de conseguir, porque solo exige ordenar las asignaciones.

Existe además una variante que absorbe la comprobación del desbordamiento en la propia llamada. reallocarray, presente en las BSD y en glibc desde la versión dos punto veintiséis, toma el número de elementos y su tamaño por separado, multiplica de forma comprobada y devuelve nulo si el producto no cabe. No es C estándar, pero es la forma más limpia de escribir el crecimiento cuando puedes depender de ella, y es trivial reproducirla con ckd_mul cuando no.

Hay un tercer error que acompaña siempre a los dos anteriores: liberar el puntero antiguo después de una reasignación con éxito. Si realloc movió el bloque, ya liberó el original y tu free es una doble liberación; si lo amplió en el sitio, estás liberando el bloque vivo que acabas de recibir. En ambos casos el resultado es corrupción del asignador. Tras un realloc con éxito no hay nada que liberar: el puntero antiguo simplemente ha dejado de ser un valor válido.