1 /*
2 * Copyright 2003-2021 The Music Player Daemon Project
3 * http://www.musicpd.org
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 */
19
20 #include "Queue.hxx"
21 #include "song/DetachedSong.hxx"
22
23 #include <algorithm>
24
Queue(unsigned _max_length)25 Queue::Queue(unsigned _max_length) noexcept
26 :max_length(_max_length),
27 items(new Item[max_length]),
28 order(new unsigned[max_length]),
29 id_table(max_length * HASH_MULT)
30 {
31 }
32
~Queue()33 Queue::~Queue() noexcept
34 {
35 Clear();
36
37 delete[] items;
38 delete[] order;
39 }
40
41 int
GetNextOrder(unsigned _order) const42 Queue::GetNextOrder(unsigned _order) const noexcept
43 {
44 assert(_order < length);
45
46 if (single != SingleMode::OFF && repeat && !consume)
47 return _order;
48 else if (_order + 1 < length)
49 return _order + 1;
50 else if (repeat && (_order > 0 || !consume))
51 /* restart at first song */
52 return 0;
53 else
54 /* end of queue */
55 return -1;
56 }
57
58 void
IncrementVersion()59 Queue::IncrementVersion() noexcept
60 {
61 static unsigned long max = ((uint32_t) 1 << 31) - 1;
62
63 version++;
64
65 if (version >= max) {
66 for (unsigned i = 0; i < length; i++)
67 items[i].version = 0;
68
69 version = 1;
70 }
71 }
72
73 void
ModifyAtOrder(unsigned _order)74 Queue::ModifyAtOrder(unsigned _order) noexcept
75 {
76 assert(_order < length);
77
78 unsigned position = order[_order];
79 ModifyAtPosition(position);
80 }
81
82 unsigned
Append(DetachedSong && song,uint8_t priority)83 Queue::Append(DetachedSong &&song, uint8_t priority) noexcept
84 {
85 assert(!IsFull());
86
87 const unsigned position = length++;
88 const unsigned id = id_table.Insert(position);
89
90 auto &item = items[position];
91 item.song = new DetachedSong(std::move(song));
92 item.id = id;
93 item.version = version;
94 item.priority = priority;
95
96 order[position] = position;
97
98 return id;
99 }
100
101 void
SwapPositions(unsigned position1,unsigned position2)102 Queue::SwapPositions(unsigned position1, unsigned position2) noexcept
103 {
104 unsigned id1 = items[position1].id;
105 unsigned id2 = items[position2].id;
106
107 std::swap(items[position1], items[position2]);
108
109 items[position1].version = version;
110 items[position2].version = version;
111
112 id_table.Move(id1, position2);
113 id_table.Move(id2, position1);
114 }
115
116 void
MovePostion(unsigned from,unsigned to)117 Queue::MovePostion(unsigned from, unsigned to) noexcept
118 {
119 const Item tmp = items[from];
120
121 /* move songs to one less in from->to */
122
123 for (unsigned i = from; i < to; i++)
124 MoveItemTo(i + 1, i);
125
126 /* move songs to one more in to->from */
127
128 for (unsigned i = from; i > to; i--)
129 MoveItemTo(i - 1, i);
130
131 /* put song at _to_ */
132
133 id_table.Move(tmp.id, to);
134 items[to] = tmp;
135 items[to].version = version;
136
137 /* now deal with order */
138
139 if (random) {
140 for (unsigned i = 0; i < length; i++) {
141 if (order[i] > from && order[i] <= to)
142 order[i]--;
143 else if (order[i] < from &&
144 order[i] >= to)
145 order[i]++;
146 else if (from == order[i])
147 order[i] = to;
148 }
149 }
150 }
151
152 void
MoveRange(unsigned start,unsigned end,unsigned to)153 Queue::MoveRange(unsigned start, unsigned end, unsigned to) noexcept
154 {
155 const auto tmp = std::make_unique<Item[]>(end - start);
156
157 // Copy the original block [start,end-1]
158 for (unsigned i = start; i < end; i++)
159 tmp[i - start] = items[i];
160
161 // If to > start, we need to move to-start items to start, starting from end
162 for (unsigned i = end; i < end + to - start; i++)
163 MoveItemTo(i, start + i - end);
164
165 // If to < start, we need to move start-to items to newend (= end + to - start), starting from to
166 // This is the same as moving items from start-1 to to (decreasing), with start-1 going to end-1
167 // We have to iterate in this order to avoid writing over something we haven't yet moved
168 for (int i = start - 1; i >= int(to); i--)
169 MoveItemTo(i, i + end - start);
170
171 // Copy the original block back in, starting at to.
172 for (unsigned i = start; i< end; i++)
173 {
174 id_table.Move(tmp[i - start].id, to + i - start);
175 items[to + i - start] = tmp[i-start];
176 items[to + i - start].version = version;
177 }
178
179 if (random) {
180 // Update the positions in the queue.
181 // Note that the ranges for these cases are the same as the ranges of
182 // the loops above.
183 for (unsigned i = 0; i < length; i++) {
184 if (order[i] >= end && order[i] < to + end - start)
185 order[i] -= end - start;
186 else if (order[i] < start &&
187 order[i] >= to)
188 order[i] += end - start;
189 else if (start <= order[i] && order[i] < end)
190 order[i] += to - start;
191 }
192 }
193 }
194
195 unsigned
MoveOrder(unsigned from_order,unsigned to_order)196 Queue::MoveOrder(unsigned from_order, unsigned to_order) noexcept
197 {
198 assert(from_order < length);
199 assert(to_order <= length);
200
201 const unsigned from_position = OrderToPosition(from_order);
202
203 if (from_order < to_order) {
204 for (unsigned i = from_order; i < to_order; ++i)
205 order[i] = order[i + 1];
206 } else {
207 for (unsigned i = from_order; i > to_order; --i)
208 order[i] = order[i - 1];
209 }
210
211 order[to_order] = from_position;
212 return to_order;
213 }
214
215 unsigned
MoveOrderBefore(unsigned from_order,unsigned to_order)216 Queue::MoveOrderBefore(unsigned from_order, unsigned to_order) noexcept
217 {
218 /* if "from_order" comes before "to_order", then the new
219 position is "to_order-1"; otherwise the "to_order" song is
220 moved one ahead */
221 return MoveOrder(from_order, to_order - (from_order < to_order));
222 }
223
224 unsigned
MoveOrderAfter(unsigned from_order,unsigned to_order)225 Queue::MoveOrderAfter(unsigned from_order, unsigned to_order) noexcept
226 {
227 /* if "from_order" comes after "to_order", then the new
228 position is "to_order+1"; otherwise the "to_order" song is
229 moved one back */
230 return MoveOrder(from_order, to_order + (from_order > to_order));
231 }
232
233 void
DeletePosition(unsigned position)234 Queue::DeletePosition(unsigned position) noexcept
235 {
236 assert(position < length);
237
238 delete items[position].song;
239
240 const unsigned id = PositionToId(position);
241 const unsigned _order = PositionToOrder(position);
242
243 --length;
244
245 /* release the song id */
246
247 id_table.Erase(id);
248
249 /* delete song from songs array */
250
251 for (unsigned i = position; i < length; i++)
252 MoveItemTo(i + 1, i);
253
254 /* delete the entry from the order array */
255
256 for (unsigned i = _order; i < length; i++)
257 order[i] = order[i + 1];
258
259 /* readjust values in the order array */
260
261 for (unsigned i = 0; i < length; i++)
262 if (order[i] > position)
263 --order[i];
264 }
265
266 void
Clear()267 Queue::Clear() noexcept
268 {
269 for (unsigned i = 0; i < length; i++) {
270 Item *item = &items[i];
271
272 delete item->song;
273
274 id_table.Erase(item->id);
275 }
276
277 length = 0;
278 }
279
280 static void
queue_sort_order_by_priority(Queue * queue,unsigned start,unsigned end)281 queue_sort_order_by_priority(Queue *queue,
282 unsigned start, unsigned end) noexcept
283 {
284 assert(queue != nullptr);
285 assert(queue->random);
286 assert(start <= end);
287 assert(end <= queue->length);
288
289 auto cmp = [queue](unsigned a_pos, unsigned b_pos){
290 const Queue::Item &a = queue->items[a_pos];
291 const Queue::Item &b = queue->items[b_pos];
292
293 return a.priority > b.priority;
294 };
295
296 std::stable_sort(queue->order + start, queue->order + end, cmp);
297 }
298
299 void
ShuffleOrderRange(unsigned start,unsigned end)300 Queue::ShuffleOrderRange(unsigned start, unsigned end) noexcept
301 {
302 assert(random);
303 assert(start <= end);
304 assert(end <= length);
305
306 rand.AutoCreate();
307 std::shuffle(order + start, order + end, rand);
308 }
309
310 /**
311 * Sort the "order" of items by priority, and then shuffle each
312 * priority group.
313 */
314 void
ShuffleOrderRangeWithPriority(unsigned start,unsigned end)315 Queue::ShuffleOrderRangeWithPriority(unsigned start, unsigned end) noexcept
316 {
317 assert(random);
318 assert(start <= end);
319 assert(end <= length);
320
321 if (start == end)
322 return;
323
324 /* first group the range by priority */
325 queue_sort_order_by_priority(this, start, end);
326
327 /* now shuffle each priority group */
328 unsigned group_start = start;
329 uint8_t group_priority = GetOrderPriority(start);
330
331 for (unsigned i = start + 1; i < end; ++i) {
332 const uint8_t priority = GetOrderPriority(i);
333 assert(priority <= group_priority);
334
335 if (priority != group_priority) {
336 /* start of a new group - shuffle the one that
337 has just ended */
338 ShuffleOrderRange(group_start, i);
339 group_start = i;
340 group_priority = priority;
341 }
342 }
343
344 /* shuffle the last group */
345 ShuffleOrderRange(group_start, end);
346 }
347
348 void
ShuffleOrder()349 Queue::ShuffleOrder() noexcept
350 {
351 ShuffleOrderRangeWithPriority(0, length);
352 }
353
354 void
ShuffleOrderFirst(unsigned start,unsigned end)355 Queue::ShuffleOrderFirst(unsigned start, unsigned end) noexcept
356 {
357 rand.AutoCreate();
358
359 std::uniform_int_distribution<unsigned> distribution(start, end - 1);
360 SwapOrders(start, distribution(rand));
361 }
362
363 void
ShuffleOrderLastWithPriority(unsigned start,unsigned end)364 Queue::ShuffleOrderLastWithPriority(unsigned start, unsigned end) noexcept
365 {
366 assert(end <= length);
367 assert(start < end);
368
369 /* skip all items at the start which have a higher priority,
370 because the last item shall only be shuffled within its
371 priority group */
372 const auto last_priority = items[OrderToPosition(end - 1)].priority;
373 while (items[OrderToPosition(start)].priority != last_priority) {
374 ++start;
375 assert(start < end);
376 }
377
378 rand.AutoCreate();
379
380 std::uniform_int_distribution<unsigned> distribution(start, end - 1);
381 SwapOrders(end - 1, distribution(rand));
382 }
383
384 void
ShuffleRange(unsigned start,unsigned end)385 Queue::ShuffleRange(unsigned start, unsigned end) noexcept
386 {
387 assert(start <= end);
388 assert(end <= length);
389
390 rand.AutoCreate();
391
392 for (unsigned i = start; i < end; i++) {
393 std::uniform_int_distribution<unsigned> distribution(start,
394 end - 1);
395 unsigned ri = distribution(rand);
396 SwapPositions(i, ri);
397 }
398 }
399
400 unsigned
FindPriorityOrder(unsigned start_order,uint8_t priority,unsigned exclude_order) const401 Queue::FindPriorityOrder(unsigned start_order, uint8_t priority,
402 unsigned exclude_order) const noexcept
403 {
404 assert(random);
405 assert(start_order <= length);
406
407 for (unsigned i = start_order; i < length; ++i) {
408 const unsigned position = OrderToPosition(i);
409 const Item *item = &items[position];
410 if (item->priority <= priority && i != exclude_order)
411 return i;
412 }
413
414 return length;
415 }
416
417 unsigned
CountSamePriority(unsigned start_order,uint8_t priority) const418 Queue::CountSamePriority(unsigned start_order, uint8_t priority) const noexcept
419 {
420 assert(random);
421 assert(start_order <= length);
422
423 for (unsigned i = start_order; i < length; ++i) {
424 const unsigned position = OrderToPosition(i);
425 const Item *item = &items[position];
426 if (item->priority != priority)
427 return i - start_order;
428 }
429
430 return length - start_order;
431 }
432
433 bool
SetPriority(unsigned position,uint8_t priority,int after_order,bool reorder)434 Queue::SetPriority(unsigned position, uint8_t priority, int after_order,
435 bool reorder) noexcept
436 {
437 assert(position < length);
438
439 Item *item = &items[position];
440 uint8_t old_priority = item->priority;
441 if (old_priority == priority)
442 return false;
443
444 item->version = version;
445 item->priority = priority;
446
447 if (!random || !reorder)
448 /* don't reorder if not in random mode */
449 return true;
450
451 unsigned _order = PositionToOrder(position);
452 if (after_order >= 0) {
453 if (_order == (unsigned)after_order)
454 /* don't reorder the current song */
455 return true;
456
457 if (_order < (unsigned)after_order) {
458 /* the specified song has been played already
459 - enqueue it only if its priority has been
460 increased and is now bigger than the
461 current one's */
462
463 const unsigned after_position =
464 OrderToPosition(after_order);
465 const Item *after_item =
466 &items[after_position];
467 if (priority <= old_priority ||
468 priority <= after_item->priority)
469 /* priority hasn't become bigger */
470 return true;
471 }
472 }
473
474 /* move the item to the beginning of the priority group (or
475 create a new priority group) */
476
477 const unsigned before_order =
478 FindPriorityOrder(after_order + 1, priority, _order);
479 const unsigned new_order = before_order > _order
480 ? before_order - 1
481 : before_order;
482 MoveOrder(_order, new_order);
483
484 /* shuffle the song within that priority group */
485
486 const unsigned priority_count = CountSamePriority(new_order, priority);
487 assert(priority_count >= 1);
488 ShuffleOrderFirst(new_order, new_order + priority_count);
489
490 return true;
491 }
492
493 bool
SetPriorityRange(unsigned start_position,unsigned end_position,uint8_t priority,int after_order)494 Queue::SetPriorityRange(unsigned start_position, unsigned end_position,
495 uint8_t priority, int after_order) noexcept
496 {
497 assert(start_position <= end_position);
498 assert(end_position <= length);
499
500 bool modified = false;
501 int after_position = after_order >= 0
502 ? (int)OrderToPosition(after_order)
503 : -1;
504 for (unsigned i = start_position; i < end_position; ++i) {
505 after_order = after_position >= 0
506 ? (int)PositionToOrder(after_position)
507 : -1;
508
509 modified |= SetPriority(i, priority, after_order);
510 }
511
512 return modified;
513 }
514