Created
February 6, 2019 07:33
-
-
Save othrayte/42a10fc37b0c9ff4d1f213be309b9819 to your computer and use it in GitHub Desktop.
[WIP] Scroll - append only list, uses paging to allow lockless single writer / multiple reader with "random access" reads
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <list> | |
| #include <array> | |
| #include <variant> | |
| #include <memory> | |
| #include <cassert> | |
| template <class ...Fs> | |
| struct overload : Fs... { | |
| template <class ...Ts> | |
| overload(Ts&& ...ts) : Fs{std::forward<Ts>(ts)}... | |
| {} | |
| using Fs::operator()...; | |
| }; | |
| template <class ...Ts> | |
| overload(Ts&&...) -> overload<std::remove_reference_t<Ts>...>; | |
| template <typename PageT, int mapSize = 64> | |
| struct PageMap { | |
| using Leaf = std::array<std::unique_ptr<PageT>, mapSize>; | |
| struct Branch { | |
| std::array<std::unique_ptr<PageMap>, mapSize> map; | |
| int order; | |
| }; | |
| std::variant<Leaf, Branch> node; | |
| int offset; | |
| const PageT& access(int pageIndex) const { | |
| return std::visit( | |
| overload( | |
| [&](const Branch& branch) { | |
| int mapIndex = (pageIndex - offset)/branch.order; | |
| assert(mapIndex < mapSize); | |
| assert(branch.map[mapIndex]); | |
| return branch.map[mapIndex].access(pageIndex); | |
| }, | |
| [&](const Leaf& leaf) { | |
| int mapIndex = (pageIndex - offset); | |
| assert(mapIndex < mapSize); | |
| assert(leaf.map[mapIndex]); | |
| return (*leaf.map[mapIndex])[pageIndex]; | |
| } | |
| ), | |
| node | |
| ); | |
| } | |
| static std::unique_ptr<PageMap> extendPageMap(std::unique_ptr<PageMap>&& pageMap, PageT&& newPage, int newPageIndex) { | |
| if (!std::visit( | |
| overload( | |
| [&](const Branch& branch) { | |
| int mapIndex = (newPageIndex - pageMap.offset)/branch.order; | |
| if (mapIndex >= mapSize) return false; | |
| assert(!branch.map[mapIndex]); | |
| return extendPageMap(std::move(branch.map[mapIndex]), std::move(newPage), newPageIndex); | |
| }, | |
| [&](const Leaf& leaf) { | |
| int mapIndex = (newPageIndex - pageMap.offset); | |
| if (mapIndex >= mapSize) return false; | |
| assert(!leaf.map[mapIndex]); | |
| leaf.map[mapIndex] = std::move(newPage); | |
| return true; | |
| } | |
| ), | |
| pageMap.node | |
| )) { | |
| if | |
| } | |
| } | |
| }; | |
| template <typename T, int size> | |
| struct Page { | |
| std::array<T, size> data; | |
| Page* prev; | |
| Page* next; | |
| }; | |
| template<typename T, int pageSize = 64> | |
| class Scroll { | |
| struct Location { | |
| int page; | |
| int element; | |
| }; | |
| public: | |
| Scroll() : pages(1), unrolledSize(0), size(0) {} | |
| T& operator[](int index) { | |
| return access(locate(index)); | |
| } | |
| const T& operator[](int index) const { | |
| return access(locate(index)); | |
| } | |
| void push_back(const T& item) { | |
| auto location = locate(size); | |
| if (location.page >= pages.size()) { | |
| pages.emplace_back(); | |
| pages.back()[location.element] = item; | |
| } else { | |
| access(location) = item; | |
| } | |
| } | |
| private: | |
| int& access(Location location) { | |
| auto iter = pages.begin(); | |
| std::advance(iter, location.page); | |
| return (*iter)[location.element]; | |
| } | |
| const int& access(Location location) const { | |
| auto iter = pages.begin(); | |
| std::advance(iter, location.page); | |
| return (*iter)[location.element]; | |
| } | |
| Location locate(int index) const { return {index / pageSize, index % pageSize}; } | |
| PageMap<Page<T, pageSize>> pages; | |
| int unrolledSize; | |
| int size; | |
| }; | |
| int main(int) { | |
| Scroll<int> ints; | |
| ints.push_back(1); | |
| ints.push_back(42); | |
| ints.push_back(13); | |
| ints.push_back(144); | |
| return ints[2]; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment