Some simple toy header-only libraries for C++. All classes are header-only and only depend on C++ standard library.

This project is mainly for learning purposes, but it may also be useful in small-scale projects.

Requires at least C++11.

Simply copy them to your include folder and include them in your project. All header files doesn't rely on other headers in this repo.

• IntrusiveNodeList
• FixedMemPool
• RingBuffer
• BlockingQueue
• FlatSet
• FlatMap
• SkipList

A simple STL-like intrusive linked list header. Not thread-safe.

Intrusive linked list can be used like normal linked list, but the nodes are embedded in the objects. Users are responsible for managing the memory of the objects, and deallocate object's memory while it is still in the list will cause undefined behavior.

Intrusive linked list can save memory allocations and improve performance in some scenarios. Users can also put one node in multiple lists by defining multiple intrusive_node members in the object.

Interfaces of intrusive_list<T, NodeMember>:

• void push_front(Node* node): Push a node to the front of the list.
• void push_back(Node* node): Push a node to the back of the list.
• void pop_front(): Pop a node from the front of the list.
• void pop_back(): Pop a node from the back of the list.
• T* front()/T* back(): Get the front/back node.
• void insert(iterator pos, T* item): Insert an item before the position.
• iterator erase(iterator pos): Erase the item at the position, return the next item.
• iterator begin()/end(): Get the begin/end iterator.
• bool empty(): Check if the list is empty.
• size_t size(): Get the size of the list.
• void clear(): Clear the list.
• void swap(intrusive_list&): Swap two lists.

Usage example:

#include <iostream>
#include "include/IntrusiveNodeList.hpp"
using namespace toylib;
struct TestNode {
    int x_;
    intrusive_node node_;
    TestNode(int x = 0) : x_(x) {}
};

int main() {
    intrusive_list<TestNode, &TestNode::node_> list;
    
    TestNode n1; n1.x_ = 1;
    list.push_back(&n1);
    TestNode n2; n2.x_ = 2;
    list.push_back(&n2);

    std::cout << "front = " << list.front()->x_ << ", back = " << list.back()->x_ << std::endl;
    return 0;
}

Header file of a simple memory pool. It supports fixed-size memory blocks and thread-safe allocation and deallocation. Contiguous memory chunks are allocated to improve cache performance and reduce frequent allocation overhead.

Interfaces of fixed_mem_pool<item_size, chunk_size>:

• void alloc_new_chunk(): Manually allocate a new chunk of memory.
• char* alloc(bool alloc_when_exhausted = true): Allocate a memory block. alloc_when_exhausted specifies whether to allocate a new chunk when there is no free block. If set to false, it will return nullptr when exhausted.
• template <typename T> T* alloc_as(): Allocate a memory block and cast it to T*.
• void free(void* ptr): Return a memory block to the pool.

Usage example:

#include <iostream>
#include "include/FixedMemPool.hpp"
using namespace toylib;
int main() {
    fixed_mem_pool<8, 32> pool(1);

    auto obj = pool.alloc_as<uint64_t>();
    (*obj) = 0x1234;

    std::cout << std::hex << *obj << std::endl;
    pool.free(obj);
    return 0;
}

A simple lock-free ring buffer header. Has SPSC and MPMC variants. Thread-safe.

Interfaces of ring_buffer_spsc<T>:

• bool pop(T& out): Pop an item from buffer, return true and set out if successful, return false if buffer is empty.
• template <typename U> bool push(U&& item): Push an item to buffer, return true if successful, return false if buffer is full.
• template <typename... Args> bool emplace(Args&&... args): Emplace an item in buffer, return true if successful, return false if buffer is full.
• bool empty(): Check if buffer is empty.
• bool full(): Check if buffer is full.
• size_t size(): Get number of items in buffer.

Usage example:

#include <iostream>
#include "include/RingBuffer.hpp"
using namespace toylib;
int main() {
    ring_buffer_spsc<int> rb(4);
    rb.push(1);
    rb.push(2);
    rb.push(3);
    int x;
    while (rb.pop(x)) {
        std::cout << x << std::endl;
    }
    return 0;
}

A thread-safe task queue with blocking command support. Though it's not as fast as lock-free queues as it used mutex to protect queue, it's more flexible and easier to use.

Interfaces of blocking_queue<T>:

• template <typename U> void push(U&& item): Push an item to the queue.
• template <typename... Args> void emplace(Args&&... args): Emplace an item in the queue.
• T pop(): Pop an item from the queue, block if the queue is empty. May throw if queue is shutdown.
• bool pop(T& out): Pop an item from the queue, return true and set out if successful, return false if the queue is shutdown.
• bool try_pop(T& out): Try to pop an item from the queue, return true and set out if successful, return false if the queue is empty.
• template <typename It> size_t bulk_try_pop(size_t max_attempt, It inserter): Try to pop up to max_attempt items from the queue, insert them using the inserter iterator. Return number of items popped.
• template <typename It> void bulk_push(It begin, It end): Push items in the range [begin, end) to the queue.
• void shutdown(): Shutdown the queue, blocking functions will either throw an runtime_error or return false.

Usage example:

#include <iostream>
#include <thread>
#include "include/BlockingQueue.hpp"
using namespace toylib;
int main() {
    blocking_queue<int> bq;
    std::thread producer([&bq]() {
        for (int i = 0; i < 10; ++i) {
            bq.push(i);
            std::this_thread::sleep_for(std::chrono::milliseconds(100));
        }
        bq.shutdown();
    });
    std::thread consumer([&bq]() {
        try {
            while (true) {
                int x = bq.pop();
                std::cout << x << std::endl;
            }
        } catch (const std::runtime_error&) {
            std::cout << "queue shutdown" << std::endl;
        }
    });
    producer.join();
    consumer.join();
    return 0;
}

Flat set container, like std::set but using sorted array as backend. Elements are sorted in ascending order by default. This is suitable for scenarios where insertion and deletion are rare but lookup and iteration are frequent.

Interfaces of flat_set<Key, Compare>:

• size_t count(const Key& key): Count the number of elements with the given key (0 or 1 since it's a set).
• std::pair<iterator, bool> insert(const Key& key): Insert an element, return a pair of iterator to the element and a bool indicating whether the insertion took place.
• iterator insert(const_iterator hint, const Key& val): Insert an element with a hint, return an iterator to the inserted or existing element.
• template <typename InputIt> void insert(InputIt first, InputIt last): Insert a range of elements.
• size_t erase(const Key& key): Erase elements with the given key, return the number of elements erased (0 or 1).
• iterator erase(iterator pos): Erase the element at the position, return the next iterator after the erased one.
• iterator erase(iterator first, iterator last): Erase elements in the range [first, last), return the next iterator after the last erased one.
• iterator find(const Key& key): Find an element, return the element's iterator or end() if not found.
• iterator begin()/end(): Get the begin/end iterator.
• bool empty(): Check if the set is empty.
• size_t size(): Get the size of the set.
• void clear(): Clear the set.
• void reserve(size_t n): Reserve space for n elements.

Usage example:

#include <iostream>
#include "FlatSet.hpp"
using namespace toylib;
int main() {
    flat_set<int> fs;
    fs.insert(1);
    std::cout << fs.count(1) << std::endl;
    fs.erase(1);
    std::cout << fs.count(1) << std::endl;
    return 0;
}

Like std::map but using sorted array as backend. Keys are sorted in ascending order by default. Implementation is similar to flat_set.

Interfaces of flat_map<Key, Value, Compare>:

Examples:

#include "../include/FlatMap.hpp"
#include "../include/ToyTest.hpp"
#include <iostream>
using namespace toylib;

int main() {
    flat_map<int, std::string> fm;
    fm[0] = "Hello toylib";
    fm[1] = "Simple library";
    std::cout << fm.at(0) << std::endl;
    std::cout << fm[1] << std::endl;
    
    fm.erase(0);
    std::cout << fm.count(0);
    return 0;
}

Skiplist is a probablistic data structure that allows fast lookup, insertion and deletion operations. Lookup/Insert/Delete an element's complexity is O(log n) on average.

Its core implementation is a ordered multi-level linked list. Every node in the list has a randomized level and multiple forward pointers. The link on the most bottom level contains all elements, and link on higher level skips some elements to allow faster traversal.

Interfaces of skip_list:

Examples:

// TO BE COMPLETED

Each header has its own test file(some of them need to be implemented though). You can compile them and run tests for each header.

To execute tests:

# example
cd test
g++ ./TestIntrusiveList.cpp -o TestIntrusiveList -std=c++11 -g && ./TestIntrusiveList

MIT License