From b159bc0c5f64dd4030f18cfa38539c5851d5157d Mon Sep 17 00:00:00 2001 From: Max Kellermann Date: Tue, 19 Jul 2011 00:34:33 +0200 Subject: queue: implement song "priorities" Sorts remaining songs by priority. This can be used for the much-demanded "queue feature". --- .gitignore | 1 + Makefile.am | 12 +- doc/protocol.xml | 81 ++++++++++++++ src/command.c | 64 +++++++++++ src/playlist.h | 9 ++ src/playlist_edit.c | 55 +++++++++ src/queue.c | 274 ++++++++++++++++++++++++++++++++++++++++++++- src/queue.h | 33 ++++++ src/queue_print.c | 4 + test/test_queue_priority.c | 174 ++++++++++++++++++++++++++++ 10 files changed, 701 insertions(+), 6 deletions(-) create mode 100644 test/test_queue_priority.c diff --git a/.gitignore b/.gitignore index 977ae6a1..3e993688 100644 --- a/.gitignore +++ b/.gitignore @@ -59,3 +59,4 @@ test/dump_playlist test/run_normalize test/tmp test/run_inotify +test/test_queue_priority diff --git a/Makefile.am b/Makefile.am index 0471bcc8..c699397b 100644 --- a/Makefile.am +++ b/Makefile.am @@ -869,9 +869,13 @@ sparse-check: if ENABLE_TEST -TESTS = +C_TESTS = \ + test/test_queue_priority + +TESTS = $(C_TESTS) noinst_PROGRAMS = \ + $(C_TESTS) \ test/read_conf \ test/run_input \ test/dump_playlist \ @@ -1153,6 +1157,12 @@ test_run_inotify_SOURCES = test/run_inotify.c \ test_run_inotify_LDADD = $(GLIB_LIBS) endif +test_test_queue_priority_SOURCES = \ + src/queue.c \ + test/test_queue_priority.c +test_test_queue_priority_LDADD = \ + $(GLIB_LIBS) + endif diff --git a/doc/protocol.xml b/doc/protocol.xml index affe852c..aba080a6 100644 --- a/doc/protocol.xml +++ b/doc/protocol.xml @@ -203,6 +203,47 @@ + + Recipes + +
+ Queuing + + + Often, users run MPD with "random" enabled, but want to + be able to insert songs "before" the rest of the playlist. + That is commonly called "queuing". + + + + MPD implements this by allowing the client to specify a + "priority" for each song in the playlist (commands prio and + prioid). A + higher priority means that the song is going to be played + before the other songs. + + + + In "random" mode, MPD maintains an internal randomized + sequence of songs. In this sequence, songs with a higher + priority come first, and all songs with the same priority are + shuffled (by default, all songs are shuffled, because all have + the same priority "0"). When you increase the priority of a + song, it is moved to the front of the sequence according to + its new priority, but always after the current one. A song + that has been played already (it's "before" the current song + in that sequence) will only be scheduled for repeated playback + if its priority has become bigger than the priority of the + current song. Decreasing the priority of a song will moved it + farther to the end of the sequence. Changing the priority of + the current song has no effect on the sequence. + +
+ + Command reference @@ -1092,6 +1133,46 @@ OK + + + + + prio + PRIORITY + START:END + + + + + Set the priority of the specified songs. A higher + priority means that it will be played first when + "random" mode is enabled. + + + + A priority is an integer between 0 and 255. The default + priority of new songs is 0. + + + + + + + + prioid + PRIORITY + ID + + + + + Same as prio, + but address the songs with their id. + + + + diff --git a/src/command.c b/src/command.c index e369da69..3e60e0ac 100644 --- a/src/command.c +++ b/src/command.c @@ -1170,6 +1170,68 @@ handle_previous(G_GNUC_UNUSED struct client *client, return COMMAND_RETURN_OK; } +static enum command_return +handle_prio(struct client *client, int argc, char *argv[]) +{ + unsigned priority; + + if (!check_unsigned(client, &priority, argv[1])) + return COMMAND_RETURN_ERROR; + + if (priority > 0xff) { + command_error(client, ACK_ERROR_ARG, + "Priority out of range: %s", argv[1]); + return COMMAND_RETURN_ERROR; + } + + for (int i = 2; i < argc; ++i) { + unsigned start_position, end_position; + if (!check_range(client, &start_position, &end_position, + argv[i], need_range)) + return COMMAND_RETURN_ERROR; + + enum playlist_result result = + playlist_set_priority(&g_playlist, + client->player_control, + start_position, end_position, + priority); + if (result != PLAYLIST_RESULT_SUCCESS) + return print_playlist_result(client, result); + } + + return COMMAND_RETURN_OK; +} + +static enum command_return +handle_prioid(struct client *client, int argc, char *argv[]) +{ + unsigned priority; + + if (!check_unsigned(client, &priority, argv[1])) + return COMMAND_RETURN_ERROR; + + if (priority > 0xff) { + command_error(client, ACK_ERROR_ARG, + "Priority out of range: %s", argv[1]); + return COMMAND_RETURN_ERROR; + } + + for (int i = 2; i < argc; ++i) { + unsigned song_id; + if (!check_unsigned(client, &song_id, argv[i])) + return COMMAND_RETURN_ERROR; + + enum playlist_result result = + playlist_set_priority_id(&g_playlist, + client->player_control, + song_id, priority); + if (result != PLAYLIST_RESULT_SUCCESS) + return print_playlist_result(client, result); + } + + return COMMAND_RETURN_OK; +} + static enum command_return handle_listall(struct client *client, G_GNUC_UNUSED int argc, char *argv[]) { @@ -2062,6 +2124,8 @@ static const struct command commands[] = { { "plchanges", PERMISSION_READ, 1, 1, handle_plchanges }, { "plchangesposid", PERMISSION_READ, 1, 1, handle_plchangesposid }, { "previous", PERMISSION_CONTROL, 0, 0, handle_previous }, + { "prio", PERMISSION_CONTROL, 2, -1, handle_prio }, + { "prioid", PERMISSION_CONTROL, 2, -1, handle_prioid }, { "random", PERMISSION_CONTROL, 1, 1, handle_random }, { "readmessages", PERMISSION_READ, 0, 0, handle_read_messages }, { "rename", PERMISSION_CONTROL, 2, 2, handle_rename }, diff --git a/src/playlist.h b/src/playlist.h index 4f8291dc..569db7bc 100644 --- a/src/playlist.h +++ b/src/playlist.h @@ -195,6 +195,15 @@ enum playlist_result playlist_swap_songs_id(struct playlist *playlist, struct player_control *pc, unsigned id1, unsigned id2); +enum playlist_result +playlist_set_priority(struct playlist *playlist, struct player_control *pc, + unsigned start_position, unsigned end_position, + uint8_t priority); + +enum playlist_result +playlist_set_priority_id(struct playlist *playlist, struct player_control *pc, + unsigned song_id, uint8_t priority); + bool playlist_get_repeat(const struct playlist *playlist); diff --git a/src/playlist_edit.c b/src/playlist_edit.c index 505247f5..92c3d44b 100644 --- a/src/playlist_edit.c +++ b/src/playlist_edit.c @@ -212,6 +212,61 @@ playlist_swap_songs_id(struct playlist *playlist, struct player_control *pc, return playlist_swap_songs(playlist, pc, song1, song2); } +enum playlist_result +playlist_set_priority(struct playlist *playlist, struct player_control *pc, + unsigned start, unsigned end, + uint8_t priority) +{ + if (start >= queue_length(&playlist->queue)) + return PLAYLIST_RESULT_BAD_RANGE; + + if (end > queue_length(&playlist->queue)) + end = queue_length(&playlist->queue); + + if (start >= end) + return PLAYLIST_RESULT_SUCCESS; + + /* remember "current" and "queued" */ + + int current_position = playlist->current >= 0 + ? (int)queue_order_to_position(&playlist->queue, + playlist->current) + : -1; + + const struct song *queued = playlist_get_queued_song(playlist); + + /* apply the priority changes */ + + queue_set_priority_range(&playlist->queue, start, end, priority, + playlist->current); + + playlist_increment_version(playlist); + + /* restore "current" and choose a new "queued" */ + + if (current_position >= 0) + playlist->current = queue_position_to_order(&playlist->queue, + current_position); + + playlist_update_queued_song(playlist, pc, queued); + + return PLAYLIST_RESULT_SUCCESS; +} + +enum playlist_result +playlist_set_priority_id(struct playlist *playlist, struct player_control *pc, + unsigned song_id, uint8_t priority) +{ + int song_position = queue_id_to_position(&playlist->queue, song_id); + if (song_position < 0) + return PLAYLIST_RESULT_NO_SUCH_SONG; + + return playlist_set_priority(playlist, pc, + song_position, song_position + 1, + priority); + +} + static void playlist_delete_internal(struct playlist *playlist, struct player_control *pc, unsigned song, const struct song **queued_p) diff --git a/src/queue.c b/src/queue.c index 9225590f..cd932875 100644 --- a/src/queue.c +++ b/src/queue.c @@ -21,6 +21,8 @@ #include "queue.h" #include "song.h" +#include + /** * Generate a non-existing id number. */ @@ -104,6 +106,7 @@ queue_append(struct queue *queue, struct song *song) .song = song, .id = id, .version = queue->version, + .priority = 0, }; queue->order[queue->length] = queue->length; @@ -220,6 +223,30 @@ queue_move_range(struct queue *queue, unsigned start, unsigned end, unsigned to) } } +/** + * 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) { @@ -308,15 +335,123 @@ queue_finish(struct queue *queue) g_rand_free(queue->rand); } -void -queue_shuffle_order(struct queue *queue) +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 = user_data; + const unsigned *const ap = av; + const unsigned *const bp = 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); - for (unsigned i = 0; i < queue->length; i++) + 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, - queue->length)); + 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 @@ -337,3 +472,132 @@ queue_shuffle_range(struct queue *queue, unsigned start, unsigned 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; +} diff --git a/src/queue.h b/src/queue.h index 03323d1d..5cb5c196 100644 --- a/src/queue.h +++ b/src/queue.h @@ -46,6 +46,13 @@ struct queue_item { /** 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; }; /** @@ -181,6 +188,15 @@ queue_position_to_order(const struct queue *queue, unsigned position) } } +G_GNUC_PURE +static inline uint8_t +queue_get_priority_at_position(const struct queue *queue, unsigned position) +{ + assert(position < queue->length); + + return queue->items[position].priority; +} + /** * Returns the song at the specified position. */ @@ -319,6 +335,14 @@ queue_restore_order(struct queue *queue) queue->order[i] = i; } +/** + * Shuffle the order of items in the specified range, taking their + * priorities into account. + */ +void +queue_shuffle_order_range_with_priority(struct queue *queue, + unsigned start, unsigned end); + /** * Shuffles the virtual order of songs, but does not move them * physically. This is used in random mode. @@ -341,4 +365,13 @@ queue_shuffle_order_last(struct queue *queue, unsigned start, unsigned end); void queue_shuffle_range(struct queue *queue, unsigned start, unsigned end); +bool +queue_set_priority(struct queue *queue, unsigned position, + uint8_t priority, int after_order); + +bool +queue_set_priority_range(struct queue *queue, + unsigned start_position, unsigned end_position, + uint8_t priority, int after_order); + #endif diff --git a/src/queue_print.c b/src/queue_print.c index a3082a35..d149e8b6 100644 --- a/src/queue_print.c +++ b/src/queue_print.c @@ -41,6 +41,10 @@ queue_print_song_info(struct client *client, const struct queue *queue, song_print_info(client, queue_get(queue, position)); client_printf(client, "Pos: %u\nId: %u\n", position, queue_position_to_id(queue, position)); + + uint8_t priority = queue_get_priority_at_position(queue, position); + if (priority != 0) + client_printf(client, "Prio: %u\n", priority); } void diff --git a/test/test_queue_priority.c b/test/test_queue_priority.c new file mode 100644 index 00000000..d61b8c8d --- /dev/null +++ b/test/test_queue_priority.c @@ -0,0 +1,174 @@ +#include "queue.h" +#include "song.h" + +void +song_free(G_GNUC_UNUSED struct song *song) +{ +} + +G_GNUC_UNUSED +static void +dump_order(const struct queue *queue) +{ + g_printerr("queue length=%u, order:\n", queue_length(queue)); + for (unsigned i = 0; i < queue_length(queue); ++i) + g_printerr(" [%u] -> %u (prio=%u)\n", i, queue->order[i], + queue->items[queue->order[i]].priority); +} + +static void +check_descending_priority(G_GNUC_UNUSED const struct queue *queue, + unsigned start_order) +{ + assert(start_order < queue_length(queue)); + + uint8_t last_priority = 0xff; + for (unsigned order = start_order; order < queue_length(queue); ++order) { + unsigned position = queue_order_to_position(queue, order); + uint8_t priority = queue->items[position].priority; + assert(priority <= last_priority); + last_priority = priority; + } +} + +int +main(G_GNUC_UNUSED int argc, G_GNUC_UNUSED char **argv) +{ + struct song songs[16]; + + struct queue queue; + queue_init(&queue, 32); + + for (unsigned i = 0; i < G_N_ELEMENTS(songs); ++i) + queue_append(&queue, &songs[i]); + + assert(queue_length(&queue) == G_N_ELEMENTS(songs)); + + /* priority=10 for 4 items */ + + queue_set_priority_range(&queue, 4, 8, 10, -1); + + queue.random = true; + queue_shuffle_order(&queue); + check_descending_priority(&queue, 0); + + for (unsigned i = 0; i < 4; ++i) { + assert(queue_position_to_order(&queue, i) >= 4); + } + + for (unsigned i = 4; i < 8; ++i) { + assert(queue_position_to_order(&queue, i) < 4); + } + + for (unsigned i = 8; i < G_N_ELEMENTS(songs); ++i) { + assert(queue_position_to_order(&queue, i) >= 4); + } + + /* priority=50 one more item */ + + queue_set_priority_range(&queue, 15, 16, 50, -1); + check_descending_priority(&queue, 0); + + assert(queue_position_to_order(&queue, 15) == 0); + + for (unsigned i = 0; i < 4; ++i) { + assert(queue_position_to_order(&queue, i) >= 4); + } + + for (unsigned i = 4; i < 8; ++i) { + assert(queue_position_to_order(&queue, i) >= 1 && + queue_position_to_order(&queue, i) < 5); + } + + for (unsigned i = 8; i < 15; ++i) { + assert(queue_position_to_order(&queue, i) >= 5); + } + + /* priority=20 for one of the 4 priority=10 items */ + + queue_set_priority_range(&queue, 3, 4, 20, -1); + check_descending_priority(&queue, 0); + + assert(queue_position_to_order(&queue, 3) == 1); + assert(queue_position_to_order(&queue, 15) == 0); + + for (unsigned i = 0; i < 3; ++i) { + assert(queue_position_to_order(&queue, i) >= 5); + } + + for (unsigned i = 4; i < 8; ++i) { + assert(queue_position_to_order(&queue, i) >= 2 && + queue_position_to_order(&queue, i) < 6); + } + + for (unsigned i = 8; i < 15; ++i) { + assert(queue_position_to_order(&queue, i) >= 6); + } + + /* priority=20 for another one of the 4 priority=10 items; + pass "after_order" (with priority=10) and see if it's moved + after that one */ + + unsigned current_order = 4; + unsigned current_position = + queue_order_to_position(&queue, current_order); + + unsigned a_order = 3; + unsigned a_position = queue_order_to_position(&queue, a_order); + assert(queue.items[a_position].priority == 10); + queue_set_priority(&queue, a_position, 20, current_order); + + current_order = queue_position_to_order(&queue, current_position); + assert(current_order == 3); + + a_order = queue_position_to_order(&queue, a_position); + assert(a_order == 4); + + check_descending_priority(&queue, current_order + 1); + + /* priority=70 for one of the last items; must be inserted + right after the current song, before the priority=20 one we + just created */ + + unsigned b_order = 10; + unsigned b_position = queue_order_to_position(&queue, b_order); + assert(queue.items[b_position].priority == 0); + queue_set_priority(&queue, b_position, 70, current_order); + + current_order = queue_position_to_order(&queue, current_position); + assert(current_order == 3); + + b_order = queue_position_to_order(&queue, b_position); + assert(b_order == 4); + + check_descending_priority(&queue, current_order + 1); + + /* priority=60 for the old prio50 item; must not be moved, + because it's before the current song, and it's status + hasn't changed (it was already higher before) */ + + unsigned c_order = 0; + unsigned c_position = queue_order_to_position(&queue, c_order); + assert(queue.items[c_position].priority == 50); + queue_set_priority(&queue, c_position, 60, current_order); + + current_order = queue_position_to_order(&queue, current_position); + assert(current_order == 3); + + c_order = queue_position_to_order(&queue, c_position); + assert(c_order == 0); + + /* move the prio=20 item back */ + + a_order = queue_position_to_order(&queue, a_position); + assert(a_order == 5); + assert(queue.items[a_position].priority == 20); + queue_set_priority(&queue, a_position, 5, current_order); + + + current_order = queue_position_to_order(&queue, current_position); + assert(current_order == 3); + + a_order = queue_position_to_order(&queue, a_position); + assert(a_order == 6); +} -- cgit v1.2.3