From 44da9fc9afb6b7e49c1558c5572213a1e6f401e8 Mon Sep 17 00:00:00 2001
From: Mikko Rasa <tdb@tdb.fi>
Date: Sun, 29 Aug 2021 16:16:44 +0300
Subject: [PATCH] Prefer more cache-efficient containers

---
 source/core/getopt.cpp   |  4 ++--
 source/core/getopt.h     |  4 ++--
 source/debug/backtrace.h |  6 +++---
 source/fs/dir.cpp        | 12 ++++++------
 source/fs/dir.h          |  8 ++++----
 source/fs/unix/utils.cpp |  3 ++-
 source/fs/utils.cpp      |  2 +-
 source/strings/regex.cpp |  3 ++-
 8 files changed, 22 insertions(+), 20 deletions(-)

diff --git a/source/core/getopt.cpp b/source/core/getopt.cpp
index ec821e0..6f7b1f8 100644
--- a/source/core/getopt.cpp
+++ b/source/core/getopt.cpp
@@ -260,7 +260,7 @@ string GetOpt::generate_help() const
 	bool any_short = any_of(opts.begin(), opts.end(), [](const OptionImpl *o){ return o->get_short(); });
 
 	string::size_type maxw = 0;
-	list<string> switches;
+	vector<string> switches;
 	for(const OptionImpl *o: opts)
 	{
 		string swtch;
@@ -289,7 +289,7 @@ string GetOpt::generate_help() const
 		maxw = max(maxw, swtch.size());
 	}
 
-	list<string> pargs;
+	vector<string> pargs;
 	for(const ArgumentImpl *a: args)
 	{
 		string parg = format("<%s>", a->get_name());
diff --git a/source/core/getopt.h b/source/core/getopt.h
index 27ce4cf..405864b 100644
--- a/source/core/getopt.h
+++ b/source/core/getopt.h
@@ -204,8 +204,8 @@ private:
 	};
 
 	bool help;
-	std::list<OptionImpl *> opts;
-	std::list<ArgumentImpl *> args;
+	std::vector<OptionImpl *> opts;
+	std::vector<ArgumentImpl *> args;
 	std::vector<std::string> args_raw;
 
 public:
diff --git a/source/debug/backtrace.h b/source/debug/backtrace.h
index 33ed893..3f32ade 100644
--- a/source/debug/backtrace.h
+++ b/source/debug/backtrace.h
@@ -1,9 +1,9 @@
 #ifndef MSP_DEBUG_BACKTRACE_H_
 #define MSP_DEBUG_BACKTRACE_H_
 
-#include <list>
 #include <ostream>
 #include <string>
+#include <vector>
 
 namespace Msp {
 namespace Debug {
@@ -19,10 +19,10 @@ public:
 	};
 
 private:
-	std::list<StackFrame> frames;
+	std::vector<StackFrame> frames;
 
 public:
-	const std::list<StackFrame> &get_frames() const { return frames; }
+	const std::vector<StackFrame> &get_frames() const { return frames; }
 
 	static Backtrace create();
 };
diff --git a/source/fs/dir.cpp b/source/fs/dir.cpp
index 99de180..0980203 100644
--- a/source/fs/dir.cpp
+++ b/source/fs/dir.cpp
@@ -101,16 +101,16 @@ void rmpath(const Path &path)
 	rmdir(path);
 }
 
-list<string> list_files(const Path &path)
+vector<string> list_files(const Path &path)
 {
 	return list_filtered(path, string());
 }
 
-list<string> list_filtered(const Path &path, const string &filter)
+vector<string> list_filtered(const Path &path, const string &filter)
 {
 	Regex r_filter(filter);
 
-	list<string> result;
+	vector<string> result;
 	DIR *dir = opendir(path.str().c_str());
 	if(!dir)
 		throw system_error("opendir");
@@ -177,7 +177,7 @@ Path get_sys_lib_dir()
 		return dir;
 }
 
-Path path_lookup(const string &name, const list<Path> &paths)
+Path path_lookup(const string &name, const vector<Path> &paths)
 {
 	for(const Path &p: paths)
 	{
@@ -192,8 +192,8 @@ Path path_lookup(const string &name, const list<Path> &paths)
 Path path_lookup(const string &name)
 {
 	const char *path = getenv("PATH");
-	list<string> dirs = split(path, ITEMSEP);
-	return path_lookup(name, list<Path>(dirs.begin(), dirs.end()));
+	vector<string> dirs = split(path, ITEMSEP);
+	return path_lookup(name, vector<Path>(dirs.begin(), dirs.end()));
 }
 
 } // namespace FS
diff --git a/source/fs/dir.h b/source/fs/dir.h
index be5fac8..c0a1c74 100644
--- a/source/fs/dir.h
+++ b/source/fs/dir.h
@@ -1,9 +1,9 @@
 #ifndef MSP_FS_DIR_H_
 #define MSP_FS_DIR_H_
 
-#include <list>
 #include <stdexcept>
 #include <string>
+#include <vector>
 #include "path.h"
 
 namespace Msp {
@@ -29,10 +29,10 @@ void rmdir(const Path &path);
 void rmpath(const Path &path);
 
 /// Lists the contents of a directory
-std::list<std::string> list_files(const Path &path);
+std::vector<std::string> list_files(const Path &path);
 
 /// Lists the contents of a directory, filtered with a regex
-std::list<std::string> list_filtered(const Path &path, const std::string &filter);
+std::vector<std::string> list_filtered(const Path &path, const std::string &filter);
 
 /// Returns the current working directory
 Path getcwd();
@@ -57,7 +57,7 @@ Path get_sys_lib_dir();
 
 /** Looks for a file in a list of paths.  Returns the absolute path to the
 first existing location, or an empty Path if the file is not found at all. */
-Path path_lookup(const std::string &, const std::list<Path> &);
+Path path_lookup(const std::string &, const std::vector<Path> &);
 
 /** Looks for a file using the PATH environment variable. */
 Path path_lookup(const std::string &);
diff --git a/source/fs/unix/utils.cpp b/source/fs/unix/utils.cpp
index c832343..a960b40 100644
--- a/source/fs/unix/utils.cpp
+++ b/source/fs/unix/utils.cpp
@@ -1,4 +1,5 @@
 #include <cstdio>
+#include <deque>
 #include <unistd.h>
 #include <msp/core/systemerror.h>
 #include "dir.h"
@@ -21,7 +22,7 @@ Path readlink(const Path &link)
 
 Path realpath(const Path &path)
 {
-	list<string> queue(path.begin(), path.end());
+	deque<string> queue(path.begin(), path.end());
 	if(!path.is_absolute())
 	{
 		Path cwd = getcwd();
diff --git a/source/fs/utils.cpp b/source/fs/utils.cpp
index e15aad4..7ceb7ad 100644
--- a/source/fs/utils.cpp
+++ b/source/fs/utils.cpp
@@ -49,7 +49,7 @@ Path fix_case(const Path &path)
 			result /= c;
 		else
 		{
-			list<string> files;
+			vector<string> files;
 			if(result.size())
 				files = list_files(result);
 			else
diff --git a/source/strings/regex.cpp b/source/strings/regex.cpp
index 9167c6b..27361b0 100644
--- a/source/strings/regex.cpp
+++ b/source/strings/regex.cpp
@@ -1,6 +1,7 @@
 #include <limits>
 #include <list>
 #include <stack>
+#include <vector>
 #include "format.h"
 #include "regex.h"
 
@@ -157,7 +158,7 @@ Regex::Code Regex::compile(const string &expr, string::const_iterator &iter, uns
 	}
 	else
 	{
-		list<Code> branches;
+		vector<Code> branches;
 		for(auto i=iter;;)
 		{
 			branches.push_back(compile(expr, i, group, true));
-- 
2.43.0