aboutsummaryrefslogtreecommitdiffstats
path: root/src/Queue.cxx
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/Queue.cxx499
1 files changed, 499 insertions, 0 deletions
diff --git a/src/Queue.cxx b/src/Queue.cxx
new file mode 100644
index 000000000..3fdb9ed1e
--- /dev/null
+++ b/src/Queue.cxx
@@ -0,0 +1,499 @@
+/*
+ * Copyright (C) 2003-2013 The Music Player Daemon Project
+ * http://www.musicpd.org
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#include "config.h"
+#include "Queue.hxx"
+#include "song.h"
+
+#include <stdlib.h>
+
+queue::queue(unsigned _max_length)
+ :max_length(_max_length), length(0),
+ version(1),
+ items(new Item[max_length]),
+ order(new unsigned[max_length]),
+ id_table(max_length * HASH_MULT),
+ repeat(false),
+ single(false),
+ consume(false),
+ random(false)
+{
+}
+
+queue::~queue()
+{
+ Clear();
+
+ delete[] items;
+ delete[] order;
+}
+
+int
+queue::GetNextOrder(unsigned _order) const
+{
+ assert(_order < length);
+
+ if (single && repeat && !consume)
+ return _order;
+ else if (_order + 1 < length)
+ return _order + 1;
+ else if (repeat && (_order > 0 || !consume))
+ /* restart at first song */
+ return 0;
+ else
+ /* end of queue */
+ return -1;
+}
+
+void
+queue::IncrementVersion()
+{
+ static unsigned long max = ((uint32_t) 1 << 31) - 1;
+
+ version++;
+
+ if (version >= max) {
+ for (unsigned i = 0; i < length; i++)
+ items[i].version = 0;
+
+ version = 1;
+ }
+}
+
+void
+queue::ModifyAtOrder(unsigned _order)
+{
+ assert(_order < length);
+
+ unsigned position = order[_order];
+ items[position].version = version;
+
+ IncrementVersion();
+}
+
+void
+queue::ModifyAll()
+{
+ for (unsigned i = 0; i < length; i++)
+ items[i].version = version;
+
+ IncrementVersion();
+}
+
+unsigned
+queue::Append(struct song *song, uint8_t priority)
+{
+ assert(!IsFull());
+
+ const unsigned position = length++;
+ const unsigned id = id_table.Insert(position);
+
+ auto &item = items[position];
+ item.song = song_dup_detached(song);
+ item.id = id;
+ item.version = version;
+ item.priority = priority;
+
+ order[position] = position;
+
+ return id;
+}
+
+void
+queue::SwapPositions(unsigned position1, unsigned position2)
+{
+ unsigned id1 = items[position1].id;
+ unsigned id2 = items[position2].id;
+
+ std::swap(items[position1], items[position2]);
+
+ items[position1].version = version;
+ items[position2].version = version;
+
+ id_table.Move(id1, position2);
+ id_table.Move(id2, position1);
+}
+
+void
+queue::MovePostion(unsigned from, unsigned to)
+{
+ const Item tmp = items[from];
+
+ /* move songs to one less in from->to */
+
+ for (unsigned i = from; i < to; i++)
+ MoveItemTo(i + 1, i);
+
+ /* move songs to one more in to->from */
+
+ for (unsigned i = from; i > to; i--)
+ MoveItemTo(i - 1, i);
+
+ /* put song at _to_ */
+
+ id_table.Move(tmp.id, to);
+ items[to] = tmp;
+ items[to].version = version;
+
+ /* now deal with order */
+
+ if (random) {
+ for (unsigned i = 0; i < length; i++) {
+ if (order[i] > from && order[i] <= to)
+ order[i]--;
+ else if (order[i] < from &&
+ order[i] >= to)
+ order[i]++;
+ else if (from == order[i])
+ order[i] = to;
+ }
+ }
+}
+
+void
+queue::MoveRange(unsigned start, unsigned end, unsigned to)
+{
+ Item tmp[end - start];
+ // Copy the original block [start,end-1]
+ for (unsigned i = start; i < end; i++)
+ tmp[i - start] = items[i];
+
+ // If to > start, we need to move to-start items to start, starting from end
+ for (unsigned i = end; i < end + to - start; i++)
+ MoveItemTo(i, start + i - end);
+
+ // If to < start, we need to move start-to items to newend (= end + to - start), starting from to
+ // This is the same as moving items from start-1 to to (decreasing), with start-1 going to end-1
+ // We have to iterate in this order to avoid writing over something we haven't yet moved
+ for (int i = start - 1; i >= int(to); i--)
+ MoveItemTo(i, i + end - start);
+
+ // Copy the original block back in, starting at to.
+ for (unsigned i = start; i< end; i++)
+ {
+ id_table.Move(tmp[i - start].id, to + i - start);
+ items[to + i - start] = tmp[i-start];
+ items[to + i - start].version = version;
+ }
+
+ if (random) {
+ // Update the positions in the queue.
+ // Note that the ranges for these cases are the same as the ranges of
+ // the loops above.
+ for (unsigned i = 0; i < length; i++) {
+ if (order[i] >= end && order[i] < to + end - start)
+ order[i] -= end - start;
+ else if (order[i] < start &&
+ order[i] >= to)
+ order[i] += end - start;
+ else if (start <= order[i] && order[i] < end)
+ order[i] += to - start;
+ }
+ }
+}
+
+void
+queue::MoveOrder(unsigned from_order, unsigned to_order)
+{
+ assert(from_order < length);
+ assert(to_order <= length);
+
+ const unsigned from_position = OrderToPosition(from_order);
+
+ if (from_order < to_order) {
+ for (unsigned i = from_order; i < to_order; ++i)
+ order[i] = order[i + 1];
+ } else {
+ for (unsigned i = from_order; i > to_order; --i)
+ order[i] = order[i - 1];
+ }
+
+ order[to_order] = from_position;
+}
+
+void
+queue::DeletePosition(unsigned position)
+{
+ assert(position < length);
+
+ struct song *song = Get(position);
+ assert(!song_in_database(song) || song_is_detached(song));
+ song_free(song);
+
+ const unsigned id = PositionToId(position);
+ const unsigned _order = PositionToOrder(position);
+
+ --length;
+
+ /* release the song id */
+
+ id_table.Erase(id);
+
+ /* delete song from songs array */
+
+ for (unsigned i = position; i < length; i++)
+ MoveItemTo(i + 1, i);
+
+ /* delete the entry from the order array */
+
+ for (unsigned i = _order; i < length; i++)
+ order[i] = order[i + 1];
+
+ /* readjust values in the order array */
+
+ for (unsigned i = 0; i < length; i++)
+ if (order[i] > position)
+ --order[i];
+}
+
+void
+queue::Clear()
+{
+ for (unsigned i = 0; i < length; i++) {
+ Item *item = &items[i];
+
+ assert(!song_in_database(item->song) ||
+ song_is_detached(item->song));
+ song_free(item->song);
+
+ id_table.Erase(item->id);
+ }
+
+ length = 0;
+}
+
+static void
+queue_sort_order_by_priority(struct queue *queue, unsigned start, unsigned end)
+{
+ assert(queue != NULL);
+ assert(queue->random);
+ assert(start <= end);
+ assert(end <= queue->length);
+
+ auto cmp = [queue](unsigned a_pos, unsigned b_pos){
+ const queue::Item &a = queue->items[a_pos];
+ const queue::Item &b = queue->items[b_pos];
+
+ return a.priority > b.priority;
+ };
+
+ std::stable_sort(queue->order + start, queue->order + end, cmp);
+}
+
+void
+queue::ShuffleOrderRange(unsigned start, unsigned end)
+{
+ assert(random);
+ assert(start <= end);
+ assert(end <= length);
+
+ rand.AutoCreate();
+ std::shuffle(order + start, order + end, rand);
+}
+
+/**
+ * Sort the "order" of items by priority, and then shuffle each
+ * priority group.
+ */
+void
+queue::ShuffleOrderRangeWithPriority(unsigned start, unsigned end)
+{
+ assert(random);
+ assert(start <= end);
+ assert(end <= length);
+
+ if (start == end)
+ return;
+
+ /* first group the range by priority */
+ queue_sort_order_by_priority(this, start, end);
+
+ /* now shuffle each priority group */
+ unsigned group_start = start;
+ uint8_t group_priority = GetOrderPriority(start);
+
+ for (unsigned i = start + 1; i < end; ++i) {
+ const uint8_t priority = GetOrderPriority(i);
+ assert(priority <= group_priority);
+
+ if (priority != group_priority) {
+ /* start of a new group - shuffle the one that
+ has just ended */
+ ShuffleOrderRange(group_start, i);
+ group_start = i;
+ group_priority = priority;
+ }
+ }
+
+ /* shuffle the last group */
+ ShuffleOrderRange(group_start, end);
+}
+
+void
+queue::ShuffleOrder()
+{
+ ShuffleOrderRangeWithPriority(0, length);
+}
+
+void
+queue::ShuffleOrderFirst(unsigned start, unsigned end)
+{
+ rand.AutoCreate();
+
+ std::uniform_int_distribution<unsigned> distribution(start, end - 1);
+ SwapOrders(start, distribution(rand));
+}
+
+void
+queue::ShuffleOrderLast(unsigned start, unsigned end)
+{
+ rand.AutoCreate();
+
+ std::uniform_int_distribution<unsigned> distribution(start, end - 1);
+ SwapOrders(end - 1, distribution(rand));
+}
+
+void
+queue::ShuffleRange(unsigned start, unsigned end)
+{
+ assert(start <= end);
+ assert(end <= length);
+
+ rand.AutoCreate();
+
+ for (unsigned i = start; i < end; i++) {
+ std::uniform_int_distribution<unsigned> distribution(start,
+ end - 1);
+ unsigned ri = distribution(rand);
+ SwapPositions(i, ri);
+ }
+}
+
+unsigned
+queue::FindPriorityOrder(unsigned start_order, uint8_t priority,
+ unsigned exclude_order) const
+{
+ assert(random);
+ assert(start_order <= length);
+
+ for (unsigned i = start_order; i < length; ++i) {
+ const unsigned position = OrderToPosition(i);
+ const Item *item = &items[position];
+ if (item->priority <= priority && i != exclude_order)
+ return i;
+ }
+
+ return length;
+}
+
+unsigned
+queue::CountSamePriority(unsigned start_order, uint8_t priority) const
+{
+ assert(random);
+ assert(start_order <= length);
+
+ for (unsigned i = start_order; i < length; ++i) {
+ const unsigned position = OrderToPosition(i);
+ const Item *item = &items[position];
+ if (item->priority != priority)
+ return i - start_order;
+ }
+
+ return length - start_order;
+}
+
+bool
+queue::SetPriority(unsigned position, uint8_t priority, int after_order)
+{
+ assert(position < length);
+
+ Item *item = &items[position];
+ uint8_t old_priority = item->priority;
+ if (old_priority == priority)
+ return false;
+
+ item->version = version;
+ item->priority = priority;
+
+ if (!random)
+ /* don't reorder if not in random mode */
+ return true;
+
+ unsigned _order = PositionToOrder(position);
+ if (after_order >= 0) {
+ if (_order == (unsigned)after_order)
+ /* don't reorder the current song */
+ return true;
+
+ if (_order < (unsigned)after_order) {
+ /* the specified song has been played already
+ - enqueue it only if its priority has just
+ become bigger than the current one's */
+
+ const unsigned after_position =
+ OrderToPosition(after_order);
+ const Item *after_item =
+ &items[after_position];
+ if (old_priority > after_item->priority ||
+ priority <= after_item->priority)
+ /* priority hasn't become bigger */
+ return true;
+ }
+ }
+
+ /* move the item to the beginning of the priority group (or
+ create a new priority group) */
+
+ const unsigned before_order =
+ FindPriorityOrder(after_order + 1, priority, _order);
+ const unsigned new_order = before_order > _order
+ ? before_order - 1
+ : before_order;
+ MoveOrder(_order, new_order);
+
+ /* shuffle the song within that priority group */
+
+ const unsigned priority_count = CountSamePriority(new_order, priority);
+ assert(priority_count >= 1);
+ ShuffleOrderFirst(new_order, new_order + priority_count);
+
+ return true;
+}
+
+bool
+queue::SetPriorityRange(unsigned start_position, unsigned end_position,
+ uint8_t priority, int after_order)
+{
+ assert(start_position <= end_position);
+ assert(end_position <= length);
+
+ bool modified = false;
+ int after_position = after_order >= 0
+ ? (int)OrderToPosition(after_order)
+ : -1;
+ for (unsigned i = start_position; i < end_position; ++i) {
+ after_order = after_position >= 0
+ ? (int)PositionToOrder(after_position)
+ : -1;
+
+ modified |= SetPriority(i, priority, after_order);
+ }
+
+ return modified;
+}