1 /*
2 * This file Copyright (C) 2007-2014 Mnemosyne LLC
3 *
4 * It may be used under the GNU GPL versions 2 or 3
5 * or any future license endorsed by Mnemosyne LLC.
6 *
7 */
8
9 #include "transmission.h"
10 #include "list.h"
11 #include "platform.h"
12 #include "utils.h"
13
14 static tr_list const TR_LIST_CLEAR =
15 {
16 .data = NULL,
17 .next = NULL,
18 .prev = NULL
19 };
20
21 static tr_list* recycled_nodes = NULL;
22
getRecycledNodesLock(void)23 static tr_lock* getRecycledNodesLock(void)
24 {
25 static tr_lock* l = NULL;
26
27 if (l == NULL)
28 {
29 l = tr_lockNew();
30 }
31
32 return l;
33 }
34
node_alloc(void)35 static tr_list* node_alloc(void)
36 {
37 tr_list* ret = NULL;
38 tr_lock* lock = getRecycledNodesLock();
39
40 tr_lockLock(lock);
41
42 if (recycled_nodes != NULL)
43 {
44 ret = recycled_nodes;
45 recycled_nodes = recycled_nodes->next;
46 }
47
48 tr_lockUnlock(lock);
49
50 if (ret == NULL)
51 {
52 ret = tr_new(tr_list, 1);
53 }
54
55 *ret = TR_LIST_CLEAR;
56 return ret;
57 }
58
node_free(tr_list * node)59 static void node_free(tr_list* node)
60 {
61 tr_lock* lock = getRecycledNodesLock();
62
63 if (node != NULL)
64 {
65 *node = TR_LIST_CLEAR;
66 tr_lockLock(lock);
67 node->next = recycled_nodes;
68 recycled_nodes = node;
69 tr_lockUnlock(lock);
70 }
71 }
72
73 /***
74 ****
75 ***/
76
tr_list_free(tr_list ** list,TrListForeachFunc data_free_func)77 void tr_list_free(tr_list** list, TrListForeachFunc data_free_func)
78 {
79 while (*list != NULL)
80 {
81 tr_list* node = *list;
82 *list = (*list)->next;
83
84 if (data_free_func != NULL)
85 {
86 data_free_func(node->data);
87 }
88
89 node_free(node);
90 }
91 }
92
tr_list_prepend(tr_list ** list,void * data)93 void tr_list_prepend(tr_list** list, void* data)
94 {
95 tr_list* node = node_alloc();
96
97 node->data = data;
98 node->next = *list;
99
100 if (*list != NULL)
101 {
102 (*list)->prev = node;
103 }
104
105 *list = node;
106 }
107
tr_list_append(tr_list ** list,void * data)108 void tr_list_append(tr_list** list, void* data)
109 {
110 tr_list* node = node_alloc();
111
112 node->data = data;
113
114 if (*list == NULL)
115 {
116 *list = node;
117 }
118 else
119 {
120 tr_list* l = *list;
121
122 while (l->next != NULL)
123 {
124 l = l->next;
125 }
126
127 l->next = node;
128 node->prev = l;
129 }
130 }
131
tr_list_find_data(tr_list * list,void const * data)132 static tr_list* tr_list_find_data(tr_list* list, void const* data)
133 {
134 for (; list != NULL; list = list->next)
135 {
136 if (list->data == data)
137 {
138 return list;
139 }
140 }
141
142 return NULL;
143 }
144
tr_list_remove_node(tr_list ** list,tr_list * node)145 static void* tr_list_remove_node(tr_list** list, tr_list* node)
146 {
147 void* data;
148 tr_list* prev = node != NULL ? node->prev : NULL;
149 tr_list* next = node != NULL ? node->next : NULL;
150
151 if (prev != NULL)
152 {
153 prev->next = next;
154 }
155
156 if (next != NULL)
157 {
158 next->prev = prev;
159 }
160
161 if (*list == node)
162 {
163 *list = next;
164 }
165
166 data = node != NULL ? node->data : NULL;
167 node_free(node);
168 return data;
169 }
170
tr_list_pop_front(tr_list ** list)171 void* tr_list_pop_front(tr_list** list)
172 {
173 void* ret = NULL;
174
175 if (*list != NULL)
176 {
177 ret = (*list)->data;
178 tr_list_remove_node(list, *list);
179 }
180
181 return ret;
182 }
183
tr_list_remove_data(tr_list ** list,void const * data)184 void* tr_list_remove_data(tr_list** list, void const* data)
185 {
186 return tr_list_remove_node(list, tr_list_find_data(*list, data));
187 }
188
tr_list_remove(tr_list ** list,void const * b,TrListCompareFunc compare_func)189 void* tr_list_remove(tr_list** list, void const* b, TrListCompareFunc compare_func)
190 {
191 return tr_list_remove_node(list, tr_list_find(*list, b, compare_func));
192 }
193
tr_list_find(tr_list * list,void const * b,TrListCompareFunc func)194 tr_list* tr_list_find(tr_list* list, void const* b, TrListCompareFunc func)
195 {
196 for (; list != NULL; list = list->next)
197 {
198 if (func(list->data, b) == 0)
199 {
200 return list;
201 }
202 }
203
204 return NULL;
205 }
206
tr_list_insert_sorted(tr_list ** list,void * data,TrListCompareFunc compare)207 void tr_list_insert_sorted(tr_list** list, void* data, TrListCompareFunc compare)
208 {
209 /* find the node that we'll insert this data before */
210 tr_list* next_node = NULL;
211
212 for (tr_list* l = *list; l != NULL; l = l->next)
213 {
214 int const c = (*compare)(data, l->data);
215
216 if (c <= 0)
217 {
218 next_node = l;
219 break;
220 }
221 }
222
223 if (next_node == NULL)
224 {
225 tr_list_append(list, data);
226 }
227 else if (next_node == *list)
228 {
229 tr_list_prepend(list, data);
230 }
231 else
232 {
233 tr_list* node = node_alloc();
234 node->data = data;
235 node->prev = next_node->prev;
236 node->next = next_node;
237 node->prev->next = node;
238 node->next->prev = node;
239 }
240 }
241
tr_list_size(tr_list const * list)242 int tr_list_size(tr_list const* list)
243 {
244 int size = 0;
245
246 while (list != NULL)
247 {
248 ++size;
249 list = list->next;
250 }
251
252 return size;
253 }
254