Updated on 2022-03-17
Get your data on, even on platforms without a reliable STL implementation using these simple but critical classes.
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.
Using it is simple:
#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:
#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 dataThis 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