Laborator 01: Introducere

Mai multe detalii pot fi găsite pe pagina Reguli de notare.

• MAXIM 3 absenţe la laborator (NU se poate reface la alte grupe)
• MINIM jumătate din punctajul de laborator

Laboratorul de Structuri de Date și Algoritmi are drept scop aprofundarea conceptelor prezentate la curs. Un laborator va prezenta un anumit set de concepte și va conține următoarele activități:

• prezentare teoretică
• rezolvarea exercițiilor propuse

Pentru o desfășurare cât mai bună a laboratorului și pentru o înțelegere cât mai bună a conceptelor vă recomandăm să parcurgeți conținutul laboratorului de acasă.

În cadrul acestui laborator vom lucra pe platforma Linux, mai precis vom lucra într-o mașină virtuală în care este instalat Lubuntu. Lubuntu este o distribuție de Linux care are la bază Ubuntu dar față de aceasta este mai lightweight.

Pe stațiile de lucru din laborator a fost instalat VMware Player și adăugată mașina virtuală cu numele SDA-AB. Porniți mașina virtuală.

Credențialele sunt următoarele:

• user: student
• password: student

Pentru a putea lucra de acasă la rezolvarea temelor, în cazul în care nu doriți să aveți instalată o distribuție de Linux, puteți găsi mașina virtuală de la laborator de aici Descărcați fișierul SDA-AB_VM.zip și dezarhivați-l. Fișierul are dimensiunea de 2.3GB (5.4GB dezarhivat).

Pentru a putea deschide mașina virtuală avem nevoie de VMware Workstation Player. Aceste este gratuit și poate fi descărcat de aici. Alegeți versiunea corespunzătoare sistemului de operare folosit.

După dezarhivarea mașinii virtuale și instalarea VMware Player, deschideți VMware Player → File → Open a Virtual Machine → Mergeți in directorul unde ați salvat mașina virtuală, SDA-AB, și selectați fișierul SDA-AB.vmx după care porniți mașina.

În mașina virtulă este deja instalat toolchain-ul GNU. Acesta este o suită de tool-uri necesare dezvoltării programelor folosind C/C++ și conține:

• GNU Compiler Collection: compilator pentru C (gcc), pentru C++ (g++)
• Utilitarul make
• Debugger (gdb)
• Linker, asamblor, etc.

Pentru exemplificare vom folosi un program simplu care tipărește la ieșirea standard (stdout) un șir de caractere.

hello.c

#include <stdio.h>
 
int main()
{
   printf("SDA - Hello, World!\n");
 
   return 0;
}

GCC folosește pentru compilarea de programare C/C++ comanda gcc, respectiv comanda g++.

student@sda-ab-vm:~/Documents$ ls
hello.c
student@sda-ab-vm:~/Documents$ gcc hello.c
student@sda-ab-vm:~/Documents$ ls
a.out  hello.c
student@sda-ab-vm:~/Documents$ ./a.out 
SDA - Hello, World!

Prin urmare, comanda gcc hello.c a fost folosită pentru compilarea fișierului sursă hello.c. Rezultatul a fost obținerea fișierului executabil a.out (nume implicit utilizat de gcc). Dacă se dorește obținerea unui executabil cu un alt nume se poate folosi opțiunea -o.

student@sda-ab-vm:~/Documents$ gcc hello.c -o hello
student@sda-ab-vm:~/Documents$ ls
hello  hello.c
student@sda-ab-vm:~/Documents$ ./hello 
SDA - Hello, World!

Observăm că de data aceasta fișierul executabil rezultat se numește hello.

În mod similar se poate folosi g++ pentru compilarea unui program sursă C++.

De cele mai multe ori nu vom lucra cu un singur fișier sursă ci vom încerca să modularizăm codul, spărgându-l în mai multe fișiere sursă, fiecare implementând o anumită funcționalitate.

Fișierele header .h nu implementează funcții ci conține doar definiții de funcții. Implementarea efectivă a acestora se realizează în fișierul asociat .c pentru C, sau .cpp pentru C++.

Să considerăm următorul scenariu: dorim să realizăm un modul care implementează funcțiile de adunare și inmulțire.

Creăm fișierul header cu numele my_math.h.

my_math.h

#ifndef MY_MATH_H
#define MY_MATH_H
 
int sum(int a, int b);
int multiply(int a, int b);
 
#endif

Prin folosirea #ifndef MY_MATH_H … #endif ne asigurăm că acest fișier header nu este inclus de mai multe ori în același fișier sursă. Cu alte cuvinte, în cazul în care simbolul MY_MATH_H este deja definit de la prima includere, a doua operație de includere nu va avea niciun efect. Această tehnică se numește Include guard și folosește directivele de preprocesoare #ifndef, #define, #endif.

Apoi, creăm fișierul sursa cu numele my_math.c.

my_math.c

#include "my_math.h"
 
int sum(int a, int b)
{
   return a + b;
}
 
int multiply(int a, int b)
{
   return a * b;
}

Creăm și un fișier cu numele main.c în care vom utiliza funcțiile implementate de modulul nostru.

main.c

#include <stdio.h>
#include "my_math.h"
 
int main()
{
   int a = 10;
   int b = 20;
 
   printf("a + b = %d\n", sum(a, b));
   printf("a * b = %d\n", multiply(a, b));
 
   return 0;
}

Observăm modul în care am inclus header-ul my_math.h față de header-ul stdio.h. Atunci când ne dorim să includem un header din biblioteca standard folosim #include < ... .h>, iar atunci când dorim să includem un header creat de noi folosim #include ".... .h>".

Programul nostru are acum mai multe fișiere sursă .c. Compilarea din mai multe astfel de fișiere se face prin specificarea tuturor fișierelor sursă .c ca argumente utilitarului gcc.

student@sda-ab-vm:~/Documents$ ls
main.c  my_math.c  my_math.h
student@sda-ab-vm:~/Documents$ gcc main.c my_math.c -o main
student@sda-ab-vm:~/Documents$ ls
main  main.c  my_math.c  my_math.h
student@sda-ab-vm:~/Documents$ ./main 
a + b = 30
a * b = 200

Make este un utilitar din GNU Toolchain care permite automatizarea și eficientizarea sarcinilor. În mod particular este folosit pentru automatizarea compilării programelor. În cazul în care avem un proiect care are un număr foarte mare de fișiere sursă, compilarea întregului proiect de la zero poate dura foarte mult. Prin folosirea utilitarului make putem automatiza compilarea fiecărui fișier separat .c într-un fișier obiect (binar) .o, apoi unirea tuturor fișierelor obiect într-un singur fișier executabil. La o modificare se va recompila doar fișierul sursă modificat, rezultând un nou fișier obiect .o. Astfel, procesul de compilare este mult mai rapid.

Utilitarul make folosește un fișier de configurare denumit Makefile. Un astfel de fișier conține reguli și comenzi de automatizare.

Makefile

all:
    gcc hello.c -o hello
clean:
    rm -f hello

student@sda-ab-vm:~/Documents$ ls
hello.c  Makefile
student@sda-ab-vm:~/Documents$ make
gcc hello.c -o hello
student@sda-ab-vm:~/Documents$ ls
hello  hello.c  Makefile
student@sda-ab-vm:~/Documents$ make clean
rm -f hello
student@sda-ab-vm:~/Documents$ ls
hello.c  Makefile
student@sda-ab-vm:~/Documents$ make all
gcc hello.c -o hello
student@sda-ab-vm:~/Documents$ ls
hello  hello.c  Makefile

Exemplul prezentat mai sus conține două reguli: all și clean. La rularea comenzii make se execută prima regulă din Makefile (în cazul de față all, nu contează în mod special denumirea). Comanda executată este gcc hello.c -o hello. Se poate preciza explicit ce regulă să se execute prin transmiterea ca argument comenzii make. (comanda make clean pentru a șterge executabilul hello și comanda make all pentru a obține din nou acel executabil).

Sintaxa unei reguli dintr-un fișier Makefile:

• target - este, de obicei, fișierul care se va obține prin rularea comenzii command. După cum s-a observat și din exemplul anterior, poate să fie o țintă virtuală care nu are asociat un fișier.
• prerequisites - reprezintă dependențele necesare pentru a urmări regula; de obicei sunt fișiere necesare pentru obținerea țintei.
• <tab> - reprezintă caracterul tab și trebuie neaparat folosit înaintea precizării comenzii.
• command - o listă de comenzi (niciuna, una, oricâte) rulate în momentul în care se trece la obținerea țintei.

Un exemplu recomandat pentru un fișier Makefile este:

Makefile

all: hello
 
hello: hello.o
        gcc hello.o -o hello
 
hello.o: hello.c
        gcc -c hello.c
 
clean:
        rm -f *.o *~ hello

Observăm prezeța regulii all care va fi executată implicit.

• all are ca dependență hello și nu execută nicio comandă
• hello are ca dependență hello.o și realizează link-editarea fișierului hello.o
• hello.o are ca dependență hello.c și realizează compilarea fișierului hello.c în fișierul obiect hello.o.

Un fișier Makefile permite folosirea de variabile. Astfel, un exemplu uzual de fișier Makefile este:

Makefile

CC = gcc
CFLAGS = -Wall -g
 
all: hello
 
hello: hello.o
        $(CC) $^ -o $@
 
hello.o: hello.c
        $(CC) $(CFLAGS) -c $<
 
clean:
        rm -f *.o *~ hello

În exemplul de mai sus au fost definite variabilele CC și CFLAGS. Variabia CC reprezintă compilatorul folosit, iar variabila CFLAGS reprezintă opțiunile de compilare utilizate; în cazul de față sunt afișarea tuturor warning-urilor (-Wall) cu suport de depanare (-g).

Variabilele predefinte sunt:

• $@ se expandează la numele target-ului
• $^ se expandează la lista de cerințe (prerequisites - lista de dependențe)
• $< se expandează la prima cerință (la prima dependență)

GDB (GNU Debugger) este unealta standard pentru debugging (depanare) din GNU. Este portabil şi poate fi folosit, printre altele, pentru a detecta instrucţiunea ce determina blocarea unui program la rulare (precum şi semnalul asociat erorii).

Exemplu de lansare:

gcc -Wall -g my_file.c -o my_file.exe
gdb my_file.exe

Câteva comenzi utile în timpul depanării:
• list - arată conţinutul unui fişier (câteva rânduri, în jurul unui punct numit)
• run - porneşte executia
• n (sau next) - trece la instrucţiunea următoare (fără a intra în apeluri de funcţii)
• s (sau step) - intră în apel de funcţie pentru a inspecta execuţia
• b (sau break sau breakpoint) - setează un breakpoint ce va forţa oprirea execuţiei în punctul respectiv
• continue - continuă execuţia până la următorul breakpoint
• fin (sau finish) - iese din funcţia curentă

Exemple de identificare a instrucţiunilor (la fel pentru list) - funcţie, rândul din fişier, adresa din memorie (eventual cu explicitarea fişierului):

breakpoint my_function
breakpoint 13
breakpoint *0x401377

breakpoint my_file:10
breakpoint my_file:my_function

Realizați un program un C/C++ care afișează mesajul Hello, World la ieșirea standard.

Realizați un fișier Makefile pentru programul de la exercițiul 1 astfel încat:

• la rularea comenzii make build să se obțină executabilul hello
• la rularea comenzii make clean să se șteargă fișierul hello de pe disc.

1. More about GCC, Linux, Makefiles