queue.c 8.04 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13
/*
 * Copyright (C) 2003-2009 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.
14 15 16 17
 *
 * 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.
18 19
 */

20
#include "config.h"
21 22 23
#include "queue.h"
#include "song.h"

24 25 26 27
/**
 * Generate a non-existing id number.
 */
static unsigned
28 29 30 31 32 33 34 35 36
queue_generate_id(const struct queue *queue)
{
	static unsigned cur = (unsigned)-1;

	do {
		cur++;

		if (cur >= queue->max_length * QUEUE_HASH_MULT)
			cur = 0;
Max Kellermann's avatar
Max Kellermann committed
37
	} while (queue->id_to_position[cur] != -1);
38 39 40 41 42 43 44 45 46

	return cur;
}

int
queue_next_order(const struct queue *queue, unsigned order)
{
	assert(order < queue->length);

47 48 49 50 51 52 53
	if (queue->single)
	{
		if (queue->repeat)
			return order;
		else
			return -1;
	}
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
	if (order + 1 < queue->length)
		return order + 1;
	else if (queue->repeat)
		/* 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++)
73
			queue->items[i].version = 0;
74 75 76 77 78 79 80 81 82 83 84 85 86

		queue->version = 1;
	}
}

void
queue_modify(struct queue *queue, unsigned order)
{
	unsigned position;

	assert(order < queue->length);

	position = queue->order[order];
87
	queue->items[position].version = queue->version;
88 89 90 91 92 93 94 95

	queue_increment_version(queue);
}

void
queue_modify_all(struct queue *queue)
{
	for (unsigned i = 0; i < queue->length; i++)
96
		queue->items[i].version = queue->version;
97 98 99 100 101 102 103 104 105 106 107

	queue_increment_version(queue);
}

unsigned
queue_append(struct queue *queue, struct song *song)
{
	unsigned id = queue_generate_id(queue);

	assert(!queue_is_full(queue));

108 109 110 111 112 113
	queue->items[queue->length] = (struct queue_item){
		.song = song,
		.id = id,
		.version = queue->version,
	};

114
	queue->order[queue->length] = queue->length;
Max Kellermann's avatar
Max Kellermann committed
115
	queue->id_to_position[id] = queue->length;
116 117 118 119 120 121 122 123 124

	++queue->length;

	return id;
}

void
queue_swap(struct queue *queue, unsigned position1, unsigned position2)
{
125 126 127
	struct queue_item tmp;
	unsigned id1 = queue->items[position1].id;
	unsigned id2 = queue->items[position2].id;
128

129 130 131
	tmp = queue->items[position1];
	queue->items[position1] = queue->items[position2];
	queue->items[position2] = tmp;
132

133 134
	queue->items[position1].version = queue->version;
	queue->items[position2].version = queue->version;
135

Max Kellermann's avatar
Max Kellermann committed
136 137
	queue->id_to_position[id1] = position2;
	queue->id_to_position[id2] = position1;
138 139 140 141 142
}

static void
queue_move_song_to(struct queue *queue, unsigned from, unsigned to)
{
143
	unsigned from_id = queue->items[from].id;
144

145
	queue->items[to] = queue->items[from];
146
	queue->items[to].version = queue->version;
Max Kellermann's avatar
Max Kellermann committed
147
	queue->id_to_position[from_id] = to;
148 149 150 151 152
}

void
queue_move(struct queue *queue, unsigned from, unsigned to)
{
153
	struct queue_item item = queue->items[from];
154 155 156 157 158 159 160 161 162 163 164 165 166

	/* 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_ */

Max Kellermann's avatar
Max Kellermann committed
167
	queue->id_to_position[item.id] = to;
168 169
	queue->items[to] = item;
	queue->items[to].version = queue->version;
170 171 172 173 174 175 176 177 178 179 180 181 182 183

	/* 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;
		}
	}
184 185
}

186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
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++)
	{
Max Kellermann's avatar
Max Kellermann committed
207
		queue->id_to_position[items[i-start].id] = to + i - start;
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227
		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;
		}
	}
}

228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246
void
queue_delete(struct queue *queue, unsigned position)
{
	struct song *song;
	unsigned id, order;

	assert(position < queue->length);

	song = queue_get(queue, position);
	if (!song_in_database(song))
		song_free(song);

	id = queue_position_to_id(queue, position);
	order = queue_position_to_order(queue, position);

	--queue->length;

	/* release the song id */

Max Kellermann's avatar
Max Kellermann committed
247
	queue->id_to_position[id] = -1;
248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269

	/* 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++) {
270 271 272 273
		struct queue_item *item = &queue->items[i];

		if (!song_in_database(item->song))
			song_free(item->song);
274

Max Kellermann's avatar
Max Kellermann committed
275
		queue->id_to_position[item->id] = -1;
276 277 278 279 280 281 282 283 284 285 286 287 288
	}

	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;
289
	queue->single = false;
290
	queue->consume = false;
291

292
	queue->items = g_new(struct queue_item, max_length);
293 294
	queue->order = g_malloc(sizeof(queue->order[0]) *
				  max_length);
Max Kellermann's avatar
Max Kellermann committed
295
	queue->id_to_position = g_malloc(sizeof(queue->id_to_position[0]) *
296 297 298
				       max_length * QUEUE_HASH_MULT);

	for (unsigned i = 0; i < max_length * QUEUE_HASH_MULT; ++i)
Max Kellermann's avatar
Max Kellermann committed
299
		queue->id_to_position[i] = -1;
300 301 302 303 304 305 306 307 308

	queue->rand = g_rand_new();
}

void
queue_finish(struct queue *queue)
{
	queue_clear(queue);

309
	g_free(queue->items);
310
	g_free(queue->order);
Max Kellermann's avatar
Max Kellermann committed
311
	g_free(queue->id_to_position);
312 313 314 315

	g_rand_free(queue->rand);
}

316 317 318 319 320 321 322 323 324 325 326
void
queue_shuffle_order(struct queue *queue)
{
	assert(queue->random);

	for (unsigned i = 0; i < queue->length; i++)
		queue_swap_order(queue, i,
				 g_rand_int_range(queue->rand, i,
						  queue->length));
}

327 328 329 330 331 332 333
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));
}

334 335 336 337 338 339 340 341 342 343 344
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);
	}
}