Products > Programming
C++ How about this std::map based datastructure?
Zeyneb:
Hi there,
The little example program shown here compiles and runs fine in GCC with C++14 language support enabled.
The objective of this program is to simulate the behavior of microcontroller memory. Instead of declaring a giant array for the entire address range of the microcontroller memory. I'd like to declare just what is needed. So the idea is this datastructure:
--- Code: ---struct addr_range
{
uint8_t addr;
uint8_t size;
};
typedef std::vector< uint8_t > vector_t;
typedef std::map< addr_range, vector_t, std::less<> > map_t;
--- End code ---
with an initialization like this:
--- Code: --- map_t mem =
{
{ {0xC0, 3}, { 1, 2, 3 } },
{ {0xD0, 8}, { 7, 6, 5, 4, 3, 2, 1, 0 } },
{ {0xB0, 4}, { 0xA, 0xB, 0xC, 0xD } },
{ {0x66, 2}, { 0xC, 0xD } },
{ {0x6D, 2}, { 0xF, 0xE } },
{ {0x70, 2}, { 0x3, 0x4 } }
};
--- End code ---
For now addresses and data values are just one byte. addr is the start address, size is the size to which data values are specified and the vector is just the data there. Obviously size should always be equal to the vector size.
With proper housekeeping I'll make sure that no address range will be overlapping another one. Also when a write occurs that will make an address range consecutive to another one I will assign the vector to the end of the vector in the lowest address and remove the vector in the higher address as well as the map entry. So for example a write to address 0x6F with the value 0x2 will have the memory look like:
--- Code: --- map_t mem =
{
{ {0xC0, 3}, { 1, 2, 3 } },
{ {0xD0, 8}, { 7, 6, 5, 4, 3, 2, 1, 0 } },
{ {0xB0, 4}, { 0xA, 0xB, 0xC, 0xD } },
{ {0x66, 2}, { 0xC, 0xD } },
{ {0x6D, 5}, { 0xF, 0xE, 0x2, 0x3, 0x4 } }
};
--- End code ---
Now for the C++ code. As you can see I have a bunch of operator< overloads. The last two can compare a single uint8_t to an address range. And these are used in the map::find function call. Notice that for map::find I only have an uint8_t argument. For insertion the full keys are being compared and that is done in the first operator< overload.
I not quite sure if it is ok to have different compare function objects depending on which member function of map is called. Do you know if that is fine? Comments and caveats on this code? How would you program something like this?
--- Code: ---#include <cstddef>
#include <cstdio>
#include <cstdint>
#include <vector>
#include <map>
struct addr_range
{
uint8_t addr;
uint8_t size;
};
typedef std::vector< uint8_t > vector_t;
typedef std::map< addr_range, vector_t, std::less<> > map_t;
bool operator<( const addr_range& a, const addr_range& b ){
//printf( "try %2.2X < %2.2X: %u\n", a.addr, b.addr, a.addr < b.addr );
return a.addr < b.addr;
}
bool operator<( const addr_range& a, const uint8_t& b )
{
bool result = (a.addr + a.size - 1) < b;
//printf( "1 try %2.2X+%2.2X=%2.2X < %2.2X: %u\n",
// a.addr, a.size - 1, (a.addr + a.size - 1), b, result );
return result;
}
bool operator<( const uint8_t& a, const addr_range& b )
{
bool result = a < b.addr;
//printf( "2 try %2.2X < %2.2X: %u\n", a, b.addr, result );
return result;
}
int main()
{
map_t mem =
{
{ {0xC0, 3}, { 1, 2, 3 } },
{ {0xD0, 8}, { 7, 6, 5, 4, 3, 2, 1, 0 } },
{ {0xB0, 4}, { 0xA, 0xB, 0xC, 0xD } },
{ {0x66, 2}, { 0xC, 0xD } },
{ {0x6D, 2}, { 0xF, 0xE } },
{ {0x70, 2}, { 0x3, 0x4 } }
};
mem.insert( {{0xCC, 1}, {8}} );
uint8_t i = 0;
next_lookup:
auto search = mem.find( i );
if ( search != mem.end() )
{
uint8_t pos = i - search->first.addr;
printf( "%2.2X: %2.2X\n", i, search->second[pos] );
}
if ( i == 255 ) { goto quit_loop; }
i++;
goto next_lookup;
quit_loop:
getchar();
return 0;
}
--- End code ---
Regards, Zeyneb
TheCalligrapher:
--- Quote from: Zeyneb on November 21, 2021, 09:46:19 pm ---As you can see I have a bunch of operator< overloads. The last two can compare a single uint8_t to an address range. And these are used in the map::find function call. Notice that for map::find I only have an uint8_t argument. For insertion the full keys are being compared and that is done in the first operator< overload.
I not quite sure if it is ok to have different compare function objects depending on which member function of map is called. Do you know if that is fine?
--- End quote ---
It is fine since C++14, provided your map's primary comparator is transparent, i.e. it contains a type-member `is_transparent`. You used `std::less` as the primary comparator. This is a transparent comparator, which enables search by a sub-key. Of course, all comparators must comply to the same ordering. In your case, if the ranges do not overlap, this requirement appears to be met.
It is not clear though, why you insist on passing `uint8_t` values by reference.
SiliconWizard:
Another thought is that it can be implemented in a much simpler way. But hey, to each their own. And to each their concept of simple.
And that being said, even so, I don't see much point. "Instead of declaring a giant array for the entire address range of the microcontroller memory": as much as I like avoiding software bloat, your typical MCU will have insignificant memory size compared to even the smallest desktop computer available. Frankly no need to care here. Whatsoever.
And if you're implementing "sparse" arrays not for emulating memory per se, but for emulating the whole address space, then why not, but you're probably not implementing address decoding the "right" way. But always interesting how people's minds can work in such different ways.
Zeyneb:
--- Quote from: SiliconWizard on November 22, 2021, 05:02:25 pm ---Another thought is that it can be implemented in a much simpler way.
--- End quote ---
Alright, so what is your idea of a much simpler way? Please be specific.
--- Quote from: SiliconWizard on November 22, 2021, 05:02:25 pm ---but you're probably not implementing address decoding the "right" way.
--- End quote ---
You mean generating a chip select signal? If so, at this time I don't need this level of simulation. It is more about the CPU perspective of reading program memory and doing RAM reads and writes.
magic:
--- Quote from: Zeyneb on November 21, 2021, 09:46:19 pm ---With proper housekeeping I'll make sure that no address range will be overlapping another one.
--- End quote ---
At this point you should declare your own class with that map of vectors hidden inside as a private member and a simple read/write API. Saves sanity when you need to access the data structure in multiple places.
--- Quote from: Zeyneb on November 21, 2021, 09:46:19 pm ---Obviously size should always be equal to the vector size.
--- End quote ---
That's redundant (the vector already knows its size). If you make it so that every read access goes through a custom class method (see above), you won't need to have that information in the key, you will have the luxury to use ordinary integer keys and map::find with the default integer comparison and then verify if the vector is long enough as a second step.
Navigation
[0] Message Index
[#] Next page
Go to full version