Archivos relacionados:

sds.h
sds.c

Definición

Tipos básicos de SDS

typedef char* sds;

SDS representa "Simple Dynamic String", o cadena dinámica simple.

Estructuras de encabezado

struct __attribute__ ((__packed__)) encabezado_sds8 {
    uint8_t longitud_uso;
    uint8_t capacidad_asignada;
    unsigned char tipo_info;
    char datos[];
};

struct __attribute__ ((__packed__)) encabezado_sds16 {
    uint16_t longitud_uso;
    uint16_t capacidad_asignada;
    unsigned char tipo_info;
    char datos[];
};

struct __attribute__ ((__packed__)) encabezado_sds32 {
    uint32_t longitud_uso;
    uint32_t capacidad_asignada;
    unsigned char tipo_info;
    char datos[];
};

struct __attribute__ ((__packed__)) encabezado_sds64 {
    uint64_t longitud_uso;
    uint64_t capacidad_asignada;
    unsigned char tipo_info;
    char datos[];
};

Consideraciones importantes:

1. encabezado_sds es el encabezado oculto de SDS
2. El atributo __packed__ evita el relleno de bytes por parte del compilador
3. Los campos tipo_info almacenan metadatos en los 3 bits menos significativos

Acceso a metadatos ocultos

Una variable sds es realmente un puntero a char* que apunta directamente al búfer de datos. Para acceder al encabezado:

1. Retroceder un byte para obtener los flags de tipo
2. Calcular la posición del encabezado según el tipo
3. Realizar un casting al tipo de estructura apropiado

#define OBTENER_ENCABEZADO(tipo, puntero) ((struct encabezado_sds##tipo *)((puntero)-(sizeof(struct encabezado_sds##tipo))))
#define TIENE_TIPO5_LONGITUD(flags) ((flags)>>3)

static inline size_t obtener_longitud(const sds str) {
    unsigned char banderas = str[-1];
    switch(banderas & 0x07) {
        case 0:  // Tipo 5
            return TIENE_TIPO5_LONGITUD(banderas);
        case 1:  // Tipo 8
            return OBTENER_ENCABEZADO(8, str)->longitud_uso;
        case 2:  // Tipo 16
            return OBTENER_ENCABEZADO(16, str)->longitud_uso;
        case 3:  // Tipo 32
            return OBTENER_ENCABEZADO(32, str)->longitud_uso;
        case 4:  // Tipo 64
            return OBTENER_ENCABEZADO(64, str)->longitud_uso;
    }
    return 0;
}

Cuando str tiene un encabezado encabezado_sds8, la macro se expande a: ((struct encabezado_sds8 *)((str)-(sizeof(struct encabezado_sds8))))

Ventajas de implementación

Estrategia de pre-asignación de memoria

#define MAX_PREASIGNACION (1024*1024)  // 1MB

size_t tamano_actual = obtener_longitud(str);
size_t tamano_requerido = (tamano_actual + tamano_adicional);

if (modo_avaro) {
    if (tamano_requerido < MAX_PREASIGNACION) {
        tamano_requerido *= 2;  // Duplicar espacio para cadenas pequeñas
    } else {
        tamano_requerido += MAX_PREASIGNACION;  // Añadir 1MB para cadenas grandes
    }
}

Ejemplo de crecimiento: Al añadir 5 caracteres a una cadena de longitud 3, el nuevo tamaño asignado sería 16.

Prevención de desbordamiento de búfer

La función de concatenación verifica automáticamente el espacio disponible:

sds concatenar_datos(sds destino, const void* fuente, size_t cantidad) {
    size_t tamano_previo = obtener_longitud(destino);
    
    // Garantizar espacio suficiente antes de la operación
    destino = ampliar_espacio(destino, cantidad);
    if (!destino) return NULL;
    
    memcpy(destino + tamano_previo, fuente, cantidad);
    establecer_longitud(destino, tamano_previo + cantidad);
    destino[tamano_previo + cantidad] = '\0';
    
    return destino;
}

Seguridad binaria

A diferencia de las cadenas C estándar, SDS almacena explícitamente la longitud, lo que permite manejar datos binarios que contengan bytes nulos:

int comparar_cadenas_sds(const sds primera, const sds segunda) {
    size_t len1 = obtener_longitud(primera);
    size_t len2 = obtener_longitud(segunda);
    size_t minimo = (len1 < len2) ? len1 : len2;
    
    int resultado = memcmp(primera, segunda, minimo);
    
    if (resultado == 0) {
        return (len1 > len2) ? 1 : ((len1 < len2) ? -1 : 0);
    }
    return resultado;
}

Compatibilidad con funciones C

SDS mantiene el terimnador nulo '\0', permitiendo interacción directa con funciones estándar de C como printf o strcmp.

Características principales

1. Obtención de longitud en tiempo O(1)
2. Protección contra desbordamientos de búfer
3. Minimización de reasignaciones de memoria
4. Capacidad para manejar datos binarios
5. Compatibilidad con el ecosistema de cadenas en C