← Back to branch summary

~ubuntu-branches/ubuntu/utopic/mpd/utopic-proposed

« back to all changes in this revision

Viewing changes to src/Queue.cxx

  • Committer: Package Import Robot
  • Author(s): Steve Kowalik
  • Date: 2013-11-12 18:17:40 UTC
  • mfrom: (2.2.36 sid)
  • Revision ID: package-import@ubuntu.com-20131112181740-72aa4zihehoobedp
Tags: 0.18.3-1ubuntu1
* Merge from Debian unstable.  Remaining changes:
  - Add libmp3lame-dev to Build-Depends, and enable LAME.
  - Read the user for the daemon from the config file in the init script.
  - Move avahi-daemon from Suggests to Recommends.
  - Added apport hook to include user configuration file.

Show diffs side-by-side

added added

removed removed

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