1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <string.h>
4.  
5. #include "CircularDoublyLinkedList.h"
6. #include "utils.h"
7.  
8. /*
9.  * Functie care trebuie apelata pentru alocarea si initializarea unei liste.
10.  * (Setare valori initiale pentru campurile specifice structurii LinkedList).
11.  */
12. doubly_linked_list_t*
13. dll_create(unsigned int data_size)
14. {
15.     doubly_linked_list_t *list = malloc(sizeof(doubly_linked_list_t));
16.     DIE(list == NULL, "Malloc failed\n");
17.  
18.     list->head = NULL;
19.     list->data_size = data_size;
20.     list->size = 0;
21.     return list;
22. }
23.  
24. /*
25.  * Functia intoarce un pointer la nodul de pe pozitia n din lista.
26.  * Pozitiile din lista sunt indexate incepand cu 0 (i.e. primul nod din lista se
27.  * afla pe pozitia n=0). Daca n >= nr_noduri, atunci se intoarce nodul de pe
28.  * pozitia rezultata daca am "cicla" (posibil de mai multe ori) pe lista si am
29.  * trece de la ultimul nod, inapoi la primul si am continua de acolo. Cum putem
30.  * afla pozitia dorita fara sa simulam intreaga parcurgere? Daca n < 0, eroare.
31.  */
32. dll_node_t*
33. dll_get_nth_node(doubly_linked_list_t* list, unsigned int n)
34. {
35.     if (n < 0) {
36.         fprintf(stderr, "Error\n");
37.         exit(-1);
38.     }
39.  
40.     if (list == NULL)
41.         exit(-1);
42.  
43.     if (n >= list->size)
44.         n = n % list->size;
45.  
46.     dll_node_t *curr;
47.     curr = list->head;
48.     while (n > 0) {
49.         curr = curr->next;
50.         n--;
51.     }
52.  
53.     return curr;
54. }
55.  
56. /*
57.  * Pe baza datelor trimise prin pointerul new_data, se creeaza un nou nod care e
58.  * adaugat pe pozitia n a listei reprezentata de pointerul list. Pozitiile din
59.  * lista sunt indexate incepand cu 0 (i.e. primul nod din lista se afla pe
60.  * pozitia n=0). Cand indexam pozitiile nu "ciclam" pe lista circulara ca la
61.  * get, ci consideram nodurile in ordinea de la head la ultimul (adica acel nod
62.  * care pointeaza la head ca nod urmator in lista). Daca n >= nr_noduri, atunci
63.  * adaugam nodul nou la finalul listei. Daca n < 0, eroare.
64.  */
65. void
66. dll_add_nth_node(doubly_linked_list_t* list, unsigned int n, const void* data)
67. {
68.     if (n < 0) {
69.         fprintf(stderr, "Error\n");
70.         return;
71.     }
72.  
73.     if (list == NULL)
74.         return;
75.  
76.     dll_node_t *new;
77.     new = malloc(sizeof(dll_node_t));
78.     DIE(new == NULL, "Malloc failed\n");
79.     new->data = malloc(list->data_size);
80.     DIE(new == NULL, "Malloc failed\n");
81.     memcpy(new->data, data, list->data_size);
82.  
83.  
84.     if (list->size == 0) {
85.         list->head = new;
86.         new->next = new;
87.         new->prev = new;
88.         list->size++;
89.         return;
90.     }
91.  
92.     dll_node_t *last;
93.  
94.     if (n > list->size)
95.         n = list->size;
96.  
97.     if (n == 0) {
98.         last = list->head->prev;
99.         new->next = list->head;
100.         new->prev = last;
101.         list->head->prev = new;
102.         list->head = new;
103.         list->size++;
104.         return;
105.     }
106.  
107.     dll_node_t *curr = list->head;
108.     while (n > 1) {
109.         curr = curr->next;
110.         n--;
111.     }
112.     new->next = curr->next;
113.     new->prev = curr;
114.     curr->next = new;
115.     curr->prev = new;
116.     list->size++;
117. }
118.  
119. /*
120.  * Elimina nodul de pe pozitia n din lista al carei pointer este trimis ca
121.  * parametru. Pozitiile din lista se indexeaza de la 0 (i.e. primul nod din
122.  * lista se afla pe pozitia n=0). Functia intoarce un pointer spre acest nod
123.  * proaspat eliminat din lista. Daca n >= nr_noduri - 1, se elimina nodul de la
124.  * finalul listei. Daca n < 0, eroare. Este responsabilitatea apelantului sa
125.  * elibereze memoria acestui nod.
126.  */
127. dll_node_t*
128. dll_remove_nth_node(doubly_linked_list_t* list, unsigned int n)
129. {
130.     if (n < 0) {
131.         fprintf(stderr, "Error\n");
132.         return NULL;
133.     }
134.  
135.     if (list == NULL)
136.         return NULL;
137.  
138.     if (list->head == NULL)
139.         return NULL;
140.  
141.     if (n == 0) {
142.         dll_node_t *first, *last;
143.         first = list->head;
144.         last = first->prev;
145.         list->head = first->next;
146.         list->head->prev = first->prev;
147.         last->next = list->head;
148.         list->size--;
149.         return first;
150.     }
151.  
152.     if (n >= list->size - 1)
153.         n = list->size - 1;
154.  
155.     dll_node_t *prev, *curr;
156.     prev = list->head;
157.     curr = list->head->next;
158.     while (n > 1) {
159.         prev = curr;
160.         curr = curr->next;
161.         n--;
162.     }
163.     prev->next = curr->next;
164.     curr->next->prev = prev;
165.     list->size--;
166.     return curr;
167. }
168.  
169. /*
170.  * Functia intoarce numarul de noduri din lista al carei pointer este trimis ca
171.  * parametru.
172.  */
173. unsigned int
174. dll_get_size(doubly_linked_list_t* list)
175. {
176.     if (list == NULL)
177.         exit(-1);
178.     return list->size;
179. }
180.  
181. /*
182.  * Procedura elibereaza memoria folosita de toate nodurile din lista, iar la
183.  * sfarsit, elibereaza memoria folosita de structura lista.
184.  */
185. void
186. dll_free(doubly_linked_list_t** pp_list)
187. {
188.     if ((*pp_list)->size == 0) {
189.         free(*pp_list);
190.         *pp_list = NULL;
191.         return;
192.     }
193.  
194.     unsigned int tmp;
195.     tmp = (*pp_list)->size;
196.  
197.     dll_node_t *node;
198.     node = (*pp_list)->head;
199.    
200.     while (tmp > 0) {
201.         dll_node_t *node1 = node->next;
202.         free(node->data);
203.         free(node);
204.         node = node1;
205.         tmp--;
206.     }
207.     free(*pp_list);
208.     *pp_list = NULL;
209. }
210.  
211. /*
212.  * Atentie! Aceasta functie poate fi apelata doar pe liste ale caror noduri STIM
213.  * ca stocheaza int-uri. Functia afiseaza toate valorile int stocate in nodurile
214.  * din lista separate printr-un spatiu, incepand de la primul nod din lista.
215.  */
216. void
217. dll_print_int_list(doubly_linked_list_t* list)
218. {
219.     if (list == NULL)
220.         return;
221.  
222.     dll_node_t *pos = list->head;
223.     unsigned int tmp = list->size;
224.    
225.     while (tmp > 0) {
226.         printf("%d ", *((int *)pos->data));
227.         pos = pos->next;
228.         tmp--;
229.     }
230.     printf("\n");
231. }
232.  
233. /*
234.  * Atentie! Aceasta functie poate fi apelata doar pe liste ale caror noduri STIM
235.  * ca stocheaza string-uri. Functia afiseaza toate string-urile stocate in
236.  * nodurile din lista separate printr-un spatiu, incepand de la primul nod din
237.  * lista.
238.  */
239. void
240. dll_print_string_list(doubly_linked_list_t* list)
241. {
242.     if (list == NULL)
243.         return;
244.    
245.     dll_node_t *pos = list->head;
246.     unsigned int tmp = list->size;
247.  
248.     while (tmp > 0) {
249.         printf("%s ", (char *)pos->data);
250.         pos = pos->next;
251.         tmp--;
252.     }
253.     printf("\n");
254. }
255.  
256. /*
257.  * Atentie! Aceasta functie poate fi apelata doar pe liste ale caror noduri STIM
258.  * ca stocheaza int-uri. Functia afiseaza o singura data toate valorile int
259.  * stocate in nodurile din lista, separate printr-un spatiu, incepand de la
260.  * nodul dat ca parametru si continuand la stanga in lista dublu inlantuita
261.  * circulara, pana cand sunt afisate valorile tuturor nodurilor.
262.  */
263. void
264. dll_print_ints_left_circular(dll_node_t* start)
265. {
266.     dll_node_t *pointer = start->prev;
267.     printf("%d ", *((int *)start->data));
268.  
269.     while (pointer != start) {
270.         printf("%d ", *((int *)pointer->data));
271.         pointer = pointer->prev;
272.     }
273.     printf("\n");
274. }
275.  
276. /*
277.  * Atentie! Aceasta functie poate fi apelata doar pe liste ale caror noduri STIM
278.  * ca stocheaza int-uri. Functia afiseaza o singura data toate valorile int
279.  * stocate in nodurile din lista, separate printr-un spatiu, incepand de la
280.  * nodul dat ca parametru si continuand la dreapta in lista dublu inlantuita
281.  * circulara, pana cand sunt afisate valorile tuturor nodurilor.
282.  */
283. void
284. dll_print_ints_right_circular(dll_node_t* start)
285. {
286.     dll_node_t *pointer = start->prev;
287.     printf("%s ", (char *)start->data);
288.  
289.     while (pointer != start) {
290.         printf("%s ", (char *)start->data);
291.         pointer = pointer->next;
292.     }
293.     printf("\n");
294. }
295.