1 /* 2 * Copyright 2003-2021 The Music Player Daemon Project 3 * http://www.musicpd.org 4 * 5 * This program is free software; you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License as published by 7 * the Free Software Foundation; either version 2 of the License, or 8 * (at your option) any later version. 9 * 10 * This program is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 * GNU General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License along 16 * with this program; if not, write to the Free Software Foundation, Inc., 17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 18 */ 19 20 #ifndef MPD_QUEUE_HXX 21 #define MPD_QUEUE_HXX 22 23 #include "util/Compiler.h" 24 #include "IdTable.hxx" 25 #include "SingleMode.hxx" 26 #include "util/LazyRandomEngine.hxx" 27 28 #include <cassert> 29 #include <cstdint> 30 #include <utility> 31 32 class DetachedSong; 33 34 /** 35 * A queue of songs. This is the backend of the playlist: it contains 36 * an ordered list of songs. 37 * 38 * Songs can be addressed in three possible ways: 39 * 40 * - the position in the queue 41 * - the unique id (which stays the same, regardless of moves) 42 * - the order number (which only differs from "position" in random mode) 43 */ 44 struct Queue { 45 /** 46 * reserve max_length * HASH_MULT elements in the id 47 * number space 48 */ 49 static constexpr unsigned HASH_MULT = 4; 50 51 /** 52 * One element of the queue: basically a song plus some queue specific 53 * information attached. 54 */ 55 struct Item { 56 DetachedSong *song; 57 58 /** the unique id of this item in the queue */ 59 unsigned id; 60 61 /** when was this item last changed? */ 62 uint32_t version; 63 64 /** 65 * The priority of this item, between 0 and 255. High 66 * priority value means that this song gets played first in 67 * "random" mode. 68 */ 69 uint8_t priority; 70 }; 71 72 /** configured maximum length of the queue */ 73 const unsigned max_length; 74 75 /** number of songs in the queue */ 76 unsigned length = 0; 77 78 /** the current version number */ 79 uint32_t version = 1; 80 81 /** all songs in "position" order */ 82 Item *const items; 83 84 /** map order numbers to positions */ 85 unsigned *const order; 86 87 /** map song ids to positions */ 88 IdTable id_table; 89 90 /** repeat playback when the end of the queue has been 91 reached? */ 92 bool repeat = false; 93 94 /** play only current song. */ 95 SingleMode single = SingleMode::OFF; 96 97 /** remove each played files. */ 98 bool consume = false; 99 100 /** play back songs in random order? */ 101 bool random = false; 102 103 /** random number generator for shuffle and random mode */ 104 LazyRandomEngine rand; 105 106 explicit Queue(unsigned max_length) noexcept; 107 ~Queue() noexcept; 108 109 Queue(const Queue &) = delete; 110 Queue &operator=(const Queue &) = delete; 111 GetLengthQueue112 unsigned GetLength() const noexcept { 113 assert(length <= max_length); 114 115 return length; 116 } 117 118 /** 119 * Determine if the queue is empty, i.e. there are no songs. 120 */ IsEmptyQueue121 bool IsEmpty() const noexcept { 122 return length == 0; 123 } 124 125 /** 126 * Determine if the maximum number of songs has been reached. 127 */ IsFullQueue128 bool IsFull() const noexcept { 129 assert(length <= max_length); 130 131 return length >= max_length; 132 } 133 134 /** 135 * Is that a valid position number? 136 */ IsValidPositionQueue137 bool IsValidPosition(unsigned position) const noexcept { 138 return position < length; 139 } 140 141 /** 142 * Is that a valid order number? 143 */ IsValidOrderQueue144 bool IsValidOrder(unsigned _order) const noexcept { 145 return _order < length; 146 } 147 IdToPositionQueue148 int IdToPosition(unsigned id) const noexcept { 149 return id_table.IdToPosition(id); 150 } 151 PositionToIdQueue152 int PositionToId(unsigned position) const noexcept { 153 assert(position < length); 154 155 return items[position].id; 156 } 157 158 gcc_pure OrderToPositionQueue159 unsigned OrderToPosition(unsigned _order) const noexcept { 160 assert(_order < length); 161 162 return order[_order]; 163 } 164 165 gcc_pure PositionToOrderQueue166 unsigned PositionToOrder(unsigned position) const noexcept { 167 assert(position < length); 168 169 for (unsigned i = 0;; ++i) { 170 assert(i < length); 171 172 if (order[i] == position) 173 return i; 174 } 175 } 176 177 gcc_pure GetPriorityAtPositionQueue178 uint8_t GetPriorityAtPosition(unsigned position) const noexcept { 179 assert(position < length); 180 181 return items[position].priority; 182 } 183 GetOrderItemQueue184 const Item &GetOrderItem(unsigned i) const noexcept { 185 assert(IsValidOrder(i)); 186 187 return items[OrderToPosition(i)]; 188 } 189 GetOrderPriorityQueue190 uint8_t GetOrderPriority(unsigned i) const noexcept { 191 return GetOrderItem(i).priority; 192 } 193 194 /** 195 * Returns the song at the specified position. 196 */ GetQueue197 DetachedSong &Get(unsigned position) const noexcept { 198 assert(position < length); 199 200 return *items[position].song; 201 } 202 203 /** 204 * Returns the song at the specified order number. 205 */ GetOrderQueue206 DetachedSong &GetOrder(unsigned _order) const noexcept { 207 return Get(OrderToPosition(_order)); 208 } 209 210 /** 211 * Is the song at the specified position newer than the specified 212 * version? 213 */ IsNewerAtPositionQueue214 bool IsNewerAtPosition(unsigned position, 215 uint32_t _version) const noexcept { 216 assert(position < length); 217 218 return _version > version || 219 items[position].version >= _version || 220 items[position].version == 0; 221 } 222 223 /** 224 * Returns the order number following the specified one. This takes 225 * end of queue and "repeat" mode into account. 226 * 227 * @return the next order number, or -1 to stop playback 228 */ 229 gcc_pure 230 int GetNextOrder(unsigned order) const noexcept; 231 232 /** 233 * Increments the queue's version number. This handles integer 234 * overflow well. 235 */ 236 void IncrementVersion() noexcept; 237 238 /** 239 * Marks the specified song as "modified". Call 240 * IncrementVersion() after all modifications have been made. 241 * number. 242 */ ModifyAtPositionQueue243 void ModifyAtPosition(unsigned position) noexcept { 244 assert(position < length); 245 246 items[position].version = version; 247 } 248 249 /** 250 * Marks the specified song as "modified". Call 251 * IncrementVersion() after all modifications have been made. 252 * number. 253 */ 254 void ModifyAtOrder(unsigned order) noexcept; 255 256 /** 257 * Appends a song to the queue and returns its position. Prior to 258 * that, the caller must check if the queue is already full. 259 * 260 * If a song is not in the database (determined by 261 * Song::IsInDatabase()), it is freed when removed from the 262 * queue. 263 * 264 * @param priority the priority of this new queue item 265 */ 266 unsigned Append(DetachedSong &&song, uint8_t priority) noexcept; 267 268 /** 269 * Swaps two songs, addressed by their position. 270 */ 271 void SwapPositions(unsigned position1, unsigned position2) noexcept; 272 273 /** 274 * Swaps two songs, addressed by their order number. 275 */ SwapOrdersQueue276 void SwapOrders(unsigned order1, unsigned order2) noexcept { 277 std::swap(order[order1], order[order2]); 278 } 279 280 /** 281 * Moves a song to a new position in the "order" list. 282 * 283 * @return to_order 284 */ 285 unsigned MoveOrder(unsigned from_order, unsigned to_order) noexcept; 286 287 /** 288 * Moves a song to a new position in the "order" list before 289 * the given one. 290 * 291 * @return the new order number of the given "from" song 292 */ 293 unsigned MoveOrderBefore(unsigned from_order, 294 unsigned to_order) noexcept; 295 296 /** 297 * Moves a song to a new position in the "order" list after 298 * the given one. 299 * 300 * @return the new order number of the given "from" song 301 */ 302 unsigned MoveOrderAfter(unsigned from_order, 303 unsigned to_order) noexcept; 304 305 /** 306 * Moves a song to a new position. 307 */ 308 void MovePostion(unsigned from, unsigned to) noexcept; 309 310 /** 311 * Moves a range of songs to a new position. 312 */ 313 void MoveRange(unsigned start, unsigned end, unsigned to) noexcept; 314 315 /** 316 * Removes a song from the playlist. 317 */ 318 void DeletePosition(unsigned position) noexcept; 319 320 /** 321 * Removes all songs from the playlist. 322 */ 323 void Clear() noexcept; 324 325 /** 326 * Initializes the "order" array, and restores "normal" order. 327 */ RestoreOrderQueue328 void RestoreOrder() noexcept { 329 for (unsigned i = 0; i < length; ++i) 330 order[i] = i; 331 } 332 333 /** 334 * Shuffle the order of items in the specified range, ignoring 335 * their priorities. 336 */ 337 void ShuffleOrderRange(unsigned start, unsigned end) noexcept; 338 339 /** 340 * Shuffle the order of items in the specified range, taking their 341 * priorities into account. 342 */ 343 void ShuffleOrderRangeWithPriority(unsigned start, 344 unsigned end) noexcept; 345 346 /** 347 * Shuffles the virtual order of songs, but does not move them 348 * physically. This is used in random mode. 349 */ 350 void ShuffleOrder() noexcept; 351 352 void ShuffleOrderFirst(unsigned start, unsigned end) noexcept; 353 354 /** 355 * Shuffles the virtual order of the last song in the 356 * specified (order) range; only songs which match this song's 357 * priority are considered. This is used in random mode after 358 * a song has been appended by Append(). 359 */ 360 void ShuffleOrderLastWithPriority(unsigned start, unsigned end) noexcept; 361 362 /** 363 * Shuffles a (position) range in the queue. The songs are physically 364 * shuffled, not by using the "order" mapping. 365 */ 366 void ShuffleRange(unsigned start, unsigned end) noexcept; 367 368 bool SetPriority(unsigned position, uint8_t priority, int after_order, 369 bool reorder=true) noexcept; 370 371 bool SetPriorityRange(unsigned start_position, unsigned end_position, 372 uint8_t priority, int after_order) noexcept; 373 374 private: MoveItemToQueue375 void MoveItemTo(unsigned from, unsigned to) noexcept { 376 unsigned from_id = items[from].id; 377 378 items[to] = items[from]; 379 items[to].version = version; 380 id_table.Move(from_id, to); 381 } 382 383 /** 384 * Find the first item that has this specified priority or 385 * higher. 386 */ 387 gcc_pure 388 unsigned FindPriorityOrder(unsigned start_order, uint8_t priority, 389 unsigned exclude_order) const noexcept; 390 391 gcc_pure 392 unsigned CountSamePriority(unsigned start_order, 393 uint8_t priority) const noexcept; 394 }; 395 396 #endif 397