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 "lib.h"
20 #include "search_mode.h"
21 #include "xmalloc.h"
22 #include "utils.h"
23 #include "debug.h"
24 #include "mergesort.h"
25 #include "options.h"
26 #include "u_collate.h"
27 #include "rbtree.h"
28
29 #include <ctype.h>
30 #include <stdio.h>
31 #include <string.h>
32 #include <strings.h>
33
34 struct searchable *tree_searchable;
35 struct window *lib_tree_win;
36 struct window *lib_track_win;
37 struct window *lib_cur_win;
38 struct rb_root lib_artist_root;
39
40 struct track_iter {
41 struct rb_root *root;
42 struct tree_track *track;
43 struct album *album;
44 };
45
tree_album_selected(void)46 static inline int tree_album_selected(void)
47 {
48 return iter_to_album(&lib_tree_win->sel) != NULL;
49 }
50
track_visible(struct tree_track * track)51 static inline int track_visible(struct tree_track *track)
52 {
53 if (tree_album_selected())
54 return track->album == iter_to_album(&lib_tree_win->sel);
55 else if (show_all_tracks)
56 return track->album->artist == iter_to_artist(&lib_tree_win->sel);
57 else
58 return 0;
59 }
60
tree_search_track_to_iter(struct tree_track * track,struct iter * iter)61 static inline void tree_search_track_to_iter(struct tree_track *track, struct iter *iter)
62 {
63 iter->data0 = &lib_artist_root;
64 iter->data1 = track;
65 iter->data2 = NULL;
66 }
67
album_to_iter(struct album * album,struct iter * iter)68 static inline void album_to_iter(struct album *album, struct iter *iter)
69 {
70 iter->data0 = &lib_artist_root;
71 iter->data1 = album->artist;
72 iter->data2 = album;
73 }
74
album_to_track_iter(struct album * album,struct track_iter * iter)75 static inline void album_to_track_iter(struct album *album, struct track_iter *iter)
76 {
77 iter->root = &album->artist->album_root;
78 iter->album = album;
79 iter->track = (struct tree_track *)album;
80 }
81
artist_to_iter(struct artist * artist,struct iter * iter)82 static inline void artist_to_iter(struct artist *artist, struct iter *iter)
83 {
84 iter->data0 = &lib_artist_root;
85 iter->data1 = artist;
86 iter->data2 = NULL;
87 }
88
tree_track_to_track_iter(struct tree_track * track,struct track_iter * iter)89 static inline void tree_track_to_track_iter(struct tree_track *track, struct track_iter *iter)
90 {
91 if (tree_album_selected()) {
92 iter->root = &track->album->track_root;
93 iter->album = NULL;
94 } else {
95 iter->root = &track->album->artist->album_root;
96 iter->album = track->album;
97 }
98 iter->track = track;
99 }
100
tree_set_expand_artist(struct artist * artist,int expand)101 static void tree_set_expand_artist(struct artist *artist, int expand)
102 {
103 struct iter sel;
104
105 if (!expand) {
106 /* deselect album, select artist */
107 artist_to_iter(artist, &sel);
108 window_set_sel(lib_tree_win, &sel);
109
110 if (!show_all_tracks)
111 lib_cur_win = lib_tree_win;
112 }
113 artist->expanded = expand;
114 window_changed(lib_tree_win);
115 }
116
117 /* tree (search) iterators {{{ */
tree_search_get_prev(struct iter * iter)118 static int tree_search_get_prev(struct iter *iter)
119 {
120 struct rb_root *root = iter->data0;
121 struct tree_track *track = iter->data1;
122 struct artist *artist;
123 struct album *album;
124
125 BUG_ON(iter->data2);
126 if (root == NULL)
127 return 0;
128 if (track == NULL) {
129 /* head, get last track */
130 if (rb_root_empty(root)) {
131 /* empty, iter points to the head already */
132 return 0;
133 }
134 artist = to_artist(rb_last(root));
135 album = to_album(rb_last(&artist->album_root));
136 iter->data1 = to_tree_track(rb_last(&album->track_root));
137 return 1;
138 }
139 /* prev track */
140 if (rb_prev(&track->tree_node) == NULL || search_restricted) {
141 /* prev album */
142 if (rb_prev(&track->album->tree_node) == NULL) {
143 /* prev artist */
144 if (rb_prev(&track->album->artist->tree_node) == NULL)
145 return 0;
146 artist = to_artist(rb_prev(&track->album->artist->tree_node));
147 album = to_album(rb_last(&artist->album_root));
148 track = to_tree_track(rb_last(&album->track_root));
149 } else {
150 album = to_album(rb_prev(&track->album->tree_node));
151 track = to_tree_track(rb_last(&album->track_root));
152 }
153 } else {
154 track = to_tree_track(rb_prev(&track->tree_node));
155 }
156 iter->data1 = track;
157 return 1;
158 }
159
tree_search_get_next(struct iter * iter)160 static int tree_search_get_next(struct iter *iter)
161 {
162 struct rb_root *root = iter->data0;
163 struct tree_track *track = iter->data1;
164 struct artist *artist;
165 struct album *album;
166
167 BUG_ON(iter->data2);
168 if (root == NULL)
169 return 0;
170 if (track == NULL) {
171 /* head, get first track */
172 if (rb_root_empty(root)) {
173 /* empty, iter points to the head already */
174 return 0;
175 }
176 artist = to_artist(rb_first(root));
177 album = to_album(rb_first(&artist->album_root));
178 iter->data1 = to_tree_track(rb_first(&album->track_root));
179 return 1;
180 }
181 /* next track */
182 if (rb_next(&track->tree_node) == NULL || search_restricted) {
183 /* next album */
184 if (rb_next(&track->album->tree_node) == NULL) {
185 /* next artist */
186 if (rb_next(&track->album->artist->tree_node) == NULL)
187 return 0;
188 artist = to_artist(rb_next(&track->album->artist->tree_node));
189 album = to_album(rb_first(&artist->album_root));
190 track = to_tree_track(rb_first(&album->track_root));
191 } else {
192 album = to_album(rb_next(&track->album->tree_node));
193 track = to_tree_track(rb_first(&album->track_root));
194 }
195 } else {
196 track = to_tree_track(rb_next(&track->tree_node));
197 }
198 iter->data1 = track;
199 return 1;
200 }
201 /* }}} */
202
203 /* tree window iterators {{{ */
tree_get_prev(struct iter * iter)204 static int tree_get_prev(struct iter *iter)
205 {
206 struct rb_root *root = iter->data0;
207 struct artist *artist = iter->data1;
208 struct album *album = iter->data2;
209
210 BUG_ON(root == NULL);
211 BUG_ON(artist == NULL && album != NULL);
212 if (artist == NULL) {
213 /* head, get last artist and/or album */
214 if (rb_root_empty(root)) {
215 /* empty, iter points to the head already */
216 return 0;
217 }
218 artist = to_artist(rb_last(root));
219 if (artist->expanded) {
220 album = to_album(rb_last(&artist->album_root));
221 } else {
222 album = NULL;
223 }
224 iter->data1 = artist;
225 iter->data2 = album;
226 return 1;
227 }
228 if (artist->expanded && album) {
229 /* prev album */
230 if (rb_prev(&album->tree_node) == NULL) {
231 iter->data2 = NULL;
232 return 1;
233 } else {
234 iter->data2 = to_album(rb_prev(&album->tree_node));
235 return 1;
236 }
237 }
238
239 /* prev artist */
240 if (rb_prev(&artist->tree_node) == NULL) {
241 iter->data1 = NULL;
242 iter->data2 = NULL;
243 return 0;
244 }
245 artist = to_artist(rb_prev(&artist->tree_node));
246 iter->data1 = artist;
247 iter->data2 = NULL;
248 if (artist->expanded) {
249 /* last album */
250 iter->data2 = to_album(rb_last(&artist->album_root));
251 }
252 return 1;
253 }
254
tree_get_next(struct iter * iter)255 static int tree_get_next(struct iter *iter)
256 {
257 struct rb_root *root = iter->data0;
258 struct artist *artist = iter->data1;
259 struct album *album = iter->data2;
260
261 BUG_ON(root == NULL);
262 BUG_ON(artist == NULL && album != NULL);
263 if (artist == NULL) {
264 /* head, get first artist */
265 if (rb_root_empty(root)) {
266 /* empty, iter points to the head already */
267 return 0;
268 }
269 iter->data1 = to_artist(rb_first(root));
270 iter->data2 = NULL;
271 return 1;
272 }
273 if (artist->expanded) {
274 /* next album */
275 if (album == NULL) {
276 /* first album */
277 iter->data2 = to_album(rb_first(&artist->album_root));
278 return 1;
279 }
280 if (rb_next(&album->tree_node) != NULL) {
281 iter->data2 = to_album(rb_next(&album->tree_node));
282 return 1;
283 }
284 }
285
286 /* next artist */
287 if (rb_next(&artist->tree_node) == NULL) {
288 iter->data1 = NULL;
289 iter->data2 = NULL;
290 return 0;
291 }
292 iter->data1 = to_artist(rb_next(&artist->tree_node));
293 iter->data2 = NULL;
294 return 1;
295 }
296 /* }}} */
297
GENERIC_TREE_ITER_PREV(tree_track_get_prev_by_album,struct tree_track,tree_node)298 static GENERIC_TREE_ITER_PREV(tree_track_get_prev_by_album, struct tree_track, tree_node)
299 static GENERIC_TREE_ITER_NEXT(tree_track_get_next_by_album, struct tree_track, tree_node)
300
301 /* track window iterators by artist */
302 static int tree_track_get_prev_by_artist(struct iter *iter)
303 {
304 struct track_iter *it = (struct track_iter *)iter;
305
306 /* get last album */
307 if (it->album == NULL) {
308 if (rb_root_empty(it->root))
309 return 0;
310 it->album = to_album(rb_last(it->root));
311 it->track = NULL;
312 return tree_track_get_prev_by_artist(iter);
313 }
314
315 /* get previous album */
316 if (it->track == (struct tree_track *)it->album) {
317 /* no more albums */
318 if (rb_prev(&it->album->tree_node) == NULL)
319 return 0;
320 it->album = to_album(rb_prev(&it->album->tree_node));
321 it->track = NULL;
322 return tree_track_get_prev_by_artist(iter);
323 }
324
325 /* get last track */
326 if (it->track == NULL) {
327 if (rb_root_empty(&it->album->track_root))
328 it->track = (struct tree_track *)it->album;
329 else
330 it->track = to_tree_track(rb_last(&it->album->track_root));
331 return 1;
332 }
333
334 /* get previous track */
335 if (rb_prev(&it->track->tree_node) != NULL) {
336 it->track = to_tree_track(rb_prev(&it->track->tree_node));
337 return 1;
338 }
339
340 /* no more tracks
341 * get album header */
342 it->track = (struct tree_track *)it->album;
343 return 1;
344 }
345
tree_track_get_next_by_artist(struct iter * iter)346 static int tree_track_get_next_by_artist(struct iter *iter)
347 {
348 struct track_iter *it = (struct track_iter *)iter;
349
350 /* get first album */
351 if (it->album == NULL) {
352 if (rb_root_empty(it->root))
353 return 0;
354 it->album = to_album(rb_first(it->root));
355 it->track = (struct tree_track *)it->album;
356 return 1;
357 }
358
359 /* get first track */
360 if (it->track == (struct tree_track *)it->album) {
361 /* this happens when the last track in an album is deleted but
362 * the album header is still referenced in lib_track_win->top
363 * set track = NULL to skip the next `if` without goto */
364 if (rb_root_empty(&it->album->track_root)) {
365 it->track = NULL;
366 } else {
367 it->track = to_tree_track(rb_first(&it->album->track_root));
368 return 1;
369 }
370 }
371
372 /* get next track */
373 if (it->track != NULL && rb_next(&it->track->tree_node) != NULL) {
374 it->track = to_tree_track(rb_next(&it->track->tree_node));
375 return 1;
376 }
377
378 /* no more tracks
379 * get next album */
380 if (rb_next(&it->album->tree_node) != NULL) {
381 it->album = to_album(rb_next(&it->album->tree_node));
382 it->track = (struct tree_track *)it->album;
383 return 1;
384 }
385
386 /* no more albums */
387 return 0;
388 }
389
390 /* track window iterators */
tree_track_get_prev(struct iter * iter)391 static int tree_track_get_prev(struct iter *iter)
392 {
393 if (tree_album_selected())
394 return tree_track_get_prev_by_album(iter);
395 else
396 return tree_track_get_prev_by_artist(iter);
397 }
398
tree_track_get_next(struct iter * iter)399 static int tree_track_get_next(struct iter *iter)
400 {
401 if (tree_album_selected())
402 return tree_track_get_next_by_album(iter);
403 else
404 return tree_track_get_next_by_artist(iter);
405 }
406
407 /* search (tree) {{{ */
tree_search_get_current(void * data,struct iter * iter)408 static int tree_search_get_current(void *data, struct iter *iter)
409 {
410 struct artist *artist;
411 struct album *album;
412 struct tree_track *track;
413 struct iter tmpiter;
414
415 if (rb_root_empty(&lib_artist_root))
416 return 0;
417 if (window_get_sel(lib_track_win, &tmpiter)) {
418 track = iter_to_tree_track(&tmpiter);
419 tree_search_track_to_iter(track, iter);
420 return 1;
421 }
422
423 /* artist not expanded. track_win is empty
424 * set tmp to the first track of the selected artist */
425 window_get_sel(lib_tree_win, &tmpiter);
426 artist = iter_to_artist(&tmpiter);
427 album = to_album(rb_first(&artist->album_root));
428 track = to_tree_track(rb_first(&album->track_root));
429 tree_search_track_to_iter(track, iter);
430 return 1;
431 }
432
iter_to_tree_search_track(const struct iter * iter)433 static inline struct tree_track *iter_to_tree_search_track(const struct iter *iter)
434 {
435 BUG_ON(iter->data0 != &lib_artist_root);
436 return iter->data1;
437 }
438
439 static int tree_search_matches(void *data, struct iter *iter, const char *text);
440
441 static const struct searchable_ops tree_search_ops = {
442 .get_prev = tree_search_get_prev,
443 .get_next = tree_search_get_next,
444 .get_current = tree_search_get_current,
445 .matches = tree_search_matches
446 };
447 /* search (tree) }}} */
448
tree_sel_changed(void)449 static void tree_sel_changed(void)
450 {
451 tree_sel_update(1);
452 }
453
tree_sel_update(int changed)454 void tree_sel_update(int changed)
455 {
456 struct iter sel;
457 struct album *album;
458 struct artist *artist;
459
460 window_get_sel(lib_tree_win, &sel);
461 album = iter_to_album(&sel);
462 artist = show_all_tracks ? iter_to_artist(&sel) : NULL;
463
464 if (album != NULL) {
465 if (changed)
466 window_set_contents(lib_track_win, &album->track_root);
467 } else if (artist != NULL) {
468 window_set_contents(lib_track_win, &artist->album_root);
469 } else {
470 if (lib_cur_win != lib_tree_win) {
471 lib_cur_win = lib_tree_win;
472 lib_tree_win->changed = 1;
473 }
474 window_set_empty(lib_track_win);
475 }
476 }
477
tree_win_get_selected(struct artist ** artist,struct album ** album)478 static inline void tree_win_get_selected(struct artist **artist, struct album **album)
479 {
480 struct iter sel;
481
482 *artist = NULL;
483 *album = NULL;
484 if (window_get_sel(lib_tree_win, &sel)) {
485 *artist = iter_to_artist(&sel);
486 *album = iter_to_album(&sel);
487 }
488 }
489
auto_artist_sort_name(const char * name)490 static char *auto_artist_sort_name(const char *name)
491 {
492 const char *name_orig = name;
493 char *buf;
494
495 if (strncasecmp(name, "the ", 4) != 0)
496 return NULL;
497
498 name += 4;
499 while (isspace((int)*name))
500 ++name;
501
502 if (*name == '\0')
503 return NULL;
504
505 buf = xnew(char, strlen(name_orig) + 2);
506 sprintf(buf, "%s, %c%c%c", name, name_orig[0],
507 name_orig[1],
508 name_orig[2]);
509 return buf;
510 }
511
artist_new(const char * name,const char * sort_name,int is_compilation)512 static struct artist *artist_new(const char *name, const char *sort_name, int is_compilation)
513 {
514 struct artist *a = xnew(struct artist, 1);
515
516 a->name = xstrdup(name);
517 a->sort_name = sort_name ? xstrdup(sort_name) : NULL;
518 a->auto_sort_name = auto_artist_sort_name(name);
519 a->collkey_name = u_strcasecoll_key(a->name);
520 a->collkey_sort_name = u_strcasecoll_key0(a->sort_name);
521 a->collkey_auto_sort_name = u_strcasecoll_key0(a->auto_sort_name);
522 a->expanded = 0;
523 a->is_compilation = is_compilation;
524 rb_root_init(&a->album_root);
525
526 return a;
527 }
528
artist_copy(const struct artist * artist)529 static struct artist *artist_copy(const struct artist *artist)
530 {
531 return artist_new(artist->name, artist->sort_name, artist->is_compilation);
532 }
533
artist_free(struct artist * artist)534 static void artist_free(struct artist *artist)
535 {
536 free(artist->name);
537 free(artist->sort_name);
538 free(artist->auto_sort_name);
539 free(artist->collkey_name);
540 free(artist->collkey_sort_name);
541 free(artist->collkey_auto_sort_name);
542 free(artist);
543 }
544
album_new(struct artist * artist,const char * name,const char * sort_name,int date)545 static struct album *album_new(struct artist *artist, const char *name,
546 const char *sort_name, int date)
547 {
548 struct album *album = xnew(struct album, 1);
549
550 album->name = xstrdup(name);
551 album->sort_name = sort_name ? xstrdup(sort_name) : NULL;
552 album->collkey_name = u_strcasecoll_key(name);
553 album->collkey_sort_name = u_strcasecoll_key0(sort_name);
554 album->date = date;
555 album->min_date = date;
556 rb_root_init(&album->track_root);
557 album->artist = artist;
558
559 return album;
560 }
561
album_free(struct album * album)562 static void album_free(struct album *album)
563 {
564 free(album->name);
565 free(album->sort_name);
566 free(album->collkey_name);
567 free(album->collkey_sort_name);
568 free(album);
569 }
570
track_selectable(struct iter * iter)571 static int track_selectable(struct iter *iter)
572 {
573 struct track_iter *it = (struct track_iter *)iter;
574 return it->album != (struct album *)it->track;
575 }
576
tree_init(void)577 void tree_init(void)
578 {
579 struct iter iter;
580
581 rb_root_init(&lib_artist_root);
582
583 lib_tree_win = window_new(tree_get_prev, tree_get_next);
584 lib_track_win = window_new(tree_track_get_prev, tree_track_get_next);
585 lib_cur_win = lib_tree_win;
586
587 lib_tree_win->sel_changed = tree_sel_changed;
588 lib_track_win->selectable = track_selectable;
589
590 window_set_empty(lib_track_win);
591 window_set_contents(lib_tree_win, &lib_artist_root);
592
593 iter.data0 = &lib_artist_root;
594 iter.data1 = NULL;
595 iter.data2 = NULL;
596 tree_searchable = searchable_new(NULL, &iter, &tree_search_ops);
597 }
598
tree_get_selected(void)599 struct tree_track *tree_get_selected(void)
600 {
601 struct artist *artist;
602 struct album *album;
603 struct tree_track *track;
604 struct iter sel;
605
606 if (rb_root_empty(&lib_artist_root))
607 return NULL;
608
609 tree_win_get_selected(&artist, &album);
610 if (album == NULL && !show_all_tracks) {
611 /* track window is empty
612 * => get first album of the selected artist and first track of that album
613 */
614 album = to_album(rb_first(&artist->album_root));
615 track = to_tree_track(rb_first(&album->track_root));
616 } else {
617 window_get_sel(lib_track_win, &sel);
618 track = iter_to_tree_track(&sel);
619 }
620
621 return track;
622 }
623
tree_activate_selected(void)624 struct track_info *tree_activate_selected(void)
625 {
626 struct track_info *info;
627
628 lib_cur_track = tree_get_selected();
629 if (!lib_cur_track)
630 return NULL;
631
632 lib_tree_win->changed = 1;
633 lib_track_win->changed = 1;
634
635 info = tree_track_info(lib_cur_track);
636 track_info_ref(info);
637 return info;
638 }
639
special_name_cmp(const char * a,const char * collkey_a,const char * b,const char * collkey_b)640 static int special_name_cmp(const char *a, const char *collkey_a,
641 const char *b, const char *collkey_b)
642 {
643 /* keep <Stream> etc. top */
644 int cmp = (*a != '<') - (*b != '<');
645
646 if (cmp)
647 return cmp;
648 return strcmp(collkey_a, collkey_b);
649 }
650
album_sort_collkey(const struct album * a)651 static inline const char *album_sort_collkey(const struct album *a)
652 {
653 if (a->sort_name)
654 return a->collkey_sort_name;
655
656 return a->collkey_name;
657 }
658
special_album_cmp(const struct album * a,const struct album * b)659 static int special_album_cmp(const struct album *a, const struct album *b)
660 {
661 return special_name_cmp(a->name, album_sort_collkey(a), b->name, album_sort_collkey(b));
662 }
663
special_album_cmp_date(const struct album * a,const struct album * b)664 static int special_album_cmp_date(const struct album *a, const struct album *b)
665 {
666 /* keep <Stream> etc. top */
667 int cmp = (*a->name != '<') - (*b->name != '<');
668 if (cmp)
669 return cmp;
670
671 cmp = a->date - b->date;
672 if (cmp)
673 return cmp;
674
675 return strcmp(album_sort_collkey(a), album_sort_collkey(b));
676 }
677
678 /* has to follow the same logic as artist_sort_name() */
artist_sort_collkey(const struct artist * a)679 static inline const char *artist_sort_collkey(const struct artist *a)
680 {
681 if (a->sort_name)
682 return a->collkey_sort_name;
683
684 if (smart_artist_sort && a->auto_sort_name)
685 return a->collkey_auto_sort_name;
686
687 return a->collkey_name;
688 }
689
do_find_artist(const struct artist * artist,struct rb_root * root,struct rb_node *** p_new,struct rb_node ** p_parent)690 static struct artist *do_find_artist(const struct artist *artist,
691 struct rb_root *root,
692 struct rb_node ***p_new,
693 struct rb_node **p_parent)
694 {
695 struct rb_node **new = &(root->rb_node), *parent = NULL;
696 const char *a = artist_sort_name(artist);
697 const char *collkey_a = artist_sort_collkey(artist);
698
699 while (*new) {
700 struct artist *cur_artist = to_artist(*new);
701 const char *b = artist_sort_name(cur_artist);
702 const char *collkey_b = artist_sort_collkey(cur_artist);
703 int result = special_name_cmp(a, collkey_a, b, collkey_b);
704
705 parent = *new;
706 if (result < 0)
707 new = &((*new)->rb_left);
708 else if (result > 0)
709 new = &((*new)->rb_right);
710 else
711 return cur_artist;
712 }
713 if (p_new)
714 *p_new = new;
715 if (p_parent)
716 *p_parent = parent;
717 return NULL;
718 }
719
720 /* search (tree) {{{ */
721 static struct artist *collapse_artist;
722
tree_search_matches(void * data,struct iter * iter,const char * text)723 static int tree_search_matches(void *data, struct iter *iter, const char *text)
724 {
725 struct tree_track *track;
726 struct iter tmpiter;
727 unsigned int flags = TI_MATCH_ARTIST | TI_MATCH_ALBUM | TI_MATCH_ALBUMARTIST;
728
729 if (!search_restricted)
730 flags |= TI_MATCH_TITLE;
731 track = iter_to_tree_search_track(iter);
732 if (!track_info_matches(tree_track_info(track), text, flags))
733 return 0;
734
735 if (auto_expand_albums_search) {
736 /* collapse old search result */
737 if (collapse_artist) {
738 struct artist *artist = do_find_artist(collapse_artist, &lib_artist_root, NULL, NULL);
739 if (artist && artist != track->album->artist) {
740 if (artist->expanded)
741 tree_set_expand_artist(artist, 0);
742 artist_free(collapse_artist);
743 collapse_artist = (!track->album->artist->expanded) ? artist_copy(track->album->artist) : NULL;
744 }
745 } else if (!track->album->artist->expanded) {
746 collapse_artist = artist_copy(track->album->artist);
747 }
748
749 track->album->artist->expanded = 1;
750 album_to_iter(track->album, &tmpiter);
751 } else {
752 artist_to_iter(track->album->artist, &tmpiter);
753 }
754
755 window_set_sel(lib_tree_win, &tmpiter);
756
757 tree_track_to_track_iter(track, (struct track_iter *)&tmpiter);
758 window_set_sel(lib_track_win, &tmpiter);
759
760 return 1;
761 }
762 /* search (tree) }}} */
763
insert_artist(struct artist * artist,struct rb_root * root)764 static void insert_artist(struct artist *artist, struct rb_root *root)
765 {
766 struct rb_node **new = &(root->rb_node), *parent = NULL;
767 struct artist *found;
768
769 found = do_find_artist(artist, root, &new, &parent);
770 if (!found) {
771 rb_link_node(&artist->tree_node, parent, new);
772 rb_insert_color(&artist->tree_node, root);
773 }
774 }
775
add_artist(struct artist * artist)776 static void add_artist(struct artist *artist)
777 {
778 insert_artist(artist, &lib_artist_root);
779 }
780
find_artist(const struct artist * artist)781 static struct artist *find_artist(const struct artist *artist)
782 {
783 return do_find_artist(artist, &lib_artist_root, NULL, NULL);
784 }
785
do_find_album(const struct album * album,int (* cmp)(const struct album *,const struct album *),struct rb_node *** p_new,struct rb_node ** p_parent)786 static struct album *do_find_album(const struct album *album,
787 int (*cmp)(const struct album *, const struct album *),
788 struct rb_node ***p_new,
789 struct rb_node **p_parent)
790 {
791 struct rb_node **new = &(album->artist->album_root.rb_node), *parent = NULL;
792
793 while (*new) {
794 struct album *a = to_album(*new);
795
796 int result = cmp(album, a);
797
798 parent = *new;
799 if (result < 0)
800 new = &((*new)->rb_left);
801 else if (result > 0)
802 new = &((*new)->rb_right);
803 else
804 return a;
805 }
806 if (p_new)
807 *p_new = new;
808 if (p_parent)
809 *p_parent = parent;
810 return NULL;
811 }
812
find_album(const struct album * album)813 static struct album *find_album(const struct album *album)
814 {
815 struct album *a;
816 struct rb_node *tmp;
817
818 /* do a linear search because we want find albums with different date */
819 rb_for_each_entry(a, tmp, &album->artist->album_root, tree_node) {
820 if (special_album_cmp(album, a) == 0)
821 return a;
822 }
823 return NULL;
824 }
825
add_album(struct album * album)826 static void add_album(struct album *album)
827 {
828 struct rb_node **new = &(album->artist->album_root.rb_node), *parent = NULL;
829 struct album *found;
830
831 /*
832 * Sort regular albums by date, but sort compilations
833 * alphabetically.
834 */
835 found = do_find_album(album,
836 album->artist->is_compilation ? special_album_cmp
837 : special_album_cmp_date,
838 &new, &parent);
839 if (!found) {
840 rb_link_node(&album->tree_node, parent, new);
841 rb_insert_color(&album->tree_node, &album->artist->album_root);
842 }
843 }
844
album_add_track(struct album * album,struct tree_track * track)845 static void album_add_track(struct album *album, struct tree_track *track)
846 {
847 /*
848 * NOTE: This is not perfect. You should ignore track numbers if
849 * either is unset and use filename instead, but usually you
850 * have all track numbers set or all unset (within one album
851 * of course).
852 */
853 static const sort_key_t album_track_sort_keys[] = {
854 SORT_DISCNUMBER, SORT_TRACKNUMBER, SORT_FILENAME, SORT_INVALID
855 };
856 struct rb_node **new = &(album->track_root.rb_node), *parent = NULL;
857
858 track->album = album;
859 while (*new) {
860 const struct simple_track *a = (const struct simple_track *) track;
861 const struct simple_track *b = (const struct simple_track *) to_tree_track(*new);
862 int result = track_info_cmp(a->info, b->info, album_track_sort_keys);
863
864 parent = *new;
865 if (result < 0)
866 new = &((*new)->rb_left);
867 else
868 new = &((*new)->rb_right);
869 }
870
871 rb_link_node(&track->tree_node, parent, new);
872 rb_insert_color(&track->tree_node, &album->track_root);
873 }
874
tree_artist_name(const struct track_info * ti)875 static const char *tree_artist_name(const struct track_info* ti)
876 {
877 const char *val = ti->albumartist;
878
879 if (ti->is_va_compilation)
880 val = "<Various Artists>";
881 if (!val || strcmp(val, "") == 0)
882 val = "<No Name>";
883
884 return val;
885 }
886
tree_album_name(const struct track_info * ti)887 static const char *tree_album_name(const struct track_info* ti)
888 {
889 const char *val = ti->album;
890
891 if (!val || strcmp(val, "") == 0)
892 val = "<No Name>";
893
894 return val;
895 }
896
remove_album(struct album * album)897 static void remove_album(struct album *album)
898 {
899 if (album->artist->expanded) {
900 struct iter iter;
901
902 album_to_iter(album, &iter);
903 window_row_vanishes(lib_tree_win, &iter);
904 }
905 rb_erase(&album->tree_node, &album->artist->album_root);
906 }
907
remove_artist(struct artist * artist)908 static void remove_artist(struct artist *artist)
909 {
910 struct iter iter;
911
912 artist_to_iter(artist, &iter);
913 window_row_vanishes(lib_tree_win, &iter);
914 rb_erase(&artist->tree_node, &lib_artist_root);
915 }
916
tree_add_track(struct tree_track * track)917 void tree_add_track(struct tree_track *track)
918 {
919 const struct track_info *ti = tree_track_info(track);
920 const char *album_name, *artist_name, *artistsort_name = NULL;
921 const char *albumsort_name = NULL;
922 struct artist *artist, *new_artist;
923 struct album *album, *new_album;
924 int date;
925 int is_va_compilation = 0;
926
927 date = ti->originaldate;
928 if (date < 0)
929 date = ti->date;
930
931 if (is_http_url(ti->filename)) {
932 artist_name = "<Stream>";
933 album_name = "<Stream>";
934 } else {
935 album_name = tree_album_name(ti);
936 artist_name = tree_artist_name(ti);
937 artistsort_name = ti->artistsort;
938 albumsort_name = ti->albumsort;
939
940 is_va_compilation = ti->is_va_compilation;
941 }
942
943 new_artist = artist_new(artist_name, artistsort_name, is_va_compilation);
944 album = NULL;
945
946 artist = find_artist(new_artist);
947 if (artist) {
948 artist_free(new_artist);
949 new_album = album_new(artist, album_name, albumsort_name, date);
950 album = find_album(new_album);
951 if (album)
952 album_free(new_album);
953 } else
954 new_album = album_new(new_artist, album_name, albumsort_name, date);
955
956 if (artist) {
957 int changed = 0;
958 /* If it makes sense to update sort_name, do it */
959 if (!artist->sort_name && artistsort_name) {
960 artist->sort_name = xstrdup(artistsort_name);
961 artist->collkey_sort_name = u_strcasecoll_key(artistsort_name);
962 changed = 1;
963 }
964 /* If names differ, update */
965 if (!artist->auto_sort_name) {
966 char *auto_sort_name = auto_artist_sort_name(artist_name);
967 if (auto_sort_name) {
968 free(artist->name);
969 free(artist->collkey_name);
970 artist->name = xstrdup(artist_name);
971 artist->collkey_name = u_strcasecoll_key(artist_name);
972 artist->auto_sort_name = auto_sort_name;
973 artist->collkey_auto_sort_name = u_strcasecoll_key(auto_sort_name);
974 changed = 1;
975 }
976 }
977 if (changed) {
978 remove_artist(artist);
979 add_artist(artist);
980 window_changed(lib_tree_win);
981 }
982 }
983
984 if (album) {
985 album_add_track(album, track);
986
987 /* If it makes sense to update album date, do it */
988 if (album->date < date) {
989 album->date = date;
990
991 remove_album(album);
992 add_album(album);
993 if (artist->expanded)
994 window_changed(lib_tree_win);
995 }
996
997 if (album->min_date <= 0 || (album->min_date > date && date > 0)) {
998 album->min_date = date;
999
1000 remove_album(album);
1001 add_album(album);
1002 if (artist->expanded)
1003 window_changed(lib_tree_win);
1004 }
1005
1006 } else if (artist) {
1007 add_album(new_album);
1008 album_add_track(new_album, track);
1009
1010 if (artist->expanded)
1011 window_changed(lib_tree_win);
1012 } else {
1013 add_artist(new_artist);
1014 add_album(new_album);
1015 album_add_track(new_album, track);
1016
1017 window_changed(lib_tree_win);
1018 }
1019
1020 if (track_visible(track))
1021 window_changed(lib_track_win);
1022 }
1023
remove_sel_artist(struct artist * artist)1024 static void remove_sel_artist(struct artist *artist)
1025 {
1026 struct rb_node *a_node, *a_tmp;
1027
1028 rb_for_each_safe(a_node, a_tmp, &artist->album_root) {
1029 struct rb_node *t_node, *t_tmp;
1030 struct album *album = to_album(a_node);
1031
1032 rb_for_each_safe(t_node, t_tmp, &album->track_root) {
1033 struct tree_track *track = to_tree_track(t_node);
1034
1035 editable_remove_track(&lib_editable, (struct simple_track *)track);
1036 }
1037 /* all tracks removed => album removed
1038 * if the last album was removed then the artist was removed too
1039 */
1040 }
1041 }
1042
remove_sel_album(struct album * album)1043 static void remove_sel_album(struct album *album)
1044 {
1045 struct rb_node *node, *tmp;
1046
1047 rb_for_each_safe(node, tmp, &album->track_root) {
1048 struct tree_track *track = to_tree_track(node);
1049
1050 editable_remove_track(&lib_editable, (struct simple_track *)track);
1051 }
1052 }
1053
tree_win_remove_sel(void)1054 static void tree_win_remove_sel(void)
1055 {
1056 struct artist *artist;
1057 struct album *album;
1058
1059 tree_win_get_selected(&artist, &album);
1060 if (album) {
1061 remove_sel_album(album);
1062 } else if (artist) {
1063 remove_sel_artist(artist);
1064 }
1065 }
1066
track_win_remove_sel(void)1067 static void track_win_remove_sel(void)
1068 {
1069 struct iter sel;
1070 struct tree_track *track;
1071
1072 if (window_get_sel(lib_track_win, &sel)) {
1073 track = iter_to_tree_track(&sel);
1074 BUG_ON(track == NULL);
1075 editable_remove_track(&lib_editable, (struct simple_track *)track);
1076 }
1077 }
1078
tree_toggle_active_window(void)1079 void tree_toggle_active_window(void)
1080 {
1081 if (lib_cur_win == lib_tree_win) {
1082 struct artist *artist;
1083 struct album *album;
1084
1085 tree_win_get_selected(&artist, &album);
1086 if (album || (artist && show_all_tracks)) {
1087 lib_cur_win = lib_track_win;
1088 lib_tree_win->changed = 1;
1089 lib_track_win->changed = 1;
1090 }
1091 } else if (lib_cur_win == lib_track_win) {
1092 lib_cur_win = lib_tree_win;
1093 lib_tree_win->changed = 1;
1094 lib_track_win->changed = 1;
1095 }
1096 }
1097
tree_toggle_expand_artist(void)1098 void tree_toggle_expand_artist(void)
1099 {
1100 struct track_iter sel;
1101 struct artist *artist;
1102 struct album *album;
1103 struct tree_track *track;
1104
1105 tree_win_get_selected(&artist, &album);
1106 if (album != NULL && show_all_tracks) {
1107 window_get_sel(lib_track_win, (struct iter *)&sel);
1108 track = sel.track;
1109 tree_set_expand_artist(artist, !artist->expanded);
1110 tree_track_to_track_iter(track, &sel);
1111 window_set_sel(lib_track_win, (struct iter *)&sel);
1112 } else if (artist != NULL) {
1113 tree_set_expand_artist(artist, !artist->expanded);
1114 }
1115
1116 }
1117
tree_expand_matching(const char * text)1118 void tree_expand_matching(const char *text)
1119 {
1120 struct artist *artist;
1121 struct rb_node *tmp1;
1122 int have_track_selected = 0;
1123
1124 rb_for_each_entry(artist, tmp1, &lib_artist_root, tree_node) {
1125 struct album *album = NULL;
1126 struct rb_node *tmp2;
1127 int album_matched = 0;
1128
1129 rb_for_each_entry(album, tmp2, &artist->album_root, tree_node) {
1130 struct tree_track *tree_track = to_tree_track(rb_first(&album->track_root));
1131 struct track_info *ti = ((struct simple_track *) tree_track)->info;
1132 album_matched = track_info_matches_full(ti, text, TI_MATCH_ALBUM, TI_MATCH_ARTIST | TI_MATCH_ALBUMARTIST, 0);
1133 if (album_matched)
1134 break;
1135 }
1136 artist->expanded = album_matched;
1137 if (!have_track_selected) {
1138 struct tree_track *tree_track;
1139 int track_matched = 0;
1140
1141 if (!album)
1142 album = to_album(rb_first(&artist->album_root));
1143
1144 rb_for_each_entry(tree_track, tmp2, &album->track_root, tree_node) {
1145 struct track_info *ti = ((struct simple_track *) tree_track)->info;
1146 track_matched = track_info_matches_full(ti, text, TI_MATCH_TITLE, 0, 0);
1147 if (track_matched)
1148 break;
1149 }
1150 if (album_matched || track_matched) {
1151 if (!tree_track)
1152 tree_track = to_tree_track(rb_first(&album->track_root));
1153 tree_sel_track(tree_track, auto_expand_albums_search);
1154 have_track_selected = 1;
1155 }
1156 }
1157 }
1158 window_changed(lib_tree_win);
1159 }
1160
tree_expand_all(void)1161 void tree_expand_all(void)
1162 {
1163 struct artist *artist;
1164 struct rb_node *tmp;
1165
1166 rb_for_each_entry(artist, tmp, &lib_artist_root, tree_node) {
1167 artist->expanded = 1;
1168 }
1169 window_changed(lib_tree_win);
1170 }
1171
remove_track(struct tree_track * track)1172 static void remove_track(struct tree_track *track)
1173 {
1174 if (track_visible(track)) {
1175 struct track_iter iter;
1176 tree_track_to_track_iter(track, &iter);
1177 window_row_vanishes(lib_track_win, (struct iter *)&iter);
1178 }
1179 rb_erase(&track->tree_node, &track->album->track_root);
1180 }
1181
tree_remove(struct tree_track * track)1182 void tree_remove(struct tree_track *track)
1183 {
1184 struct album *album = track->album;
1185 struct artist *sel_artist;
1186 struct album *sel_album;
1187
1188 tree_win_get_selected(&sel_artist, &sel_album);
1189
1190 remove_track(track);
1191 /* don't free the track */
1192
1193 if (rb_root_empty(&album->track_root)) {
1194 struct artist *artist = album->artist;
1195
1196 if (sel_album == album)
1197 lib_cur_win = lib_tree_win;
1198
1199 if (track_visible(track) && !tree_album_selected()) {
1200 struct iter iter;
1201 album_to_track_iter(album, (struct track_iter*)&iter);
1202 window_row_vanishes(lib_track_win, &iter);
1203 }
1204
1205 remove_album(album);
1206 album_free(album);
1207
1208 if (rb_root_empty(&artist->album_root)) {
1209 artist->expanded = 0;
1210 remove_artist(artist);
1211 artist_free(artist);
1212 }
1213 }
1214 }
1215
tree_remove_sel(void)1216 void tree_remove_sel(void)
1217 {
1218 if (lib_cur_win == lib_tree_win) {
1219 tree_win_remove_sel();
1220 } else {
1221 track_win_remove_sel();
1222 }
1223 }
1224
tree_sort_artists(void)1225 void tree_sort_artists(void)
1226 {
1227 struct rb_node *a_node, *a_tmp;
1228
1229 rb_for_each_safe(a_node, a_tmp, &lib_artist_root) {
1230 struct rb_node *l_node, *l_tmp;
1231 struct artist *artist = to_artist(a_node);
1232
1233 rb_for_each_safe(l_node, l_tmp, &artist->album_root) {
1234 struct rb_node *t_node, *t_tmp;
1235 struct album *album = to_album(l_node);
1236
1237 rb_for_each_safe(t_node, t_tmp, &album->track_root) {
1238 struct tree_track *track = to_tree_track(t_node);
1239
1240 tree_remove(track);
1241 tree_add_track(track);
1242 }
1243 }
1244 }
1245 }
1246
tree_sel_current(int auto_expand_albums)1247 void tree_sel_current(int auto_expand_albums)
1248 {
1249 tree_sel_track(lib_cur_track, auto_expand_albums);
1250 }
1251
tree_sel_first(void)1252 void tree_sel_first(void)
1253 {
1254 if (!rb_root_empty(&lib_artist_root)) {
1255 struct artist *artist = to_artist(rb_first(&lib_artist_root));
1256 struct album *album = to_album(rb_first(&artist->album_root));
1257 struct tree_track *tree_track = to_tree_track(rb_first(&album->track_root));
1258 tree_sel_track(tree_track, auto_expand_albums_search);
1259 }
1260 }
1261
tree_sel_track(struct tree_track * t,int auto_expand_albums)1262 void tree_sel_track(struct tree_track *t, int auto_expand_albums)
1263 {
1264 if (t) {
1265 struct iter iter;
1266
1267 if (auto_expand_albums)
1268 t->album->artist->expanded = 1;
1269 if (t->album->artist->expanded)
1270 album_to_iter(t->album, &iter);
1271 else
1272 artist_to_iter(t->album->artist, &iter);
1273
1274 window_set_sel(lib_tree_win, &iter);
1275
1276 tree_track_to_track_iter(t, (struct track_iter *)&iter);
1277 window_set_sel(lib_track_win, &iter);
1278
1279 if (lib_cur_win == lib_tree_win) {
1280 lib_cur_win = lib_track_win;
1281 lib_tree_win->changed = 1;
1282 lib_track_win->changed = 1;
1283 }
1284 }
1285 }
1286
album_for_each_track(struct album * album,int (* cb)(void * data,struct track_info * ti),void * data,int reverse)1287 static int album_for_each_track(struct album *album, int (*cb)(void *data, struct track_info *ti),
1288 void *data, int reverse)
1289 {
1290 struct tree_track *track;
1291 struct rb_node *tmp;
1292 int rc = 0;
1293
1294 if (reverse) {
1295 rb_for_each_entry_reverse(track, tmp, &album->track_root, tree_node) {
1296 rc = cb(data, tree_track_info(track));
1297 if (rc)
1298 break;
1299 }
1300 } else {
1301 rb_for_each_entry(track, tmp, &album->track_root, tree_node) {
1302 rc = cb(data, tree_track_info(track));
1303 if (rc)
1304 break;
1305 }
1306 }
1307 return rc;
1308 }
1309
artist_for_each_track(struct artist * artist,int (* cb)(void * data,struct track_info * ti),void * data,int reverse)1310 static int artist_for_each_track(struct artist *artist, int (*cb)(void *data, struct track_info *ti),
1311 void *data, int reverse)
1312 {
1313 struct album *album;
1314 struct rb_node *tmp;
1315 int rc = 0;
1316
1317 if (reverse) {
1318 rb_for_each_entry_reverse(album, tmp, &artist->album_root, tree_node) {
1319 rc = album_for_each_track(album, cb, data, 1);
1320 if (rc)
1321 break;
1322 }
1323 } else {
1324 rb_for_each_entry(album, tmp, &artist->album_root, tree_node) {
1325 rc = album_for_each_track(album, cb, data, 0);
1326 if (rc)
1327 break;
1328 }
1329 }
1330 return rc;
1331 }
1332
_tree_for_each_sel(int (* cb)(void * data,struct track_info * ti),void * data,int reverse)1333 int _tree_for_each_sel(int (*cb)(void *data, struct track_info *ti), void *data, int reverse)
1334 {
1335 int rc = 0;
1336
1337 if (lib_cur_win == lib_tree_win) {
1338 struct artist *artist;
1339 struct album *album;
1340
1341 tree_win_get_selected(&artist, &album);
1342 if (artist) {
1343 if (album == NULL) {
1344 rc = artist_for_each_track(artist, cb, data, reverse);
1345 } else {
1346 rc = album_for_each_track(album, cb, data, reverse);
1347 }
1348 }
1349 } else {
1350 struct iter sel;
1351 struct tree_track *track;
1352
1353 if (window_get_sel(lib_track_win, &sel)) {
1354 track = iter_to_tree_track(&sel);
1355 rc = cb(data, tree_track_info(track));
1356 }
1357 }
1358 return rc;
1359 }
1360
tree_for_each_sel(int (* cb)(void * data,struct track_info * ti),void * data,int reverse,int advance)1361 int tree_for_each_sel(int (*cb)(void *data, struct track_info *ti), void *data, int reverse, int advance)
1362 {
1363 int rc = _tree_for_each_sel(cb, data, reverse);
1364
1365 if (advance)
1366 window_down(lib_cur_win, 1);
1367 return rc;
1368 }
1369