Last time I implemented it in Java, this time I'm trying to get something more primitive (compared to the Java implementation) working in C++ (it should be straight-forward to port to C).
The use-case I had in mind when implementing this was how to distribute loggers or hierarchical configurations to every part of an application. In such code is is usually required to pass a Logger or a Configuration around to basically every function. However, with the approach described here, there is no need to pass stuff around like that, instead one uses stack-searching technique.
This little demo demonstrates the idea:
int func1() {
TaggedInt i1(1);
printf("i1 = %d\n", findClosestTaggedInt());
}
int func0() {
printf("i0 = %d\n", findClosestTaggedInt());
func1();
}
int main() {
TaggedInt i0(0);
func0();
}
When run, the following is printed:TaggedInt i1(1);
printf("i1 = %d\n", findClosestTaggedInt());
}
int func0() {
printf("i0 = %d\n", findClosestTaggedInt());
func1();
}
int main() {
TaggedInt i0(0);
func0();
}
i0 = 0
i1 = 1
Ok, what happens here? It's pretty simple. The class TaggedInt is a class that holds two values. A tag and an int. The function findClosestTaggedInt searches backwards through the stack until it finds the tag of a TaggedInt object and returns the corresponding int of that object.
In a real application the int would probably be replaced by something else, like a pointer to a LogConfig object or something similar. Further more, the findClosestTaggedInt would be replaced by findClosestTaggedLogConfig and probably not be used explicitly like in this demo, but rather implicitly in a constructor of some other object such as Logger. For instance:
void func() {
Logger logger; // findClosestTaggedLogConfig is called by the ctor.
logger.warning("Something is happening!");
}
int main() {
LogConfig config(std::cerr); // This is a tagged object.
func();
}
Now, there is a problem with this approach. Searching through the stack is an expensive operation, and not something you should do often. That implies that findClosetsTaggedXYZ should only be rarely called, or when the program is not in a time-critical phase. However, since findClosestTaggedXYZ is only used when distributing an object throughout the application (not when the object is used) this can usually be done once at application start-up and never again.
To sum up, here's a the rest of the code for running the demo above:
#include <string.h>
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
static const unsigned TAG_SIZE = 16;
static const char TAG[TAG_SIZE] = "my magic string";
// A tagged int is an magic tag followed by an int. The tag
// *must* be at zero offset relative to the 'this' pointer.
class TaggedInt {
char tag[TAG_SIZE + sizeof(void*)];
public:
int variable;
TaggedInt(int variable) : variable(variable) {
// Setup the tag.
memcpy(tag, TAG, TAG_SIZE);
TaggedInt* self = this;
memcpy(&tag[TAG_SIZE], &self, sizeof(self));
}
};
// Find which direction the stack grows.
int stackDirection() {
int first;
int second;
int diff = intptr_t(&second) - intptr_t(&first);
return diff > 0 ? 1 : -1;
}
// The maximum number of bytes to search backwards through
// the stack for the tagged int before giving up.
static const unsigned STACK_SIZE = 1024 * 1024;
// Search backwards through the stack for the first tag.
// Note: this might be possible to optimize by a large factor
// by knowing the alignment of stack allocated variables.
int findClosestTaggedInt() {
static const unsigned ALIGMENT = 1;
int direction = stackDirection();
char start;
for (char* ptr = &start; ptr != &start - STACK_SIZE;
ptr -= direction * ALIGMENT) {
if (0 == strcmp(TAG, ptr)) {
TaggedInt* tagged;
memcpy(&tagged, &ptr[TAG_SIZE], sizeof(tagged));
return tagged->variable;
}
}
assert(false);
}
With this code you should have a fairly good start for implementing something more useful, such as a distributor of Loggers or Configurations.
One last thing, I would be really interested in hearing from any anyone that figures out how to compute the ALIGMENT constant in findClosestTaggedInt to increase performance while still making sure no tag is missed.
