1 /*
2     DeaDBeeF -- the music player
3     Copyright (C) 2009-2015 Alexey Yakovenko and other contributors
4 
5     This software is provided 'as-is', without any express or implied
6     warranty.  In no event will the authors be held liable for any damages
7     arising from the use of this software.
8 
9     Permission is granted to anyone to use this software for any purpose,
10     including commercial applications, and to alter it and redistribute it
11     freely, subject to the following restrictions:
12 
13     1. The origin of this software must not be misrepresented; you must not
14      claim that you wrote the original software. If you use this software
15      in a product, an acknowledgment in the product documentation would be
16      appreciated but is not required.
17 
18     2. Altered source versions must be plainly marked as such, and must not be
19      misrepresented as being the original software.
20 
21     3. This notice may not be removed or altered from any source distribution.
22 */
23 
24 #include <sys/time.h>
25 #include <ctype.h>
26 #include <string.h>
27 #include <stdlib.h>
28 #include "utf8.h"
29 #include "sort.h"
30 #include "tf.h"
31 
32 //#define trace(...) { fprintf(stderr, __VA_ARGS__); }
33 #define trace(fmt,...)
34 
35 static void
36 plt_sort_internal (playlist_t *playlist, int iter, int id, const char *format, int order, int version);
37 
plt_sort_v2(playlist_t * plt,int iter,int id,const char * format,int order)38 void plt_sort_v2 (playlist_t *plt, int iter, int id, const char *format, int order) {
39     plt_sort_internal (plt, iter, id, format, order, 1);
40 }
41 
42 // sort for title formatting v1
43 void
plt_sort(playlist_t * playlist,int iter,int id,const char * format,int order)44 plt_sort (playlist_t *playlist, int iter, int id, const char *format, int order) {
45     plt_sort_internal (playlist, iter, id, format, order, 0);
46 }
47 
48 static int pl_sort_is_duration;
49 static int pl_sort_is_track;
50 static int pl_sort_ascending;
51 static int pl_sort_id;
52 static int pl_sort_version; // 0: use pl_sort_format, 1: use pl_sort_tf_bytecode
53 static const char *pl_sort_format;
54 static char *pl_sort_tf_bytecode;
55 static ddb_tf_context_t pl_sort_tf_ctx;
56 
57 static int
strcasecmp_numeric(const char * a,const char * b)58 strcasecmp_numeric (const char *a, const char *b) {
59     if (isdigit (*a) && isdigit (*b)) {
60         int anum = *a-'0';
61         const char *ae = a+1;
62         while (*ae && isdigit (*ae)) {
63             anum *= 10;
64             anum += *ae-'0';
65             ae++;
66         }
67         int bnum = *b-'0';
68         const char *be = b+1;
69         while (*be && isdigit (*be)) {
70             bnum *= 10;
71             bnum += *be-'0';
72             be++;
73         }
74         if (anum == bnum) {
75             return u8_strcasecmp (ae, be);
76         }
77         return anum - bnum;
78     }
79     return u8_strcasecmp (a,b);
80 }
81 
82 static int
pl_sort_compare_str(playItem_t * a,playItem_t * b)83 pl_sort_compare_str (playItem_t *a, playItem_t *b) {
84     if (pl_sort_is_duration) {
85         float dur_a = a->_duration * 100000;
86         float dur_b = b->_duration * 100000;
87         return !pl_sort_ascending ? dur_b - dur_a : dur_a - dur_b;
88     }
89     else if (pl_sort_is_track) {
90         int t1;
91         int t2;
92         const char *t;
93         t = pl_find_meta_raw (a, "track");
94         if (t && !isdigit (*t)) {
95             t1 = 999999;
96         }
97         else {
98             t1 = t ? atoi (t) : -1;
99         }
100         t = pl_find_meta_raw (b, "track");
101         if (t && !isdigit (*t)) {
102             t2 = 999999;
103         }
104         else {
105             t2 = t ? atoi (t) : -1;
106         }
107         return !pl_sort_ascending ? t2 - t1 : t1 - t2;
108     }
109     else {
110         char tmp1[1024];
111         char tmp2[1024];
112         if (pl_sort_version == 0) {
113             pl_format_title (a, -1, tmp1, sizeof (tmp1), pl_sort_id, pl_sort_format);
114             pl_format_title (b, -1, tmp2, sizeof (tmp2), pl_sort_id, pl_sort_format);
115         }
116         else {
117             pl_sort_tf_ctx.id = pl_sort_id;
118             pl_sort_tf_ctx.it = (ddb_playItem_t *)a;
119             tf_eval(&pl_sort_tf_ctx, pl_sort_tf_bytecode, tmp1, sizeof(tmp1));
120             pl_sort_tf_ctx.it = (ddb_playItem_t *)b;
121             tf_eval(&pl_sort_tf_ctx, pl_sort_tf_bytecode, tmp2, sizeof(tmp2));
122         }
123         int res = strcasecmp_numeric (tmp1, tmp2);
124         if (!pl_sort_ascending) {
125             res = -res;
126         }
127         return res;
128     }
129 }
130 
131 static int
qsort_cmp_func(const void * a,const void * b)132 qsort_cmp_func (const void *a, const void *b) {
133     playItem_t *aa = *((playItem_t **)a);
134     playItem_t *bb = *((playItem_t **)b);
135     return pl_sort_compare_str (aa, bb);
136 }
137 
138 void
plt_sort_random(playlist_t * playlist,int iter)139 plt_sort_random (playlist_t *playlist, int iter) {
140     if (!playlist->head[iter] || !playlist->head[iter]->next[iter]) {
141         return;
142     }
143 
144     pl_lock ();
145 
146     const int playlist_count = playlist->count[iter];
147     playItem_t **array = malloc (playlist_count * sizeof (playItem_t *));
148     int idx = 0;
149     for (playItem_t *it = playlist->head[iter]; it; it = it->next[iter], idx++) {
150         array[idx] = it;
151     }
152 
153     //randomize array
154     for (int swap_a = 0; swap_a < playlist_count - 1; swap_a++) {
155         //select random item above swap_a-1
156         const int swap_b = swap_a + (rand() / (float)RAND_MAX * (playlist_count - swap_a));
157 
158         //swap a with b
159         playItem_t* const swap_temp = array[swap_a];
160         array[swap_a] = array[swap_b];
161         array[swap_b] = swap_temp;
162 
163     }
164 
165     playItem_t *prev = NULL;
166     playlist->head[iter] = 0;
167     for (idx = 0; idx < playlist->count[iter]; idx++) {
168         playItem_t *it = array[idx];
169         it->prev[iter] = prev;
170         it->next[iter] = NULL;
171         if (!prev) {
172             playlist->head[iter] = it;
173         }
174         else {
175             prev->next[iter] = it;
176         }
177         prev = it;
178     }
179     playlist->tail[iter] = array[playlist->count[iter]-1];
180 
181     free (array);
182 
183     plt_modified (playlist);
184 
185     pl_unlock ();
186 }
187 
188 // version 0: title formatting v1
189 // version 1: title formatting v2
190 void
plt_sort_internal(playlist_t * playlist,int iter,int id,const char * format,int order,int version)191 plt_sort_internal (playlist_t *playlist, int iter, int id, const char *format, int order, int version) {
192     if (order == DDB_SORT_RANDOM) {
193         plt_sort_random (playlist, iter);
194         return;
195     }
196     int ascending = order == DDB_SORT_DESCENDING ? 0 : 1;
197 
198     if (format == NULL || id == DB_COLUMN_FILENUMBER || !playlist->head[iter] || !playlist->head[iter]->next[iter]) {
199         return;
200     }
201     pl_lock ();
202     struct timeval tm1;
203     gettimeofday (&tm1, NULL);
204     pl_sort_ascending = ascending;
205     trace ("ascending: %d\n", ascending);
206     pl_sort_id = id;
207 
208     pl_sort_version = version;
209     if (version == 0) {
210         pl_sort_format = format;
211         pl_sort_tf_bytecode = NULL;
212     }
213     else {
214         pl_sort_format = NULL;
215         pl_sort_tf_bytecode = tf_compile (format);
216         pl_sort_tf_ctx._size = sizeof (pl_sort_tf_ctx);
217         pl_sort_tf_ctx.it = NULL;
218         pl_sort_tf_ctx.plt = (ddb_playlist_t *)playlist;
219         pl_sort_tf_ctx.idx = -1;
220         pl_sort_tf_ctx.id = id;
221     }
222 
223     if (format && id == -1
224         && ((version == 0 && !strcmp (format, "%l"))
225             || (version == 1 && !strcmp (format, "%length%")))
226         ) {
227         pl_sort_is_duration = 1;
228     }
229     else {
230         pl_sort_is_duration = 0;
231     }
232     if (format && id == -1
233         && ((version == 0 && !strcmp (format, "%n"))
234             || (version == 1 && (!strcmp (format, "%track number%") || !strcmp (format, "%tracknumber%"))))
235         ) {
236         pl_sort_is_track = 1;
237     }
238     else {
239         pl_sort_is_track = 0;
240     }
241 
242     playItem_t **array = malloc (playlist->count[iter] * sizeof (playItem_t *));
243     int idx = 0;
244     for (playItem_t *it = playlist->head[iter]; it; it = it->next[iter], idx++) {
245         array[idx] = it;
246     }
247     qsort (array, playlist->count[iter], sizeof (playItem_t *), qsort_cmp_func);
248     playItem_t *prev = NULL;
249     playlist->head[iter] = 0;
250     for (idx = 0; idx < playlist->count[iter]; idx++) {
251         playItem_t *it = array[idx];
252         it->prev[iter] = prev;
253         it->next[iter] = NULL;
254         if (!prev) {
255             playlist->head[iter] = it;
256         }
257         else {
258             prev->next[iter] = it;
259         }
260         prev = it;
261     }
262 
263     playlist->tail[iter] = array[playlist->count[iter]-1];
264 
265     free (array);
266 
267     struct timeval tm2;
268     gettimeofday (&tm2, NULL);
269     int ms = (tm2.tv_sec*1000+tm2.tv_usec/1000) - (tm1.tv_sec*1000+tm1.tv_usec/1000);
270     trace ("sort time: %f seconds\n", ms / 1000.f);
271 
272     plt_modified (playlist);
273 
274     if (version == 0) {
275         pl_sort_format = NULL;
276     }
277 
278     if (version == 1) {
279         tf_free (pl_sort_tf_bytecode);
280         pl_sort_tf_bytecode = NULL;
281         memset (&pl_sort_tf_ctx, 0, sizeof (pl_sort_tf_ctx));
282     }
283 
284     pl_unlock ();
285 }
286