Here are two or three things that may come as a surprise for the beginning [embedded] C++ users:
1. The compiler is generating default constructors if not provided explicitly by the programmer.
This may not be what you want, because the default constructors created by the compiler may allocate the objects dynamically from the heap. The default constructor will be called if a programmer accidentally declares the object but doesn't specifically provide the constructor to be used. Been there, done that.
In order to prevent this, declare the default constructor for each and every class as private. This will effectively hide the default constructor, and prevent accidental invocation of the default constructor by creating a compile-time error.
2. The objects declared at global scope level, file static level, or as a static function member will be constructed before the main() is called.
This may not be what you want, and may cause confusion because the objects may be constructed in an order you did not expect.
This can be handled quite easily by creating an init()-function for each module, and calling the modules' init()-functions from the main() in the order you want. Make these modules' init()-functions to allocate and construct the objects as required, and you are in control again.
3. Declare all destructors as virtual, unless you really want to do otherwise.
I have to respectfully disagree with some of these points. Here is why:
1. While the language standards stipulates that conceptually default constructors is called for every new object created, the C++ language also mandates that compilers should generate code with zero cost abstraction. What this means, default constructors will have no run-time cost if they don't need to do work (see code examples below). Furthermore, if you delete default constructors (as per your suggestion), then you disable your ability to create objects, which doesn't make sense at all.
// Default constructor will have no runtime cost as there is nothing to do.
struct Foo
{
int a, b, c;
};
// Compiler will generate a default constructor that initializes member variables.
struct Foo2
{
int a = 0, b = 0, c = 0;
};
// This deletes the default constructor, but then it also renders the class useless as you cant construct it any more.
struct Foo3
{
int a, b, c;
Foo3() = delete;
};
2. Be careful with static initialisation. The order of static initialisation is undefined across different implementation files (or translation units). See static order initialization fiasco (https://en.cppreference.com/w/cpp/language/siof). Also avoid using static global objects unless there is a real good reason to use one.
3. Adding virtual destructors to every object is superfluous for several reasons. First, you only need virtual destructor, if the class is participates in an inheritance hierarchy and engages in polymorphism. Second, if you add a custom destructor to your object, then you also need to implement the class constructor(s) and assignment operator(s) to conform with the rule of three/five/zero (https://en.cppreference.com/w/cpp/language/rule_of_three) convention, which again is superfluous unless you really need to manually track internal state.
I highly recommend to reading through the C++ Core Guidelines (https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines) for best practices. It's maintained by Bjarne Stroustrup and Herb Sutter. I always refer to it, to make sure I don't do anything silly in C++, because it's very easy to do.
Start with figuring out the requirements because there are many ways to skin the cat.
Speed?
Code size?
Structure size?
Dumb OO approach a'la Java or "C with classes": equip each key object with a pointer to a list of pointers to functions implementing overloaded operators for that key type. Automatic in OO languages, or you could code this in vanilla C if you feel masochistic.
A smarter approach to the above: recognize that it's the same pointer for each key and store it only once in the root of the tree. You can code this in C with little effort: pass the key operators pointer as an argument to internal tree traversal functions, API entry points read the pointer from the root.
BONUS:
Type safety in vanilla C. Don't store the pointer in the root. Take it as an argument to tree_insert(), tree_lookup(), etc and hide those functions from users. For API entry points, create wrappers:
struct {some_function_pointer; other_function_pointer;} int_key_ops;
struct int_tree {struct tree tree;};
xxx int_tree_insert(struct int_tree *it, yyy) {return tree_insert(int_key_ops, it.tree, yyy);}
Speed/size tradeoff: separate version of code for each key type, possibly inlined comparison operators. Easily and cleanly solved with C++ templates, maybe doable in C if you compile the same .c file to different .o files with different #defines set by command line.
C++ doesn't make compile time computation as easy to express as runtime computation.
I would argue that with the advent of constexpr, it actually does, at least since C++14's improvements.
That does help a lot, yes.
I'm not sure it's fast. I guess I could do an experiment...
OK, given this code:
#include <stdio.h>
constexpr long fib(long n) {
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
int main(){
printf("%ld\n", fib(36));
return 0;
}
... gcc -O takes 1.58 seconds to compile it, then the compiled program takes 0.01 seconds to run (basically, helloworld).
If I change the 36 to 37 then gcc takes 1.99 seconds to compile it, then the compiled program takes 0.130 seconds to run.
Basically, with 37 gcc hits a time limit and gives up on evaluating it at compile time.
If I do it for 36 but disable the compile-time evaluation then it takes 0.100 seconds to run.
So compile-time evaluation takes around 15 times as long as running compiled code. And there is a definite and fairly low upper limit to how much computation is permitted.
Clang refuses to compile-time evaluate this function for any argument except 0 or 1, no matter the optimisation level. Clang will compile-time evaluate a singly-recursive function such as factorial.
So, I did some crude code experimentation with a binary search tree, with the aim of being MISRA C++ compliant (except that I don't have the actual spec, so I'm guessing) for use in an embedded (freestanding C/C++) environment while maximising maintainability, readability, and verifiability, without compromising performance too much; all just to see what I would end up with.
Here's how I went about it.
At the very core, I defined a key comparison function that we define for each key type we need. For example,
enum class compares_as { below, equal, above };
template <class T>
compares_as key_compare(T key1, T key2)
{
return (key1 < key2) ? compares_as::below :
(key1 > key2) ? compares_as::above :
compares_as::equal ;
}
template <>
compares_as key_compare<const char *>(const char *key1, const char *key2)
{
const int rc = strcmp((key1) ? key1 : "", (key2) ? key2 : "");
return (rc < 0) ? compares_as::below :
(rc > 0) ? compares_as::above :
compares_as::equal ;
}
The above implements key_compare() for all numeric types, and for strings using strcmp(). For a 2D point (or complex number) type, something like
template <>
compares_as key_compare<vec2>(vec2 key1, vec2 key2)
{
return (key1.y < key2.y) ? compares_as::below :
(key1.y > key2.y) ? compares_as::above :
(key1.x < key2.x) ? compares_as::below :
(key1.x > key2.x) ? compares_as::above :
compares_as::equal ;
}
should work, sorting points in ascending y coordinates, and points with the same y coordinate in ascending x coordinates.
The binary search tree node template class heavily relies on the compares_as enumeration logic above. Omitting sensible destructors, I initially came up with
template <class K, class V>
class node {
private:
K key;
V val;
node<K,V> *lt;
node<K,V> *gt;
public:
node(K key, V val): key(key), val(val), lt(nullptr), gt(nullptr) { }
K get_key(void) { return key; }
V get_val(void) { return val; }
compares_as towards_key(K otherkey) { return key_compare(otherkey, key); }
node<K,V> *get_child(compares_as direction) {
return (direction == compares_as::below) ? lt :
(direction == compares_as::above) ? gt :
nullptr;
}
bool add_child(compares_as cmp, K newkey, V newval) {
if (cmp == compares_as::below) {
if (!lt) {
lt = new node<K,V>(newkey, newval);
return true;
}
} else
if (cmp == compares_as::above) {
if (!gt) {
gt = new node<K,V>(newkey, newval);
return true;
}
}
return false;
}
int in_order(node<K,V> *parent, compares_as descent, int (*callback)(node<K,V> *, node<K,V> *, compares_as)) {
int rc;
if (lt) {
rc = lt->in_order(this, compares_as::below, callback);
if (rc) {
return rc;
}
}
rc = callback(this, parent, descent);
if (rc) {
return rc;
}
if (gt) {
rc = gt->in_order(this, compares_as::above, callback);
if (rc) {
return rc;
}
}
return 0;
}
};
The node::in_order() member function is a recursive function that traverses the tree, calling the callback function for each visited node in order. I used it to output the trees generated in Graphviz DOT format, for simple visual verification. (EDIT: It is not supposed to be included in actual used code, and is not MISRA compliant; I included it only because it lets us verify test trees very easily, with just one helper call back function per tree/node type.)
The "trick" is the node::towards_key() member function, which compares the specified key to the key in the current node. It simply calls the key_compare() function we defined earlier. This way, to add new key types, one only needs to define a template specialization for key_compare().
The actual tree template class:
template <class K, class V>
class tree {
private:
node<K,V> *root;
public:
tree(): root(nullptr) { }
bool add(K newkey, V newval) {
if (root) {
node<K,V> *next = root;
node<K,V> *curr;
compares_as direction;
do {
curr = next;
direction = curr->towards_key(newkey);
next = curr->get_child(direction);
} while (next);
return curr->add_child(direction, newkey, newval);
} else {
root = new node<K,V>(newkey, newval);
return true;
}
}
bool find(K thekey, V* oldval) {
if (root) {
node<K,V> *curr = root;
compares_as direction;
do {
direction = curr->towards_key(thekey);
if (direction == compares_as::equal) {
if (oldval) {
*oldval = curr->get_val();
}
return true;
}
curr = curr->get_child(direction);
} while (curr);
}
return false;
}
V get(K thekey, V notfound) {
if (root) {
node<K,V> *curr = root;
compares_as direction;
do {
direction = curr->towards_key(thekey);
if (direction == compares_as::equal) {
return curr->get_val();
}
curr = curr->get_child(direction);
} while (curr);
}
return notfound;
}
int in_order(int (*callback)(node<K,V> *, node<K,V> *, compares_as)) {
if (root) {
return root->in_order(nullptr, compares_as::equal, callback);
} else {
return 0;
}
}
};
To instantiate a tree with integer keys and integer values, I used
tree<int, int> itree;
itree.add(4, 1);
itree.add(2, 2);
itree.add(6, 2);
itree.add(1, 3);
itree.add(3, 3);
itree.add(5, 3);
itree.add(7, 3);
and another with C string keys and values with
tree<const char *, const char *> stree;
stree.add("one", "1");
stree.add("two", "2");
stree.add("three", "3");
stree.add("four", "4");
stree.add("five", "5");
stree.add("six", "6");
It seems to work.
Because this was the first go at it, I omitted all comments, and the code is quite crude. Remember, first sketch. Here are my observations on this exercise:- Adding new key types using this scheme is very easy, as it only requires a new template specialization for the key_compare() function.
The only requirement is that the key set is totally ordered with respect to key_compare(), without conflicts. - Names matter. compares_as seemed a good name while I wrote the key_compare() function, but it is a poor name for the use cases. order would be a more descriptive name.
- The root node is created in tree::add(), but all subsequent ones in node::add_child(). This needs documenting, and probably a comment in both places for maintenance purposes.
- I completely omitted destructors and deleteing the nodes created with new.
- I avoided virtual methods, to keep any overhead (when compiled with optimizations enabled) to a minimum.
I do not claim this code is efficient, though. - Since the tree class only cares about the keys in their ordinal sense, an unit test with say integer keys suffices for the tree template class verification.
All key types should be carefully verified, so that each key type forms a totally ordered set. But since that is just one function, it should be easy to do. - I do think the code is a lot more compact, readable, and maintainable than the C (or GNU C) version I might write, assuming – as we are in this thread – that multiple key types are actually needed.
At this point, I'm very interested in what others think of the approach (given the aims stated at the beginning of this post), and whether DiTBho believes this kind of approach would have helped with their B*tree implementation. The code itself is just crude first sketch; and I apologise for the lack of comments.
So, I did some crude code experimentation with a binary search tree
[...]
thank you a lot! I will for sure study this draft :D
void btree_methods_string_init
(
p_btree_t p_btree
)
{
p_btree->context.coin.method.cmp.isle = cmp_isle; /* A <= B */
p_btree->context.coin.method.cmp.islt = cmp_islt; /* A < B */
p_btree->context.coin.method.cmp.isge = cmp_isge; /* A >= B */
p_btree->context.coin.method.cmp.isgt = cmp_isgt; /* A > B */
p_btree->context.coin.method.cmp.iseq = cmp_iseq; /* A == B */
p_btree->context.coin.method.let.show = let_show;
p_btree->context.coin.method.let.copy = let_copy; /* A = B */
}
That's what I need to define for each key-type.
To compare strings, I use lexicographic ordering. To compare rect(x,y) and cplx numbers in Euler form, I only consider the module, unless the two modules are equal, in that case, I also consider the angle.
in rect(x,y): { x,y } are a pair of uint32
in cplx(r,theta): { r , theta} are a pair of fixedpoint
/*
* finds and returns the record to which a coin refers
*/
btree_ans_t btree_coin_find
(
p_btree_t p_btree,
btree_coin_t coin
)
{
p_btree_node_t p_root;
p_btree_node_t p_node;
btree_coin_t penny;
btree_item_method2_t cmp_iseq;
btree_item_method2_t let_copy;
...
p_root = p_btree->context.p_root;
...
cmp_iseq = p_btree->context.coin.method.cmp.iseq;
let_copy = p_btree->context.coin.method.let.copy;
...
while (...)
{
let_copy(p_btree, penny, p_node->as.leaf.coin[i0]);
is_found = cmp_iseq(p_btree, penny, coin);
if (is_found)
{
...
That's how the code looks like with function-methods to copy and compare.
LG__ ________________ c:0002 d:01 lib_btree_z_v1.btree_coins_show
____ ________________ c:0001 d:01 lib_btree_z_v1.btree_height_get
LG__ _123456_________ c:0616 d:01 lib_btree_z_v1.btree_coin_insert
LG__ _1234___________ c:7708 d:01 lib_btree_z_v1.btree_coin_find
____ ________________ c:0139 d:01 lib_btree_z_v1.record_make
L___ ________________ c:0005 d:01 lib_btree_z_v1.btree_start_new
L___ ________________ c:0081 d:01 lib_btree_z_v1.node_make_leaf
_G__ ________________ c:0106 d:01 lib_btree_z_v1.node_make
LG__ __2_____________ c:7837 d:01 lib_btree_z_v1.node_leaf_get
L___ _12_____________ c:0059 d:02 lib_btree_z_v1.node_insert_leaf
LG__ ________________ c:0077 d:02 lib_btree_z_v1.node_insert_leaf_after_splitting
____ _12_____________ c:0183 d:01 lib_btree_z_v1.node_cutpoint_get
LG__ _123____________ c:0092 d:03 lib_btree_z_v1.node_insert_parent
LG__ ________________ c:0011 d:02 lib_btree_z_v1.node_insert_new_root
_G__ ________________ c:0081 d:01 lib_btree_z_v1.node_iLP_get
LG__ ________________ c:0067 d:02 lib_btree_z_v1.node_insert
_G__ ________________ c:0015 d:01 lib_btree_z_v1.node_insert_after_splitting
_G__ ________________ c:0005 d:02 lib_btree_z_v1.destroy_tree
LG__ _12_____________ c:0046 d:04 lib_btree_z_v1.nodes_destroy
_G__ ________________ c:0053 d:02 lib_btree_z_v1.btree_coin_delete
LG__ _1234___________ c:0099 d:04 lib_btree_z_v1.node_entry_delete
LG__ ________________ c:0099 d:02 lib_btree_z_v1.node_entry_remove
LG__ ________________ c:0051 d:04 lib_btree_z_v1.node_iNG_get
LG__ ________________ c:0047 d:03 lib_btree_z_v1.nodes_coalesce
_G__ ________________ c:0007 d:02 lib_btree_z_v1.node_root_adjust
LG__ ________________ c:0005 d:02 lib_btree_z_v1.nodes_redistribute
This is a shot with minimal coverage, considering a minimum test with
- start a new tree
- fill 20 keys
- random delete and check
- check global consistency
- check local consistency
- delete everything (tree destroy + check for memory leakage)
- fill the tree again
- fill it again with special keys to force nodes_redistribute
- selective delete and check for consistency (forces nodes_redistribute)
- fill it again with special keys to force nodes_coalesce
The most of the functions have to work with both "glue" (internal node) and "leaf" nodes.
I also need to check the maximal stack deep because the code is not "recursion free".
The in_order() function is definitely not MISRA compliant, and not intended to be; I only included it because it helps testing the generated tree structures quickly and visually. (I use Graphviz DOT language output, with the third parameter to the callback, compares_as, providing the flag for the directed graph tail label (< or >).) I edited my post to make that clearer; one should not need it in final code.
I vaguely recall that there is a way to traverse trees without recursion or stack, with just fixed amount of storage (some sort of direction cookie or something, with checking which side one came from when going towards the root), but it requires a parent pointer in each node. If tree traversal is needed, then I'd modify the node structure accordingly, and implement that.
A quick glance showed that it uses new to allocate nodes, is that really MISRA C++ compliant?
I don't know, I don't have MISRA C++ either.
If it matters, AUTOSAR AP Release 18-10 for C++14 (https://www.autosar.org/fileadmin/user_upload/standards/adaptive/18-10/AUTOSAR_RS_CPP14Guidelines.pdf), which targets C++14 but builds upon MISRA C++ 2008, forbids malloc()/free() but allows new/delete in section 6.1.
If the tree nodes are of fixed size, I could change the code to use a template parameter for statically allocating the tree nodes, with a secondary tree as a singly-linked list holding the unused nodes for quick reuse. Populating the next tree node would move from node::add_child() to tree::add(), but the populated node would only be removed from the free list if the node::add_child() call succeeded. So, I don't think it matters that much here, both dynamic and static allocation patterns are easily achieved with very minimal changes. It is why I didn't include any delete operators or destructors.
p_btree->context.coin.method.cmp.isle = cmp_isle; /* A <= B */
p_btree->context.coin.method.cmp.islt = cmp_islt; /* A < B */
p_btree->context.coin.method.cmp.isge = cmp_isge; /* A >= B */
p_btree->context.coin.method.cmp.isgt = cmp_isgt; /* A > B */
p_btree->context.coin.method.cmp.iseq = cmp_iseq; /* A == B */
Why separate comparison functions, instead of just one that returns less/below, equal, greater/above?
If cmp(x,y) returns 0 if equal, -1 if less/below, or 1 if greater/above, then
logic │ expression
────────┼────────────────
x == y │ cmp(x, y) == 0
x != y │ cmp(x, y) != 0
x <= y │ cmp(x, y) <= 0
x >= y │ cmp(x, y) >= 0
x < y │ cmp(x, y) < 0
x > y | cmp(x, y) > 0
Is there something in MISRA that forbids this?
You see, it is of crucial importance that the key set is totally ordered, meaning that if x < y and y <= z, then z > x or the data structure will fail because the keys are not properly ordered.
Another option is to use a bit mask, so that 0 denotes "not comparable" or "unknown order" (which the unit tests would try to look for, since it should not happen). Then, say
/* Bit 0: Equal, Bit 1: Less/Below, Bit 2: Greater/Above */
enum order_bits {
MASK_EQ = 1,
MASK_LT = 2,
MASK_LE = 3,
MASK_GT = 4,
MASK_GE = 5,
MASK_NE = 6,
};
in which case we'd have
logic │ expression
────────┼───────────────────────────
x == y │ (cmpmask(x, y) & MASK_EQ)
x != y │ (cmpmask(x, y) & MASK_NE)
x <= y │ (cmpmask(x, y) & MASK_LE)
x >= y │ (cmpmask(x, y) & MASK_GE)
x < y │ (cmpmask(x, y) & MASK_LT)
x > y | (cmpmask(x, y) & MASK_GT)
and the unit test would ensure that for all possible keys, cmpmask(x, y) returns a value between 1 and 6, inclusive.