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.
Home
Help
Search
Login
Register
