diff --git a/libc/src/__support/CPP/blockstore.h b/libc/src/__support/CPP/blockstore.h --- a/libc/src/__support/CPP/blockstore.h +++ b/libc/src/__support/CPP/blockstore.h @@ -13,6 +13,11 @@ #include #include +// TODO: fix our assert.h to make it useable +#define assert(x) \ + if (!(x)) \ + __builtin_trap() + namespace __llvm_libc { namespace cpp { @@ -40,6 +45,22 @@ Block *current = &first; size_t fill_count = 0; + struct Pair { + Block *first, *second; + }; + Pair getLastBlocks() { + if (REVERSE_ORDER) + return {current, current->next}; + Block *prev = nullptr; + Block *curr = &first; + for (; curr->next; prev = curr, curr = curr->next) + ; + assert(curr == current); + return {curr, prev}; + } + + Block *getLastBlock() { return getLastBlocks().first; } + public: constexpr BlockStore() = default; ~BlockStore() = default; @@ -113,6 +134,31 @@ *ptr = value; } + T &back() { + return *reinterpret_cast(getLastBlock()->data + + sizeof(T) * (fill_count - 1)); + } + + void pop_back() { + fill_count--; + if (fill_count || current == &first) + return; + auto [last, prev] = getLastBlocks(); + if (REVERSE_ORDER) { + assert(last == current); + current = current->next; + } else { + assert(prev->next == last); + current = prev; + current->next = nullptr; + } + if (last != &first) + ::free(last); + fill_count = BLOCK_SIZE; + } + + bool empty() const { return current == &first && !fill_count; } + iterator begin() { if (REVERSE_ORDER) return iterator(current, fill_count); diff --git a/libc/test/src/__support/CPP/blockstore_test.cpp b/libc/test/src/__support/CPP/blockstore_test.cpp --- a/libc/test/src/__support/CPP/blockstore_test.cpp +++ b/libc/test/src/__support/CPP/blockstore_test.cpp @@ -41,6 +41,27 @@ __llvm_libc::cpp::BlockStore::destroy( &block_store); } + + template void back_test() { + using __llvm_libc::cpp::BlockStore; + BlockStore block_store; + for (int i = 0; i < 20; i++) + block_store.push_back(i); + for (int i = 19; i >= 0; i--, block_store.pop_back()) + ASSERT_EQ(block_store.back(), i); + block_store.destroy(&block_store); + } + + template void empty_test() { + using __llvm_libc::cpp::BlockStore; + BlockStore block_store; + + ASSERT_TRUE(block_store.empty()); + block_store.push_back(1); + for (int i = 0; i < 10; i++, block_store.push_back(1)) + ASSERT_FALSE(block_store.empty()); + block_store.destroy(&block_store); + } }; TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterate4) { @@ -66,3 +87,13 @@ TEST_F(LlvmLibcBlockStoreTest, PopulateAndIterateReverse10) { populate_and_iterate<4, 10, true>(); } + +TEST_F(LlvmLibcBlockStoreTest, Back) { + back_test(); + back_test(); +} + +TEST_F(LlvmLibcBlockStoreTest, Empty) { + empty_test(); + empty_test(); +}