aboutsummaryrefslogtreecommitdiffstats
path: root/src/Queue.hxx
blob: 0088e080f21430bf82dfca93bd94941b477f70f3 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
/*
 * 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.
 */

#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>

struct Song;

/**
 * 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 {
		Song *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;

	queue(unsigned max_length);

	/**
	 * Deinitializes a queue object.  It does not free the queue
	 * pointer itself.
	 */
	~queue();

	queue(const queue &other) = delete;
	queue &operator=(const queue &other) = 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.
	 */
	Song &Get(unsigned position) const {
		assert(position < length);

		return *items[position].song;
	}

	/**
	 * Returns the song at the specified order number.
	 */
	Song &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" and increments the version
	 * number.
	 */
	void ModifyAtOrder(unsigned order);

	/**
	 * Marks all songs as "modified" and increments the version number.
	 */
	void ModifyAll();

	/**
	 * 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(Song *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