1 /*
2 * Copyright 2008-2013 Various Authors
3 * Copyright 2006 Timo Hirvonen
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation; either version 2 of the
8 * License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include "track.h"
20 #include "iter.h"
21 #include "search_mode.h"
22 #include "window.h"
23 #include "options.h"
24 #include "uchar.h"
25 #include "xmalloc.h"
26 #include "debug.h"
27 #include "misc.h"
28
29 #include <string.h>
30
simple_track_init(struct simple_track * track,struct track_info * ti)31 void simple_track_init(struct simple_track *track, struct track_info *ti)
32 {
33 track->info = ti;
34 track->marked = 0;
35 RB_CLEAR_NODE(&track->tree_node);
36 }
37
simple_track_new(struct track_info * ti)38 struct simple_track *simple_track_new(struct track_info *ti)
39 {
40 struct simple_track *t = xnew(struct simple_track, 1);
41
42 track_info_ref(ti);
43 simple_track_init(t, ti);
44 return t;
45 }
46
GENERIC_ITER_PREV(simple_track_get_prev,struct simple_track,node)47 GENERIC_ITER_PREV(simple_track_get_prev, struct simple_track, node)
48 GENERIC_ITER_NEXT(simple_track_get_next, struct simple_track, node)
49
50 int simple_track_search_get_current(void *data, struct iter *iter)
51 {
52 return window_get_sel(data, iter);
53 }
54
_simple_track_search_matches(struct iter * iter,const char * text)55 int _simple_track_search_matches(struct iter *iter, const char *text)
56 {
57 unsigned int flags = TI_MATCH_TITLE;
58 struct simple_track *track = iter_to_simple_track(iter);
59
60 if (!search_restricted)
61 flags |= TI_MATCH_ARTIST | TI_MATCH_ALBUM | TI_MATCH_ALBUMARTIST;
62
63 return track_info_matches(track->info, text, flags);
64 }
65
simple_track_search_matches(void * data,struct iter * iter,const char * text)66 int simple_track_search_matches(void *data, struct iter *iter, const char *text)
67 {
68 int rc = _simple_track_search_matches(iter, text);
69 if (rc)
70 window_set_sel(data, iter);
71 return rc;
72 }
73
shuffle_insert(struct rb_root * root,struct shuffle_track * previous,struct shuffle_track * next)74 void shuffle_insert(struct rb_root *root, struct shuffle_track *previous, struct shuffle_track *next)
75 {
76 BUG_ON(root == NULL);
77 BUG_ON(next == NULL);
78
79 if (previous == next)
80 return;
81 rb_erase(&next->tree_node, root);
82
83 struct rb_node *parent = previous ? &previous->tree_node : NULL;
84 struct rb_node **new = parent ? &parent->rb_right : &root->rb_node;
85 while (*new) {
86 parent = *new;
87 new = &(*new)->rb_left;
88 }
89
90 rb_link_node(&next->tree_node, parent, new);
91 rb_insert_color(&next->tree_node, root);
92 }
93
shuffle_list_get_next(struct rb_root * root,struct shuffle_track * cur,int (* filter_callback)(const struct simple_track *))94 struct shuffle_track *shuffle_list_get_next(struct rb_root *root, struct shuffle_track *cur,
95 int (*filter_callback)(const struct simple_track *))
96 {
97 struct rb_node *node;
98
99 if (!cur)
100 return tree_node_to_shuffle_track(rb_first(root));
101
102 node = rb_next(&cur->tree_node);
103 again:
104 while (node) {
105 struct shuffle_track *track = tree_node_to_shuffle_track(node);
106
107 if (filter_callback((struct simple_track *)track))
108 return track;
109 node = rb_next(node);
110 }
111 if (repeat) {
112 if (auto_reshuffle)
113 shuffle_list_reshuffle(root);
114 node = rb_first(root);
115 goto again;
116 }
117 return NULL;
118 }
119
shuffle_list_get_prev(struct rb_root * root,struct shuffle_track * cur,int (* filter_callback)(const struct simple_track *))120 struct shuffle_track *shuffle_list_get_prev(struct rb_root *root, struct shuffle_track *cur,
121 int (*filter_callback)(const struct simple_track *))
122 {
123 struct rb_node *node;
124
125 if (!cur)
126 return tree_node_to_shuffle_track(rb_last(root));
127
128 node = rb_prev(&cur->tree_node);
129 again:
130 while (node) {
131 struct shuffle_track *track = tree_node_to_shuffle_track(node);
132
133 if (filter_callback((struct simple_track *)track))
134 return track;
135 node = rb_prev(node);
136 }
137 if (repeat) {
138 if (auto_reshuffle)
139 shuffle_list_reshuffle(root);
140 node = rb_last(root);
141 goto again;
142 }
143 return NULL;
144 }
145
simple_list_get_next(struct list_head * head,struct simple_track * cur,int (* filter_callback)(const struct simple_track *))146 struct simple_track *simple_list_get_next(struct list_head *head, struct simple_track *cur,
147 int (*filter_callback)(const struct simple_track *))
148 {
149 struct list_head *item;
150
151 if (cur == NULL)
152 return to_simple_track(head->next);
153
154 item = cur->node.next;
155 again:
156 while (item != head) {
157 struct simple_track *track = to_simple_track(item);
158
159 if (filter_callback(track))
160 return track;
161 item = item->next;
162 }
163 item = head->next;
164 if (repeat)
165 goto again;
166 return NULL;
167 }
168
simple_list_get_prev(struct list_head * head,struct simple_track * cur,int (* filter_callback)(const struct simple_track *))169 struct simple_track *simple_list_get_prev(struct list_head *head, struct simple_track *cur,
170 int (*filter_callback)(const struct simple_track *))
171 {
172 struct list_head *item;
173
174 if (cur == NULL)
175 return to_simple_track(head->next);
176
177 item = cur->node.prev;
178 again:
179 while (item != head) {
180 struct simple_track *track = to_simple_track(item);
181
182 if (filter_callback(track))
183 return track;
184 item = item->prev;
185 }
186 item = head->prev;
187 if (repeat)
188 goto again;
189 return NULL;
190 }
191
sorted_list_add_track(struct list_head * head,struct rb_root * tree_root,struct simple_track * track,const sort_key_t * keys,int tiebreak)192 void sorted_list_add_track(struct list_head *head, struct rb_root *tree_root, struct simple_track *track,
193 const sort_key_t *keys, int tiebreak)
194 {
195 struct rb_node **new = &(tree_root->rb_node), *parent = NULL, *curr, *next;
196 struct list_head *node;
197 int result = 0;
198
199 /* try to locate track in tree */
200 while (*new) {
201 const struct simple_track *t = tree_node_to_simple_track(*new);
202 result = track_info_cmp(track->info, t->info, keys);
203
204 parent = *new;
205 if (result < 0)
206 new = &(parent->rb_left);
207 else if (result > 0)
208 new = &(parent->rb_right);
209 else
210 break;
211 }
212
213 /* duplicate is present in the tree */
214 if (parent && result == 0) {
215 if (tiebreak < 0) {
216 node = &(tree_node_to_simple_track(parent)->node);
217 rb_replace_node(parent, &track->tree_node, tree_root);
218 RB_CLEAR_NODE(parent);
219 } else {
220 next = rb_next(parent);
221 node = next ? &(tree_node_to_simple_track(next)->node) : head;
222 }
223 } else {
224 rb_link_node(&track->tree_node, parent, new);
225 curr = *new;
226 rb_insert_color(&track->tree_node, tree_root);
227 if (result < 0) {
228 node = &(tree_node_to_simple_track(parent)->node);
229 } else if (result > 0) {
230 next = rb_next(curr);
231 node = next ? &(tree_node_to_simple_track(next)->node) : head;
232 } else {
233 /* rbtree was empty, just add after list head */
234 node = head;
235 }
236 }
237 list_add(&track->node, node->prev);
238 }
239
sorted_list_remove_track(struct list_head * head,struct rb_root * tree_root,struct simple_track * track)240 void sorted_list_remove_track(struct list_head *head, struct rb_root *tree_root, struct simple_track *track)
241 {
242 struct simple_track *next_track;
243 struct rb_node *tree_next;
244
245 if (!RB_EMPTY_NODE(&track->tree_node)) {
246 next_track = (track->node.next != head) ? to_simple_track(track->node.next) : NULL;
247 tree_next = rb_next(&track->tree_node);
248
249 if (next_track && (!tree_next || tree_node_to_simple_track(tree_next) != next_track)) {
250 rb_replace_node(&track->tree_node, &next_track->tree_node, tree_root);
251 RB_CLEAR_NODE(&track->tree_node);
252 } else
253 rb_erase(&track->tree_node, tree_root);
254 }
255 list_del(&track->node);
256 }
257
rand_list_rebuild(struct list_head * head,struct rb_root * tree_root)258 void rand_list_rebuild(struct list_head *head, struct rb_root *tree_root)
259 {
260 struct list_head *item, *tmp;
261 struct rb_root tmp_tree = RB_ROOT;
262 struct simple_track **track_array;
263 static const sort_key_t empty_sort_keys[] = { SORT_INVALID };
264
265 unsigned int len = 0, track_cnt = 0;
266
267 list_for_each(item, head) {
268 len++;
269 }
270 track_array = xmalloc(len * sizeof(track_array[0]));
271
272 LIST_HEAD(tmp_head);
273 list_for_each_safe(item, tmp, head) {
274 struct simple_track *track = to_simple_track(item);
275 sorted_list_remove_track(head, tree_root, track);
276 track_array[track_cnt] = track;
277 track_cnt++;
278 }
279 shuffle_array(track_array, len, sizeof(track_array[0]));
280 for (unsigned int i=0; i<len; i++) {
281 sorted_list_add_track(&tmp_head, &tmp_tree, track_array[i], empty_sort_keys, 0);
282 }
283 free(track_array);
284
285 tree_root->rb_node = tmp_tree.rb_node;
286 _list_add(head, tmp_head.prev, tmp_head.next);
287 }
288
sorted_list_rebuild(struct list_head * head,struct rb_root * tree_root,const sort_key_t * keys)289 void sorted_list_rebuild(struct list_head *head, struct rb_root *tree_root, const sort_key_t *keys)
290 {
291 struct list_head *item, *tmp;
292 struct rb_root tmp_tree = RB_ROOT;
293 LIST_HEAD(tmp_head);
294
295 list_for_each_safe(item, tmp, head) {
296 struct simple_track *track = to_simple_track(item);
297 sorted_list_remove_track(head, tree_root, track);
298 sorted_list_add_track(&tmp_head, &tmp_tree, track, keys, 0);
299 }
300 tree_root->rb_node = tmp_tree.rb_node;
301 _list_add(head, tmp_head.prev, tmp_head.next);
302 }
303
compare_rand(const struct rb_node * a,const struct rb_node * b)304 static int compare_rand(const struct rb_node *a, const struct rb_node *b)
305 {
306 struct shuffle_track *tr_a = tree_node_to_shuffle_track(a);
307 struct shuffle_track *tr_b = tree_node_to_shuffle_track(b);
308
309 if (tr_a->rand < tr_b->rand)
310 return -1;
311 if (tr_a->rand > tr_b->rand)
312 return +1;
313
314 return 0;
315 }
316
shuffle_track_init(struct shuffle_track * track)317 static void shuffle_track_init(struct shuffle_track *track)
318 {
319 track->rand = rand() / ((double) RAND_MAX + 1);
320 }
321
shuffle_list_add(struct shuffle_track * track,struct rb_root * tree_root)322 void shuffle_list_add(struct shuffle_track *track, struct rb_root *tree_root)
323 {
324 struct rb_node **new = &(tree_root->rb_node), *parent = NULL;
325
326 shuffle_track_init(track);
327
328 /* try to locate track in tree */
329 while (*new) {
330 int result = compare_rand(&track->tree_node, *new);
331
332 parent = *new;
333 if (result < 0)
334 new = &((*new)->rb_left);
335 else if (result > 0)
336 new = &((*new)->rb_right);
337 else {
338 /* very unlikely, try again! */
339 shuffle_list_add(track, tree_root);
340 return;
341 }
342 }
343
344 rb_link_node(&track->tree_node, parent, new);
345 rb_insert_color(&track->tree_node, tree_root);
346 }
347
shuffle_list_reshuffle(struct rb_root * tree_root)348 void shuffle_list_reshuffle(struct rb_root *tree_root)
349 {
350 struct rb_node *node, *tmp;
351 struct rb_root tmptree = RB_ROOT;
352
353 rb_for_each_safe(node, tmp, tree_root) {
354 struct shuffle_track *track = tree_node_to_shuffle_track(node);
355 rb_erase(node, tree_root);
356 shuffle_list_add(track, &tmptree);
357 }
358
359 tree_root->rb_node = tmptree.rb_node;
360 }
361
362 /* expensive */
list_add_rand(struct list_head * head,struct list_head * node,int nr)363 void list_add_rand(struct list_head *head, struct list_head *node, int nr)
364 {
365 struct list_head *item;
366 int pos;
367
368 pos = rand() % (nr + 1);
369 item = head;
370 if (pos <= nr / 2) {
371 while (pos) {
372 item = item->next;
373 pos--;
374 }
375 /* add after item */
376 list_add(node, item);
377 } else {
378 pos = nr - pos;
379 while (pos) {
380 item = item->prev;
381 pos--;
382 }
383 /* add before item */
384 list_add_tail(node, item);
385 }
386 }
387
simple_list_for_each_marked(struct list_head * head,track_info_cb cb,void * data,int reverse)388 int simple_list_for_each_marked(struct list_head *head, track_info_cb cb,
389 void *data, int reverse)
390 {
391 struct simple_track *t;
392 int rc = 0;
393
394 if (reverse) {
395 list_for_each_entry_reverse(t, head, node) {
396 if (t->marked) {
397 rc = cb(data, t->info);
398 if (rc)
399 break;
400 }
401 }
402 } else {
403 list_for_each_entry(t, head, node) {
404 if (t->marked) {
405 rc = cb(data, t->info);
406 if (rc)
407 break;
408 }
409 }
410 }
411 return rc;
412 }
413
simple_list_for_each(struct list_head * head,track_info_cb cb,void * data,int reverse)414 int simple_list_for_each(struct list_head *head, track_info_cb cb, void *data,
415 int reverse)
416 {
417 struct simple_track *t;
418 int rc = 0;
419
420 if (reverse) {
421 list_for_each_entry_reverse(t, head, node) {
422 if ((rc = cb(data, t->info)))
423 break;
424 }
425 } else {
426 list_for_each_entry(t, head, node) {
427 if ((rc = cb(data, t->info)))
428 break;
429 }
430 }
431
432 return rc;
433 }
434