Monday, September 25, 2006

Function Pointers in C/C++ and boost::bind

In a previous blog entry, I showed the Windows QueueUserAPC function, and how you could use it to get other threads to execute functions. Now this was kind of cool, but if the only functions we can use are free functions which have only a single 32 bit parameter, not so useful. I said I'd explain how to use boost::bind to solve this.

Now, I'm not going to explain how this interacts with QueueUserAPC just yet, because explaining boost functions and bind is well big enough for a blog entry of it's own. Here it is.

Intro - Function Pointers in C and C++

If you're not familiar with what a function pointer even is, well:

  • All your code that you write gets turned into a big bunch of binary stuff by your compiler.
  • In order for this code to run, it has to load this binary stuff into memory
  • Once the binary stuff is in memory, the CPU can be told to execute arbitrary bits of it. This is what C/C++ does behind the scenes when you normally call a function
  • A function pointer in C/C++ is a pointer to a bit of that memory where a function lives.
  • When more code is loaded, or passed around from one part to another, you can get pointers to this new code as well as the static stuff which you wrote upfront.
  • This lets you do things like call functions which didn't exist when you compiled the program, (ie: DLL's), or tell some code to execute a runtime-specified piece of other code on some event (ie: callback functions)

If you're not familiar with function pointers in C, here's an example:

void Print( int a ) {
    std::cout << "Free Function, a = " << a << std::endl; 

void main() {
     void( *x )(int) = &a_function;
      // we now have an object x, which is a pointer to function of type void(*)(int).
     // it happens to be pointing at our Print function
     x( 5 ); //call it 

This syntax is fine and dandy for C functions, which don't have classes or anything, so the types are all pretty simple, however in C++, we have classes, which have member functions (or methods if you prefer to call them that). Imagine the following class:

class FooClass {
    void Print( int a ) {
         std::cout << "A FooClass, param = "<< a <<" this = " << this << std::endl;

Now, if we want to get a pointer to the Print function, we have to write some extra stuff so the compiler can tell that it's a member function of FooClass, and we also have to pass the instance, so the compiler knows which FooClass the Print function should belong to. We might have 50 of FooClass in an array and it's got to be able to figure out which one is the right one.

FooClass* myFoo = new FooClass(); //create an instance of our FooClass
void( FooClass::* x )(int) = &FooClass::Print 
// we now have an object called x, which is a pointer to function of type void(FooClass::*)(int)
// it happens to be pointing at our FooClass::Print function, but it doesn't know which FooClass instance yet

(myFoo->*x)( 5 );
//call the function, telling it that the FooClass represented by myFoo is the one to use 
//, as if we'd called myFoo->Print( 5 );

As you may well have noticed, using pointers to class members sucks. I've done a fair bit of this kind of thing and I had to go and look up the documentation to remember quite how it was supposed to work. C++ cops a lot of flak for this kind of stuff, and deservedly so in my humble opinion.

We could always make it nicer by using some typedef's, but it's still ugly, still probably wouldn't make sense to most novice programmers, and we still have the problem that the function pointer doesn't stand alone - we also need to pass the object instance around.

If they didn't know any better, but wanted to use this kind of thing, most programmers would probably end up creating some kind of struct which contained the instance, the function pointer, and some other arbitrary data, and passing that around the place. That at least makes it possible, but it still sucks.


If you take the following 3 things:

  • Function pointer type declarations suck
  • You can do lots of amazing stuff with templates in C++
  • The guys who write the boost libraries are really really smart

Then, for free functions, we get this:
void Print( int a ) {
    std::cout << "A Free function, param = "<< a << std::endl;

void main() {
    void( *oldFunc )(int) = &Print; //C style function pointer
    oldFunc( 5 );

    boost::function<void(int)> newFunc = &Print; //boost function
    newFunc( 5 ); 

It's just my opinion of course, but I think the C style function pointer with the variable name in between the void and the (int) is confusing, whereas the boost function just behaves how you'd expect it to. Code that clearly states what it does, and then simply does it, is the best code.

Even though this is a trivial example and the boost one isn't actually much nicer, I'd still use it just because it's easier to read. However, it still hasn't solved the problem of passing around the instance along with the function for C++ members...


What boost::bind does, is "bind" parameters into a boost::function object (how this actually happens is a bit beyond the scope of this article so I won't go into it )... like an object instance (or a pointer to one). Observe and rejoice

class FooClass {
     void Print( int a ) {
         std::cout << "A FooClass, param = "<< a <<" this = " << this << std::endl;

void main() {
    FooClass *myFoo = new FooClass();
    void( FooClass::* oldFunc )(int) = &FooClass::Print; //C style function pointer
    (myFoo->*oldFunc)( 5 );

    boost::function<void(int)> newFunc = boost::bind( &FooClass::Print, myFoo, _1 ); //boost function      
    newFunc( 5 );

What is effectively happening, is that myFoo is being "bound" into the newFunc object. Think of it as creating a private variable inside newFunc and sticking myFoo in it. When newFunc is invoked, it will use myFoo as a parameter.

Boost is smart enough to figure out that we're passing in an instance of FooClass instead of just a number or string or whatever, and so when the function is called, it will use that instance, and will do myFoo->Print() automagically for you. This means we don't have to carry the instance round or worry about the awful syntax when we want to use it, we just bind it into the function object, and away we go.

But but but, what's the _1?

Aha! Remember, boost::bind is not "mysterious way to get functions to work", it's "bind a parameter into a function object." It can bind any variable of any type, so long as it matches the boost::function which will hold it. Also, it wants to bind variables for every parameter in the function. This is also perfectly valid code:

boost::function<void()> newFunc = boost::bind( &FooClass::Print, instance, 6 );
newFunc(); //this will call Print with 6 as the 'a' parameter.

What the heck, I hear you say? We're calling the Print function, which takes one int as a parameter, but we're not passing any int's to it. This is just boost::bind doing it's thing. Remember, it wants to bind every parameter it can.

...But if you bind every parameter, you can't supply them later!

This is what the _1 is for. It means "The first parameter, which will be supplied later". In our first example, we used _1 to indicate that we wouldn't bind the parameter to newFunc in straight away, and that we would supply it later on when we invoke the function.

The cool thing about this is, you can mix and match them, and do all kinds of silly stuff, like this:

int MessageBox( HWND, char*, char*, int ); 
//Probably looks familiar to windows coders

boost::function<int( int, char*, char*, HWND )> reversed_params =
      boost::bind( &MessageBox, _4, _3, _2, _1 ); 
      //use the _ markers to move the parameters around

boost::function<int( char*, char* )> bind_some =
      boost::bind( &MessageBox, m_hWnd, _1, _2, 0 ); 
      // bind in some parameters, but leave others to be supplied later,
      // creating a function where the user must supply 2 params instead of 4 

If you're a functional programming fanatic, you'll have been whinging about closures for years, and how langauges that don't have them suck. boost::bind isn't a closure, but if you know what you're doing you can get pretty close to acheiving the same functionality as one, which is pretty cool for C++

Anyway. I've spent ages writing this so hopefully someone will read it. Good Luck!

Sunday, September 17, 2006

Windows live writer is catastrophically broken

As with other microsoft editors, live writer decides that it will kindly reformat your HTML for you. By 'reformat' I mean "remove all the line breaks"

Now, if you're just having a rant, like I am here, you really don't care. So long as the HTML isn't full of <p><p></p></p> like so many other WSIWYG editor outputs, or has (god forbid) css classes of -mso-x-y-random-otherthing everywhere, I don't mind

Except though, when you're trying to write a post which contains code, and that code is inside a white-space:pre; element, like I am. Then, you care a lot about programs that delete all your newlines and turn your 6 line clearly-written code example into a gibbering mess.

It turns out also, that if you tell live writer to download your existing blog posts from blogger, so you can spruce them up a bit with some WSIWYG loving, it removes all your newlines too, so if you dare republish them, they'll be a gibbering mess too.

So, I ask you, windows live writer team. What the hell kind of good is the HTML editing mode if the app is just going to reformat and screw over any HTML you care to write? Why not just change the menu item to spawn a dialog which says "ALL YOUR HTML ARE BELONG TO US." and then quit the app? That at least would have saved me a bunch of time.

Windows Live Writer part 2

Well, it's actually _really_ good. Yesterday blogger was throwing error 500's like crazy so I guess that stopped it.

Anyway, I'll be using live writer for blogging from now on I think, it sure beats publishing via the website textboxes, that's for sure.

More stuff about C++ threading and other stuff coming soon...

Friday, September 15, 2006

This is a test of windows live writer beta

Apparently it's quite good, but well... if it works, perhaps.

Wednesday, September 13, 2006

Your friendly QueueUserAPC

I'm a reasonably active reader of and lately there has been a whole ton of articles about concurrent programming, so here's my 2c to throw into the ring. Basically, there seem to be 2 approaches to concurrent programming these days - the classic shared memory/locking model, which the majority of applications these days use, and the 'erlang style' nothing shared/message passing model. They both have their uses - I guess if you were using erlang you'd do that, if you were using C# you would use shared/locking. My job is to program mostly C++ apps on windows, so I'd like to share what I think is a neat trick you can use ( when programming C++ apps on windows ). This may be commonly known by everyone, but I've not seen it mentioned on reddit or anywhere else, so I'm guessing that it's not. In windows NT4 and up, native windows threads have what is called an APC Queue. APC stands for Asynchronous Procedure Call. This is used if you are using any of the Overlapped IO functions ( ReadFileEx and WriteFileEx amongst others ). Basically what it is, is a list of function pointer/ULONG_PTR pairs. So, you ask, what good might that be? Well, this APC Queue gets processed whenever the thread enters what is called an 'Alertable Wait State'. "Alertable Wait State" is a fancy name for "Has called the SleepEx function, WaitForSingleObjectEx function, or one of the many other Wait*Ex functions". So, wherever you'd do a WaitForSomething, you do a WaitForSomethingEx, and windows automagically pulls things off the APC queue and executes them. The QueueUserAPC function allows you to insert your own functions into this Queue. In a nutshell, it says "Execute this callback function in this thread" If you haven't clicked onto why that's so cool, bear with me... Observe the following program. If you're a windows C/C++ coder, it probably looks somewhat familiar #include "windows.h" #include <list> std::list<int> g_listOfInts; DWORD WINAPI ThreadProc( LPVOID param ) { g_listOfInts.push_back( 7 ); } void AddToList( int param ) { g_listOfInts.push_back( param ); } void PrintList() { std::list<int>::iterator iter; for( iter = g_listOfInts.begin(); iter != g_listOfInts.end(); ++iter ) std::cout << *iter << std::endl; } void main() { DWORD dwThreadId; HANDLE hSecondThread = CreateThread( NULL, 0, ThreadProc, 0, &dwThreadId ); AddToList( 5 ); //... do some other stuff PrintList(); } Now, this code of course has a big nasty race condition. As both threads insert into the list, they could both do it at the same time, which would either cause the list to be invalid, the program to crash, or memory corruption, or any number of other bad things. Also, the second thread could modify the list while the iterator is looping over it, which is also problematic. The classic solution is to lock the list. You could use a windows CRITICAL_SECTION, a boost::mutex::scoped_lock, or dozens of other things, which all boil down to "If any other thread wants to look at this object, it must wait for any other threads which might also be lookin at or modifying it. Also, if everything that needs to access the object must wait for everything else, we effectively serialise access to that variable down to 1 thread - if we've got 32 CPU's running 32 threads, 31 of them are going to be waiting on our lock, so we have zero performance improvement over just running a single thread. The 'non-shared' solution would be to somehow enforce that one thread "owns" the list. If any other threads want to get any data from it, they must send a message to the "owner" thread, and it must reply. This is probably trivial in something like erlang, but I don't know erlang, so I can't comment. In Windows/C++, you've got trusty old Windows Messages ( using MSG and PEEKMESSAGE, etc, like you'd have in any windows GUI app ). However, if you were to use this approach for any nontrivial program you'd end up creating hundreds of GET_X and GET_Y messages, and it would soon become unmanagable. QueueUserAPC to the rescue! Look at the next program. #include "windows.h" #include <list> std::list<int> g_listOfInts; HANDLE g_terminateSignal; DWORD WINAPI ThreadProc( LPVOID param ) { g_listOfInts.push_back( 7 ); while( WaitForSingleObjectEx( g_terminateSignal, INFINITE, TRUE ) == WAIT_IO_COMPLETION ); //apc's can execute in this loop while we wait for the quit signal. } void CALLBACK ApcAddToList( ULONG_PTR param ) { g_listOfInts.push_back( (int)param ); } void CALLBACK ApcPrintList( ULONG_PTR param ) { std::list<int>::iterator iter; for( iter = g_listOfInts.begin(); iter != g_listOfInts.end(); ++iter ) std::cout << *iter << std::endl; } void main() { g_terminateSignal = CreateEvent( NULL, TRUE, FALSE, NULL ); DWORD dwThreadId; HANDLE hSecondThread = CreateThread( NULL, 0, ThreadProc, 0, &dwThreadId ); QueueUserAPC( ApcAddToList, hSecondThread, 5 ); QueueUserAPC( ApcPrintList, hSecondThread, NULL ); //magically assume we've written some code to wait for a WM_QUIT //and set g_terminateSignal when we get it. } So, what's the difference here (apart from the code looking all werid and different)? Well, we create our second thread, which adds something to the list, like it did last time, but instead of exiting, it does a WaitEx for the terminate signal to be set. It's now in the "Alertable Wait State". Also, our main function doesn't mess with the list any more. The program is written so the second thread "owns" the list. If the main thread wants to modify it, he must make it happen in the second thread. In this example, first ApcAddToList and then ApcPrintList are "Queued" to the thread (which is in it's alertable wait state), where they are executed. Because everything involving the list only ever happens in thread 2, we no longer have our race condition. We don't have to lock at all either, instead of the threads waiting for each other so they can access the locked memory, they are free to carry on doing other stuff while thread 2 does whatever it needs to. Just like as if we'd written it in one of those fancy concurrent no-shared-state languages, but without having to rewrite your entire codebase. Cool, no? PS: If you're thinking "That's cool, but how can it be useful given that the APC callback has to be a free C-style function and only has one 32 bit parameter...", the answer will come soon. PPS: for those of you that can't wait for me to explain how it can be more useful, go and look at boost::bind.