playlist: convert to C++

1 files changed, 604 insertions, 0 deletions

diff --git a/src/Queue.cxx b/src/Queue.cxx
new file mode 100644
index 00000000..485ffb1c
--- /dev/null
+++ b/src/Queue.cxx
@@ -0,0 +1,604 @@
+/*
+ * 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>
+
+/**
+ * Generate a non-existing id number.
+ */
+static unsigned
+queue_generate_id(const struct queue *queue)
+{
+	static unsigned cur = (unsigned)-1;
+
+	do {
+		cur++;
+
+		if (cur >= queue->max_length * QUEUE_HASH_MULT)
+			cur = 0;
+	} while (queue->id_to_position[cur] != -1);
+
+	return cur;
+}
+
+int
+queue_next_order(const struct queue *queue, unsigned order)
+{
+	assert(order < queue->length);
+
+	if (queue->single && queue->repeat && !queue->consume)
+		return order;
+	else if (order + 1 < queue->length)
+		return order + 1;
+	else if (queue->repeat && (order > 0 || !queue->consume))
+		/* restart at first song */
+		return 0;
+	else
+		/* end of queue */
+		return -1;
+}
+
+void
+queue_increment_version(struct queue *queue)
+{
+	static unsigned long max = ((uint32_t) 1 << 31) - 1;
+
+	queue->version++;
+
+	if (queue->version >= max) {
+		for (unsigned i = 0; i < queue->length; i++)
+			queue->items[i].version = 0;
+
+		queue->version = 1;
+	}
+}
+
+void
+queue_modify(struct queue *queue, unsigned order)
+{
+	unsigned position;
+
+	assert(order < queue->length);
+
+	position = queue->order[order];
+	queue->items[position].version = queue->version;
+
+	queue_increment_version(queue);
+}
+
+void
+queue_modify_all(struct queue *queue)
+{
+	for (unsigned i = 0; i < queue->length; i++)
+		queue->items[i].version = queue->version;
+
+	queue_increment_version(queue);
+}
+
+unsigned
+queue_append(struct queue *queue, struct song *song, uint8_t priority)
+{
+	unsigned id = queue_generate_id(queue);
+
+	assert(!queue_is_full(queue));
+
+	auto &item = queue->items[queue->length];
+	item.song = song_dup_detached(song);
+	item.id = id;
+	item.version = queue->version;
+	item.priority = priority;
+
+	queue->order[queue->length] = queue->length;
+	queue->id_to_position[id] = queue->length;
+
+	++queue->length;
+
+	return id;
+}
+
+void
+queue_swap(struct queue *queue, unsigned position1, unsigned position2)
+{
+	struct queue_item tmp;
+	unsigned id1 = queue->items[position1].id;
+	unsigned id2 = queue->items[position2].id;
+
+	tmp = queue->items[position1];
+	queue->items[position1] = queue->items[position2];
+	queue->items[position2] = tmp;
+
+	queue->items[position1].version = queue->version;
+	queue->items[position2].version = queue->version;
+
+	queue->id_to_position[id1] = position2;
+	queue->id_to_position[id2] = position1;
+}
+
+static void
+queue_move_song_to(struct queue *queue, unsigned from, unsigned to)
+{
+	unsigned from_id = queue->items[from].id;
+
+	queue->items[to] = queue->items[from];
+	queue->items[to].version = queue->version;
+	queue->id_to_position[from_id] = to;
+}
+
+void
+queue_move(struct queue *queue, unsigned from, unsigned to)
+{
+	struct queue_item item = queue->items[from];
+
+	/* move songs to one less in from->to */
+
+	for (unsigned i = from; i < to; i++)
+		queue_move_song_to(queue, i + 1, i);
+
+	/* move songs to one more in to->from */
+
+	for (unsigned i = from; i > to; i--)
+		queue_move_song_to(queue, i - 1, i);
+
+	/* put song at _to_ */
+
+	queue->id_to_position[item.id] = to;
+	queue->items[to] = item;
+	queue->items[to].version = queue->version;
+
+	/* now deal with order */
+
+	if (queue->random) {
+		for (unsigned i = 0; i < queue->length; i++) {
+			if (queue->order[i] > from && queue->order[i] <= to)
+				queue->order[i]--;
+			else if (queue->order[i] < from &&
+				 queue->order[i] >= to)
+				queue->order[i]++;
+			else if (from == queue->order[i])
+				queue->order[i] = to;
+		}
+	}
+}
+
+void
+queue_move_range(struct queue *queue, unsigned start, unsigned end, unsigned to)
+{
+	struct queue_item items[end - start];
+	// Copy the original block [start,end-1]
+	for (unsigned i = start; i < end; i++)
+		items[i - start] = queue->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++)
+		queue_move_song_to(queue, 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 (unsigned i = start - 1; i >= to && i != G_MAXUINT; i--)
+		queue_move_song_to(queue, i, i + end - start);
+
+	// Copy the original block back in, starting at to.
+	for (unsigned i = start; i< end; i++)
+	{
+		queue->id_to_position[items[i-start].id] = to + i - start;
+		queue->items[to + i - start] = items[i-start];
+		queue->items[to + i - start].version = queue->version;
+	}
+
+	if (queue->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 < queue->length; i++) {
+			if (queue->order[i] >= end && queue->order[i] < to + end - start)
+				queue->order[i] -= end - start;
+			else if (queue->order[i] < start &&
+				 queue->order[i] >= to)
+				queue->order[i] += end - start;
+			else if (start <= queue->order[i] && queue->order[i] < end)
+				queue->order[i] += to - start;
+		}
+	}
+}
+
+/**
+ * Moves a song to a new position in the "order" list.
+ */
+static void
+queue_move_order(struct queue *queue, unsigned from_order, unsigned to_order)
+{
+	assert(queue != NULL);
+	assert(from_order < queue->length);
+	assert(to_order <= queue->length);
+
+	const unsigned from_position =
+		queue_order_to_position(queue, from_order);
+
+	if (from_order < to_order) {
+		for (unsigned i = from_order; i < to_order; ++i)
+			queue->order[i] = queue->order[i + 1];
+	} else {
+		for (unsigned i = from_order; i > to_order; --i)
+			queue->order[i] = queue->order[i - 1];
+	}
+
+	queue->order[to_order] = from_position;
+}
+
+void
+queue_delete(struct queue *queue, unsigned position)
+{
+	struct song *song;
+	unsigned id, order;
+
+	assert(position < queue->length);
+
+	song = queue_get(queue, position);
+	assert(!song_in_database(song) || song_is_detached(song));
+	song_free(song);
+
+	id = queue_position_to_id(queue, position);
+	order = queue_position_to_order(queue, position);
+
+	--queue->length;
+
+	/* release the song id */
+
+	queue->id_to_position[id] = -1;
+
+	/* delete song from songs array */
+
+	for (unsigned i = position; i < queue->length; i++)
+		queue_move_song_to(queue, i + 1, i);
+
+	/* delete the entry from the order array */
+
+	for (unsigned i = order; i < queue->length; i++)
+		queue->order[i] = queue->order[i + 1];
+
+	/* readjust values in the order array */
+
+	for (unsigned i = 0; i < queue->length; i++)
+		if (queue->order[i] > position)
+			--queue->order[i];
+}
+
+void
+queue_clear(struct queue *queue)
+{
+	for (unsigned i = 0; i < queue->length; i++) {
+		struct queue_item *item = &queue->items[i];
+
+		assert(!song_in_database(item->song) ||
+		       song_is_detached(item->song));
+		song_free(item->song);
+
+		queue->id_to_position[item->id] = -1;
+	}
+
+	queue->length = 0;
+}
+
+void
+queue_init(struct queue *queue, unsigned max_length)
+{
+	queue->max_length = max_length;
+	queue->length = 0;
+	queue->version = 1;
+	queue->repeat = false;
+	queue->random = false;
+	queue->single = false;
+	queue->consume = false;
+
+	queue->items = g_new(struct queue_item, max_length);
+	queue->order = (unsigned *)
+		g_malloc(sizeof(queue->order[0]) * max_length);
+	queue->id_to_position = (int *)
+		g_malloc(sizeof(queue->id_to_position[0]) *
+			 max_length * QUEUE_HASH_MULT);
+
+	for (unsigned i = 0; i < max_length * QUEUE_HASH_MULT; ++i)
+		queue->id_to_position[i] = -1;
+
+	queue->rand = g_rand_new();
+}
+
+void
+queue_finish(struct queue *queue)
+{
+	queue_clear(queue);
+
+	g_free(queue->items);
+	g_free(queue->order);
+	g_free(queue->id_to_position);
+
+	g_rand_free(queue->rand);
+}
+
+static const struct queue_item *
+queue_get_order_item_const(const struct queue *queue, unsigned order)
+{
+	assert(queue != NULL);
+	assert(order < queue->length);
+
+	return &queue->items[queue->order[order]];
+}
+
+static uint8_t
+queue_get_order_priority(const struct queue *queue, unsigned order)
+{
+	return queue_get_order_item_const(queue, order)->priority;
+}
+
+static gint
+queue_item_compare_order_priority(gconstpointer av, gconstpointer bv,
+				  gpointer user_data)
+{
+	const struct queue *queue = (const struct queue *)user_data;
+	const unsigned *const ap = (const unsigned *)av;
+	const unsigned *const bp = (const unsigned *)bv;
+	assert(ap >= queue->order && ap < queue->order + queue->length);
+	assert(bp >= queue->order && bp < queue->order + queue->length);
+	uint8_t a = queue->items[*ap].priority;
+	uint8_t b = queue->items[*bp].priority;
+
+	if (G_LIKELY(a == b))
+		return 0;
+	else if (a > b)
+		return -1;
+	else
+		return 1;
+}
+
+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);
+
+	g_qsort_with_data(&queue->order[start], end - start,
+			  sizeof(queue->order[0]),
+			  queue_item_compare_order_priority,
+			  queue);
+}
+
+/**
+ * Shuffle the order of items in the specified range, ignoring their
+ * priorities.
+ */
+static void
+queue_shuffle_order_range(struct queue *queue, unsigned start, unsigned end)
+{
+	assert(queue != NULL);
+	assert(queue->random);
+	assert(start <= end);
+	assert(end <= queue->length);
+
+	for (unsigned i = start; i < end; ++i)
+		queue_swap_order(queue, i,
+				 g_rand_int_range(queue->rand, i, end));
+}
+
+/**
+ * Sort the "order" of items by priority, and then shuffle each
+ * priority group.
+ */
+void
+queue_shuffle_order_range_with_priority(struct queue *queue,
+					unsigned start, unsigned end)
+{
+	assert(queue != NULL);
+	assert(queue->random);
+	assert(start <= end);
+	assert(end <= queue->length);
+
+	if (start == end)
+		return;
+
+	/* first group the range by priority */
+	queue_sort_order_by_priority(queue, start, end);
+
+	/* now shuffle each priority group */
+	unsigned group_start = start;
+	uint8_t group_priority = queue_get_order_priority(queue, start);
+
+	for (unsigned i = start + 1; i < end; ++i) {
+		uint8_t priority = queue_get_order_priority(queue, i);
+		assert(priority <= group_priority);
+
+		if (priority != group_priority) {
+			/* start of a new group - shuffle the one that
+			   has just ended */
+			queue_shuffle_order_range(queue, group_start, i);
+			group_start = i;
+			group_priority = priority;
+		}
+	}
+
+	/* shuffle the last group */
+	queue_shuffle_order_range(queue, group_start, end);
+}
+
+void
+queue_shuffle_order(struct queue *queue)
+{
+	queue_shuffle_order_range_with_priority(queue, 0, queue->length);
+}
+
+static void
+queue_shuffle_order_first(struct queue *queue, unsigned start, unsigned end)
+{
+	queue_swap_order(queue, start,
+			 g_rand_int_range(queue->rand, start, end));
+}
+
+void
+queue_shuffle_order_last(struct queue *queue, unsigned start, unsigned end)
+{
+	queue_swap_order(queue, end - 1,
+			 g_rand_int_range(queue->rand, start, end));
+}
+
+void
+queue_shuffle_range(struct queue *queue, unsigned start, unsigned end)
+{
+	assert(start <= end);
+	assert(end <= queue->length);
+
+	for (unsigned i = start; i < end; i++) {
+		unsigned ri = g_rand_int_range(queue->rand, i, end);
+		queue_swap(queue, i, ri);
+	}
+}
+
+/**
+ * Find the first item that has this specified priority or higher.
+ */
+G_GNUC_PURE
+static unsigned
+queue_find_priority_order(const struct queue *queue, unsigned start_order,
+			  uint8_t priority, unsigned exclude_order)
+{
+	assert(queue != NULL);
+	assert(queue->random);
+	assert(start_order <= queue->length);
+
+	for (unsigned order = start_order; order < queue->length; ++order) {
+		const unsigned position = queue_order_to_position(queue, order);
+		const struct queue_item *item = &queue->items[position];
+		if (item->priority <= priority && order != exclude_order)
+			return order;
+	}
+
+	return queue->length;
+}
+
+G_GNUC_PURE
+static unsigned
+queue_count_same_priority(const struct queue *queue, unsigned start_order,
+			  uint8_t priority)
+{
+	assert(queue != NULL);
+	assert(queue->random);
+	assert(start_order <= queue->length);
+
+	for (unsigned order = start_order; order < queue->length; ++order) {
+		const unsigned position = queue_order_to_position(queue, order);
+		const struct queue_item *item = &queue->items[position];
+		if (item->priority != priority)
+			return order - start_order;
+	}
+
+	return queue->length - start_order;
+}
+
+bool
+queue_set_priority(struct queue *queue, unsigned position, uint8_t priority,
+		   int after_order)
+{
+	assert(queue != NULL);
+	assert(position < queue->length);
+
+	struct queue_item *item = &queue->items[position];
+	uint8_t old_priority = item->priority;
+	if (old_priority == priority)
+		return false;
+
+	item->version = queue->version;
+	item->priority = priority;
+
+	if (!queue->random)
+		/* don't reorder if not in random mode */
+		return true;
+
+	unsigned order = queue_position_to_order(queue, 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 =
+				queue_order_to_position(queue, after_order);
+			const struct queue_item *after_item =
+				&queue->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 =
+		queue_find_priority_order(queue, after_order + 1, priority,
+					  order);
+	const unsigned new_order = before_order > order
+		? before_order - 1
+		: before_order;
+	queue_move_order(queue, order, new_order);
+
+	/* shuffle the song within that priority group */
+
+	const unsigned priority_count =
+		queue_count_same_priority(queue, new_order, priority);
+	assert(priority_count >= 1);
+	queue_shuffle_order_first(queue, new_order,
+				  new_order + priority_count);
+
+	return true;
+}
+
+bool
+queue_set_priority_range(struct queue *queue,
+			 unsigned start_position, unsigned end_position,
+			 uint8_t priority, int after_order)
+{
+	assert(queue != NULL);
+	assert(start_position <= end_position);
+	assert(end_position <= queue->length);
+
+	bool modified = false;
+	int after_position = after_order >= 0
+		? (int)queue_order_to_position(queue, after_order)
+		: -1;
+	for (unsigned i = start_position; i < end_position; ++i) {
+		after_order = after_position >= 0
+			? (int)queue_position_to_order(queue, after_position)
+			: -1;
+
+		modified |= queue_set_priority(queue, i, priority,
+					       after_order);
+	}
+
+	return modified;
+}