1 files changed, 378 insertions, 0 deletions
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