Friday, 18 May 2012

One Definition Rule and Unnamed namespaces

It is possible to have multiple (different) definitions of a class with all methods declared as inline, in different translation units. Both compiler and linker do not complain. Compiler sees only a single unit and so only a single definition. Linker treats all definitions of inline class methods equally, picks only one for linking and discards the rest. But different definitions of the same class are introducing undefined behaviour as linker can pick e.g. constructor implementation from one module and method implementation from another. So the client code might potentially call method defined in one module on some object created with constructor defined in another module. Different definitions of the same class within the same program break the One Definition Rule (§3.2, C++11 standard draft N3242=11-0012). (See my Stack Overflow question)

It is possible to define classes with the same name in different translation units in a safe way. Classes are visible in all units because member functions of non-local classes have external linkage by default. It doesn't matter whether methods are declared as inline, static or they are declared without any specifiers. So this is the reason why linker is able to see multiple definitions of the same method, allowing it to (arbitrary) pick the one and discard the rest. We need to suppress this, we need to hide definitions inside translation units. If we had a variable or a function, we could achieve this by declaring it as static and therefore imposing internal linkage on them. But we cannot apply static keyword on classes (user defined types). What we can do is to place class definition in each translation unit inside a unnamed namespace. This way we are limiting class access only to the translation unit this class is defined in and disable breaking of the One Definition Rule.


Links and References:

external vs internal linkage and performance (SO)
Unnamed/anonymous namespaces vs. static functions (SO)
Superiority of unnamed namespace over static? (SO)
Why unnamed namespace is a“ superior” alternative to static? (SO)
static keyword useless in namespace scope? (SO)


Tuesday, 15 May 2012

WaitForMultipleObjects and priority of the events

The order of event handlers in the handler array passed to WaitForMultipleObjects function must be carefully chosen if we want to differentiate priorities of events.

Let us assume that we have two events, Event1 and Event2, and that we want Event2 to have a higher priority so if both events are set, WaitForMultipleObjects returns the index of the Event2. We can make this by defining the order of the event handlers in the array passed to WaitForMultipleObjects.

In the example below, Event2 controls when the program execution jumps out of the loop. If Event1 is set quickly enough between ResetEvent() and WaitForMultipleObjects, it is Event1 that will always cause WaitForMultipleObjects to return, no matter what is the state of Event2. Execution will get out of the loop only if Event2 is set and Event1 is not set before WaitForMultipleObjects (which might never happen):



If we want to make sure that WaitForMultipleObjects first checks whether Event2 is set so it breaks out of the loop as soon as this event is set, we need to place Event2 before Event1 in the array:



This time, even if both events are set, WAIT_OBJECT_0 case is executed and program flow leaves the loop.

This is the consequence of the following feature of WaitForMultipleObjects:

If more than one object became signaled during the call, WAIT_OBJECT_0 is the array index of the signaled object with the smallest index value of all the signaled objects.


Listening TCP Socket

TCP is a connection-oriented transport protocol which means that end points have to establish a connection prior to sending any (payload) data. Server opens one socket only for listening for incoming connection requests that come from clients. When placing a socket into a listening state, a maximum number of pending incoming connections is set. Those connections are waiting to be accepted and when backlog gets full no new connections are accepted.

Operations on listening socket are:
Listening socket never gets into connected state and shutdown() called on it yields socket error 10057 - WSAENOTCONN (Socket is not connected).

Here is the timeline of one simple dialogue between the client and the server:

Client Server
sock = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP) sockListen= socket(AF_INET, SOCK_STREAM, IPPROTO_TCP)
- sockaddr_in sSockAddr;
sSockAddr.sin_family = AF_INET;
sSockAddr.sin_addr.s_addr = inet_addr("192.168.0.24");
sSockAddr.sin_port = htons(43501);

bind(sockListen, (SOCKADDR*)&sSockAddr, sizeof(sSockAddr));
- listen(sockListen, MAXPENDING)
struct sockaddr_in sockAddrRemoteNode;
memset(&sockAddrRemoteNode, 0, sizeof(sockAddrRemoteNode));
sockAddrRemoteNode.sin_family = AF_INET;
sockAddrRemoteNode.sin_addr.s_addr = inet_addr("192.168.0.24");
sockAddrRemoteNode.sin_port = htons(43501);

connect(sock, (struct sockaddr*) &sockAddrRemoteNode, sizeof(sockAddrRemoteNode));
struct sockaddr sockAddrClt;
int nSockAddrLen = sizeof(sockAddrClt);

sockClient = accept(sockListen, (struct sockaddr*) &sockAddrClt, &nSockAddrLen);
send(sock, buffSend, SEND_BUFF_SIZE, 0) int recvPacketLen = recv(sockClient, buffRecv, RECV_BUFF_SIZE, 0)
shutdown(sock, SD_BOTH) shutdown(sockClient, SD_BOTH)
closesocket(sock) closesocket(sockClient)
- closesocket(sockListen)

Thursday, 3 May 2012

Observer pattern: from GoF implementation to events and delegates


Let us assume we have some class (Subject) with properties that can be changed. A set of current values of all properties defines Subject's state. Another class (Observer) must be notified each time Subject's state changes (each time some property changes). Observer pattern decouples direct dependencies between (concrete) subject and (concrete) observer by using interfaces.

The following code shows classic (Gang of Four) implementation of the Observer pattern applied to two subjects (PropertyOwner1 and PropertyOwner2) and their observers (PropertyObserver1 and PropertyObserver2):

main.cpp:


Output:


PropertyOwner1: property1's new value is: 1
PropertyObserver1: PropertyOwner1 property1's value is: 1
PropertyObserver2: PropertyOwner1 property2's value is: 0

PropertyOwner1: property2's new value is: 1.2
PropertyObserver1: PropertyOwner1 property1's value is: 1
PropertyObserver2: PropertyOwner1 property2's value is: 1.2

PropertyOwner2: property1's new value is: 1
PropertyObserver1: PropertyOwner2 property2's value is: 0
PropertyObserver2: PropertyOwner2 property1's value is: 1

PropertyOwner2: property2's new value is: 3.4
PropertyObserver1: PropertyOwner2 property2's value is: 3.4
PropertyObserver2: PropertyOwner2 property1's value is: 1

PropertyOwner1: property1's new value is: 2
PropertyObserver2: PropertyOwner1 property2's value is: 1.2

PropertyOwner1: property2's new value is: 4.5
PropertyObserver2: PropertyOwner1 property2's value is: 4.5

As we can see, observer is notified each time any property of the subject changes. E.g. if we look the test where PropertyOwner1's property1 changes to 2 but PropertyObserver2 is notified regardless the fact that it is interested only in PropertyOwner1's property2.

In this model client gets information that the subject's state (some property) has been changed but it does not know exactly which property has been changed. Of course, observer could maintain the history of obtained values for each property and compare new values with the previous ones and thus detect for which property the value has changed but this increases complexity of the observer.

Somehow we need to pass to the observer information about which property has changed. If we assign each property in a system a unique ID we could pass it to the observer as an additional parameter of the Subject::update() method:

main.cpp:



Output shows that this time each observer knew exactly which property of which subject has been changed:


PropertyOwner1: property1's new value is: 1
PropertyObserver1: PropertyOwner1 property1's value is: 1

PropertyOwner1: property2's new value is: 1.2
PropertyObserver2: PropertyOwner1 property2's value is: 1.2

PropertyOwner2: property1's new value is: 1
PropertyObserver2: PropertyOwner2 property1's value is: 1

PropertyOwner2: property2's new value is: 3.4
PropertyObserver1: PropertyOwner2 property2's value is: 3.4

PropertyOwner1: property1's new value is: 2

PropertyOwner1: property2's new value is: 4.5
PropertyObserver2: PropertyOwner1 property2's value is: 4.5

There is a room for further improvements: notify() (and so observer's update()) function is called each time any property of the subject is changed. Yes, Property ID is passed so observer knows which property has been modified but still - can we avoid calling update() of the observer that is not interested in that particular property?

The solution is to granulate Observer pattern: instead of taking PropertyOwners as concrete subjects, let us move Observer pattern one level down and take PropertyOwners' properties as explicit concrete subjects. This implies that observers will need to register with properties, not with their owning classes - PropertyOwners. Each property will implement Subject interface and maintain its list of observers. When calling notify()/update() it needs to pass information on the type of its owner (PropertyOwner - "implicit concrete subject") so the observer knows which PropertyOwner has changed. On the observer's side we can do the same, granulate the pattern to smaller units which belong to particular class (PropertyObserverOwner - "implicit concrete observer") and which observe particular
property of the particular class. Templates come handy for this implementation:


main.cpp:



Output shows that this time a single update() call is made for a single property change:

struct PropertyOwner1's property of type int has been set to 1
   PropertyObserverOwner1::OnPropertyOwner1Property1Changed():
   new value is: 1
struct PropertyOwner1's property of type float has been set to 1.2
   PropertyObserverOwner2::OnPropertyOwner1Property2Changed():
   new value is: 1.2
struct PropertyOwner2's property of type bool has been set to 1
   PropertyObserverOwner2::OnPropertyOwner2Property1Changed()
   new value is: 1
struct PropertyOwner2's property of type double has been set to 3.4
   PropertyObserverOwner1::OnPropertyOwner2Property2Changed():
   new value is: 3.4
struct PropertyOwner1's property of type int has been set to 2
struct PropertyOwner1's property of type float has been set to 4.5
   PropertyObserverOwner2::OnPropertyOwner1Property2Changed():
   new value is: 4.5

I don't like the previous implementation. It is too complex and its scalability is questionable.

I was always a big fan of C# events and delegates. It is so easy to bind some event with its handler. I tried to implement something similar in C++ and here is the result:

main.cpp:



Output:
PropertyOwner1::property1(): property1_ set to 1
   PropertyObserver1::OnPropertyOwner1Property1Changed():
   new value is: 1
PropertyOwner1::property2(): property2_ set to 1.2
   PropertyObserver2::OnPropertyOwner1Property2Changed():
   new value is: 1.2
PropertyOwner2::property1(): property1_ set to 1
   PropertyObserver1::OnPropertyOwner2Property1Changed():
   new value is: 1
PropertyOwner2::property2(): property2_ set to 3.4
   PropertyObserver2::OnPropertyOwner2Property2Changed():
   new value is: 3.4
PropertyOwner1::property1(): property1_ set to 2
PropertyOwner1::property2(): property2_ set to 4.5
   PropertyObserver2::OnPropertyOwner1Property2Changed():
   new value is: 4.5

This is exactly what I wanted: observer registered with particular property (event), notified when property's changed and with a knowledge of property's owner and a new value.

Removing STL list elements whilst iterating through it

I have already written about the traps and solutions when we try to remove elements from vectors and maps whilst iterating through them. Today I want to cover the same topic regarding lists.

Let us assume we have a list containing integers and we want to remove all elements that are odd numbers. If not aware of std::list::remove() side effects, the first thing we would try could be the following:



When run, this program removes element with the value 1 but the next time it tries to dereference iterator it crashes with the message:

Microsoft Visual Studio
Unhandled exception at 0x00d5c7a2 in Test.exe: 0xC0000005: Access violation reading location 0xfeeefef6.

The most often source of errors when working with STL containers are invalid iterators. Before calling some function on some STL container, we need to make sure we understand how it affects container's iterators. The latest draft of the new C++ standard (C++11) says (§ 23.3.5.5):

void remove(const T& value);
template void remove_if(Predicate pred);

Effects: Erases all the elements in the list referred by a list iterator i for which the following conditions
hold: *i == value, pred(*i) != false. Invalidates only the iterators and references to the erased
elements.


Throws: Nothing unless an exception is thrown by *i == value or pred(*i) != false.

This explains what happened in our program: remove() invalidated iterator and all subsequent operations on iterator (incrementing, dereferencing) yielded undefined behaviour (crash in our case).

A simple solution to this is to save iterator's value before removing an element, increment it and then remove element on the saved (previous) iterator value. In the next iteration iterator will be pointing to the next element after the removed one:


This time program works as expected and yields the following output:

display_elements()
list[0] = 1
list[1] = 2
list[2] = 3
list[3] = 4


display_elements()
list[0] = 2
list[1] = 4

Instead of using temporary variable to store previous value of the iterator, we can use post-increment operator (this works as function arguments are fully evaluated before a function is called):



Another function that removes an element (or a range of elements) from a list is std::list::erase(). Instead of the element value, an iterator is passes as its argument. Similar to list::remove(), it invalidates the iterator of the erased element.



This yields debug assertion error:

---------------------------
Microsoft Visual C++ Debug Library
---------------------------
Debug Assertion Failed!

Program: C:\test\Tests.exe
File: c:\program files\microsoft visual studio 10.0\vc\include\list
Line: 227

Expression: list iterator not incrementable

For information on how your program can cause an assertion
failure, see the Visual C++ documentation on asserts.

(Press Retry to debug the application)
---------------------------
Abort Retry Ignore
---------------------------

Applying the same fix like before solves the problem:



If we want to remove from a list all elements that match certain criteria, the best way to achieve that is not to fiddle with iterators and loops but to use std::list::remove_if(). This function uses unary predicate to check the criteria for the current element. In our case the predicate returns true if the value is odd number:



Output:

display_elements()
list[0] = 1
list[1] = 2
list[2] = 3
list[3] = 4


display_elements()
list[0] = 2
list[1] = 4

NOTE: The signature of the predicate does not need to have const &, but the function must not modify the objects passed to it.

To make the code even smaller, we can move the code from a predicate to a lambda expression: