From 05c91082e3de0b0078c26ddb9da68fd00da8c90e Mon Sep 17 00:00:00 2001 From: Max Kellermann Date: Fri, 4 Jan 2013 20:50:00 +0100 Subject: playlist: convert to C++ --- src/Queue.cxx | 604 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 604 insertions(+) create mode 100644 src/Queue.cxx (limited to 'src/Queue.cxx') diff --git a/src/Queue.cxx b/src/Queue.cxx new file mode 100644 index 00000000..485ffb1c --- /dev/null +++ b/src/Queue.cxx @@ -0,0 +1,604 @@ +/* + * 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. + */ + +#include "config.h" +#include "Queue.hxx" +#include "song.h" + +#include + +/** + * Generate a non-existing id number. + */ +static unsigned +queue_generate_id(const struct queue *queue) +{ + static unsigned cur = (unsigned)-1; + + do { + cur++; + + if (cur >= queue->max_length * QUEUE_HASH_MULT) + cur = 0; + } while (queue->id_to_position[cur] != -1); + + return cur; +} + +int +queue_next_order(const struct queue *queue, unsigned order) +{ + assert(order < queue->length); + + if (queue->single && queue->repeat && !queue->consume) + return order; + else if (order + 1 < queue->length) + return order + 1; + else if (queue->repeat && (order > 0 || !queue->consume)) + /* 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++) + queue->items[i].version = 0; + + queue->version = 1; + } +} + +void +queue_modify(struct queue *queue, unsigned order) +{ + unsigned position; + + assert(order < queue->length); + + position = queue->order[order]; + queue->items[position].version = queue->version; + + queue_increment_version(queue); +} + +void +queue_modify_all(struct queue *queue) +{ + for (unsigned i = 0; i < queue->length; i++) + queue->items[i].version = queue->version; + + queue_increment_version(queue); +} + +unsigned +queue_append(struct queue *queue, struct song *song, uint8_t priority) +{ + unsigned id = queue_generate_id(queue); + + assert(!queue_is_full(queue)); + + auto &item = queue->items[queue->length]; + item.song = song_dup_detached(song); + item.id = id; + item.version = queue->version; + item.priority = priority; + + queue->order[queue->length] = queue->length; + queue->id_to_position[id] = queue->length; + + ++queue->length; + + return id; +} + +void +queue_swap(struct queue *queue, unsigned position1, unsigned position2) +{ + struct queue_item tmp; + unsigned id1 = queue->items[position1].id; + unsigned id2 = queue->items[position2].id; + + tmp = queue->items[position1]; + queue->items[position1] = queue->items[position2]; + queue->items[position2] = tmp; + + queue->items[position1].version = queue->version; + queue->items[position2].version = queue->version; + + queue->id_to_position[id1] = position2; + queue->id_to_position[id2] = position1; +} + +static void +queue_move_song_to(struct queue *queue, unsigned from, unsigned to) +{ + unsigned from_id = queue->items[from].id; + + queue->items[to] = queue->items[from]; + queue->items[to].version = queue->version; + queue->id_to_position[from_id] = to; +} + +void +queue_move(struct queue *queue, unsigned from, unsigned to) +{ + struct queue_item item = queue->items[from]; + + /* 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_ */ + + queue->id_to_position[item.id] = to; + queue->items[to] = item; + queue->items[to].version = queue->version; + + /* 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; + } + } +} + +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++) + { + queue->id_to_position[items[i-start].id] = to + i - start; + 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; + } + } +} + +/** + * 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) +{ + struct song *song; + unsigned id, order; + + assert(position < queue->length); + + song = queue_get(queue, position); + assert(!song_in_database(song) || song_is_detached(song)); + song_free(song); + + id = queue_position_to_id(queue, position); + order = queue_position_to_order(queue, position); + + --queue->length; + + /* release the song id */ + + queue->id_to_position[id] = -1; + + /* 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++) { + struct queue_item *item = &queue->items[i]; + + assert(!song_in_database(item->song) || + song_is_detached(item->song)); + song_free(item->song); + + queue->id_to_position[item->id] = -1; + } + + 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; + queue->single = false; + queue->consume = false; + + queue->items = g_new(struct queue_item, max_length); + queue->order = (unsigned *) + g_malloc(sizeof(queue->order[0]) * max_length); + queue->id_to_position = (int *) + g_malloc(sizeof(queue->id_to_position[0]) * + max_length * QUEUE_HASH_MULT); + + for (unsigned i = 0; i < max_length * QUEUE_HASH_MULT; ++i) + queue->id_to_position[i] = -1; + + queue->rand = g_rand_new(); +} + +void +queue_finish(struct queue *queue) +{ + queue_clear(queue); + + g_free(queue->items); + g_free(queue->order); + g_free(queue->id_to_position); + + g_rand_free(queue->rand); +} + +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 = (const struct queue *)user_data; + const unsigned *const ap = (const unsigned *)av; + const unsigned *const bp = (const unsigned *)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); + + 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, 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 +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)); +} + +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); + } +} + +/** + * 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; +} -- cgit v1.2.3