diff options
| -rw-r--r-- | Makefile.am | 1 | ||||
| -rw-r--r-- | src/IdTable.hxx | 91 | ||||
| -rw-r--r-- | src/Queue.cxx | 48 | ||||
| -rw-r--r-- | src/Queue.hxx | 15 |
4 files changed, 108 insertions, 47 deletions
diff --git a/Makefile.am b/Makefile.am index cc4c8b9ac..5393f5273 100644 --- a/Makefile.am +++ b/Makefile.am @@ -275,6 +275,7 @@ src_mpd_SOURCES = \ src/PlaylistVector.cxx src/PlaylistVector.hxx \ src/PlaylistInfo.hxx \ src/PlaylistDatabase.cxx \ + src/IdTable.hxx \ src/Queue.cxx src/Queue.hxx \ src/QueuePrint.cxx src/QueuePrint.hxx \ src/QueueSave.cxx src/QueueSave.hxx \ diff --git a/src/IdTable.hxx b/src/IdTable.hxx new file mode 100644 index 000000000..8925fe8ab --- /dev/null +++ b/src/IdTable.hxx @@ -0,0 +1,91 @@ +/* + * 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. + */ + +#ifndef MPD_ID_TABLE_HXX +#define MPD_ID_TABLE_HXX + +#include "gcc.h" + +#include <algorithm> + +#include <assert.h> + +/** + * A table that maps id numbers to position numbers. + */ +class IdTable { + unsigned size; + + unsigned next; + + int *data; + +public: + IdTable(unsigned _size):size(_size), next(1), data(new int[size]) { + std::fill(data, data + size, -1); + } + + ~IdTable() { + delete[] data; + } + + int IdToPosition(unsigned id) const { + return id < size + ? data[id] + : -1; + } + + unsigned GenerateId() { + assert(next > 0); + assert(next < size); + + while (true) { + unsigned id = next; + + ++next; + if (next == size) + next = 1; + + if (data[id] < 0) + return id; + } + } + + unsigned Insert(unsigned position) { + unsigned id = GenerateId(); + data[id] = position; + return id; + } + + void Move(unsigned id, unsigned position) { + assert(id < size); + assert(data[id] >= 0); + + data[id] = position; + } + + void Erase(unsigned id) { + assert(id < size); + assert(data[id] >= 0); + + data[id] = -1; + } +}; + +#endif diff --git a/src/Queue.cxx b/src/Queue.cxx index c77647eae..34f891262 100644 --- a/src/Queue.cxx +++ b/src/Queue.cxx @@ -28,15 +28,12 @@ queue::queue(unsigned _max_length) version(1), items(g_new(Item, max_length)), order((unsigned *)g_malloc(sizeof(order[0]) * max_length)), - id_to_position((int *)g_malloc(sizeof(id_to_position[0]) * - max_length * HASH_MULT)), + id_table(max_length * HASH_MULT), repeat(false), single(false), consume(false), random(false) { - for (unsigned i = 0; i < max_length * HASH_MULT; ++i) - id_to_position[i] = -1; } queue::~queue() @@ -45,25 +42,6 @@ queue::~queue() g_free(items); g_free(order); - g_free(id_to_position); -} - -/** - * Generate a non-existing id number. - */ -unsigned -queue::GenerateId() const -{ - static unsigned cur = (unsigned)-1; - - do { - cur++; - - if (cur >= max_length * HASH_MULT) - cur = 0; - } while (id_to_position[cur] != -1); - - return cur; } int @@ -121,20 +99,18 @@ queue::ModifyAll() unsigned queue::Append(struct song *song, uint8_t priority) { - const unsigned id = GenerateId(); - assert(!IsFull()); - auto &item = items[length]; + const unsigned position = length++; + const unsigned id = id_table.Insert(position); + + auto &item = items[position]; item.song = song_dup_detached(song); item.id = id; item.version = version; item.priority = priority; - order[length] = length; - id_to_position[id] = length; - - ++length; + order[position] = position; return id; } @@ -150,8 +126,8 @@ queue::SwapPositions(unsigned position1, unsigned position2) items[position1].version = version; items[position2].version = version; - id_to_position[id1] = position2; - id_to_position[id2] = position1; + id_table.Move(id1, position2); + id_table.Move(id2, position1); } void @@ -171,7 +147,7 @@ queue::MovePostion(unsigned from, unsigned to) /* put song at _to_ */ - id_to_position[tmp.id] = to; + id_table.Move(tmp.id, to); items[to] = tmp; items[to].version = version; @@ -211,7 +187,7 @@ queue::MoveRange(unsigned start, unsigned end, unsigned to) // Copy the original block back in, starting at to. for (unsigned i = start; i< end; i++) { - id_to_position[tmp[i-start].id] = to + i - start; + id_table.Move(tmp[i - start].id, to + i - start); items[to + i - start] = tmp[i-start]; items[to + i - start].version = version; } @@ -267,7 +243,7 @@ queue::DeletePosition(unsigned position) /* release the song id */ - id_to_position[id] = -1; + id_table.Erase(id); /* delete song from songs array */ @@ -296,7 +272,7 @@ queue::Clear() song_is_detached(item->song)); song_free(item->song); - id_to_position[item->id] = -1; + id_table.Erase(item->id); } length = 0; diff --git a/src/Queue.hxx b/src/Queue.hxx index a453ddcf1..6e7786bcd 100644 --- a/src/Queue.hxx +++ b/src/Queue.hxx @@ -21,6 +21,7 @@ #define MPD_QUEUE_HXX #include "gcc.h" +#include "IdTable.hxx" #include "util/LazyRandomEngine.hxx" #include <algorithm> @@ -82,7 +83,7 @@ struct queue { unsigned *order; /** map song ids to positions */ - int *id_to_position; + IdTable id_table; /** repeat playback when the end of the queue has been reached? */ @@ -148,13 +149,7 @@ struct queue { } int IdToPosition(unsigned id) const { - if (id >= max_length * HASH_MULT) - return -1; - - assert(id_to_position[id] >= -1); - assert(id_to_position[id] < (int)length); - - return id_to_position[id]; + return id_table.IdToPosition(id); } int PositionToId(unsigned position) const @@ -344,8 +339,6 @@ struct queue { uint8_t priority, int after_order); private: - unsigned GenerateId() const; - /** * Moves a song to a new position in the "order" list. */ @@ -356,7 +349,7 @@ private: items[to] = items[from]; items[to].version = version; - id_to_position[from_id] = to; + id_table.Move(from_id, to); } /** |