Queue*: move to queue/

7 files changed, 1270 insertions, 0 deletions

diff --git a/src/queue/IdTable.hxx b/src/queue/IdTable.hxx
new file mode 100644
index 000000000..8e445243d
--- /dev/null
+++ b/src/queue/IdTable.hxx
@@ -0,0 +1,91 @@
+/*
+ * Copyright (C) 2003-2014 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.
+ */
+
+#ifndef MPD_ID_TABLE_HXX
+#define MPD_ID_TABLE_HXX
+
+#include "Compiler.h"
+
+#include <algorithm>
+
+#include <assert.h>
+
+/**
+ * A table that maps id numbers to position numbers.
+ */
+class IdTable {
+	unsigned size;
+
+	unsigned next;
+
+	int *data;
+
+public:
+	IdTable(unsigned _size):size(_size), next(1), data(new int[size]) {
+		std::fill_n(data, size, -1);
+	}
+
+	~IdTable() {
+		delete[] data;
+	}
+
+	int IdToPosition(unsigned id) const {
+		return id < size
+			? data[id]
+			: -1;
+	}
+
+	unsigned GenerateId() {
+		assert(next > 0);
+		assert(next < size);
+
+		while (true) {
+			unsigned id = next;
+
+			++next;
+			if (next == size)
+				next = 1;
+
+			if (data[id] < 0)
+				return id;
+		}
+	}
+
+	unsigned Insert(unsigned position) {
+		unsigned id = GenerateId();
+		data[id] = position;
+		return id;
+	}
+
+	void Move(unsigned id, unsigned position) {
+		assert(id < size);
+		assert(data[id] >= 0);
+
+		data[id] = position;
+	}
+
+	void Erase(unsigned id) {
+		assert(id < size);
+		assert(data[id] >= 0);
+
+		data[id] = -1;
+	}
+};
+
+#endif
diff --git a/src/queue/Queue.cxx b/src/queue/Queue.cxx
new file mode 100644
index 000000000..99b545ab1
--- /dev/null
+++ b/src/queue/Queue.cxx
@@ -0,0 +1,482 @@
+/*
+ * Copyright (C) 2003-2014 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 "DetachedSong.hxx"
+
+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];
+	ModifyAtPosition(position);
+}
+
+unsigned
+Queue::Append(DetachedSong &&song, uint8_t priority)
+{
+	assert(!IsFull());
+
+	const unsigned position = length++;
+	const unsigned id = id_table.Insert(position);
+
+	auto &item = items[position];
+	item.song = new DetachedSong(std::move(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);
+
+	delete items[position].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];
+
+		delete item->song;
+
+		id_table.Erase(item->id);
+	}
+
+	length = 0;
+}
+
+static void
+queue_sort_order_by_priority(Queue *queue, unsigned start, unsigned end)
+{
+	assert(queue != nullptr);
+	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;
+}
diff --git a/src/queue/Queue.hxx b/src/queue/Queue.hxx
new file mode 100644
index 000000000..016619e65
--- /dev/null
+++ b/src/queue/Queue.hxx
@@ -0,0 +1,378 @@
+/*
+ * Copyright (C) 2003-2014 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.
+ */
+
+#ifndef MPD_QUEUE_HXX
+#define MPD_QUEUE_HXX
+
+#include "Compiler.h"
+#include "IdTable.hxx"
+#include "util/LazyRandomEngine.hxx"
+
+#include <algorithm>
+
+#include <assert.h>
+#include <stdint.h>
+
+class DetachedSong;
+
+/**
+ * A queue of songs.  This is the backend of the playlist: it contains
+ * an ordered list of songs.
+ *
+ * Songs can be addressed in three possible ways:
+ *
+ * - the position in the queue
+ * - the unique id (which stays the same, regardless of moves)
+ * - the order number (which only differs from "position" in random mode)
+ */
+struct Queue {
+	/**
+	 * reserve max_length * HASH_MULT elements in the id
+	 * number space
+	 */
+	static constexpr unsigned HASH_MULT = 4;
+
+	/**
+	 * One element of the queue: basically a song plus some queue specific
+	 * information attached.
+	 */
+	struct Item {
+		DetachedSong *song;
+
+		/** the unique id of this item in the queue */
+		unsigned id;
+
+		/** when was this item last changed? */
+		uint32_t version;
+
+		/**
+		 * The priority of this item, between 0 and 255.  High
+		 * priority value means that this song gets played first in
+		 * "random" mode.
+		 */
+		uint8_t priority;
+	};
+
+	/** configured maximum length of the queue */
+	unsigned max_length;
+
+	/** number of songs in the queue */
+	unsigned length;
+
+	/** the current version number */
+	uint32_t version;
+
+	/** all songs in "position" order */
+	Item *items;
+
+	/** map order numbers to positions */
+	unsigned *order;
+
+	/** map song ids to positions */
+	IdTable id_table;
+
+	/** repeat playback when the end of the queue has been
+	    reached? */
+	bool repeat;
+
+	/** play only current song. */
+	bool single;
+
+	/** remove each played files. */
+	bool consume;
+
+	/** play back songs in random order? */
+	bool random;
+
+	/** random number generator for shuffle and random mode */
+	LazyRandomEngine rand;
+
+	explicit Queue(unsigned max_length);
+
+	/**
+	 * Deinitializes a queue object.  It does not free the queue
+	 * pointer itself.
+	 */
+	~Queue();
+
+	Queue(const Queue &) = delete;
+	Queue &operator=(const Queue &) = delete;
+
+	unsigned GetLength() const {
+		assert(length <= max_length);
+
+		return length;
+	}
+
+	/**
+	 * Determine if the queue is empty, i.e. there are no songs.
+	 */
+	bool IsEmpty() const {
+		return length == 0;
+	}
+
+	/**
+	 * Determine if the maximum number of songs has been reached.
+	 */
+	bool IsFull() const {
+		assert(length <= max_length);
+
+		return length >= max_length;
+	}
+
+	/**
+	 * Is that a valid position number?
+	 */
+	bool IsValidPosition(unsigned position) const {
+		return position < length;
+	}
+
+	/**
+	 * Is that a valid order number?
+	 */
+	bool IsValidOrder(unsigned _order) const {
+		return _order < length;
+	}
+
+	int IdToPosition(unsigned id) const {
+		return id_table.IdToPosition(id);
+	}
+
+	int PositionToId(unsigned position) const
+	{
+		assert(position < length);
+
+		return items[position].id;
+	}
+
+	gcc_pure
+	unsigned OrderToPosition(unsigned _order) const {
+		assert(_order < length);
+
+		return order[_order];
+	}
+
+	gcc_pure
+	unsigned PositionToOrder(unsigned position) const {
+		assert(position < length);
+
+		for (unsigned i = 0;; ++i) {
+			assert(i < length);
+
+			if (order[i] == position)
+				return i;
+		}
+	}
+
+	gcc_pure
+	uint8_t GetPriorityAtPosition(unsigned position) const {
+		assert(position < length);
+
+		return items[position].priority;
+	}
+
+	const Item &GetOrderItem(unsigned i) const {
+		assert(IsValidOrder(i));
+
+		return items[OrderToPosition(i)];
+	}
+
+	uint8_t GetOrderPriority(unsigned i) const {
+		return GetOrderItem(i).priority;
+	}
+
+	/**
+	 * Returns the song at the specified position.
+	 */
+	DetachedSong &Get(unsigned position) const {
+		assert(position < length);
+
+		return *items[position].song;
+	}
+
+	/**
+	 * Returns the song at the specified order number.
+	 */
+	DetachedSong &GetOrder(unsigned _order) const {
+		return Get(OrderToPosition(_order));
+	}
+
+	/**
+	 * Is the song at the specified position newer than the specified
+	 * version?
+	 */
+	bool IsNewerAtPosition(unsigned position, uint32_t _version) const {
+		assert(position < length);
+
+		return _version > version ||
+			items[position].version >= _version ||
+			items[position].version == 0;
+	}
+
+	/**
+	 * Returns the order number following the specified one.  This takes
+	 * end of queue and "repeat" mode into account.
+	 *
+	 * @return the next order number, or -1 to stop playback
+	 */
+	gcc_pure
+	int GetNextOrder(unsigned order) const;
+
+	/**
+	 * Increments the queue's version number.  This handles integer
+	 * overflow well.
+	 */
+	void IncrementVersion();
+
+	/**
+	 * Marks the specified song as "modified".  Call
+	 * IncrementVersion() after all modifications have been made.
+	 * number.
+	 */
+	void ModifyAtPosition(unsigned position) {
+		assert(position < length);
+
+		items[position].version = version;
+	}
+
+	/**
+	 * Marks the specified song as "modified".  Call
+	 * IncrementVersion() after all modifications have been made.
+	 * number.
+	 */
+	void ModifyAtOrder(unsigned order);
+
+	/**
+	 * Appends a song to the queue and returns its position.  Prior to
+	 * that, the caller must check if the queue is already full.
+	 *
+	 * If a song is not in the database (determined by
+	 * Song::IsInDatabase()), it is freed when removed from the
+	 * queue.
+	 *
+	 * @param priority the priority of this new queue item
+	 */
+	unsigned Append(DetachedSong &&song, uint8_t priority);
+
+	/**
+	 * Swaps two songs, addressed by their position.
+	 */
+	void SwapPositions(unsigned position1, unsigned position2);
+
+	/**
+	 * Swaps two songs, addressed by their order number.
+	 */
+	void SwapOrders(unsigned order1, unsigned order2) {
+		std::swap(order[order1], order[order2]);
+	}
+
+	/**
+	 * Moves a song to a new position.
+	 */
+	void MovePostion(unsigned from, unsigned to);
+
+	/**
+	 * Moves a range of songs to a new position.
+	 */
+	void MoveRange(unsigned start, unsigned end, unsigned to);
+
+	/**
+	 * Removes a song from the playlist.
+	 */
+	void DeletePosition(unsigned position);
+
+	/**
+	 * Removes all songs from the playlist.
+	 */
+	void Clear();
+
+	/**
+	 * Initializes the "order" array, and restores "normal" order.
+	 */
+	void RestoreOrder() {
+		for (unsigned i = 0; i < length; ++i)
+			order[i] = i;
+	}
+
+	/**
+	 * Shuffle the order of items in the specified range, ignoring
+	 * their priorities.
+	 */
+	void ShuffleOrderRange(unsigned start, unsigned end);
+
+	/**
+	 * Shuffle the order of items in the specified range, taking their
+	 * priorities into account.
+	 */
+	void ShuffleOrderRangeWithPriority(unsigned start, unsigned end);
+
+	/**
+	 * Shuffles the virtual order of songs, but does not move them
+	 * physically.  This is used in random mode.
+	 */
+	void ShuffleOrder();
+
+	void ShuffleOrderFirst(unsigned start, unsigned end);
+
+	/**
+	 * Shuffles the virtual order of the last song in the specified
+	 * (order) range.  This is used in random mode after a song has been
+	 * appended by queue_append().
+	 */
+	void ShuffleOrderLast(unsigned start, unsigned end);
+
+	/**
+	 * Shuffles a (position) range in the queue.  The songs are physically
+	 * shuffled, not by using the "order" mapping.
+	 */
+	void ShuffleRange(unsigned start, unsigned end);
+
+	bool SetPriority(unsigned position, uint8_t priority, int after_order);
+
+	bool SetPriorityRange(unsigned start_position, unsigned end_position,
+			      uint8_t priority, int after_order);
+
+private:
+	/**
+	 * Moves a song to a new position in the "order" list.
+	 */
+	void MoveOrder(unsigned from_order, unsigned to_order);
+
+	void MoveItemTo(unsigned from, unsigned to) {
+		unsigned from_id = items[from].id;
+
+		items[to] = items[from];
+		items[to].version = version;
+		id_table.Move(from_id, to);
+	}
+
+	/**
+	 * Find the first item that has this specified priority or
+	 * higher.
+	 */
+	gcc_pure
+	unsigned FindPriorityOrder(unsigned start_order, uint8_t priority,
+				   unsigned exclude_order) const;
+
+	gcc_pure
+	unsigned CountSamePriority(unsigned start_order,
+				   uint8_t priority) const;
+};
+
+#endif
diff --git a/src/queue/QueuePrint.cxx b/src/queue/QueuePrint.cxx
new file mode 100644
index 000000000..1f3c8fd57
--- /dev/null
+++ b/src/queue/QueuePrint.cxx
@@ -0,0 +1,102 @@
+/*
+ * Copyright (C) 2003-2014 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 "QueuePrint.hxx"
+#include "Queue.hxx"
+#include "SongFilter.hxx"
+#include "SongPrint.hxx"
+#include "Client.hxx"
+
+/**
+ * Send detailed information about a range of songs in the queue to a
+ * client.
+ *
+ * @param client the client which has requested information
+ * @param start the index of the first song (including)
+ * @param end the index of the last song (excluding)
+ */
+static void
+queue_print_song_info(Client &client, const Queue &queue,
+		      unsigned position)
+{
+	song_print_info(client, queue.Get(position));
+	client_printf(client, "Pos: %u\nId: %u\n",
+		      position, queue.PositionToId(position));
+
+	uint8_t priority = queue.GetPriorityAtPosition(position);
+	if (priority != 0)
+		client_printf(client, "Prio: %u\n", priority);
+}
+
+void
+queue_print_info(Client &client, const Queue &queue,
+		 unsigned start, unsigned end)
+{
+	assert(start <= end);
+	assert(end <= queue.GetLength());
+
+	for (unsigned i = start; i < end; ++i)
+		queue_print_song_info(client, queue, i);
+}
+
+void
+queue_print_uris(Client &client, const Queue &queue,
+		 unsigned start, unsigned end)
+{
+	assert(start <= end);
+	assert(end <= queue.GetLength());
+
+	for (unsigned i = start; i < end; ++i) {
+		client_printf(client, "%i:", i);
+		song_print_uri(client, queue.Get(i));
+	}
+}
+
+void
+queue_print_changes_info(Client &client, const Queue &queue,
+			 uint32_t version)
+{
+	for (unsigned i = 0; i < queue.GetLength(); i++) {
+		if (queue.IsNewerAtPosition(i, version))
+			queue_print_song_info(client, queue, i);
+	}
+}
+
+void
+queue_print_changes_position(Client &client, const Queue &queue,
+			     uint32_t version)
+{
+	for (unsigned i = 0; i < queue.GetLength(); i++)
+		if (queue.IsNewerAtPosition(i, version))
+			client_printf(client, "cpos: %i\nId: %i\n",
+				      i, queue.PositionToId(i));
+}
+
+void
+queue_find(Client &client, const Queue &queue,
+	   const SongFilter &filter)
+{
+	for (unsigned i = 0; i < queue.GetLength(); i++) {
+		const DetachedSong &song = queue.Get(i);
+
+		if (filter.Match(song))
+			queue_print_song_info(client, queue, i);
+	}
+}
diff --git a/src/queue/QueuePrint.hxx b/src/queue/QueuePrint.hxx
new file mode 100644
index 000000000..1aa876219
--- /dev/null
+++ b/src/queue/QueuePrint.hxx
@@ -0,0 +1,54 @@
+/*
+ * Copyright (C) 2003-2014 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.
+ */
+
+/*
+ * This library sends information about songs in the queue to the
+ * client.
+ */
+
+#ifndef MPD_QUEUE_PRINT_HXX
+#define MPD_QUEUE_PRINT_HXX
+
+#include <stdint.h>
+
+struct Queue;
+class SongFilter;
+class Client;
+
+void
+queue_print_info(Client &client, const Queue &queue,
+		 unsigned start, unsigned end);
+
+void
+queue_print_uris(Client &client, const Queue &queue,
+		 unsigned start, unsigned end);
+
+void
+queue_print_changes_info(Client &client, const Queue &queue,
+			 uint32_t version);
+
+void
+queue_print_changes_position(Client &client, const Queue &queue,
+			     uint32_t version);
+
+void
+queue_find(Client &client, const Queue &queue,
+	   const SongFilter &filter);
+
+#endif
diff --git a/src/queue/QueueSave.cxx b/src/queue/QueueSave.cxx
new file mode 100644
index 000000000..87de02c56
--- /dev/null
+++ b/src/queue/QueueSave.cxx
@@ -0,0 +1,121 @@
+/*
+ * Copyright (C) 2003-2014 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 "QueueSave.hxx"
+#include "Queue.hxx"
+#include "PlaylistError.hxx"
+#include "DetachedSong.hxx"
+#include "SongSave.hxx"
+#include "DatabaseSong.hxx"
+#include "fs/TextFile.hxx"
+#include "util/StringUtil.hxx"
+#include "util/UriUtil.hxx"
+#include "util/Error.hxx"
+#include "fs/Traits.hxx"
+#include "Log.hxx"
+
+#include <stdlib.h>
+
+#define PRIO_LABEL "Prio: "
+
+static void
+queue_save_database_song(FILE *fp, int idx, const DetachedSong &song)
+{
+	fprintf(fp, "%i:%s\n", idx, song.GetURI());
+}
+
+static void
+queue_save_full_song(FILE *fp, const DetachedSong &song)
+{
+	song_save(fp, song);
+}
+
+static void
+queue_save_song(FILE *fp, int idx, const DetachedSong &song)
+{
+	if (song.IsInDatabase())
+		queue_save_database_song(fp, idx, song);
+	else
+		queue_save_full_song(fp, song);
+}
+
+void
+queue_save(FILE *fp, const Queue &queue)
+{
+	for (unsigned i = 0; i < queue.GetLength(); i++) {
+		uint8_t prio = queue.GetPriorityAtPosition(i);
+		if (prio != 0)
+			fprintf(fp, PRIO_LABEL "%u\n", prio);
+
+		queue_save_song(fp, i, queue.Get(i));
+	}
+}
+
+void
+queue_load_song(TextFile &file, const char *line, Queue &queue)
+{
+	if (queue.IsFull())
+		return;
+
+	uint8_t priority = 0;
+	if (StringStartsWith(line, PRIO_LABEL)) {
+		priority = strtoul(line + sizeof(PRIO_LABEL) - 1, nullptr, 10);
+
+		line = file.ReadLine();
+		if (line == nullptr)
+			return;
+	}
+
+	DetachedSong *song;
+
+	if (StringStartsWith(line, SONG_BEGIN)) {
+		const char *uri = line + sizeof(SONG_BEGIN) - 1;
+		if (!uri_has_scheme(uri) && !PathTraitsUTF8::IsAbsolute(uri))
+			return;
+
+		Error error;
+		song = song_load(file, uri, error);
+		if (song == nullptr) {
+			LogError(error);
+			return;
+		}
+	} else {
+		char *endptr;
+		long ret = strtol(line, &endptr, 10);
+		if (ret < 0 || *endptr != ':' || endptr[1] == 0) {
+			LogError(playlist_domain,
+				 "Malformed playlist line in state file");
+			return;
+		}
+
+		const char *uri = endptr + 1;
+
+		if (uri_has_scheme(uri)) {
+			song = new DetachedSong(uri);
+		} else {
+			song = DatabaseDetachSong(uri, IgnoreError());
+			if (song == nullptr)
+				return;
+		}
+	}
+
+	queue.Append(std::move(*song), priority);
+	delete song;
+}
diff --git a/src/queue/QueueSave.hxx b/src/queue/QueueSave.hxx
new file mode 100644
index 000000000..c9a646369
--- /dev/null
+++ b/src/queue/QueueSave.hxx
@@ -0,0 +1,42 @@
+/*
+ * Copyright (C) 2003-2014 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.
+ */
+
+/*
+ * This library saves the queue into the state file, and also loads it
+ * back into memory.
+ */
+
+#ifndef MPD_QUEUE_SAVE_HXX
+#define MPD_QUEUE_SAVE_HXX
+
+#include <stdio.h>
+
+struct Queue;
+class TextFile;
+
+void
+queue_save(FILE *fp, const Queue &queue);
+
+/**
+ * Loads one song from the state file and appends it to the queue.
+ */
+void
+queue_load_song(TextFile &file, const char *line, Queue &queue);
+
+#endif