El enunciado — Ejecutable
rush-02, compilado con
un Makefile (reglas
$(NAME),
clean y
fclean). Con un
argumento, es el número; con dos, el primero es otro diccionario. Si el número no es un entero
sin signo,
Error; si el diccionario está mal o no basta para escribir el número,
Dict Error. Y una frase en recuadro:
«vuestro programa debe ir más allá de
unsigned int». El diccionario tiene líneas
número : palabra, con espacios
opcionales que hay que recortar:
$> ./rush-02 42
forty two
$> ./rush-02 100000
one hundred thousand
$> ./rush-02 10.4
Error
Como bonus se puede añadir «and» y guiones, otro idioma con otro diccionario, o leer números
de la entrada estándar si el argumento es
-. Este grupo hizo el último. Trabajo de
grupo; el código está en
packs/piscine/018_rush02/repo/ex00/.
GGlosario de teoría
El Rush 02 es el primer programa «de verdad» de la piscine: lee un fichero, lo trocea, guarda
lo leído en memoria dinámica, lo libera y se compila con un Makefile. La página usa el vocabulario
de todo eso; aquí está cada término explicado desde cero y con un ejemplo sacado del propio rush. En
el resto de la página, la primera vez que sale uno de estos términos en cada tarjeta lleva un enlace
a su entrada.
Ficheros y entrada/salida
Descriptor de fichero, stdin y stdout
Un descriptor de fichero (fd) es un número pequeño con el que el programa se refiere a
algo donde puede leer o escribir. Todo programa arranca con tres: 0 es la entrada estándar
(stdin), 1 la salida estándar (stdout) y 2 la salida de errores (stderr). Con una tubería
(printf "42\n" | ./rush-02 -) la salida de un programa se convierte en el stdin del
siguiente.
En el rush, ft_putstr escribe siempre en el 1, también los mensajes
Error y Dict Error (los ejemplos del enunciado los muestran pasando por
| cat -e, así que van por stdout). El bonus lee del 0 con la misma
ft_read_file que lee el diccionario.
open, read y close
open(nombre, O_RDONLY) abre un fichero para leer y devuelve su descriptor, o −1 si
no puede (no existe, no hay permiso). read(fd, buf, n) lee como mucho
n bytes y devuelve cuántos ha leído de verdad: puede ser menos que n, 0
al llegar al final y −1 si hay un error. close(fd) lo cierra cuando ya no hace
falta.
ft_read_dict hace open, devuelve NULL si da −1 (por eso
./rush-02 noexiste.dict 42 da Dict Error), lee con
ft_read_file y cierra antes de parsear.
Buffer
Una zona de memoria donde se guardan datos de paso, mientras se leen o se escriben. Su tamaño
es fijo, así que si los datos no caben hay que trabajar a trozos.
ft_read_file usa char buffer[255] y lee 254 bytes cada vez; el byte
que queda es para el '\0'. El diccionario de referencia ocupa más que eso, así que se
lee en varias vueltas y se va pegando cada trozo.
Terminador nulo
En C una cadena es una fila de char que termina en el byte '\0' (valor
0). La longitud no se guarda: se sabe dónde acaba porque ahí está el cero. read no lo
pone, porque lee bytes, no cadenas.
Por eso ft_read_file hace buffer[n] = '\0' tras cada lectura, antes de
pasarlo a ft_strcat, que busca el final con ese cero. Sin él, ft_strcat
seguiría leyendo basura detrás del trozo.
Memoria
Memoria dinámica: malloc y free
Las variables locales viven en la pila de llamadas y desaparecen al salir de su
función; su tamaño se fija al compilar. malloc(n) reserva n bytes en otra
zona, el heap, que dura hasta que se llama a free y cuyo tamaño se decide
mientras el programa corre. Si no hay memoria, malloc devuelve NULL.
El rush no sabe cuánto mide el diccionario ni cuántas líneas tiene hasta leerlo, así que todo lo
que guarda es del heap: la cadena del fichero, los arrays de ft_split, cada palabra
recortada y la tabla de t_dict.
Fuga de memoria y valgrind
Una fuga (leak) es memoria del heap que ya no se puede liberar porque no queda
ningún puntero hacia ella. El sistema la recupera al terminar el proceso, pero en 42 cuenta como
error, y el enunciado avisa de que se revisa. Valgrind ejecuta el programa vigilando cada
malloc y cada free y al final dice lo que quedó sin liberar.
Con valgrind --leak-check=full ./rush-02 123456, y también con un diccionario que
da Dict Error, el informe acaba en All heap blocks were freed -- no leaks are
possible.
Propiedad de la memoria
Para cada bloque de malloc tiene que haber un responsable claro de su
free: quien lo reservó, quien lo recibió o la función a la que se le pasa. Si dos
partes creen que les toca, hay doble free; si ninguna lo cree, hay fuga. Por eso se
documenta.
El ft_strcat del rush consume su primer argumento: lo libera y devuelve un
bloque nuevo. Quien lo llama pierde la propiedad del viejo y gana la del nuevo; por eso se usa como
s = ft_strcat(s, trozo) y nunca con un literal. ft_strifcpy hace lo
contrario: reserva, y la propiedad pasa a quien recoge el retorno.
Centinela
Un valor especial al final de un array que marca dónde acaba, para no tener que guardar su
longitud aparte. Las cadenas de C usan el '\0'; argv y los arrays de
ft_split terminan en NULL.
La tabla del diccionario acaba en una entrada con nbr a 0. find_word y
ft_free_dict recorren hasta encontrarla, y en el camino de error
ft_parse_error la pone en la entrada i para que solo se libere lo que ya
estaba relleno.
struct y typedef
Un struct agrupa varias variables bajo un mismo nombre, como una ficha con campos.
typedef le da un nombre corto al tipo para no escribir struct s_dict cada
vez. En la Norma, los structs empiezan por s_ y los typedef por t_.
rush02.h define t_dict con dos cadenas, nbr y
word: una entrada del diccionario. dict[i].word es la palabra de la
entrada i.
Texto
Parsear
Convertir un texto con un formato en datos que el programa pueda usar, comprobando por el camino
que el formato se cumple. Si no se cumple, es un error de parseo.
ft_parse_dict convierte las líneas número : palabra en la tabla de
t_dict; una línea que no da exactamente dos trozos al partirla por ':' es
un Dict Error.
Split (trocear)
Partir una cadena en trozos allí donde aparece un separador, y devolverlos como un array de
cadenas. En este ft_split varios separadores seguidos cuentan como uno, así que no
salen trozos vacíos.
El rush lo usa dos veces: por "\n" para sacar las líneas (las vacías desaparecen
solas, como pide el enunciado) y por ":" para separar clave y valor. Esa segunda vez
es la que hace que 20: a:b dé tres trozos.
Recortar (trim)
Quitar los espacios (u otros caracteres) del principio y del final de una cadena, sin tocar los
de en medio.
ft_outspace mueve un índice desde delante y otro desde detrás mientras haya
espacios, y copia lo que queda entre ellos. " forty " queda en
"forty"; "hey everybody !" se queda igual, porque los espacios están
en medio.
Comparar cadenas
== entre dos char * compara direcciones, no contenido: dos copias de
"42" en sitios distintos darían «distintas». Para comparar el texto se recorren las
dos a la vez hasta la primera diferencia; ft_strcmp devuelve 0 si son iguales.
Todas las búsquedas del diccionario son con ft_strcmp, y por eso las claves pueden
ser tan largas como se quiera: "1000000000000000000000000000000000000" se compara
igual que "7".
Búsqueda lineal
Buscar un elemento mirando uno por uno desde el principio hasta encontrarlo o llegar al final.
No necesita que los datos estén ordenados, y el coste crece en proporción al tamaño.
find_word recorre la tabla hasta el centinela. Con las 41 entradas de
numbers.dict no se nota, y además el enunciado dice que las entradas pueden venir en
cualquier orden, así que no se podría buscar por mitades sin ordenar antes.
Números
Notación posicional y grupos de tres
En base 10 cada cifra vale según su posición: en 345, el 3 vale 300. Para leerlos en voz alta,
en inglés y en español se agrupan las cifras de tres en tres desde la derecha, y cada grupo lleva
su escala: 1 234 567 es «one million, two hundred thirty four thousand, five hundred sixty
seven».
write_num hace exactamente eso: exp va de 3 en 3 (… 6, 3, 0),
group_value saca las tres cifras de esa posición y scale_key construye la
clave de la escala.
Escala corta
En inglés, cada palabra nueva de escala multiplica por mil: million es 106, billion
109, trillion 1012. Es la escala corta. En español se usa la
larga, donde billón es 1012 (un millón de millones) y entre medias se dice
«mil millones».
numbers.dict va hasta undecillion, 1036. Un diccionario en
español no bastaría con cambiar las palabras: la estructura de grupos de tres del programa da «mil
millones» solo si hay una clave 1000000000 que diga eso.
unsigned int y su límite
Un unsigned int de 32 bits guarda enteros de 0 a 4 294 967 295 (232 −
1). Si un cálculo se pasa, el valor da la vuelta y vuelve a empezar desde 0, sin avisar. Por eso
el enunciado insiste en que el programa tiene que «ir más allá de unsigned int».
./rush-02 4294967296, uno más que el máximo, escribe four billion two hundred
ninety four million nine hundred sixty seven thousand two hundred ninety six: el número
nunca se convierte, se trata como cadena.
Números como cadenas de dígitos
Si un número no cabe en ningún tipo de C, se puede guardar como texto, una cifra por carácter.
Las bibliotecas de «precisión arbitraria» lo llevan al extremo y suman o multiplican cifra a cifra.
Si solo hay que leer el número, no hace falta ni eso.
El rush nunca hace aritmética con el número entero: lo valida con ft_is_positive
(solo dígitos), le quita los ceros de delante y lo recorre por posiciones. El único entero que
calcula es el valor de un grupo, que como mucho es 999. El límite real lo pone el diccionario:
hasta 39 cifras escribe el número; con 40, Dict Error.
Compilar y comprobar
Validar antes de escribir (dos pasadas)
Si un proceso puede fallar a mitad, a veces conviene hacerlo primero «en seco», solo
comprobando, y después de verdad. Así o sale todo o no sale nada. Las bases de datos llaman a esa
garantía transacción.
ft_write_nbr llama a write_num con do_write = 0, que solo
busca las claves; si falta alguna, escribe Dict Error sin haber escrito media frase.
Solo si la primera pasada sale bien, se repite con do_write = 1.
Makefile, reglas y relink
Un Makefile describe cómo construir un programa: cada regla dice qué fichero produce,
de qué depende y qué comando lo genera. make solo rehace lo que está más viejo que sus
dependencias. Si al ejecutar make dos veces la segunda vuelve a compilar o enlazar,
hay relink, y en 42 es un error.
El del rush tiene all, $(NAME), clean,
fclean y re, todas en .PHONY salvo $(NAME).
Un segundo make responde make: Nothing to be done for 'all'., y
tras touch rush02.h recompila todos los .o, porque todos dependen del
header.
Regla patrón: %, $< y $@
Una regla con % sirve para muchos ficheros a la vez: %.o: %.c dice
«cualquier .o se hace a partir del .c del mismo nombre». Dentro del
comando, $< es la primera dependencia y $@ el fichero que se está
generando.
En el rush, %.o: %.c rush02.h con $(CC) $(FLAGS) -c $< -o $@ se
convierte, para rush02.o, en cc -Wall -Wextra -Werror -c rush02.c -o
rush02.o: $< es el .c (va primero) y el header solo está para
que su cambio dispare la regla.
AddressSanitizer
Una herramienta del compilador que se activa con -fsanitize=address: vigila cada
acceso a memoria y, si uno se sale de su sitio o usa memoria ya liberada, para el programa y dice
dónde. Encuentra desbordamientos que sin ella pasarían desapercibidos.
Con un número de 49 cifras, el informe empieza por AddressSanitizer:
stack-buffer-overflow en scale_key: la clave de escala no cabe en el
char buf[48] de write_num.
mainmain, get_args y read_stdin
Entrega: ex00/rush02.c, ex00/rush02.hAutorizado: write, malloc, free, open, read, close
El orden de main es: decidir qué es diccionario y qué es número, validar el
número antes de abrir el diccionario, cargar el diccionario y escribir.
get_args(argc, argv, &dict_name, &num);
if (!is_stdin(num) && !ft_is_positive(num))
{
ft_putstr("Error\n");
return (0);
}
dict = ft_read_dict(dict_name);
if (dict == NULL)
{
ft_putstr("Dict Error\n");
return (0);
}
if (is_stdin(num))
read_stdin(dict);
else
ft_write_nbr(num, dict);
ft_free_dict(dict);
El bonus de la entrada estándar reutiliza piezas: ft_read_file(0) lee del
descriptor 0 igual que de un fichero, y ft_split(content, "\n") lo trocea en
líneas. Cada línea se valida y se escribe por separado.
$> printf "42\n7\n\n1000001\n" | ./rush-02 -
forty two
seven
one million one
Qué te obliga a aprender — Que la entrada estándar es un
descriptor más (el 0). Si
ft_read_file recibe un
fd en vez de un
nombre de fichero, el bonus sale casi gratis. Y que el número nunca se convierte a
int: se valida y se trata como
cadena de dígitos, que es la única forma de «ir más
allá de
unsigned int» sin tipos grandes.
leerft_read_file y ft_strcat
Entrega: ex00/ft_read_dict.c, ex00/ft_strutils.cAutorizado: read, malloc, free
No se sabe de antemano cuánto mide el fichero, así que se lee a trozos de 254 bytes y se va
pegando cada trozo a lo acumulado. El ft_strcat de este rush no es el de la libc:
devuelve un bloque nuevo y libera el primero, pensado para usarse como
s = ft_strcat(s, trozo). Por eso la cadena inicial es una cadena vacía del heap y
no el literal "".
dict_str = ft_strifcpy("", 0, 0);
n = read(fd, buffer, sizeof(buffer) - 1);
while (n > 0)
{
buffer[n] = '\0';
dict_str = ft_strcat(dict_str, buffer);
n = read(fd, buffer, sizeof(buffer) - 1);
}
if (n == -1)
{
free(dict_str);
return (0);
}
Qué te obliga a aprender —
read no lee «el
fichero»: lee
como mucho n bytes y te dice cuántos ha leído (0 al final, −1 si falla).
El
sizeof(buffer) - 1 reserva el hueco del
'\0' para poder tratar cada
trozo como cadena. Y la regla de propiedad de memoria: una función que libera su argumento tiene
que decirlo, porque quien la llame con un literal se lleva un
free inválido. El
comentario del código lo deja escrito.
parseft_parse_dict y ft_outspace
Entrega: ex00/ft_read_dict.c, ex00/ft_split.cAutorizado: malloc, free
El texto se convierte en un array de t_dict (pares nbr /
word, ambos cadenas) terminado en una entrada con nbr a 0, igual que
argv termina en NULL. Primero se parte por '\n' (las
líneas vacías desaparecen solas en el split), luego cada línea por ':'. Si no salen
exactamente dos trozos, es un Dict Error.
while (dict_lines[i])
{
dict_split = ft_split(dict_lines[i], ":");
if (ft_arrlen(dict_split) != 2)
return (ft_parse_error(dict, dict_lines, dict_split, i));
dict[i].nbr = ft_outspace(dict_split[0]);
dict[i].word = ft_outspace(dict_split[1]);
ft_free_split(dict_split);
i++;
}
dict[i].nbr = 0;
dict[i].word = 0;
ft_outspace recorta espacios por los dos extremos moviendo dos índices hacia
dentro, y copia lo que queda con ft_strifcpy(str, ini, fin), que reserva y copia
el trozo [ini, fin). El camino de error, ft_parse_error, pone el
centinela en la entrada i para que ft_free_dict sepa hasta dónde
liberar.
Qué te obliga a aprender — A diseñar una estructura de datos
propia (el
struct de C11 en un caso real) y a decidir cómo se sabe dónde acaba un
array dinámico: aquí con un centinela. Y que el camino de error también tiene que liberar todo
lo reservado hasta ese momento, que es donde suelen aparecer las
fugas.
clavewrite_num, group_value y scale_key
Entrega: ex00/ft_write_nbr.c, ex00/ft_write_utils.cAutorizado: write
Así se leen los números en inglés (y en español): en grupos de tres cifras, cada uno
seguido de su escala. 123456789 es «123 million, 456 thousand, 789». El número
nunca pasa a entero: exp es la potencia de 10 del grupo (0, 3, 6…), y
group_value saca las tres cifras de esas posiciones de la cadena. Esas sí caben en
un int, porque nunca pasan de 999.
len = ft_strlen(nbr);
exp = ((len + 2) / 3 - 1) * 3;
while (exp >= 0)
{
v = group_value(nbr, len, exp);
if (v > 0)
{
if (!write_group(v, dict, do_write, first))
return (0);
if (exp > 0)
{
if (!put_word(dict, scale_key(buf, exp), do_write, first))
return (0);
}
}
exp -= 3;
}
Para buscar la escala en el diccionario no hace falta calcular 10exp:
scale_key escribe la clave como texto, un '1' y exp
ceros. Las claves del diccionario son cadenas y se comparan con ft_strcmp, así que
"1000000000000000000000000000000000000" (undecillion) funciona igual que
"1000". Los grupos a cero se saltan enteros: por eso 1000000 da
one million y no «one million zero thousand».
Qué te obliga a aprender — Que un número es una
representación: si el problema no pide aritmética, no hace falta convertirlo, y
trabajar con los dígitos como texto elimina el límite de tamaño. Es la misma descomposición
posicional de
ft_putnbr (C00), pero de tres en tres cifras y sin división.
grupowrite_group y find_word
Entrega: ex00/ft_write_nbr.c, ex00/ft_write_utils.cAutorizado: write
Un grupo de 1 a 999: las centenas como «cifra + hundred», y para los dos últimos dígitos
primero se busca el número entero en el diccionario. Del 0 al 20 y las decenas tienen clave
propia; si no está (21, 47…), se compone con decena + unidad.
if (d >= 100)
{
if (!put_word(dict, ft_itokey(buf, d / 100), do_write, first))
return (0);
if (!put_word(dict, "100", do_write, first))
return (0);
}
r = d % 100;
if (r == 0)
return (1);
if (find_word(dict, ft_itokey(buf, r)))
return (put_word(dict, ft_itokey(buf, r), do_write, first));
if (!put_word(dict, ft_itokey(buf, (r / 10) * 10), do_write, first))
return (0);
Buscar primero la clave exacta tiene un efecto bonito: si alguien añade
42: the answer a un diccionario, el programa lo usa. find_word es una
búsqueda lineal por la tabla, suficiente para cuarenta entradas.
Qué te obliga a aprender — A no meter datos en el código. El
programa no sabe inglés: sabe la estructura de los números (centenas, decenas,
escalas) y le pide las palabras al diccionario. Cambiar el fichero cambia el idioma, que es la
idea detrás del bonus. La separación entre lógica y datos es la que luego verás en
configuraciones, traducciones y plantillas.
salidaft_write_nbr y put_word — dos pasadas
Entrega: ex00/ft_write_nbr.cAutorizado: write
Si al diccionario le falta una palabra a mitad de número, no debería salir media frase y
luego Dict Error. La solución del grupo: write_num recibe un
do_write, y se llama dos veces. La primera en seco, solo comprobando que todas las
claves existen; la segunda, escribiendo. put_word pone el espacio
antes de cada palabra salvo la primera (first).
while (nbr[0] == '0' && nbr[1])
nbr++;
...
if (!write_num(nbr, dict, 0, &first))
{
ft_putstr("Dict Error\n");
return ;
}
first = 1;
write_num(nbr, dict, 1, &first);
write(1, "\n", 1);
Los ceros de delante se saltan (007 → seven) y el cero, que no
tiene grupos, se trata aparte con la clave "0".
Qué te obliga a aprender — Que una salida a medias es peor que
un error limpio, y que validar todo antes de escribir nada es una técnica general (las bases de
datos lo llaman transacción). También el problema de la valla de C00, otra vez: el separador va
entre palabras, y la bandera first es la forma de no poner un espacio de
más.
?Preguntas probables de la evaluación
Lo que es fácil que pregunte quien te evalúe, con una respuesta corta y el enlace a la sección
donde está explicado a fondo. El enunciado avisa de que la memoria se revisa en la evaluación, así
que espera preguntas de malloc y free. Antes de mirar la respuesta,
intenta contestar tú.
Diseño
¿Cómo vais «más allá de unsigned int»?
No convirtiendo nunca el número: se valida como cadena de dígitos y se recorre por grupos de
tres cifras. El único entero que se calcula es el valor de un grupo, de 0 a 999. Las claves de
escala se construyen como texto ('1' y exp ceros) y se comparan con
ft_strcmp. 4294967296 se escribe sin problema.
→ write_num, unsigned int
¿Cómo evitáis escribir media frase y después Dict Error?
Con dos pasadas: write_num se llama primero con
do_write = 0, que solo busca las claves. Si falta alguna, sale Dict Error
sin haber escrito nada; si no, se repite escribiendo. → ft_write_nbr
¿Cómo cambiaríais de idioma?
Con otro diccionario como primer argumento: el programa no sabe inglés, solo la estructura de
centenas, decenas y escalas, y las palabras salen del fichero (en español, además, la escala es otra). Si el diccionario tiene la clave
exacta de un número de dos cifras (por ejemplo 42), se usa antes de descomponerlo.
→ write_group
Casos límite
¿Qué da Error y qué da Dict Error?
Error: un número que no son solo dígitos (10.4, -5,
+5, ""). Se comprueba antes de abrir el diccionario.
Dict Error: el diccionario no se puede abrir, una línea no da exactamente dos trozos
al parsearla partiéndola por ':', o falta una clave para el número pedido (a partir de 40 cifras
con numbers.dict). Los dos van por stdout, como en los ejemplos del enunciado.
→ main, ft_parse_dict
¿Qué pasa con 0 y con 007?
0 da zero: como no tiene grupos, se trata aparte con la clave
"0". A 007 se le quitan los ceros de delante y da seven.
→ ft_write_nbr
Con 20 : hey everybody !, ¿qué sale?
hey everybody !, con los espacios de en medio, y el enunciado espera
hey everybody !. ft_outspace solo recorta los
extremos. Es el punto débil más visible, porque está en el propio ejemplo del enunciado.
→ lo que no cumple
¿Y un número de 49 cifras?
Desborda char buf[48] en scale_key durante la pasada en seco
(AddressSanitizer lo marca). Hasta 39 cifras escribe el número y de 40 a 48
da Dict Error. El arreglo es dejar de construir la clave cuando no cabe, o dar
Dict Error en cuanto exp pasa del tamaño del buffer.
→ lo que no cumple
Memoria y Makefile
¿Hay leaks? ¿Quién libera cada cosa?
Valgrind no da fugas, ni con un número normal ni con un Dict Error. Cada split se
libera con ft_free_split, la cadena del fichero en ft_read_dict después
de parsear, y la tabla con ft_free_dict al final de main. En el camino de
error, ft_parse_error pone el centinela donde se quedó para
liberar solo lo relleno. → memoria, ft_parse_dict
¿Por qué ft_strcat libera su primer argumento?
Para acumular en bucle: s = ft_strcat(s, trozo) crea un bloque nuevo con los dos
pegados, y el viejo ya no sirve. Por eso la cadena inicial es ft_strifcpy("", 0, 0),
del heap: con el literal "" el free sería inválido.
→ ft_read_file, propiedad de la memoria
¿Y si falla un malloc?
No está cubierto del todo. Si falla el de la tabla en ft_parse_dict, se devuelve
NULL (sale Dict Error) pero las líneas de ft_split no se
liberan; y el retorno de ft_split no se comprueba en ningún sitio, así que si fuera
NULL, ft_arrlen lo leería. Mejor reconocerlo que defenderlo.
→ ft_parse_dict
¿El Makefile hace relink?
No: un segundo make responde Nothing to be done for 'all'. Y como cada
.o depende también de rush02.h, al cambiar el header se recompila todo
lo que lo incluye. Tiene las reglas que pide el enunciado ($(NAME),
clean, fclean) más all y re.
→ Makefile, relink
Sobre el trabajo en grupo
¿Quién hizo qué? ¿Qué bonus hicisteis?
El reparto te lo tienes que preparar tú; en la defensa cualquiera del grupo tiene que poder
explicar cualquier fichero. El bonus hecho es la entrada estándar: con - como número,
cada línea de stdin se convierte por separado (printf "1\n2\n" | ./rush-02 - da
one y two). Ni «and» ni guiones. → main