C++

In the previous articles of the series we’ve reviewed the adaptive process of the square game field for concepts of boost graphs. Now we’ll consider the process of finding the path in the square field. Implementation of boost search allows adapting the algorithm quite accurately. In this article we’ll provide just one example of such parameterization – an ability to create various lengths of graph edges.

Let’s begin with describing the parameter. We should create a map of edge weights. This map will meet requirements of ReadablePropertyMapConcept concept. It’s quite easy to implement. We should define several types and [] iterator. On the basis of the key-type edge the latter returns its length.

Read more →

I’ll briefly remind you of the task. There’s a two-dimensional game field consisting of squares. Some of them are vacant and others are occupied. We should find a path through vacant squares from one field position to another one. We implemented the search algorithm in Boost. But it requires our field to fit the graph definition. Or rather the class should meet the requirements of two concepts: boost::VertexListGraph and boost::IncidenceGraph. We don't want to change the interface of game field, as it’s not a graph for the remaining project and will never be one.

In the previous part we’ve reviewed attaching the external associative types that are necessary for interpreting the class as boost graph. Of course types only are not enough. We should also implement several functions with the assigned signature, and iterators which will help the library to handle the game field as a graph.

Read more →

I had to rebuild a pathfinding algorithm for our game recently. The previous one (Boost Concepts) was bad as any sidestep was dangerous. So I wanted to take a ready algorithm from a good source. That’s exactly when I remembered about boost as there’s functionality for working with graphs. Unfortunately “find a function, call it and everything will work” approach wasn’t meant to be realized. The library is focused on the maximum use flexibility which has badly affected its simplicity. But it’s better than creating it from scratch (then fixing it). I didn’t want to bother with other libraries, while boost has already been used in the project.

Read more →

Looking through programming articles sometimes I see posts about creating your own HTTP server. I am most interested in C++ so I often read blogs about it. After looking them through you could easily write you own web server “on sockets” using boost.asio or something else. I also examined libevent and libev. Each of them has its advantages. Libevent is of great interest to me for developing a small HTTP server. Considering some innovations in C++11 the code becomes much more space-efficient and allows for the creation of a basic HTTP server in less than 40 lines.

The information of this post will be useful for those not familiar with libevent and those who want to quickly create an HTTP server. There’s nothing innovative in this post, so you can use it as material for working in the right direction.

libevent is better than libev and boost.asio because of its embedded HTTP server and some abstraction for operating with buffers. It also has a large set of helper functions. You can examine HTTP protocol by yourself by writing a simple FSN (finite state machine) or maybe through some other means. When working with libevent – it’s all there already. You can also go to a lower level and write your own parser for HTTP and perform the work with sockets on libevent. I liked the detail level of this library. If you want to do something quickly you’ll find a higher-level interface that is usually less flexible. When there are more serious requirements you can go down gradually, level by level. The library allows doing many things, such as: asynchronous input/output, work with the network, work with timers, rpc, etc. You can also use it to create both server-side and client-side software.

Read more →

I was always scared to use C++ templates due to the absence of standard mechanisms for setting parameter limits. In other words, when a developer writes the following function:

template 
bool someFunc(T t)
{
    if (t.someCheck()) {
        t.someAction(0);
    }
}

it makes different assumptions as for the functionality of T type objects, but doesn’t have a standard facility to inform the user about them. Thus, the provided example can suppose at least the following things:

1. T type objects are passed by value. So they should have on open copy constructor.
2. There’s an open T::someCheck method with no parameters. It returns the value that is cast to bool type.
3. There’s an open T::someAction method that can accept one parameter that is cast to numeric data type.

Read more →

As I’ve already mentioned in the previous articles, the main difficulties when implementing lock-free data structures are ABA problem and memory reclamation. I will separate these two problems even though they are connected as there are algorithms that can solve only one of them.
In this article I am going to review popular methods of safe memory reclamation for lock-free containers. I’ll demonstrate the application of one or another method of the classic lock-free queue by Michael-Scott [MS98].

Read more →

It is common practice not to like Windows. But, as a rule, phrase: “I haven't read the book but still condemn it” describes this situation well. Despite the tendency of not like Windows, there are still some things that are implemented well. I’d like to tell you about one of them.

I’ll review the embedded into OS implementation of the lock-free stack and its performance comparison with the cross-platform analogues.

The implementation of non-blocking stack on the basis of a singly linked list (Interlocked Singly Linked Lists, SList), has been available in WinAPI for quite a while. Operations on such list initializing and stack primitives over it have been implemented. Without going into details of implementing the SLists, the Microsoft just say that they use some non-blocking algorithm in order to implement atomic synchronization, increase performance and get rid of lock problems.

You can implement non-blocking singly linked lists by yourself. There are some articles written on the topic.
But there have been no 128-bit CAS operation before Windows 8. This fact caused problems when implementing such algorithms in 64-bit applications. SList helps to solve this task.

Read more →

Today I’m going to tell you about a new and a little known (to my mind) C++ feature — reference-qualified member functions. I’ll tell about the rules of such functions overloading and, as an example of use, I’ll show you that with the help of ref-qualified you can try to improve the resource management scheme, which is implemented with the help of another C++ idiom — RAII.

Read more →

I have recently read an article about computations on C++ templates. One of the comments to the article was a sort of a challenge for me.

The number of methods to rack your brains with the help of C++ is increasing with every new release.

Especially when the approach to playing field implementation isn’t changed and all the computations are carried out on types rather than constants.

But would it be that difficult to write a multipurpose computer on types, which would be handier for programming rather than a cellular automaton? As it turned out, it’s not difficult. I spent 30 times more hours to write this article than to write and debug the code itself.

Read more →

In the previous article we looked inside the processor, even if it’s hypothetic. We have clarified that for the proper parallel code execution we should prompt the processor to what limits he is allowed to execute its internal read/write optimizations. These prompts are memory barriers. They allow regulating memory access to some extent (or rather the cache as the processor interacts with the outer world through cache only). The “weight” of such regulation can be different. Every architecture can provide the entire set of barriers “for choice”. Using these or those barriers we can build different memory models. It’s the set of warranties which will be executed for our programs.

In the article we’ll talk about C++11 memory model.

Read more →