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