From 0596a4afb1b3b835f3cf9912551e4fbf74c2b70b Mon Sep 17 00:00:00 2001
From: Liam <byteslice@airmail.cc>
Date: Fri, 26 May 2023 15:41:17 -0400
Subject: vfs_concat: fix time complexity of read

---
 src/core/file_sys/vfs_concat.h | 28 +++++++++++++++++++++-------
 1 file changed, 21 insertions(+), 7 deletions(-)

(limited to 'src/core/file_sys/vfs_concat.h')

diff --git a/src/core/file_sys/vfs_concat.h b/src/core/file_sys/vfs_concat.h
index 9be0261b6..6b329d545 100644
--- a/src/core/file_sys/vfs_concat.h
+++ b/src/core/file_sys/vfs_concat.h
@@ -3,6 +3,7 @@
 
 #pragma once
 
+#include <compare>
 #include <map>
 #include <memory>
 #include "core/file_sys/vfs.h"
@@ -12,19 +13,33 @@ namespace FileSys {
 // Class that wraps multiple vfs files and concatenates them, making reads seamless. Currently
 // read-only.
 class ConcatenatedVfsFile : public VfsFile {
-    explicit ConcatenatedVfsFile(std::vector<VirtualFile> files, std::string name_);
-    explicit ConcatenatedVfsFile(std::multimap<u64, VirtualFile> files, std::string name_);
+private:
+    struct ConcatenationEntry {
+        u64 offset;
+        VirtualFile file;
+
+        auto operator<=>(const ConcatenationEntry& other) const {
+            return this->offset <=> other.offset;
+        }
+    };
+    using ConcatenationMap = std::vector<ConcatenationEntry>;
+
+    explicit ConcatenatedVfsFile(std::vector<ConcatenationEntry>&& concatenation_map,
+                                 std::string&& name);
+    bool VerifyContinuity() const;
 
 public:
     ~ConcatenatedVfsFile() override;
 
     /// Wrapper function to allow for more efficient handling of files.size() == 0, 1 cases.
-    static VirtualFile MakeConcatenatedFile(std::vector<VirtualFile> files, std::string name);
+    static VirtualFile MakeConcatenatedFile(const std::vector<VirtualFile>& files,
+                                            std::string&& name);
 
     /// Convenience function that turns a map of offsets to files into a concatenated file, filling
     /// gaps with a given filler byte.
-    static VirtualFile MakeConcatenatedFile(u8 filler_byte, std::multimap<u64, VirtualFile> files,
-                                            std::string name);
+    static VirtualFile MakeConcatenatedFile(u8 filler_byte,
+                                            const std::multimap<u64, VirtualFile>& files,
+                                            std::string&& name);
 
     std::string GetName() const override;
     std::size_t GetSize() const override;
@@ -37,8 +52,7 @@ public:
     bool Rename(std::string_view new_name) override;
 
 private:
-    // Maps starting offset to file -- more efficient.
-    std::multimap<u64, VirtualFile> files;
+    ConcatenationMap concatenation_map;
     std::string name;
 };
 
-- 
cgit v1.2.3