====== Laborator 01: Introducere ======

===== 1. Reguli pentru laborator=====

Mai multe detalii pot fi găsite pe pagina [[informaii-generale:notare|Reguli de notare]].

==== Reguli esenţiale pentru promovarea laboratorului====

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


-----
===== 2. Desfășurarea laboratorului =====
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.

==== 2.1. Mașina virtuală SDA-AB în laborator ====
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ă.

{{ :laboratoare:vmware_player.png?nolink&786 |}}

Credențialele sunt următoarele:
* user: **student**
* password: **student**

<note warning>Utilizatorul **student** are drepturi de scriere doar în directorul ///home/student//. **La repornirea mașinii virtuale conținutul acestui director este șters automat.**</note>

==== 2.2. Mașina virtuală pentru acasă ====
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 [[https://drive.google.com/drive/folders/0B3s0Ou3_zjgMSnB6ODV0SGlnaG8?usp=sharing|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 [[http://www.vmware.com/products/player/playerpro-evaluation.html|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.

<note>În cazul în care vă apare mesajul //**This virtual machine may have been moved or copied**// selectați **I copied it**.</note>

<note important>Mașina virtuală pentru acasă **păstrează** conținutul directorului ///home/student//, iar utilizatorul **student** cu parola **student** are drepturi de administrare. Acest lucru nu este valabil pentru mașina virtuală de pe stațiile de lucru din laborator. </note>

==== 2.3. GNU Toolchain ====
Î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.


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

<file cpp hello.c>
#include <stdio.h>

int main()
{
   printf("SDA - Hello, World!\n");
   
   return 0;
}
</file>

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

<code bash>
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!
</code>

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%%''.

<code bash>
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!
</code>

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++.

=== 2.3.2. Fișiere header și include guards
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%%''.
<file cpp my_math.h>
#ifndef MY_MATH_H
#define MY_MATH_H

int sum(int a, int b);
int multiply(int a, int b);

#endif
</file>

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%%''.
<file cpp 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;
}
</file>

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

<file cpp 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;
}
</file>

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%%''.

<code bash>
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
</code>

<note>Fișierele header ''%%.h%%'' nu trebuie date ca argumente utilitarului ''%%gcc%%''. În etapa de compilare conținutul unui fișier ''%%.h%%'' este copiat în interiorul fișierului sursă care îl include.</note>

=== 2.3.2. GNU Make ===
**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.

=== Exemplu de utilizare ===
<file Makefile Makefile>
all:
    gcc hello.c -o hello
clean:
    rm -f hello
</file>

<code bash>
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
</code>

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 ===
Sintaxa unei reguli dintr-un fișier Makefile:

{{ :laboratoare:makefile.png?nolink |}}


 * **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:
<file Makefile Makefile>
all: hello
 
hello: hello.o
        gcc hello.o -o hello
 
hello.o: hello.c
        gcc -c hello.c
 
clean:
        rm -f *.o *~ hello
</file>

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%%''.

<note>La regula cu target-ul ''%%hello.o%%'' se observă folosirea opțiunii ''%%-c%%'' a utilitarului ''%%gcc%%''. Aceasta opțiune se folosește pentru a obține doar fișierul obiect din codul sursă. Se oprește procesul de compilare inainte de obținerea executabilului. La final se continua compilarea cu unirea tuturor fișierelor obiect ''%%.o%%'' într-un fișier executabil. </note>

=== Folosirea variabilelor ===
Un fișier ''%%Makefile%%'' permite folosirea de variabile. Astfel, un exemplu uzual de fișier ''%%Makefile%%'' este:

<file Makefile 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
</file>

Î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ță)


===== 4. GDB =====

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:\\
<code>
gcc -Wall -g my_file.c -o my_file.exe
gdb my_file.exe
</code>

**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ă\\

<note important>**list** şi **breakpoint** au nevoie de un parametru care să indice o instrucţiune ("punctul" dorit).</note>

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):\\
<code>
breakpoint my_function
breakpoint 13
breakpoint *0x401377

breakpoint my_file:10
breakpoint my_file:my_function
</code>


----
===== 5. Exerciții =====

==== Exercițiul 1 - Hello world  ====
Realizați un program un C/C++ care afișează mesajul //Hello, World// la ieșirea standard.

==== Exercițiul 2 - Makefile  ====
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.


==== Exercițiul 3 - Makefile cu surse multiple  ====



----
===== 6. Referințe =====
  - [[https://ocw.cs.pub.ro/courses/so/laboratoare/laborator-01|More about GCC, Linux, Makefiles]]