Click here to Skip to main content
15,561,125 members
Articles / Internet of Things / Arduino
Tip/Trick
Posted 17 Mar 2022

Stats

3.6K views
27 downloads
2 bookmarked

A Small Vector and Hash Table Implementation w/ No STL Dependencies

Rate me:
Please Sign up or sign in to vote.
4.50/5 (7 votes)
17 Mar 2022MIT
Get your data on, even on platforms without a reliable STL implementation using these simple but critical classes.
On some Arduino devices, and perhaps some embedded platforms, you may not have access to the full measure of The Standard Template Library. In those cases, it might not be feasible to rely on the STL for std::map - maybe even std::vector. Also these are very lightweight compared to The STL implementation, because aren't designed to handle every possible scenario - just the simple ones.

Introduction

I target the Arduino framework a lot, and there is no reliable cross-platform std::map implementation that can be relied on, mostly because The STL isn't fully implemented for many of these devices. Also The STL tends to have some hidden overhead due to the general purpose nature of it. It's designed to handle all scenarios, so it trades on complexity in order to do so.

To that end, I've created some simple alternatives to std::vector<> and std::map<>. The interfaces aren't exactly the same as The STL versions, but they are similar, minus many of the methods, including having no way to remove individual items.

Coding this Mess

Using it is simple:

C++
#include <stdio.h>
#include <htcw_data.hpp>
using namespace data;
int hash(const int& x) {
    return x;
}
int main(int argc, char** argv) {
    simple_vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    printf("v.begin()[0]=%d\r\n",v.begin()[0]);
    printf("v.begin()[1]=%d\r\n",v.begin()[1]);
    printf("v.begin()[2]=%d\r\n",v.begin()[2]);
    simple_fixed_map<int,int,2> test(hash);
    test.insert({1,3});
    test.insert({2,2});
    test.insert({3,1});
    printf("test.find(1)=%d\r\n",*test.find(1));
    printf("test.find(2)=%d\r\n",*test.find(2));
    printf("test.find(3)=%d\r\n",*test.find(3));
    if(test.find(4)==nullptr) {
        printf("test.find(4)=nullptr\r\n");
    }
    return 0;
}

Keep in mind that these classes do not allocate memory for your individual items, so if you are storing pointers (like C strings or arrays for example), those pointers must be kept valid outside of this class.

The entire implementation is here:

C++
#pragma once
#include <stdlib.h>
namespace data {
    // dynamic vector of scalar data
    template <typename T>
    class simple_vector final {
        void* (*m_allocator)(size_t);
        void* (*m_reallocator)(void*, size_t);
        void (*m_deallocator)(void*);
        size_t m_size;          // size in number of T values
        T* m_begin;
        size_t m_capacity;      // allocated size in T values
        bool resize(size_t new_size) {
            size_t capacity = new_size;
            if (capacity > this->m_capacity) {
                size_t newcap = capacity + (this->m_capacity >> 1u);
                void* data ;
                if(this->m_begin) {
                    data = m_reallocator(this->m_begin, newcap * sizeof(T));
                } else {
                    newcap=8;
                    const size_t newsz = newcap*sizeof(T);
                    data = m_allocator(newsz);
                }
                if (data) {
                    this->m_capacity = newcap;
                    this->m_begin = (T*)data;
                } else
                    return false; //error: not enough memory
            }
            this->m_size = new_size;
            return true;
        }

    public:
        simple_vector(void*(allocator)(size_t) = ::malloc,
                    void*(reallocator)(void*, size_t) = ::realloc,
                    void(deallocator)(void*) = ::free) : 
                        m_allocator(allocator),
                        m_reallocator(reallocator),
                        m_deallocator(deallocator) {
            m_begin = nullptr;
            m_size = 0;
            m_capacity = 0;
        }
        ~simple_vector() {
            m_size = 0;
            if (m_begin != nullptr) {
                m_deallocator(m_begin);
                m_begin = nullptr;
            }
        }
        inline size_t size() const { return m_size; }
        inline size_t capacity() const { return m_capacity; }
        inline const T* cbegin() const { return m_begin; }
        inline const T* cend() const { return m_begin + m_size; }
        inline T* begin() { return m_begin; }
        inline T* end() { return m_begin + m_size; }
        void clear() {
            if(m_begin) {
                m_size = 0;
                m_capacity = 0;
                m_deallocator(m_begin);
                m_begin = nullptr;
            }
        }
        bool push_back(const T& value) {
            if (!resize(m_size + 1)) {
                return false;
            }
            m_begin[m_size - 1] = value;
            return true;
        }
    };
    template<typename TKey, typename TValue> 
    struct simple_pair {
        TKey key;
        TValue value;
        simple_pair(TKey key,TValue value) : key(key), value(value) {

        }
        simple_pair(const simple_pair& rhs) {
            key = rhs.key;
            value = rhs.value;
        }
        simple_pair& operator=(const simple_pair& rhs) {
            key = rhs.key;
            value = rhs.value;
            return *this;
        }
        simple_pair(simple_pair&& rhs) {
            key = rhs.key;
            value = rhs.value;
        }
        simple_pair& operator=(simple_pair&& rhs) {
            key = rhs.key;
            value = rhs.value;
            return *this;
        }
    };
    template<typename TKey,typename TValue, size_t Size> 
    class simple_fixed_map final {
        static_assert(Size>0,"Size must be a positive integer");
        using bucket_type = simple_vector<simple_pair<TKey,TValue>>;
        bucket_type m_buckets[Size];
        int(*m_hash_function)(const TKey&);
        size_t m_size;
    public:
        simple_fixed_map(int(hash_function)(const TKey&),
                        void*(allocator)(size_t) = ::malloc,
                        void*(reallocator)(void*, size_t) = ::realloc,
                        void(deallocator)(void*) = ::free) : 
                            m_hash_function(hash_function),
                            m_size(0) {
            for(int i = 0;i<Size;++i) {
                m_buckets[i]=bucket_type(allocator,reallocator,deallocator);
            }
        }
        using key_type = TKey;
        using mapped_type = TValue;
        using value_type = simple_pair<const TKey,TValue>;
        inline size_t size() const { return m_size; }
        void clear() {
            m_size = 0;
            for(int i = 0;i<Size;++i) {
                m_buckets->clear();
            }
        }
        bool insert(const value_type& value) {
            int h = m_hash_function(value.key)%Size;
            bucket_type& bucket = m_buckets[h];
            if(bucket.size()) {
                auto it = bucket.cbegin();
                while(it!=bucket.cend()) {
                    if(it->key==value.key) {
                        return false;
                    }
                    ++it;
                }
            }
            
            if(bucket.push_back({value.key,value.value})) {
                ++m_size;
                return true;
            }
            return false;
        }
        const mapped_type* find(const key_type& key) const {
            int h = m_hash_function(key)%Size;
            const bucket_type& bucket = m_buckets[h];
            if(bucket.size()) {
                auto it = bucket.cbegin();
                while(it!=bucket.cend()) {
                    if(it->key==key) {
                        return &it->value;
                    }
                    ++it;
                }
            }
            return nullptr;
        }
        
    };
    
}  // namespace data

Including Using Platform IO

This library is available as a Platform IO library and can be installed by adding the following line to your platformio.ini:

lib_deps = 
    codewitch-honey-crisis/htcw_data@^1.0.2 

History

  • 17th March, 2022 - Initial submission

License

This article, along with any associated source code and files, is licensed under The MIT License


Written By
United States United States
Just a shiny lil monster. Casts spells in C++. Mostly harmless.

Comments and Discussions

 
GeneralMy vote of 5 Pin
Jan Heckman21-Mar-22 0:05
professionalJan Heckman21-Mar-22 0:05 
GeneralRe: My vote of 5 Pin
honey the codewitch21-Mar-22 1:33
mvahoney the codewitch21-Mar-22 1:33 
Questioncapacity and new_size? Pin
Paulo Zemek20-Mar-22 17:36
Paulo Zemek20-Mar-22 17:36 
AnswerRe: capacity and new_size? Pin
Jan Heckman21-Mar-22 0:03
professionalJan Heckman21-Mar-22 0:03 
GeneralRe: capacity and new_size? Pin
Paulo Zemek21-Mar-22 4:45
Paulo Zemek21-Mar-22 4:45 
In most cases a double delete would cause an exception independently if the variables are set to nullptr or not... so I am really not convinced that this is fixing any real issue.

GeneralRe: capacity and new_size? Pin
honey the codewitch21-Mar-22 5:46
mvahoney the codewitch21-Mar-22 5:46 
GeneralRe: capacity and new_size? Pin
Paulo Zemek21-Mar-22 5:48
Paulo Zemek21-Mar-22 5:48 
AnswerRe: capacity and new_size? Pin
honey the codewitch21-Mar-22 1:32
mvahoney the codewitch21-Mar-22 1:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.