summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/audio/CMakeLists.txt2
-rw-r--r--src/audio/include/track_queue.hpp27
-rw-r--r--src/audio/track_queue.cpp168
-rw-r--r--src/database/CMakeLists.txt2
-rw-r--r--src/database/include/tag_parser.hpp14
-rw-r--r--src/database/include/track.hpp3
-rw-r--r--src/database/tag_parser.cpp7
-rw-r--r--src/playlist/CMakeLists.txt10
-rw-r--r--src/playlist/include/shuffler.hpp68
-rw-r--r--src/playlist/include/source.hpp105
-rw-r--r--src/playlist/shuffler.cpp166
-rw-r--r--src/playlist/source.cpp145
-rw-r--r--src/ui/include/screen_track_browser.hpp8
-rw-r--r--src/ui/include/ui_events.hpp5
-rw-r--r--src/ui/screen_track_browser.cpp65
-rw-r--r--src/ui/ui_fsm.cpp16
-rw-r--r--src/util/CMakeLists.txt7
-rw-r--r--src/util/include/bloom_filter.hpp40
-rw-r--r--src/util/include/lru_cache.hpp69
-rw-r--r--src/util/include/random.hpp39
-rw-r--r--src/util/random.cpp37
21 files changed, 886 insertions, 117 deletions
diff --git a/src/audio/CMakeLists.txt b/src/audio/CMakeLists.txt
index 38e367aa..2501f773 100644
--- a/src/audio/CMakeLists.txt
+++ b/src/audio/CMakeLists.txt
@@ -7,6 +7,6 @@ idf_component_register(
"stream_message.cpp" "i2s_audio_output.cpp" "stream_buffer.cpp" "track_queue.cpp"
"stream_event.cpp" "pipeline.cpp" "stream_info.cpp" "audio_fsm.cpp"
INCLUDE_DIRS "include"
- REQUIRES "codecs" "drivers" "cbor" "result" "tasks" "span" "memory" "tinyfsm" "database" "system_fsm")
+ REQUIRES "codecs" "drivers" "cbor" "result" "tasks" "span" "memory" "tinyfsm" "database" "system_fsm" "playlist")
target_compile_options(${COMPONENT_LIB} PRIVATE ${EXTRA_WARNINGS})
diff --git a/src/audio/include/track_queue.hpp b/src/audio/include/track_queue.hpp
index 840d71ee..49c0d61b 100644
--- a/src/audio/include/track_queue.hpp
+++ b/src/audio/include/track_queue.hpp
@@ -6,10 +6,12 @@
#pragma once
-#include <deque>
+#include <list>
+#include <memory>
#include <mutex>
#include <vector>
+#include "source.hpp"
#include "track.hpp"
namespace audio {
@@ -44,7 +46,9 @@ class TrackQueue {
* If there is no current track, the given track will begin playback.
*/
auto AddNext(database::TrackId) -> void;
- auto AddNext(const std::vector<database::TrackId>&) -> void;
+ auto AddNext(std::shared_ptr<playlist::ISource>) -> void;
+
+ auto IncludeNext(std::shared_ptr<playlist::IResetableSource>) -> void;
/*
* Enqueues a track, placing it the end of all enqueued tracks.
@@ -52,7 +56,9 @@ class TrackQueue {
* If there is no current track, the given track will begin playback.
*/
auto AddLast(database::TrackId) -> void;
- auto AddLast(const std::vector<database::TrackId>&) -> void;
+ auto AddLast(std::shared_ptr<playlist::ISource>) -> void;
+
+ auto IncludeLast(std::shared_ptr<playlist::IResetableSource>) -> void;
/*
* Advances to the next track in the queue, placing the current track at the
@@ -65,11 +71,6 @@ class TrackQueue {
* Removes all tracks from all queues, and stops any currently playing track.
*/
auto Clear() -> void;
- /*
- * Removes a specific track from the queue of upcoming tracks. Has no effect
- * on the currently playing track.
- */
- auto RemoveUpcoming(database::TrackId) -> void;
TrackQueue(const TrackQueue&) = delete;
TrackQueue& operator=(const TrackQueue&) = delete;
@@ -77,9 +78,13 @@ class TrackQueue {
private:
mutable std::mutex mutex_;
- std::deque<database::TrackId> played_;
- std::deque<database::TrackId> upcoming_;
- std::optional<database::TrackId> current_;
+ std::list<std::variant<database::TrackId,
+ std::shared_ptr<playlist::IResetableSource>>>
+ played_;
+ std::list<std::variant<database::TrackId,
+ std::shared_ptr<playlist::ISource>,
+ std::shared_ptr<playlist::IResetableSource>>>
+ enqueued_;
};
} // namespace audio
diff --git a/src/audio/track_queue.cpp b/src/audio/track_queue.cpp
index 1c233f8f..0709056f 100644
--- a/src/audio/track_queue.cpp
+++ b/src/audio/track_queue.cpp
@@ -8,10 +8,12 @@
#include <algorithm>
#include <mutex>
+#include <variant>
#include "audio_events.hpp"
#include "audio_fsm.hpp"
#include "event_queue.hpp"
+#include "source.hpp"
#include "track.hpp"
#include "ui_fsm.hpp"
@@ -21,107 +23,163 @@ TrackQueue::TrackQueue() {}
auto TrackQueue::GetCurrent() const -> std::optional<database::TrackId> {
const std::lock_guard<std::mutex> lock(mutex_);
- return current_;
+ if (enqueued_.empty()) {
+ return {};
+ }
+ auto item = enqueued_.front();
+ if (std::holds_alternative<database::TrackId>(item)) {
+ return std::get<database::TrackId>(item);
+ }
+ if (std::holds_alternative<std::shared_ptr<playlist::ISource>>(item)) {
+ return std::get<std::shared_ptr<playlist::ISource>>(item)->Current();
+ }
+ if (std::holds_alternative<std::shared_ptr<playlist::IResetableSource>>(
+ item)) {
+ return std::get<std::shared_ptr<playlist::IResetableSource>>(item)
+ ->Current();
+ }
+ return {};
}
auto TrackQueue::GetUpcoming(std::size_t limit) const
-> std::vector<database::TrackId> {
const std::lock_guard<std::mutex> lock(mutex_);
std::vector<database::TrackId> ret;
- limit = std::min(limit, upcoming_.size());
- std::for_each_n(upcoming_.begin(), limit,
- [&](const auto i) { ret.push_back(i); });
+
+ auto it = enqueued_.begin();
+ if (it == enqueued_.end()) {
+ return ret;
+ }
+
+ // Don't include the current track. This is only relevant to raw track ids,
+ // since sources include multiple tracks.
+ if (std::holds_alternative<database::TrackId>(*it)) {
+ it++;
+ }
+
+ while (limit > 0 && it != enqueued_.end()) {
+ auto item = *it;
+ if (std::holds_alternative<database::TrackId>(item)) {
+ ret.push_back(std::get<database::TrackId>(item));
+ limit--;
+ } else if (std::holds_alternative<std::shared_ptr<playlist::ISource>>(
+ item)) {
+ limit -=
+ std::get<std::shared_ptr<playlist::ISource>>(item)->Peek(limit, &ret);
+ } else if (std::holds_alternative<
+ std::shared_ptr<playlist::IResetableSource>>(item)) {
+ limit -=
+ std::get<std::shared_ptr<playlist::IResetableSource>>(item)->Peek(
+ limit, &ret);
+ }
+ it++;
+ }
+
return ret;
}
auto TrackQueue::AddNext(database::TrackId t) -> void {
const std::lock_guard<std::mutex> lock(mutex_);
- if (!current_) {
- current_ = t;
- } else {
- upcoming_.push_front(t);
- }
+ enqueued_.push_front(t);
+ events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
+}
+auto TrackQueue::AddNext(std::shared_ptr<playlist::ISource> src) -> void {
+ const std::lock_guard<std::mutex> lock(mutex_);
+ enqueued_.push_front(src);
events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
}
-auto TrackQueue::AddNext(const std::vector<database::TrackId>& t) -> void {
+auto TrackQueue::IncludeNext(std::shared_ptr<playlist::IResetableSource> src)
+ -> void {
const std::lock_guard<std::mutex> lock(mutex_);
- std::for_each(t.rbegin(), t.rend(),
- [&](const auto i) { upcoming_.push_front(i); });
- if (!current_) {
- current_ = upcoming_.front();
- upcoming_.pop_front();
- }
+ enqueued_.push_front(src);
events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
}
auto TrackQueue::AddLast(database::TrackId t) -> void {
const std::lock_guard<std::mutex> lock(mutex_);
- if (!current_) {
- current_ = t;
- } else {
- upcoming_.push_back(t);
- }
+ enqueued_.push_back(t);
+ events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
+}
+auto TrackQueue::AddLast(std::shared_ptr<playlist::ISource> src) -> void {
+ const std::lock_guard<std::mutex> lock(mutex_);
+ enqueued_.push_back(src);
events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
}
-auto TrackQueue::AddLast(const std::vector<database::TrackId>& t) -> void {
+auto TrackQueue::IncludeLast(std::shared_ptr<playlist::IResetableSource> src)
+ -> void {
const std::lock_guard<std::mutex> lock(mutex_);
- std::for_each(t.begin(), t.end(),
- [&](const auto i) { upcoming_.push_back(i); });
- if (!current_) {
- current_ = upcoming_.front();
- upcoming_.pop_front();
- }
+ enqueued_.push_back(src);
events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
}
auto TrackQueue::Next() -> void {
const std::lock_guard<std::mutex> lock(mutex_);
- if (current_) {
- played_.push_front(*current_);
+ if (enqueued_.empty()) {
+ return;
+ }
+
+ auto item = enqueued_.front();
+ if (std::holds_alternative<database::TrackId>(item)) {
+ played_.push_front(std::get<database::TrackId>(item));
+ enqueued_.pop_front();
+ }
+ if (std::holds_alternative<std::shared_ptr<playlist::ISource>>(item)) {
+ auto src = std::get<std::shared_ptr<playlist::ISource>>(item);
+ played_.push_front(*src->Current());
+ if (!src->Advance()) {
+ enqueued_.pop_front();
+ }
}
- if (!upcoming_.empty()) {
- current_ = upcoming_.front();
- upcoming_.pop_front();
- } else {
- current_.reset();
+ if (std::holds_alternative<std::shared_ptr<playlist::IResetableSource>>(
+ item)) {
+ auto src = std::get<std::shared_ptr<playlist::IResetableSource>>(item);
+ if (!src->Advance()) {
+ played_.push_back(src);
+ enqueued_.pop_front();
+ }
}
+
events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
}
auto TrackQueue::Previous() -> void {
const std::lock_guard<std::mutex> lock(mutex_);
- if (current_) {
- upcoming_.push_front(*current_);
+ if (!enqueued_.empty() &&
+ std::holds_alternative<std::shared_ptr<playlist::IResetableSource>>(
+ enqueued_.front())) {
+ auto src = std::get<std::shared_ptr<playlist::IResetableSource>>(
+ enqueued_.front());
+ if (src->Previous()) {
+ events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
+ return;
+ }
+ }
+
+ if (played_.empty()) {
+ return;
}
- if (!played_.empty()) {
- current_ = played_.front();
- played_.pop_front();
- } else {
- current_.reset();
+
+ auto item = played_.front();
+ if (std::holds_alternative<database::TrackId>(item)) {
+ enqueued_.push_front(std::get<database::TrackId>(item));
+ } else if (std::holds_alternative<
+ std::shared_ptr<playlist::IResetableSource>>(item)) {
+ enqueued_.push_front(
+ std::get<std::shared_ptr<playlist::IResetableSource>>(item));
}
+ played_.pop_front();
+
events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
}
auto TrackQueue::Clear() -> void {
const std::lock_guard<std::mutex> lock(mutex_);
played_.clear();
- upcoming_.clear();
- current_.reset();
- events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
-}
-
-auto TrackQueue::RemoveUpcoming(database::TrackId t) -> void {
- const std::lock_guard<std::mutex> lock(mutex_);
- for (auto it = upcoming_.begin(); it != upcoming_.end(); it++) {
- if (*it == t) {
- upcoming_.erase(it);
- return;
- }
- }
+ enqueued_.clear();
events::Dispatch<QueueUpdate, AudioState, ui::UiState>({});
}
diff --git a/src/database/CMakeLists.txt b/src/database/CMakeLists.txt
index 04e1d5d8..c5cc59cb 100644
--- a/src/database/CMakeLists.txt
+++ b/src/database/CMakeLists.txt
@@ -5,7 +5,7 @@
idf_component_register(
SRCS "env_esp.cpp" "database.cpp" "track.cpp" "records.cpp" "file_gatherer.cpp" "tag_parser.cpp" "index.cpp"
INCLUDE_DIRS "include"
- REQUIRES "result" "span" "esp_psram" "fatfs" "libtags" "komihash" "cbor" "tasks" "shared_string")
+ REQUIRES "result" "span" "esp_psram" "fatfs" "libtags" "komihash" "cbor" "tasks" "shared_string" "util")
target_compile_options(${COMPONENT_LIB} PRIVATE ${EXTRA_WARNINGS})
diff --git a/src/database/include/tag_parser.hpp b/src/database/include/tag_parser.hpp
index 4be5ad16..b0e9a151 100644
--- a/src/database/include/tag_parser.hpp
+++ b/src/database/include/tag_parser.hpp
@@ -8,6 +8,7 @@
#include <string>
+#include "lru_cache.hpp"
#include "track.hpp"
namespace database {
@@ -21,8 +22,19 @@ class ITagParser {
class TagParserImpl : public ITagParser {
public:
- virtual auto ReadAndParseTags(const std::string& path, TrackTags* out)
+ auto ReadAndParseTags(const std::string& path, TrackTags* out)
-> bool override;
+
+ private:
+ /*
+ * Cache of tags that have already been extracted from files. Ideally this
+ * cache should be slightly larger than any page sizes in the UI.
+ */
+ util::LruCache<16, std::string, TrackTags> cache_;
+
+ // We could also consider keeping caches of artist name -> shared_string and
+ // similar. This hasn't been done yet, as this isn't a common workload in any
+ // of our UI.
};
} // namespace database
diff --git a/src/database/include/track.hpp b/src/database/include/track.hpp
index 620fc59e..78f973ac 100644
--- a/src/database/include/track.hpp
+++ b/src/database/include/track.hpp
@@ -12,6 +12,7 @@
#include <memory>
#include <optional>
#include <string>
+#include <unordered_map>
#include <utility>
#include "leveldb/db.h"
@@ -88,7 +89,7 @@ class TrackTags {
private:
Encoding encoding_;
- std::map<Tag, shared_string> tags_;
+ std::unordered_map<Tag, shared_string> tags_;
};
/*
diff --git a/src/database/tag_parser.cpp b/src/database/tag_parser.cpp
index 2b784ea5..06d8a8c9 100644
--- a/src/database/tag_parser.cpp
+++ b/src/database/tag_parser.cpp
@@ -97,6 +97,12 @@ static const char* kTag = "TAGS";
auto TagParserImpl::ReadAndParseTags(const std::string& path, TrackTags* out)
-> bool {
+ std::optional<TrackTags> cached = cache_.Get(path);
+ if (cached) {
+ *out = *cached;
+ return true;
+ }
+
if (path.ends_with(".m4a")) {
// TODO(jacqueline): Re-enabled once libtags is fixed.
ESP_LOGW(kTag, "skipping m4a %s", path.c_str());
@@ -160,6 +166,7 @@ auto TagParserImpl::ReadAndParseTags(const std::string& path, TrackTags* out)
out->duration = ctx.duration;
}
+ cache_.Put(path, *out);
return true;
}
diff --git a/src/playlist/CMakeLists.txt b/src/playlist/CMakeLists.txt
new file mode 100644
index 00000000..6c08dd5a
--- /dev/null
+++ b/src/playlist/CMakeLists.txt
@@ -0,0 +1,10 @@
+# Copyright 2023 jacqueline <me@jacqueline.id.au>
+#
+# SPDX-License-Identifier: GPL-3.0-only
+
+idf_component_register(
+ SRCS "source.cpp" "shuffler.cpp"
+ INCLUDE_DIRS "include"
+ REQUIRES "database" "util")
+
+target_compile_options(${COMPONENT_LIB} PRIVATE ${EXTRA_WARNINGS})
diff --git a/src/playlist/include/shuffler.hpp b/src/playlist/include/shuffler.hpp
new file mode 100644
index 00000000..affc6301
--- /dev/null
+++ b/src/playlist/include/shuffler.hpp
@@ -0,0 +1,68 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#pragma once
+
+#include <deque>
+#include <memory>
+#include <mutex>
+#include <variant>
+#include <vector>
+
+#include "bloom_filter.hpp"
+#include "database.hpp"
+#include "future_fetcher.hpp"
+#include "random.hpp"
+#include "source.hpp"
+#include "track.hpp"
+
+namespace playlist {
+
+/*
+ * A source composes of other sources and/or specific extra tracks. Supports
+ * iteration over its contents in a random order.
+ */
+class Shuffler : public ISource {
+ public:
+ static auto Create() -> Shuffler*;
+
+ explicit Shuffler(
+ util::IRandom* random,
+ std::unique_ptr<util::BloomFilter<database::TrackId>> filter);
+
+ auto Current() -> std::optional<database::TrackId> override;
+ auto Advance() -> std::optional<database::TrackId> override;
+ auto Peek(std::size_t, std::vector<database::TrackId>*)
+ -> std::size_t override;
+
+ typedef std::variant<database::TrackId, std::shared_ptr<IResetableSource>>
+ Item;
+ auto Add(Item) -> void;
+
+ /*
+ * Returns the enqueued items, starting from the current item, in their
+ * original insertion order.
+ */
+ auto Unshuffle() -> std::vector<Item>;
+
+ // Not copyable or movable.
+
+ Shuffler(const Shuffler&) = delete;
+ Shuffler& operator=(const Shuffler&) = delete;
+
+ private:
+ auto RefillBuffer() -> void;
+
+ util::IRandom* random_;
+
+ std::unique_ptr<util::BloomFilter<database::TrackId>> already_played_;
+ bool out_of_items_;
+
+ std::deque<Item> ordered_items_;
+ std::deque<database::TrackId> shuffled_items_buffer_;
+};
+
+} // namespace playlist
diff --git a/src/playlist/include/source.hpp b/src/playlist/include/source.hpp
new file mode 100644
index 00000000..069c1e93
--- /dev/null
+++ b/src/playlist/include/source.hpp
@@ -0,0 +1,105 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#pragma once
+
+#include <deque>
+#include <memory>
+#include <mutex>
+#include <variant>
+#include <vector>
+
+#include "bloom_filter.hpp"
+#include "database.hpp"
+#include "future_fetcher.hpp"
+#include "random.hpp"
+#include "track.hpp"
+
+namespace playlist {
+
+/*
+ * Stateful interface for iterating over a collection of tracks by id.
+ */
+class ISource {
+ public:
+ virtual ~ISource() {}
+
+ virtual auto Current() -> std::optional<database::TrackId> = 0;
+
+ /*
+ * Discards the current track id and continues to the next in this source.
+ * Returns the new current track id.
+ */
+ virtual auto Advance() -> std::optional<database::TrackId> = 0;
+
+ /*
+ * Repeatedly advances until a track with the given id is the current track.
+ * Returns false if this source ran out of tracks before the requested id
+ * was encounted, true otherwise.
+ */
+ virtual auto AdvanceTo(database::TrackId id) -> bool {
+ for (auto t = Current(); t.has_value(); t = Advance()) {
+ if (*t == id) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /*
+ * Places the next n tracks into the given vector, in order. Does not change
+ * the value returned by Current().
+ */
+ virtual auto Peek(std::size_t n, std::vector<database::TrackId>*)
+ -> std::size_t = 0;
+};
+
+/*
+ * A Source that supports restarting iteration from its original initial
+ * value.
+ */
+class IResetableSource : public ISource {
+ public:
+ virtual ~IResetableSource() {}
+
+ virtual auto Previous() -> std::optional<database::TrackId> = 0;
+
+ /*
+ * Restarts iteration from this source's initial value.
+ */
+ virtual auto Reset() -> void = 0;
+};
+
+class IndexRecordSource : public IResetableSource {
+ public:
+ IndexRecordSource(std::weak_ptr<database::Database> db,
+ std::shared_ptr<database::Result<database::IndexRecord>>);
+
+ IndexRecordSource(std::weak_ptr<database::Database> db,
+ std::shared_ptr<database::Result<database::IndexRecord>>,
+ std::size_t,
+ std::shared_ptr<database::Result<database::IndexRecord>>,
+ std::size_t);
+
+ auto Current() -> std::optional<database::TrackId> override;
+ auto Advance() -> std::optional<database::TrackId> override;
+ auto Peek(std::size_t n, std::vector<database::TrackId>*)
+ -> std::size_t override;
+
+ auto Previous() -> std::optional<database::TrackId> override;
+ auto Reset() -> void override;
+
+ private:
+ std::weak_ptr<database::Database> db_;
+
+ std::shared_ptr<database::Result<database::IndexRecord>> initial_page_;
+ ssize_t initial_item_;
+
+ std::shared_ptr<database::Result<database::IndexRecord>> current_page_;
+ ssize_t current_item_;
+};
+
+} // namespace playlist
diff --git a/src/playlist/shuffler.cpp b/src/playlist/shuffler.cpp
new file mode 100644
index 00000000..b1c92335
--- /dev/null
+++ b/src/playlist/shuffler.cpp
@@ -0,0 +1,166 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#include "shuffler.hpp"
+
+#include <algorithm>
+#include <functional>
+#include <memory>
+#include <set>
+#include <variant>
+
+#include "bloom_filter.hpp"
+#include "database.hpp"
+#include "komihash.h"
+#include "random.hpp"
+#include "track.hpp"
+
+static constexpr std::size_t kShufflerBufferSize = 32;
+
+namespace playlist {
+
+auto Shuffler::Create() -> Shuffler* {
+ return new Shuffler(util::sRandom,
+ std::make_unique<util::BloomFilter<database::TrackId>>(
+ [](database::TrackId id) {
+ return komihash(&id, sizeof(database::TrackId), 0);
+ }));
+}
+
+Shuffler::Shuffler(util::IRandom* random,
+ std::unique_ptr<util::BloomFilter<database::TrackId>> filter)
+ : random_(random), already_played_(std::move(filter)) {}
+
+auto Shuffler::Current() -> std::optional<database::TrackId> {
+ if (shuffled_items_buffer_.empty()) {
+ return {};
+ }
+ return shuffled_items_buffer_.front();
+}
+
+auto Shuffler::Advance() -> std::optional<database::TrackId> {
+ if (shuffled_items_buffer_.empty() && !out_of_items_) {
+ RefillBuffer();
+ }
+
+ auto res = Current();
+ if (res) {
+ // Mark tracks off in the bloom filter only *after* they've been advanced
+ // past. This gives us the most flexibility for reshuffling when adding new
+ // items.
+ already_played_->Insert(*res);
+ shuffled_items_buffer_.pop_front();
+ }
+ return res;
+}
+
+auto Shuffler::Peek(std::size_t num, std::vector<database::TrackId>* out)
+ -> std::size_t {
+ if (shuffled_items_buffer_.size() < num) {
+ RefillBuffer();
+ }
+ for (int i = 0; i < num; i++) {
+ if (i >= shuffled_items_buffer_.size()) {
+ // We must be out of data, since the buffer didn't fill up.
+ return i;
+ }
+ out->push_back(shuffled_items_buffer_.at(i));
+ }
+ return num;
+}
+
+auto Shuffler::Add(Item item) -> void {
+ ordered_items_.push_back(item);
+ out_of_items_ = false;
+
+ // Empty out the buffer of already shuffled items, since we will need to
+ // shuffle again in order to incorporate the newly added item(s). We keep the
+ // current item however because we wouldn't want Add() to change the value of
+ // Current() unless we're completely out of items.
+ if (shuffled_items_buffer_.size() > 1) {
+ shuffled_items_buffer_.erase(shuffled_items_buffer_.begin() + 1,
+ shuffled_items_buffer_.end());
+ }
+ RefillBuffer();
+}
+
+auto Shuffler::Unshuffle() -> std::vector<Item> {
+ std::vector<Item> ret;
+ database::TrackId current = shuffled_items_buffer_.front();
+ bool has_found_current = false;
+
+ for (const Item& item : ordered_items_) {
+ if (!has_found_current) {
+ // TODO(jacqueline): *Should* this include previous items? What is the
+ // 'previous' button meant to do after unshuffling?
+ if (std::holds_alternative<database::TrackId>(item)) {
+ has_found_current = current == std::get<database::TrackId>(item);
+ } else {
+ auto source = std::get<std::shared_ptr<IResetableSource>>(item);
+ source->Reset();
+ has_found_current =
+ std::get<std::shared_ptr<IResetableSource>>(item)->AdvanceTo(
+ current);
+ }
+ } else {
+ ret.push_back(item);
+ }
+ }
+
+ return ret;
+}
+
+auto Shuffler::RefillBuffer() -> void {
+ // Don't waste time iterating if we know there's nothing new.
+ if (out_of_items_) {
+ return;
+ }
+
+ int num_to_sample = kShufflerBufferSize - shuffled_items_buffer_.size();
+ int resovoir_offset = shuffled_items_buffer_.size();
+
+ std::set<database::TrackId> in_buffer;
+ for (const database::TrackId& id : shuffled_items_buffer_) {
+ in_buffer.insert(id);
+ }
+
+ uint32_t i = 0;
+ auto consider_item = [&, this](const database::TrackId& item) {
+ if (already_played_->Contains(item) || in_buffer.contains(item)) {
+ return;
+ }
+ if (i < num_to_sample) {
+ shuffled_items_buffer_.push_back(item);
+ } else {
+ uint32_t index_to_replace = random_->RangeInclusive(0, i);
+ if (index_to_replace < num_to_sample) {
+ shuffled_items_buffer_[resovoir_offset + index_to_replace] = item;
+ }
+ }
+ i++;
+ };
+
+ for (const Item& item : ordered_items_) {
+ if (std::holds_alternative<database::TrackId>(item)) {
+ std::invoke(consider_item, std::get<database::TrackId>(item));
+ } else {
+ auto source = std::get<std::shared_ptr<IResetableSource>>(item);
+ source->Reset();
+ while (source->Advance()) {
+ std::invoke(consider_item, *source->Current());
+ }
+ }
+ }
+
+ out_of_items_ = i > num_to_sample;
+ // We've now got a random *selection*, but the order might be predictable
+ // (e.g. if there were only `num_to_sample` new items). Do a final in-memory
+ // shuffle.
+ std::random_shuffle(shuffled_items_buffer_.begin() + resovoir_offset,
+ shuffled_items_buffer_.end());
+}
+
+} // namespace playlist
diff --git a/src/playlist/source.cpp b/src/playlist/source.cpp
new file mode 100644
index 00000000..0df514e4
--- /dev/null
+++ b/src/playlist/source.cpp
@@ -0,0 +1,145 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#include "source.hpp"
+
+#include <algorithm>
+#include <functional>
+#include <memory>
+#include <set>
+#include <variant>
+
+#include "esp_log.h"
+
+#include "bloom_filter.hpp"
+#include "database.hpp"
+#include "komihash.h"
+#include "random.hpp"
+#include "track.hpp"
+
+namespace playlist {
+
+IndexRecordSource::IndexRecordSource(
+ std::weak_ptr<database::Database> db,
+ std::shared_ptr<database::Result<database::IndexRecord>> initial)
+ : db_(db),
+ initial_page_(initial),
+ initial_item_(0),
+ current_page_(initial_page_),
+ current_item_(initial_item_) {}
+
+IndexRecordSource::IndexRecordSource(
+ std::weak_ptr<database::Database> db,
+ std::shared_ptr<database::Result<database::IndexRecord>> initial,
+ std::size_t initial_index,
+ std::shared_ptr<database::Result<database::IndexRecord>> current,
+ std::size_t current_index)
+ : db_(db),
+ initial_page_(initial),
+ initial_item_(initial_index),
+ current_page_(current),
+ current_item_(current_index) {}
+
+auto IndexRecordSource::Current() -> std::optional<database::TrackId> {
+ if (current_page_->values().size() <= current_item_) {
+ return {};
+ }
+ if (current_page_ == initial_page_ && current_item_ < initial_item_) {
+ return {};
+ }
+
+ return current_page_->values().at(current_item_).track();
+}
+
+auto IndexRecordSource::Advance() -> std::optional<database::TrackId> {
+ current_item_++;
+ if (current_item_ >= current_page_->values().size()) {
+ auto next_page = current_page_->next_page();
+ if (!next_page) {
+ current_item_--;
+ return {};
+ }
+
+ auto db = db_.lock();
+ if (!db) {
+ return {};
+ }
+
+ current_page_.reset(db->GetPage(&*next_page).get());
+ current_item_ = 0;
+ }
+
+ return Current();
+}
+
+auto IndexRecordSource::Previous() -> std::optional<database::TrackId> {
+ if (current_page_ == initial_page_ && current_item_ <= initial_item_) {
+ return {};
+ }
+
+ current_item_--;
+ if (current_item_ < 0) {
+ auto prev_page = current_page_->prev_page();
+ if (!prev_page) {
+ return {};
+ }
+
+ auto db = db_.lock();
+ if (!db) {
+ return {};
+ }
+
+ current_page_.reset(db->GetPage(&*prev_page).get());
+ current_item_ = current_page_->values().size() - 1;
+ }
+
+ return Current();
+}
+
+auto IndexRecordSource::Peek(std::size_t n, std::vector<database::TrackId>* out)
+ -> std::size_t {
+ if (current_page_->values().size() <= current_item_) {
+ return {};
+ }
+
+ auto db = db_.lock();
+ if (!db) {
+ return 0;
+ }
+
+ std::size_t items_added = 0;
+
+ std::shared_ptr<database::Result<database::IndexRecord>> working_page =
+ current_page_;
+ std::size_t working_item = current_item_ + 1;
+
+ while (n > 0) {
+ if (working_item >= working_page->values().size()) {
+ auto next_page = current_page_->next_page();
+ if (!next_page) {
+ break;
+ }
+ // TODO(jacqueline): It would probably be a good idea to hold onto these
+ // peeked pages, to avoid needing to look them up again later.
+ working_page.reset(db->GetPage(&*next_page).get());
+ working_item = 0;
+ }
+
+ out->push_back(working_page->values().at(working_item).track().value());
+ n--;
+ items_added++;
+ working_item++;
+ }
+
+ return items_added;
+}
+
+auto IndexRecordSource::Reset() -> void {
+ current_page_ = initial_page_;
+ current_item_ = initial_item_;
+}
+
+} // namespace playlist
diff --git a/src/ui/include/screen_track_browser.hpp b/src/ui/include/screen_track_browser.hpp
index af80f29c..3d347158 100644
--- a/src/ui/include/screen_track_browser.hpp
+++ b/src/ui/include/screen_track_browser.hpp
@@ -38,15 +38,14 @@ class TrackBrowser : public Screen {
END = 1,
};
auto AddLoadingIndictor(Position pos) -> void;
- auto AddResults(Position pos, database::Result<database::IndexRecord>*)
+ auto AddResults(Position pos,
+ std::shared_ptr<database::Result<database::IndexRecord>>)
-> void;
auto DropPage(Position pos) -> void;
auto FetchNewPage(Position pos) -> void;
auto GetNumRecords() -> std::size_t;
auto GetItemIndex(lv_obj_t* obj) -> std::optional<std::size_t>;
- auto GetRecordByIndex(std::size_t index)
- -> std::optional<database::IndexRecord>;
std::weak_ptr<database::Database> db_;
lv_obj_t* back_button_;
@@ -57,7 +56,8 @@ class TrackBrowser : public Screen {
std::optional<std::future<database::Result<database::IndexRecord>*>>
loading_page_;
- std::deque<std::unique_ptr<database::Result<database::IndexRecord>>>
+ std::shared_ptr<database::Result<database::IndexRecord>> initial_page_;
+ std::deque<std::shared_ptr<database::Result<database::IndexRecord>>>
current_pages_;
};
diff --git a/src/ui/include/ui_events.hpp b/src/ui/include/ui_events.hpp
index cc7db349..a0ef1c31 100644
--- a/src/ui/include/ui_events.hpp
+++ b/src/ui/include/ui_events.hpp
@@ -6,6 +6,7 @@
#pragma once
+#include <memory>
#include "database.hpp"
#include "index.hpp"
#include "tinyfsm.hpp"
@@ -25,7 +26,9 @@ struct OnSystemError : tinyfsm::Event {};
namespace internal {
struct RecordSelected : tinyfsm::Event {
- database::IndexRecord record;
+ std::shared_ptr<database::Result<database::IndexRecord>> initial_page;
+ std::shared_ptr<database::Result<database::IndexRecord>> page;
+ std::size_t record;
};
struct IndexSelected : tinyfsm::Event {
diff --git a/src/ui/screen_track_browser.cpp b/src/ui/screen_track_browser.cpp
index a9333be4..07977710 100644
--- a/src/ui/screen_track_browser.cpp
+++ b/src/ui/screen_track_browser.cpp
@@ -66,7 +66,8 @@ TrackBrowser::TrackBrowser(
list_(nullptr),
loading_indicator_(nullptr),
loading_pos_(END),
- loading_page_(std::move(initial_page)),
+ loading_page_(move(initial_page)),
+ initial_page_(),
current_pages_() {
lv_obj_set_layout(root_, LV_LAYOUT_FLEX);
lv_obj_set_size(root_, lv_pct(100), lv_pct(100));
@@ -102,7 +103,8 @@ auto TrackBrowser::Tick() -> void {
}
if (loading_page_->wait_for(std::chrono::seconds(0)) ==
std::future_status::ready) {
- auto result = loading_page_->get();
+ std::shared_ptr<database::Result<database::IndexRecord>> result{
+ loading_page_->get()};
AddResults(loading_pos_.value_or(END), result);
loading_page_.reset();
@@ -126,18 +128,26 @@ auto TrackBrowser::OnItemSelected(lv_event_t* ev) -> void {
}
auto TrackBrowser::OnItemClicked(lv_event_t* ev) -> void {
- auto index = GetItemIndex(lv_event_get_target(ev));
- if (!index) {
+ auto res = GetItemIndex(lv_event_get_target(ev));
+ if (!res) {
return;
}
- auto record = GetRecordByIndex(*index);
- if (!record) {
- return;
+
+ auto index = *res;
+ for (const auto& page : current_pages_) {
+ for (std::size_t i = 0; i < page->values().size(); i++) {
+ if (index == 0) {
+ events::Dispatch<internal::RecordSelected, UiState>(
+ internal::RecordSelected{
+ .initial_page = initial_page_,
+ .page = page,
+ .record = i,
+ });
+ return;
+ }
+ index--;
+ }
}
- ESP_LOGI(kTag, "clicked item %u (%s)", *index,
- record->text().value_or("[nil]").c_str());
- events::Dispatch<internal::RecordSelected, UiState>(
- internal::RecordSelected{.record = *record});
}
auto TrackBrowser::AddLoadingIndictor(Position pos) -> void {
@@ -150,14 +160,18 @@ auto TrackBrowser::AddLoadingIndictor(Position pos) -> void {
}
}
-auto TrackBrowser::AddResults(Position pos,
- database::Result<database::IndexRecord>* results)
- -> void {
+auto TrackBrowser::AddResults(
+ Position pos,
+ std::shared_ptr<database::Result<database::IndexRecord>> results) -> void {
if (loading_indicator_ != nullptr) {
lv_obj_del(loading_indicator_);
loading_indicator_ = nullptr;
}
+ if (initial_page_ == nullptr) {
+ initial_page_ = results;
+ }
+
auto fn = [&](const database::IndexRecord& record) {
auto text = record.text();
if (!text) {
@@ -192,11 +206,11 @@ auto TrackBrowser::AddResults(Position pos,
switch (pos) {
case START:
std::for_each(results->values().rbegin(), results->values().rend(), fn);
- current_pages_.emplace_front(results);
+ current_pages_.push_front(results);
break;
case END:
std::for_each(results->values().begin(), results->values().end(), fn);
- current_pages_.emplace_back(results);
+ current_pages_.push_back(results);
break;
}
@@ -302,24 +316,5 @@ auto TrackBrowser::GetItemIndex(lv_obj_t* obj) -> std::optional<std::size_t> {
return {};
}
-auto TrackBrowser::GetRecordByIndex(std::size_t index)
- -> std::optional<database::IndexRecord> {
- std::size_t total_tracks = 0;
- for (int i = 0; i < current_pages_.size(); i++) {
- total_tracks += current_pages_.at(i)->values().size();
- }
- ESP_LOGI(kTag, "total tracks %u, getting index %u", total_tracks, index);
-
- for (const auto& page : current_pages_) {
- for (int i = 0; i < page->values().size(); i++) {
- if (index == 0) {
- return page->values().at(i);
- }
- index--;
- }
- }
- return {};
-}
-
} // namespace screens
} // namespace ui
diff --git a/src/ui/ui_fsm.cpp b/src/ui/ui_fsm.cpp
index 96949cd0..a9c3b61c 100644
--- a/src/ui/ui_fsm.cpp
+++ b/src/ui/ui_fsm.cpp
@@ -17,6 +17,7 @@
#include "screen_playing.hpp"
#include "screen_splash.hpp"
#include "screen_track_browser.hpp"
+#include "source.hpp"
#include "system_events.hpp"
#include "touchwheel.hpp"
#include "track_queue.hpp"
@@ -117,20 +118,21 @@ void Browse::react(const internal::RecordSelected& ev) {
return;
}
- if (ev.record.track()) {
- ESP_LOGI(kTag, "selected track '%s'", ev.record.text()->c_str());
- // TODO(jacqueline): We should also send some kind of playlist info here.
+ auto record = ev.page->values().at(ev.record);
+ if (record.track()) {
+ ESP_LOGI(kTag, "selected track '%s'", record.text()->c_str());
sQueue->Clear();
- sQueue->AddLast(*ev.record.track());
+ sQueue->IncludeLast(std::make_shared<playlist::IndexRecordSource>(
+ sDb, ev.initial_page, 0, ev.page, ev.record));
transit<Playing>();
} else {
- ESP_LOGI(kTag, "selected record '%s'", ev.record.text()->c_str());
- auto cont = ev.record.Expand(kRecordsPerPage);
+ ESP_LOGI(kTag, "selected record '%s'", record.text()->c_str());
+ auto cont = record.Expand(kRecordsPerPage);
if (!cont) {
return;
}
auto query = db->GetPage(&cont.value());
- std::string title = ev.record.text().value_or("TODO");
+ std::string title = record.text().value_or("TODO");
PushScreen(
std::make_shared<screens::TrackBrowser>(sDb, title, std::move(query)));
}
diff --git a/src/util/CMakeLists.txt b/src/util/CMakeLists.txt
new file mode 100644
index 00000000..0903a912
--- /dev/null
+++ b/src/util/CMakeLists.txt
@@ -0,0 +1,7 @@
+# Copyright 2023 jacqueline <me@jacqueline.id.au>
+#
+# SPDX-License-Identifier: GPL-3.0-only
+
+idf_component_register(
+ INCLUDE_DIRS "include"
+ REQUIRES "database")
diff --git a/src/util/include/bloom_filter.hpp b/src/util/include/bloom_filter.hpp
new file mode 100644
index 00000000..04b72e20
--- /dev/null
+++ b/src/util/include/bloom_filter.hpp
@@ -0,0 +1,40 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#pragma once
+
+#include <bitset>
+#include <cstdint>
+#include <functional>
+
+namespace util {
+
+template <typename T>
+class BloomFilter {
+ public:
+ explicit BloomFilter(std::function<uint64_t(T)> hasher)
+ : hasher_(hasher), bits_() {}
+
+ auto Insert(T val) -> void {
+ uint64_t hash = std::invoke(hasher_, val);
+ bits_[hash & 0xFFFF] = 1;
+ bits_[(hash >> 16) & 0xFFFF] = 1;
+ bits_[(hash >> 32) & 0xFFFF] = 1;
+ bits_[(hash >> 48) & 0xFFFF] = 1;
+ }
+
+ auto Contains(T val) -> bool {
+ uint64_t hash = std::invoke(hasher_, val);
+ return bits_[hash & 0xFFFF] && bits_[(hash >> 16) & 0xFFFF] &&
+ bits_[(hash >> 32) & 0xFFFF] && bits_[(hash >> 48) & 0xFFFF];
+ }
+
+ private:
+ std::function<uint64_t(T)> hasher_;
+ std::bitset<(1 << 16)> bits_;
+};
+
+} // namespace util
diff --git a/src/util/include/lru_cache.hpp b/src/util/include/lru_cache.hpp
new file mode 100644
index 00000000..8f955a07
--- /dev/null
+++ b/src/util/include/lru_cache.hpp
@@ -0,0 +1,69 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#pragma once
+
+#include <algorithm>
+#include <bitset>
+#include <cstdint>
+#include <list>
+#include <optional>
+#include <unordered_map>
+#include <utility>
+
+namespace util {
+
+/*
+ * Basic least recently used cache. Stores the `Size` most recently accessed
+ * entries in memory.
+ *
+ * Not safe for use from multiple tasks, but all operations are constant time.
+ */
+template <int Size, typename K, typename V>
+class LruCache {
+ public:
+ LruCache() : entries_(), key_to_it_() {}
+
+ auto Put(K key, V val) -> void {
+ if (key_to_it_.contains(key)) {
+ // This key was already present. Overwrite by removing the previous
+ // value.
+ entries_.erase(key_to_it_[key]);
+ key_to_it_.erase(key);
+ } else if (entries_.size() >= Size) {
+ // Cache is full. Evict the last entry.
+ key_to_it_.erase(entries_.back().first);
+ entries_.pop_back();
+ }
+
+ // Add the new value.
+ entries_.push_front({key, val});
+ key_to_it_[key] = entries_.begin();
+ }
+
+ auto Get(K key) -> std::optional<V> {
+ if (!key_to_it_.contains(key)) {
+ return {};
+ }
+ // Use splice() to move the entry to the front of the list. This approach
+ // doesn't invalidate any of the iterators in key_to_it_, and is constant
+ // time.
+ auto it = key_to_it_[key];
+ entries_.splice(entries_.begin(), entries_, it);
+ return it->second;
+ }
+
+ auto Clear() -> void {
+ entries_.clear();
+ key_to_it_.clear();
+ }
+
+ private:
+ std::list<std::pair<K, V>> entries_;
+ std::unordered_map<K, decltype(entries_.begin())> key_to_it_;
+};
+
+} // namespace util
diff --git a/src/util/include/random.hpp b/src/util/include/random.hpp
new file mode 100644
index 00000000..cd8ab1c6
--- /dev/null
+++ b/src/util/include/random.hpp
@@ -0,0 +1,39 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#pragma once
+
+#include <cstdint>
+
+#include "komihash.h"
+
+namespace util {
+
+class IRandom {
+ public:
+ virtual ~IRandom() {}
+
+ virtual auto Next() -> std::uint64_t = 0;
+ virtual auto RangeInclusive(std::uint64_t lower, std::uint64_t upper)
+ -> std::uint64_t = 0;
+};
+
+extern IRandom* sRandom;
+
+class Random : public IRandom {
+ public:
+ Random();
+
+ auto Next() -> std::uint64_t override;
+ auto RangeInclusive(std::uint64_t lower, std::uint64_t upper)
+ -> std::uint64_t override;
+
+ private:
+ std::uint64_t seed1_;
+ std::uint64_t seed2_;
+};
+
+} // namespace util
diff --git a/src/util/random.cpp b/src/util/random.cpp
new file mode 100644
index 00000000..ae543765
--- /dev/null
+++ b/src/util/random.cpp
@@ -0,0 +1,37 @@
+/*
+ * Copyright 2023 jacqueline <me@jacqueline.id.au>
+ *
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+
+#include "random.hpp"
+
+#include <cstdint>
+
+#include "esp_random.h"
+#include "komihash.h"
+
+namespace util {
+
+IRandom* sRandom = new Random();
+
+Random::Random() {
+ esp_fill_random(&seed1_, sizeof(seed1_));
+ seed2_ = seed1_;
+
+ // komirand needs four iterations to properly self-start.
+ for (int i = 0; i < 4; i++) {
+ Next();
+ }
+}
+
+auto Random::Next() -> std::uint64_t {
+ return komirand(&seed1_, &seed2_);
+}
+
+auto Random::RangeInclusive(std::uint64_t lower, std::uint64_t upper)
+ -> std::uint64_t {
+ return (Next() % (upper - lower + 1)) + lower;
+}
+
+} // namespace util
generated by cgit v1.2.3 (git 2.25.1) at 2026-04-29 19:57:53 +0000