aboutsummaryrefslogtreecommitdiff
path: root/src/queue.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/queue.c')
-rw-r--r--src/queue.c603
1 files changed, 0 insertions, 603 deletions
diff --git a/src/queue.c b/src/queue.c
deleted file mode 100644
index 4fe564a3..00000000
--- a/src/queue.c
+++ /dev/null
@@ -1,603 +0,0 @@
-/*
- * Copyright (C) 2003-2011 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.h"
-#include "song.h"
-
-#include <stdlib.h>
-
-/**
- * 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));
-
- queue->items[queue->length] = (struct queue_item){
- .song = song,
- .id = id,
- .version = queue->version,
- .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);
- if (!song_in_database(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];
-
- if (!song_in_database(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 = g_malloc(sizeof(queue->order[0]) *
- max_length);
- queue->id_to_position = 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 = 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);
-
- 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;
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-18 06:54:52 +0000