diff options
Diffstat (limited to '')
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Makefile.am | 12 | ||||
| -rw-r--r-- | doc/protocol.xml | 81 | ||||
| -rw-r--r-- | src/command.c | 64 | ||||
| -rw-r--r-- | src/playlist.h | 9 | ||||
| -rw-r--r-- | src/playlist_edit.c | 55 | ||||
| -rw-r--r-- | src/queue.c | 274 | ||||
| -rw-r--r-- | src/queue.h | 33 | ||||
| -rw-r--r-- | src/queue_print.c | 4 | ||||
| -rw-r--r-- | test/test_queue_priority.c | 174 |
10 files changed, 701 insertions, 6 deletions
diff --git a/.gitignore b/.gitignore index 977ae6a12..3e9936882 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 0471bcc8a..c699397b5 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 affe852cb..aba080a6a 100644 --- a/doc/protocol.xml +++ b/doc/protocol.xml @@ -204,6 +204,47 @@ </chapter> <chapter> + <title>Recipes</title> + + <section> + <title>Queuing</title> + + <para> + Often, users run MPD with "<link + linkend="command_random">random</link>" enabled, but want to + be able to insert songs "before" the rest of the playlist. + That is commonly called "queuing". + </para> + + <para> + MPD implements this by allowing the client to specify a + "priority" for each song in the playlist (commands <link + linkend="command_prio"><command>prio</command></link> and + <link + linkend="command_prioid"><command>prioid</command></link>). A + higher priority means that the song is going to be played + before the other songs. + </para> + + <para> + 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. + </para> + </section> + </chapter> + + <chapter> <title>Command reference</title> <note> @@ -1092,6 +1133,46 @@ OK </para> </listitem> </varlistentry> + + <varlistentry id="command_prio"> + <term> + <cmdsynopsis> + <command>prio</command> + <arg choice="req"><replaceable>PRIORITY</replaceable></arg> + <arg choice="req" rep="repeat"><replaceable>START:END</replaceable></arg> + </cmdsynopsis> + </term> + <listitem> + <para> + Set the priority of the specified songs. A higher + priority means that it will be played first when + "random" mode is enabled. + </para> + + <para> + A priority is an integer between 0 and 255. The default + priority of new songs is 0. + </para> + </listitem> + </varlistentry> + + <varlistentry id="command_prioid"> + <term> + <cmdsynopsis> + <command>prioid</command> + <arg choice="req"><replaceable>PRIORITY</replaceable></arg> + <arg choice="req" rep="repeat"><replaceable>ID</replaceable></arg> + </cmdsynopsis> + </term> + <listitem> + <para> + Same as <link + linkend="command_prio"><command>prio</command></link>, + but address the songs with their id. + </para> + </listitem> + </varlistentry> + <varlistentry id="command_shuffle"> <term> <cmdsynopsis> diff --git a/src/command.c b/src/command.c index e369da69b..3e60e0ac3 100644 --- a/src/command.c +++ b/src/command.c @@ -1171,6 +1171,68 @@ handle_previous(G_GNUC_UNUSED struct client *client, } 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[]) { char *directory = NULL; @@ -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 4f8291dc0..569db7bc3 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 505247f50..92c3d44b0 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 9225590fc..cd932875e 100644 --- a/src/queue.c +++ b/src/queue.c @@ -21,6 +21,8 @@ #include "queue.h" #include "song.h" +#include <stdlib.h> + /** * 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 03323d1d1..5cb5c196b 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. */ @@ -320,6 +336,14 @@ queue_restore_order(struct queue *queue) } /** + * 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 a3082a35c..d149e8b6f 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 000000000..d61b8c8da --- /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); +} |