Loki Astari

Thoughts of a Former Code Monkey

Socket Protocols

| Comments

In the previous articles I have used a very simplistic protocol. In real world situations this simple protocol is not sufficient. To provide a more robust connection between client and server a communications protocol is required so that we can validate messages are sent correctly and generate appropriate responses that can also be validated.

Designing a communication protocol is a non trivial task and personally I would look for an existing protocol that matches your use case rather than trying to create protocol from scratch.

Example Protocols

Rather than go through all the different protocols I am simply going to pick the HTTP(S) protocol and use that for further discussion. HTTP(S) is relatively well known; It is simple to implement the basics; There are well known server implementations that support it; There are well known client libraries that can be used in application development.

Example HTTP(S) servers

Client Side HTTP Libraries

HTTP(S)

Basically HTTP(S) defines two object. A request object is sent from the client to the server and response object is sent back as a result of a request. The only difference between the two is the start-line. Both HTTP objects can be broken down into three pieces.

  1. Start-Line
  2. Header-Section
  3. Body

Start-Line

For a request object this is:

• Method:HEAD/GET/PUT/POST/DELETE
• Space:One Space character
• URL:Identification of the object/service needed
• Space:One Space character
• HTTP-Version:Usually HTTP/1.1
• CR/LF:Literally ‘\r\n’

Example:

1
GET http://google.com/maps?id=456 HTTP/1.1\r\n

For a response object this is:

• HTTP-Version:Usually HTTP/1.1
• Space:One Space character
• Response Code:100->599
• Space:One Space character
• Human Readable Response:Human readable explanation of the response code
• CR/LF:Literally ‘\r\n’

Example:

1
HTTP/1.1 200 OK\r\n

Header-Section

This is a set of key/value pairs one per line separated by a colon. Each Line is terminated by CR/LF and the end of the header section is marked by an empty line.

• Key:A text string representing the keys.
• Colon:A single colon (note: some implementations are lax and insert a space before the colon).
• Space:One Space character (note: some implementations are lax and more then one space may be present)
• Value:A set of characters that does not include CR or LF.
• CR/LF:Literally ‘\r\n’

Example

1
2
3
Content-Length: 42\r\n
Content-Type: text/text\r\n
\r\n

Body

The payload of the object should be in the body. Its size is defined by the headers defined in rfc-2616 section 4.4 Message Length.

Required Headers

According to the rfc(s) 7230, 7231, 7232, 7233, 7234 or 7235 there are no header fields there are actually required header fields.

Request Object

But real world implementations need some headers to work efficiently, so you probably should send the following headers when making a request to a server:

It is also polite to send the following.

Response Object

A server implementation “Must” send a Date: header field if it is a reasonable approximation of UTC. But that means servers may not supply the Date: field so you can’t say it is a requirement of the standard. But you will usually see the following headers returned from a server:

Implementation

Given this very basic protocol; it seems like the implementation of these requirements should be quite trivial. To be honest the implementation of creating the objects to send is relatively trivial, the hard part is reading objects from the stream in an efficiently and correctly validated manner. You can find my attempt here: It works but its 500 lines long and only covers the most basics parts of the protocol and does not do any of the hard parts (like authentication or HTTPS).

To use this protocol correctly you really need to use one of the existing libraries. Here I have re-implemented the client using libcurl.

Client uses libcurl wrappersource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main(int argc, char* argv[])
{
    namespace Sock = ThorsAnvil::Socket;
    if (argc != 3)
    {
        std::cerr << "Usage: client <host> <Message>\n";
        std::exit(1);
    }

    Sock::CurlGlobal    curlInit;
    Sock::CurlPost      connect(argv[1], 8080);

    connect.sendMessage("/message", argv[2]);

    std::string message;
    connect.recvMessage(message);
    std::cout << message << "\n";
}
libCurl simple wrappersource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include "Utility.h"
#include <curl/curl.h>
#include <sstream>
#include <iostream>
#include <cstdlib>

namespace ThorsAnvil
{
    namespace Socket
    {

class CurlGlobal
{
    public:
        CurlGlobal()
        {
            if (curl_global_init(CURL_GLOBAL_ALL) != 0)
            {
                throw std::runtime_error(buildErrorMessage("CurlGlobal::", __func__, ": curl_global_init: fail"));
            }
        }
        ~CurlGlobal()
        {
            curl_global_cleanup();
        }
};

extern "C" size_t curlConnectorGetData(char *ptr, size_t size, size_t nmemb, void *userdata);

enum RequestType {Get, Head, Put, Post, Delete};
class CurlConnector
{
    CURL*       curl;
    std::string host;
    int         port;
    std::string response;

    friend size_t curlConnectorGetData(char *ptr, size_t size, size_t nmemb, void *userdata);
    std::size_t getData(char *ptr, size_t size)
    {
        response.append(ptr, size);
        return size;
    }
    template<typename Param, typename... Args>
    void curlSetOptionWrapper(CURLoption option, Param parameter, Args... errorMessage)
    {
        CURLcode res;
        if ((res = curl_easy_setopt(curl, option, parameter)) != CURLE_OK)
        {
            throw std::runtime_error(buildErrorMessage(errorMessage..., curl_easy_strerror(res)));
        }
    }

    public:
        CurlConnector(std::string const& host, int port)
            : curl(curl_easy_init( ))
            , host(host)
            , port(port)
        {
            if (curl == NULL)
            {
                throw std::runtime_error(buildErrorMessage("CurlConnector::", __func__, ": curl_easy_init: fail"));
            }
        }
        ~CurlConnector()
        {
            curl_easy_cleanup(curl);
        }
        CurlConnector(CurlConnector&)               = delete;
        CurlConnector& operator=(CurlConnector&)    = delete;
        CurlConnector(CurlConnector&& rhs) noexcept
            : curl(nullptr)
        {
            rhs.swap(*this);
        }
        CurlConnector& operator=(CurlConnector&& rhs) noexcept
        {
            rhs.swap(*this);
            return *this;
        }
        void swap(CurlConnector& other) noexcept
        {
            using std::swap;
            swap(curl, other.curl);
            swap(host, other.host);
            swap(port, other.port);
            swap(response, other.response);
        }

        virtual RequestType getRequestType() const = 0;

        void sendMessage(std::string const& urlPath, std::string const& message)
        {
            std::stringstream url;
            response.clear();
            url << "http://" << host;
            if (port != 80)
            {
                url << ":" << port;
            }
            url << urlPath;

            CURLcode res;
            auto sListDeleter = [](struct curl_slist* headers){curl_slist_free_all(headers);};
            std::unique_ptr<struct curl_slist, decltype(sListDeleter)> headers(nullptr, sListDeleter);
            headers = std::unique_ptr<struct curl_slist, decltype(sListDeleter)>(curl_slist_append(headers.get(), "Content-Type: text/text"), sListDeleter);

            curlSetOptionWrapper(CURLOPT_HTTPHEADER,        headers.get(),          "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_HTTPHEADER:");
            curlSetOptionWrapper(CURLOPT_ACCEPT_ENCODING,   "*/*",                  "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_ACCEPT_ENCODING:");
            curlSetOptionWrapper(CURLOPT_USERAGENT,         "ThorsCurl-Client/0.1", "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_USERAGENT:");
            curlSetOptionWrapper(CURLOPT_URL,               url.str().c_str(),      "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_URL:");
            curlSetOptionWrapper(CURLOPT_POSTFIELDSIZE,     message.size(),         "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_POSTFIELDSIZE:");
            curlSetOptionWrapper(CURLOPT_COPYPOSTFIELDS,    message.data(),         "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_COPYPOSTFIELDS:");
            curlSetOptionWrapper(CURLOPT_WRITEFUNCTION,     curlConnectorGetData,   "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_WRITEFUNCTION:");
            curlSetOptionWrapper(CURLOPT_WRITEDATA,         this,                   "CurlConnector::", __func__, ": curl_easy_setopt CURLOPT_WRITEDATA:");

            switch(getRequestType())
            {
                case Get:       res = CURLE_OK; /* The default is GET. So do nothing.*/         break;
                case Head:      res = curl_easy_setopt(curl, CURLOPT_CUSTOMREQUEST, "HEAD");    break;
                case Put:       res = curl_easy_setopt(curl, CURLOPT_PUT, 1);                   break;
                case Post:      res = curl_easy_setopt(curl, CURLOPT_POST, 1);                  break;
                case Delete:    res = curl_easy_setopt(curl, CURLOPT_CUSTOMREQUEST, "DELETE");  break;
                default:
                    throw std::domain_error(buildErrorMessage("CurlConnector::", __func__, ": invalid method: ", static_cast<int>(getRequestType())));
            }
            if (res != CURLE_OK)
            {
                throw std::runtime_error(buildErrorMessage("CurlConnector::", __func__, ": curl_easy_setopt CURL_METHOD:", curl_easy_strerror(res)));
            }
            if ((res = curl_easy_perform(curl)) != CURLE_OK)
            {
                throw std::runtime_error(buildErrorMessage("CurlConnector::", __func__, ": curl_easy_perform:", curl_easy_strerror(res)));
            }
        }
        void recvMessage(std::string& message)
        {
            message = std::move(response);
        }
};

class CurlPost: public CurlConnector
{
    public:
        using CurlConnector::CurlConnector;
        virtual RequestType getRequestType() const {return Post;}

};

size_t curlConnectorGetData(char *ptr, size_t size, size_t nmemb, void *userdata)
{
    CurlConnector*  self = reinterpret_cast<CurlConnector*>(userdata);
    return self->getData(ptr, size * nmemb);
}

    }
}

C++ Wrapper for Socket

| Comments

The last two articles examined the “C Socket” interface that is provided by OS. In this article I wrap this functionality in a very simple C++ class to provide guaranteed closing and apply a consistent exception strategy. The first step is to rewrite the client/server code with all the low level socket code removed. This will help identify the interface that the wrapper class needs to implement.

The client code becomes really trivial. Create a ConnectSocket specifying host and a port. Then use the putMessage() and getMessage() to communicate with the server. Note: I am continuing to use the trivial protocol that was defined in the last article: putMessage() writes a string to the socket then closes the connection; getMessage() reads a socket until it is closed by the other end (I will cover more sophisticated protocols in a subsequent article).

client.cppsource
1
2
3
4
5
6
7
    ConnectSocket    connect("localhost", 8080);          // Connect to a server
    ProtocolSimple   connectSimple(connect);              // Knows how to send/recv a message over a socket
    connectSimple.sendMessage("", "A test message going to the server");

    std::string message;
    connectSimple.recvMessage(message);
    std::cout << message << "\n";

For the server end this nearly as trivial as the client. Create a ServerSocket and wait for incoming connections from clients. When we get a connection we return a SocketData object. The reason for returning a new Socket like object is that this mimics the behavior of the underlying ::accept() call which opens a new port for the client to interact with the server on. The additional benefit of separating this from the ServerSocket is that a subsequent version may allow multiple connections and we want to be able to interact with each connection independently without sharing state, potentially across threads, so modelling it with an object makes sense in an OO world.

server.cppsource
1
2
3
4
5
6
7
8
9
10
11
12
ServerSocket   server(8080);                          // Create a lisening connection
while(true)
{
    DataSocket      accept  = server.accept();            // Wait for a clinet to connect
    ProtocolSimple  acceptSimple(accept);                 // Knows how to send/recv a message over a socket

    std::string message;
    acceptSimple.recvMessage(message);
    std::cout << message << "\n";

    acceptSimple.sendMessage("", "OK");
}

Surprisingly this actually gives us three types of socket interface (not the two most people expect).

  • The ServerSocket class has no ability to read/write just accept connections
  • The ConnectSocket class connects and can be used to read/write
  • The DataSocket class is an already connected socket that can be used to read/write

Since a socket is a resource that we don’t want duplicated. So this is a resource that can be moved but not copied.

This lets me to define a very simple interface like this:

Socket.hsource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// An RAII base class for handling sockets.
// Socket is movable but not copyable.
class BaseSocket
{
    int     socketId;
    protected:
        // Designed to be a base class not used used directly.
        BaseSocket(int socketId);
        int getSocketId() const {return socketId;}
    public:
        ~BaseSocket();

        // Moveable but not Copyable
        BaseSocket(BaseSocket&& move)               noexcept;
        BaseSocket& operator=(BaseSocket&& move)    noexcept;
        void swap(BaseSocket& other)                noexcept;
        BaseSocket(BaseSocket const&)               = delete;
        BaseSocket& operator=(BaseSocket const&)    = delete;

        // User can manually call close
        void close();
};

// A class that can read/write to a socket
class DataSocket: public BaseSocket
{
    public:
        DataSocket(int socketId);

        bool getMessage(std::string& message);
        void putMessage(std::string const& message);
        void putMessageClose();
};

// A class the conects to a remote machine
// Allows read/write accesses to the remote machine
class ConnectSocket: public DataSocket
{
    public:
        ConnectSocket(std::string const& host, int port);
};

// A server socket that listens on a port for a connection
class ServerSocket: public BaseSocket
{
    public:
        ServerSocket(int port);

        // An accepts waits for a connection and returns a socket
        // object that can be used by the client for communication
        DataSocket accept();
};

Taking the existing code and wrapping this interface around it becomes trivial. The code full code is provided here.

In the previous article I talked about the different types of errors that could be generated by read/write. In the following code I take this a step further. Since the code is wrapped inside a class and thus can control the socket resources more cleanly it feels more natural to use exceptions rather than error codes, consequentially error codes are not leaked across any public API boundary.

  1. domain_error
    • This is caused by an error that theoretically can not happen (since we have full control of the class). If this type of error occurs there is a bug in the socket code or there has been massive data corruption. Consequently you should not be trying to catch these type of exception as there is a fundamental bug in the code. It is better to let the application exit as it is likely there is substantial corruption of any data.
  2. logic_error
    • This is caused by an error that theoretically can not happen if the class is used correctly. This means that calling code has some form of logic error. It is caused by calling any method on a socket object that was previously closed or moved. Again this type of error should not be caught (but can be). You should try and remove all potential for this type of error by good unit tests.
  3. runtime_error:
    • This is caused by an unlikely situation that can not be handled by the Socket code. This type of error requires a broader context to be resolved. As result the socket code will throw an exception that the user can catch and potentially correct from.

Socket Read/Write

| Comments

Checking read/write success

The read() and write() command can fail in a couple of ways but can also succeed without reading/writing all the data, a common mistake is not to check the amount of data read/written from/to a stream. Interestingly not all error condition are fatal and reading/writing can potentially be resumed after an error.

Read

To understand if you have read all the information that is available on a stream you need to define a communication protocol (like HTTP). For the first version of this server the protocol is very simple. Messages are passed as strings (not null terminated) and the end of the message is marked by closing the write stream. Thus a client can send one message and receive one reply with each connection it makes.

getMessage()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
 * Returns:     0   EOM reached.
 *                  The message is complete. There is no more data to be read.
 *              >0  Message data has been read (and a null terminator added).
 *                  The value is the number of bytes read from the stream
 *                  You should call getMessage() again to get the next section of the message.
 *                  Note: the message is terminated when 0 is returned.
 *              -1  An error occured.
 */
int getMessage(int socketId, char* buffer, std::ssize_t size)
{
    std::ssize_t     dataRead = 0;
    std::ssize_t     dataMax  = size - 1;

    while(dataRead < dataMax)
    {
        ssize_t get = read(socketId, buffer + dataRead, size - dataRead);
        if (get == -1)
        {
            return -1;
        }
        if (get == 0)
        {
            break;
        }
        dataRead += get;
    }
    buffer[dataRead] = '\0';
    return dataRead;
}

Read Errors

This initial version treats all read() errors as unrecoverable and getMessage() return an error state. But not all error codes need to result in a failure. So in this section I will go through some of the error codes and give some potentially actions. In a subsequent articles I may revise these actions as we cover more complex ways of interacting with sockets.

The following errors are the result of programming bugs and should not happen in production.

[EBADF]            fildes is not a valid file or socket descriptor open for reading.
[EFAULT]           Buf points outside the allocated address space.
[EINVAL]           The pointer associated with fildes was negative.
[ENXIO]            A requested action cannot be performed by the device.

If they do happen in production there is no way to correct for them pragmatically because the error has happened in another part of the code unassociated with this function.

One could argue that because these should never happen the application can abort, but for now we will settle for the read operation aborting with an error code. If we wrap this in a C++ class to control the state of the socket then exceptions may be more appropriate and we will look into that approach in a subsequent article.

The following errors are potentially recoverable from.

[EIO]              An I/O error occurred while reading from the file system.
[ENOBUFS]          An attempt to allocate a memory buffer fails.
[ENOMEM]           Insufficient memory is available.
[ETIMEDOUT]        A transmission timeout occurs during a read attempt on a socket.

But in reality recovering from them within the context of a read operation is not practical (you need to recover from these operations at a point were resource are controlled or user interaction is possible). So for now we will abort the read operation with an error code (we will revisit this in a later article).

The following error codes means that no more data will be available because the connection has been interrupted.

[ECONNRESET]       The connection is closed by the peer during a read attempt on a socket.
[ENOTCONN]         A read is attempted on an unconnected socket.

How the application reacts to a broken connection depends on the communication protocol. For the simple protocol defined above we can return any data that has been retrieved from the socket and then indicating to the calling code that we have reached the end of the message (we will revisit this in a later article). This is probably the most iffy decision in handling error codes and returning an error code could be more appropriate but I want to illustrate that we can potentially continue depending on the situation.

The following error codes are recoverable from.

[EAGAIN]           The file was marked for non-blocking I/O, and no data were ready to be read.

These error codes are generated when you have a non-blocking stream. In a future article we will discuss how to take advantage of non-blocking streams.

[EINTR]            A read from a slow device was interrupted before any data arrived by the delivery of a signal.

The exact action that you take will depend on your application (like doing some useful work) but for our simple application simply re-trying the read operation will be the standard action. Again we will come back to this, but taking advantage of timeouts will require a slightly more sophisticated approach rather than using the sockets API directly.

EINTR:
An important note about signals. There are a lot of signals that are non lethal and will result in this EINTR error code. But one should note that lethal signals like SIGINT by default will kill the application and thus will not cause this error code (as the call to read() will never return).

But you can override the SIGINT signal handler and a allow your application to continue and at this point your read operation will receive this error. How your code interacts with signals like SIGINT is beyond the scope of this article and it will be discussed just like other signals.

getMessage() Improved
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
 * Returns:     0   EOM reached.
 *                  There is no data in the buffer.
 *              >0  Message data has been read.
 *                  If the buffer is full then it is not null terminated.
 *                  If the buffer is partially full then it is null terminated
 *                  and the next call to get getMessage() will return 0.
 *              <0  An error occured.
 */
int getMessage(int socketId, char* buffer, std::ssize_t size)
{
    std::ssize_t     dataRead = 0;
    std::ssize_t     dataMax  = size - 1;

    while(dataRead < dataMax)
    {
        ssize_t get = read(socketId, buffer + dataRead, size - dataRead);
        if (get == -1)
        {
            switch(errno)
            {
                case EBADF:
                case EFAULT:
                case EINVAL:
                case ENXIO:
                    // Fatal error. Programming bug
                    return -3;
                case EIO:
                case ENOBUFS:
                case ENOMEM:
                    // Resource aquisition failure or device error
                    // Can't recover from here so indicate failure
                    // and exit
                    return -2;
                case ETIMEDOUT:
                case EAGAIN:
                case EINTR:
                    // Temporrary error.
                    // Simply retry the read.
                    continue;
                case ECONNRESET:
                case ENOTCONN:
                    // Connection broken.
                    // Return the data we have available and exit
                    // as if the connection was closed correctly.
                    get = 0;
                    break;
                default:
                    return -1;
            }
        }
        if (get == 0)
        {
            break;
        }
        dataRead += get;
    }
    buffer[dataRead] = '\0';
    return dataRead;
}

Write

The write() has exactly the same scenario as read().

The following errors are the reuls of programming bugs and should not happen in production.

 [EINVAL]           The pointer associated with fildes is negative.
 [EBADF]            fildes is not a valid file descriptor open for writing.
 [ECONNRESET]       A write is attempted on a socket that is not connected.
 [ENXIO]            A request is made of a nonexistent device, or the request is outside the capabilities of the device.
 [EPIPE]            An attempt is made to write to a socket of type SOCK_STREAM that is not connected to a peer socket.

The following errors are potentially recoverable bugs. Though recovering from them requires some form of awarness of the context that is not provided at the read level. So we must generate an error to stop reading and allow the caller to sort out the problem.

 [EDQUOT]           The user's quota of disk blocks on the file system containing the file is exhausted.
 [EFBIG]            An attempt is made to write a file that exceeds the process's file size limit or the maximum file size.
 [EIO]              An I/O error occurs while reading from or writing to the file system.
 [ENETDOWN]         A write is attempted on a socket and the local network interface used to reach the destination is down.
 [ENETUNREACH]      A write is attempted on a socket and no route to the network is present.
 [ENOSPC]           There is no free space remaining on the file system containing the file.

The following error codes are recoverable from and we covered them above in the section on read().

 [EAGAIN]           The file is marked for non-blocking I/O, and no data could be written immediately.
 [EINTR]            A signal interrupts the write before it could be completed.

The resulting put function then looks like this.

putMessage() Improved
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
 * Returns:
 *              >0  Indicates success and the number of bytes written.
 *              <0  Indicates failure.
 */
int putMessage(int socketId, char* buffer, ssize_t size)
{
    ssize_t     dataWritten = 0;

    while(dataWritten < size)
    {
        ssize_t put = write(socketId, buffer + dataWritten, size - dataWritten);
        if (put == -1)
        {
            switch(errno)
            {
                case EINVAL:
                case EBADF:
                case ECONNRESET:
                case ENXIO:
                case EPIPE:
                    // Fatal error. Programming bug
                    return -3;
                case EDQUOT:
                case EFBIG:
                case EIO:
                case ENETDOWN:
                case ENETUNREACH:
                case ENOSPC:
                    // Resource aquisition failure or device error
                    // Can't recover from here so indicate failure
                    // and exit
                    return -2;
                case EAGAIN:
                case EINTR:
                    // Temporrary error.
                    // Simply retry the read.
                    continue;
                default:
                    return -1;
            }
        }
        dataWritten += put;
    }
    return dataWritten;
}

Summary

This article has shown the most important error that people skip over when reading and writing to a socket: Not all the data was transported at the same time. The read and write command may only read/write a portion of the data that you wanted to send/receive and thus you must check the amount that actually was sent/received.

The next most important point is that not all error codes are fatal (most people actually check these) but an interrupt (EINTR) can be relatively common and you can continue reading after it has happened.

Inspiration

Socket Programming in C

| Comments

Building a simple client/server application is the common first internet based applications developers attempt. These applications are built on top of the socket communication library, but socket programming in C++ is not obvious as there are no standard libraries and thus you have to fall back to the C API. The closest “standardish” sort of thing we have is Boost.asio which is at the other end of the spectrum in terms of API and involves a cognitive leap to understand what is happening underneath (or you can just trust the library maintainers). The other alternative is libcurl; the “easy curl” layer is an abstraction of the socket() API, while the “multi curl” layer is an abstraction of the pselect() API that allows multiple sockets to be handled in a single thread.

I am writing a series of articles that start with a basic C++ client/server application and walk through building a C++ communication library. During this processes I will be using examples from codereview.stackexchange.com to illustrate common mistakes and try to show how to write the code correctly (This will also be a learning exercise for me so please let me know if you spot a mistake).

Currently the plan is to write the following articles:

  • Client/Server C
  • Client/Server C Read/Write
  • Client/Server C++ Wrapper
  • Mult-Threaded Server
  • Non-Blocking Socket
  • Co-Routines

Client/Server C++ Basic Version

The minimum example of a working Client/Server application in C++:
The full working version is here

C Serversource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <netinet/in.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define SERVER_BUFFER_SIZE      1024

int main()
{
    int socketId = socket(PF_INET, SOCK_STREAM, 0);

    struct sockaddr_in serverAddr;
    bzero((char*)&serverAddr, sizeof(serverAddr));
    serverAddr.sin_family       = AF_INET;
    serverAddr.sin_port         = htons(8080);
    serverAddr.sin_addr.s_addr  = INADDR_ANY;
    bind(socketId, (struct sockaddr *) &serverAddr, sizeof(serverAddr));

    listen(socketId, 5);

    int                         finished    = 0;
    while(!finished)
    {
        struct  sockaddr_storage    serverStorage;
        socklen_t                   addr_size   = sizeof serverStorage;
        int newSocket = accept(socketId, (struct sockaddr*)&serverStorage, &addr_size);

        char        buffer[SERVER_BUFFER_SIZE];
        int         get = read(newSocket, buffer, SERVER_BUFFER_SIZE - 1);

        buffer[get] = '\0';
        fprintf(stdout, "%s\n", buffer);

        write(newSocket, "OK", 2);

        fprintf(stdout, "Message Complete\n");

        close(newSocket);
    }
    close(socketId);
}
C Clientsource
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <arpa/inet.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define CLIENT_BUFFER_SIZE     1024

int main(int argc, char* argv[])
{
    if (argc != 3)
    {
        fprintf(stderr, "Usage: client <host> <Message>\n");
        exit(1);
    }

    int socketId = socket(PF_INET, SOCK_STREAM, 0);

    struct sockaddr_in serverAddr;
    socklen_t addrSize = sizeof(serverAddr);
    bzero((char*)&serverAddr, sizeof(serverAddr));
    serverAddr.sin_family       = AF_INET;
    serverAddr.sin_port         = htons(8080);
    serverAddr.sin_addr.s_addr  = inet_addr(argv[1]);
    connect(socketId, (struct sockaddr*)&serverAddr, addrSize);

    write(socketId, argv[2], strlen(argv[2]));

    shutdown(socketId, SHUT_WR);

    char    buffer[CLIENT_BUFFER_SIZE];
    size_t  get = read(socketId, buffer, CLIENT_BUFFER_SIZE - 1);

    buffer[get] = '\0';
    fprintf(stdout, "%s %s\n", "Response from server", buffer);

    close(socketId);
}

This version of the Client/Server actually works (a lot of the time) but obviously has a couple of major issues.

Checking Error Codes

If the calls to socket(), bind(), listen() or connect() fail then we have a catastrophic error any further actions will also fail. A few of the error codes generated by these functions can potentially be recovered from but most are programming error or permission failure as a result a human readable message with application termination is an acceptable solution (at this point).

Note: When these functions don’t succeed they set the global variable errno which can be translated into a human readable string with strerror(). So the simplest solution is to generate an appropriate error message for the user and terminate the application.

Socket Validation
1
2
3
4
5
6
int socketId = socket(PF_INET, SOCK_STREAM, 0);
if (socketId == -1)
{
    fprintf(stderr, "Failed: socket()\n%s\n", strerror());
    exit(1);
}
Bind Validation
1
2
3
4
5
6
if (bind(socketId, (struct sockaddr *) &serverAddr, sizeof(serverAddr)) == -1)
{
    fprintf(stderr, "Failed: bind()\n%s\n", strerror());
    close(socketId);    // Don't forget to close the socket.
    exit(1);
}
Listen Validation
1
2
3
4
5
6
if (listen(socketId, 5) == -1)
{
    fprintf(stderr, "Failed: connect()\n%s\n", strerror());
    close(socketId);    // Don't forget to close the socket.
    exit(1);
}
Connect Validation
1
2
3
4
5
6
if (connect(socketId, (struct sockaddr*)&serverAddr, addrSize) == -1)
{
    fprintf(stderr, "Failed: connect()\n%s\n", strerror());
    close(socketId);    // Don't forget to close the socket.
    exit(1);
}

Summary

The basic socket programs are relatively trivial. But this version 1 has some obvious flaws the major one being checking error states (which a lot of beginners forget in their first version). The next article will look into some more details about read and write operations on the socket.

Inspiration for Article

Memory Resizing

| Comments

So I never really considered why the resize of vector used a constant expansion of 1.5 or 2 (in some popular implementations). That was until I did my previous article series “Vector” where I concentrated a lot on resource management and did a section on resizing the vector. Originally in the code I tried to be clever, a mistake. I used a resize value of 1.62 (an approximation of Phi), because I vaguely remembered reading an article that this was the optimum resize factor. When I put this out for code review it was pointed out to me that this value was too large, the optimum value must be less than or equal to Phi (1.6180339887) and that exceeding this limit actually made things a lot worse.

So I had to know why….

So the theory goes: You have a memory resource of size B. If you resize this resource by a constant factor r by re-allocating a new block then releasing the old block. Then if the value of r is smaller than or equal to Phi you will eventually be able to reuse memory that has previously been released; otherwise the new block of memory being allocated will always be larger than the previously released memory.

So I thought lets try that:
Test one r > Phi:

B=10
r=2.0

            Sum Memory      Memory      Memory Needed       Difference
             Released     Allocated     Next Iteration
Start            0            10              20                 20
Resize 1        10            20              40                 30
Resize 2        30            40              80                 50
Resize 3        70            80             160                 90
Resize 4       150           160             320                170

OK. That seems to be holding (at least in the short term). Lo lets try a smaller value.
Test two r < Phi:

B=10
r=1.5

            Sum Memory      Memory      Memory Needed       Difference
             Released     Allocated     Next Iteration
Start            0            10              15                 15
Resize 1        10            15              22                 12
Resize 2        25            22              33                  8
Resize 3        47            33              48                  1
Resize 4        80            48              72                 -8 // Reuse released memory next iteration

OK. That also seems to be holding. But can we show that holds for all values of B? Also this is a bit anecdotal can we actually show this relationship actually hold? Time to break out some maths (not math as my American cousins seem to insist on for the shortening of mathematics).

So the size S of any block after n resize operations will be:

\[ S = Br^n \]

Thus the size of Released Memory can be expressed as:

\[ \sum_{k=0}^{n-1}\ Br^k \]

Also the size of the next block will be:

\[ Br^{n+1} \]

So if the amount of Released Memory >= the amount required for the next block, then we can reuse the Released Memory.

\[ \sum_{k=0}^{n-1}\ Br^k >= Br^{n+1} \] \[ B \sum_{k=0}^{n-1}\ r^k >= Br^{n+1} \] \[ \sum_{k=0}^{n-1}\ r^k >= r^{n+1} \] \[ {1-r^{(n-1)+1}\over1-r} >= r^{n+1} \] \[ {1-r^n\over1-r} >= r^{n+1} \] \[ 1-r^n >= r^{n+1} (1-r) \] \[ 1-r^n >= r^{n+1} - r^{n+2} \] \[ 1 + r^{n+2} - r^{n+1} - r^n >= 0 \] \[ 1 + r^n (r^2 - r - 1) >= 0 \]

This is were my maths broke down and I had to plot some graphs (my old “maths” teacher would have been so proud).

"n=4" "n=8"



So after looking at the graphs (to understand the formula) then talking to some smart people.
They noticed that:

\[ (r^2 - r - 1) root . when . r = \Phi \]

We find that the first root of the equation is 1. The second root of the equation depends on n, as n tends to infinity the other root tends towards Phi. From this we can infer the following:

\[ 1 < r <= \Phi \]

Thus if r remains in the above range then the above theory holds.

Vector - the Other Stuff

| Comments

So the C++ standard specifies a set of requirements for containers. Very few requirements are specified in terms of containers so adhering to these exactly is not required (unless you want to be considered for the standard). But they provide an insight into what can be done with them and if you support them will allow your container to be more easily used with some features of the language and standard library. I am not going to go over all of them here (that is left as an exercise for the reader), but I will go over the ones I would expect to see in a simple implementation (the kind you would see in a university project).

For details see the latest copy of the C++ standard.

  • 23.2.1 General container requirements [container.requirements.general]
  • 23.2.3 Sequence containers [sequence.reqmts]

Internal Types

  • value_type
  • reference
  • const_reference
  • iterator
  • const_iterator
  • difference_type
  • size_type

It is worth specifying the internal types defined here. As this allows you to abstract the implementation details of the container. This will allow you to change the implementation details without users having to change their implementation; as long as the changes still provide the same interface but the interface to reference/pointers/iterators are relatively trivial and well defined.

Constructors

In C++11 the std::initializer_list<T> was introduced. This allows a better list initialization syntax to be used with user defined types. Since this is usually defined in terms of the range based construction we should probably add both of these constructors.

  • Vector(std::initializer_list const& list)
  • Vector(I begin, I end)

Iterators

  • begin()
  • rbegin()
  • begin() const
  • rbegin() const
  • cbegin() const
  • crbegin() const
  • end()
  • rend()
  • end() const
  • cend() const
  • rend() const
  • crend() const

The iterators are relatively easy to write. They also allow the container to be used with the new range based for that was added in C++14. So this becomes another easy add.

Member Access

  • at(<index>)
  • at(<index>) const
  • operator[](<index>)
  • operator[](<index>) const
  • front()
  • back()
  • front() const
  • back() const

Member access to a vector should be very efficient. As a result normally range checks are not performed on member access, i.e. the user is expected to make sure that the method preconditions have been met before calling the method. This results in very efficient access to the members of a Vector. This is not normally a problem because index ranges are normally checked as part of a loop range as long as these are validated against the size of the array it does not need to be validated again.

For Loop Vector Access
1
2
3
4
5
6
7
    Vector<T>   d = getData();
    for(int loop = 0; loop < d.size(); ++loop)
    {
        std::cout << d[loop];   // No need for antoher range
                                // check here as we know that loop is inside the
                                // bounds of the vector d.
    }

There is also the at() method which does validate the index provided before accessing the element (throwing an exception if the index is out of range).

Non-Mutating Member Functions

  • size() const
  • bool() const

To allow us to check the preconditions on the element access methods we need some functions that check the state of the object. These are provided here.

Mutating Member Functions

  • push_back(<object-ref>)
  • push_back(<object-rvalue-ref>)
  • emplace_back(<args…>)
  • pop_back()

The following members are standard easy to implement methods of std::vector (O(1)) that I would expect to see in every implementation.

The other mutating member functions are less trivial as they require elements to be moved around. They are not that hard but you must put some thought into the most efficient techniques to move elements (i.e. move or copy) and make sure that capacity is not exceeded by multiple inserts. As a result I would expect to see these methods only on an as needed basis.

Comparators

  • operator== const
  • operator!= const

Easy comparison operators. Optionally you can provide the other comparison operators.

Final

No idea why Jackal is adding all the blank lines to my source

Vector
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
#include <type_traits>
#include <memory>
#include <algorithm>
#include <stdexcept>
#include <iterator>

template<typename T>
class Vector

    public:
        using value_type        = T;
        using reference         = T&;
        using const_reference   = T const&;
        using pointer           = T*;
        using const_pointer     = T const*;
        using iterator          = T*;
        using const_iterator    = T const*;
        using riterator         = std::reverse_iterator<iterator>;
        using const_riterator   = std::reverse_iterator<const_iterator>;
        using difference_type   = std::ptrdiff_t;
        using size_type         = std::size_t;

    private:
        size_type       capacity;
        size_type       length;
        T*              buffer;

        struct Deleter
        {
            void operator()(T* buffer) const
            {
                ::operator delete(buffer);
            }
        };

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        template<typename I>
        Vector(I begin, I end)
            : capacity(std::distance(begin, end))
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            for(auto loop = begin;loop != end; ++loop)
            {
                pushBackInternal(*loop);
            }
        }
        Vector(std::initializer_list<T> const& list)
            : Vector(std::begin(list), std::end(list))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
            clearElements<T>();
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
                clearElements<T>();

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            copyAssign<T>(copy);
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }

        // Non-Mutating functions
        size_type           size() const                        {return length;}
        bool                empty() const                       {return length == 0;}

        // Validated element access
        reference           at(size_type index)                 {validateIndex(index);return buffer[index];}
        const_reference     at(size_type index) const           {validateIndex(index);return buffer[index];}

        // Non-Validated element access
        reference           operator[](size_type index)         {return buffer[index];}
        const_reference     operator[](size_type index) const   {return buffer[index];}
        reference           front()                             {return buffer[0];}
        const_reference     front() const                       {return buffer[0];}
        reference           back()                              {return buffer[length - 1];}
        const_reference     back() const                        {return buffer[length - 1];}

        // Iterators
        iterator            begin()                             {return buffer;}
        riterator           rbegin()                            {return riterator(end());}
        const_iterator      begin() const                       {return buffer;}
        const_riterator     rbegin() const                      {return const_riterator(end());}

        iterator            end()                               {return buffer + length;}
        riterator           rend()                              {return riterator(begin());}
        const_iterator      end() const                         {return buffer + length;}
        const_riterator     rend() const                        {return const_riterator(begin());}

        const_iterator      cbegin() const                      {return begin();}
        const_riterator     crbegin() const                     {return rbegin();}
        const_iterator      cend() const                        {return end();}
        const_riterator     crend() const                       {return rend();}

        // Comparison
        bool operator!=(Vector const& rhs) const {return !(*this == rhs);}
        bool operator==(Vector const& rhs) const
        {
            return  (size() == rhs.size())
                &&  std::equal(begin(), end(), rhs.begin());
        }

        // Mutating functions
        void push_back(value_type const& value)
        {
            resizeIfRequire();
            pushBackInternal(value);
        }
        void push_back(value_type&& value)
        {
            resizeIfRequire();
            moveBackInternal(std::move<T>(value));
        }
        template<typename... Args>
        void emplace_back(Args&&... args)
        {
            resizeIfRequire();
            emplaceBackInternal(std::move<T>(args)...);
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
        void reserve(size_type capacityUpperBound)
        {
            if (capacityUpperBound > capacity)
            {
                reserveCapacity(capacityUpperBound);
            }
        }
    private:
        void validateIndex(size_type index) const
        {
            if (index >= length)
            {
                throw std::out_of_range("Out of Range");
            }
        }

        void resizeIfRequire()
        {
            if (length == capacity)
            {
                size_type     newCapacity  = std::max(2.0, capacity * 1.5);
                reserveCapacity(newCapacity);
            }
        }
        void reserveCapacity(size_type newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            simpleCopy<T>(tmpBuffer);

            tmpBuffer.swap(*this);
        }

        // Add new element to the end using placement new
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::move(value));
            ++length;
        }
        template<typename... Args>
        void emplaceBackInternal(Args&&... args)
        {
            new (buffer + length) T(std::move<Args>(args)...);
            ++length;
        }

        // Optimizations that use SFINAE to only instantiate one
        // of two versions of a function.
        //      simpleCopy()        Moves when no exceptions are guaranteed, otherwise copies.
        //      clearElements()     When no destructor remove loop.
        //      copyAssign()        Avoid resource allocation when no exceptions guaranteed.
        //                          ie. When copying integers reuse the buffer if we can
        //                          to avoid expensive resource allocation.

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T const& v){dst.pushBackInternal(v);}
                         );
        }
        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T& v){dst.moveBackInternal(std::move(v));}
                         );
        }


        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
        clearElements()
        {
            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }

        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
        clearElements()
        {
            // Trivially destructible objects can be reused without using the destructor.
        }

        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                            &&  std::is_nothrow_destructible<X>::value) == true>::type
        copyAssign(Vector<X>& copy)
        {
            // This function is only used if there is no chance of an exception being
            // thrown during destruction or copy construction of the type T.


            // Quick return for self assignment.
            if (this == &copy)
            {
                return;
            }

            if (capacity <= copy.length)
            {
                // If we have enough space to copy then reuse the space we currently
                // have to avoid the need to perform an expensive resource allocation.

                clearElements<T>();     // Potentially does nothing (see above)
                                        // But if required will call the destructor of
                                        // all elements.

                // buffer now ready to get a copy of the data.
                length = 0;
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    pushBackInternal(copy[loop]);
                }
            }
            else
            {
                // Fallback to copy and swap if we need to more space anyway
                Vector<T>  tmp(copy);
                tmp.swap(*this);
            }
        }

        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                             &&  std::is_nothrow_destructible<X>::value) == false>::type
        copyAssign(Vector<X>& copy)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
        }
};

Vector - Simple Optimizations

| Comments

So now that we have used std::is_nothrow_move_constructible we can also look at a couple of other types available in the template utility library.

Optimized Destruction

Since we have to manually call the destructor on all objects in the container (because we are using placement new) we can look to see if we can optimize that. The type std::is_trivially_destructible detects if the type is Trivially destructible. This basically means that there will be no side effects from the destructor (See: Section 12.4 Paragraph 5 of the standard). For types we don’t need to call the destructor of the object. For the Vector class this means we can eliminate the call to the destructor but more importantly the loop.

Destroying Elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
    ~Vector()
    {
        // STUFF..

        // Call the destructor on all the members in reverse order
        for(int loop = 0; loop < length; ++loop)
        {
            // Note we destroy the elements in reverse order.
            buffer[length - 1 - loop].~T();
        }
    }
    Vector(Vector const& copy)
        : capacity(copy.length)
        , length(0)
        , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
    {
        try
        {
            // STUFF 1 ...
        }
        catch(...)
        {
            // STUFF 2 ...
            // If there was an exception then destroy everything
            // that was created to make it exception safe.
            for(int loop = 0; loop < length; ++loop)
            {
                buffer[length - 1 - loop].~T();
            }
            throw;
        }
    }

We can use the same SFINAE technique that we used in the previous article to remove the loops when the contained type is trivially destructible.

Destroying Elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    ~Vector()
    {
        // STUFF..
        clearElements<T>();
    }
    Vector(Vector const& copy)
        : capacity(copy.length)
        , length(0)
        , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
    {
        try
        {
            // STUFF 1 ...
        }
        catch(...)
        {
            // STUFF 2 ...
            clearElements<T>();
            throw;
        }
    }

    template<typename X>
    typename std::enable_if<std::std::is_trivially_destructible<X>::value == false>::type
    clearElements()
    {
        // Call the destructor on all the members in reverse order
        for(int loop = 0; loop < length; ++loop)
        {
            // Note we destroy the elements in reverse order.
            buffer[length - 1 - loop].~T();
        }
    }

    template<typename X>
    typename std::enable_if<std::std::is_trivially_destructible<X>::value == true>::type
    clearElements()
    {
        // Trivially destructible objects can be re-used without using the destructor.
    }

Optimized Assignment Operator

The final optimization is because resource allocation is expensive. So if we can avoid the resource allocation completely and just reuse the space we currently have.

Copy Assignment
1
2
3
4
5
6
7
    Vector& operator=(Vector const& copy)
    {
        // Copy and Swap idiom
        Vector<T>  tmp(copy);
        tmp.swap(*this);
        return *this;
    }

The copy and swap idiom is perfect for providing the strong exception guarantee in the presence of exceptions. But if there are no exceptions during destruction or construction then we can potentially just reuse the available memory. So if we rewrote the assignment operator with the assumption that there were no exceptions it would look like the following (Note in the real code use SFINAE to do the optimization only when necessary).

Copy the easy way
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    Vector& operator=(Vector const& copy)
    {
        // Check for self assignment
        // As we are doing work anyway.
        if (this == &copy)
        {
            return *this;
        }

        // If the length of the `copy` object exceeds
        // the capacity of the current object then
        // we have to do resource management. It costs
        // nothing extra to use the copy and swap idiom
        if (copy.length > capacity)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
            return *this;
        }

        // The optimization happens here.
        // We can reuse the buffer we already have.
        clearElements<T>();     // use clearElements() as it probably does very little.
        length = 0;

        // Now add the elements to this container as cheaply as possible.
        for(int loop = 0; loop < copy.length; ++loop)
        {
            pushBackInternal(copy[loop]);
        }
        return *this;
    }

Final Version

The final version

Vector Final Version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
template<typename T>
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;

    struct Deleter
    {
        void operator()(T* buffer) const
        {
            ::operator delete(buffer);
        }
    };

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());

            clearElements<T>();
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
                clearElements<T>();

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            copyAssign<T>(copy);
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }
        void push_back(T const& value)
        {
            resizeIfRequire();
            pushBackInternal(value);
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
        void reserve(std::size_t capacityUpperBound)
        {
            if (capacityUpperBound > capacity)
            {
                reserveCapacity(capacityUpperBound);
            }
        }
    private:
        void resizeIfRequire()
        {
            if (length == capacity)
            {
                std::size_t     newCapacity  = std::max(2.0, capacity * 1.5);
                reserveCapacity(newCapacity);
            }
        }
        void reserveCapacity(std::size_t newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            simpleCopy<T>(tmpBuffer);

            tmpBuffer.swap(*this);
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::move(value));
            ++length;
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T const& v){dst.pushBackInternal(v);}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T& v){dst.moveBackInternal(std::move(v));}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
        clearElements()
        {
            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }

        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
        clearElements()
        {
            // Trivially destructible objects can be reused without using the destructor.
        }

        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                             &&  std::is_nothrow_destructible<X>::value) == true>::type
        copyAssign(Vector<X>& copy)
        {
            if (this == &copy)
            {
                return;
            }

            if (capacity <= copy.length)
            {
                clearElements<T>();
                length = 0;
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    pushBackInternal(copy[loop]);
                }
            }
            else
            {
                // Copy and Swap idiom
                Vector<T>  tmp(copy);
                tmp.swap(*this);
            }
        }
        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                             &&  std::is_nothrow_destructible<X>::value) == false>::type
        copyAssign(Vector<X>& copy)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
        }
};

Summary

Vector - Resize

| Comments

Because resizing a vector is expensive; the std::vector class uses exponential growth to minimize the number of times that the vector is resized: a technique we replicate in this version. But every now and then you still need to resize the internal buffer.

In the current version, resizing the vector requires allocating a new buffer and copying all the members into it. Basically we are using the copy and swap idiom to provide the strong exception guarantee (If an exception is thrown all resources are cleaned up and the object remains unchanged).

Vector Resize with Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    void pushBackInternal(T const& value)
    {
        new (buffer + length) T(value);
        ++length;
    }

    void reserveCapacity(std::size_t newCapacity)
    {
        Vector<T>  tmpBuffer(newCapacity);
        std::for_each(buffer, buffer + length,
                      [&tmpBuffer](T const& v){tmpBuffer.pushBackInternal(v);}
                     );

        tmpBuffer.swap(*this);
    }

Resize With Move Construction

Thus resizing a Vector can be a very expensive operation because of all the copying that can happen.

Using the move constructor rather than the copy constructor during a resize operation could potentially be much more efficient. But the move constructor mutates the original object and thus if there is a problem we need to undo the mutations to maintain the strong exception guarantee.

The first attempt at this is:

Vector Resize with Move With Exceptions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
    void moveBackInternal(T&& value)
    {
        new (buffer + length) T(std::move(value));
        ++length;
    }

    void reserveCapacity(std::size_t newCapacity)
    {
        Vector<T>  tmpBuffer(newCapacity);
        try
        {
            std::for_each(buffer, buffer + length,
                          [&tmpBuffer](T& v){tmpBuffer.moveBackInternal(std::move(v));}
                         );
        }
        catch(...)
        {
            // If an exception is thrown you need to move the objects back
            // from the temporary buffer back to this object.
            for(int loop=0; loop < tmpBuffer.length; ++loop)
            {
                // The problem is here:
                // If the initial move can throw,
                // then trying to move any of the objects back can also throw.
                // which would leave the object in an inconsistent state.
                buffer[loop] = std::move(tmpBuffer[loop]);
            }

            // Then remember to rethrow the exception after we have fixed the state.
            throw;
        }

        tmpBuffer.swap(*this);
    }

Resize With NoThrow Move Construction

As the above code shows; if the type T can throw during its move constructor then you can’t guarantee that the object gets returned to the original state (as moving the already moved elements back may cause another exception). So we cannot use the move constructor to resize the vector if the type T can throw during move construction.

But not all types throw when being moved. In fact it is recommended that move constructors never throw. If we can guarantee that the move constructor does not throw then we can simplify the above code considerably and still provide the strong exception guarantee.

Vector Resize with Move
1
2
3
4
5
6
7
8
9
10
11
12
13
14
    void reserveCapacity(std::size_t newCapacity)
    {
        Vector<T>  tmpBuffer(newCapacity);
        std::for_each(buffer, buffer + length,
                      [&tmpBuffer](T& v){tmpBuffer.moveBackInternal(std::move(v));}
                     );

        tmpBuffer.swap(*this);
    }
    void moveBackInternal(T&& value)
    {
        new (buffer + length) T(std::move(value));
        ++length;
    }

Resize Template Specialization

So now we have to write the code that decides at compile time which version we should use. The simplest way to do this is to use template specialization of a class using the standard class std::is_nothrow_move_constructible<T> to help differentiate types that have a non-throwing move constructor. This is simple enough:

Template class Specialization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
template<typename T, bool = std::is_nothrow_move_constructible<T>::value>
struct SimpleCopy
{
    // Define two different versions of this class.
    // The object is to copy all the elements from src to dst Vector
    // using pushBackInternal or moveBackInternal
    //
    // SimpleCopy<T, false>:        Defines a version that use pushBackInternal (copy constructor)
    //                              This is always safe to use.
    // SimpleCopy<T, true>:         Defines a version that uses moveBackInternal (move constructor)
    //                              Safe when move construction does not throw.
    //
    void operator()(Vector<T>& src, Vector<T>& dst) const;
};
template<typename T>
class Vector
{
    public:
        .....
    private:
        // We are using private methods for effeciency.
        // So these classes need to be friends.
        friend struct SimpleCopy<T, true>;
        friend struct SimpleCopy<T, false>;

        void reserveCapacity(std::size_t newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            // Create the copier object base on the type T.
            // Note: The second parameter is automatically generated based
            //       on if the type T is move constructable with no exception.
            SimpleCopy<T>   copier;
            copier(*this, tmpBuffer);

            tmpBuffer.swap(*this);
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::move(value));
            ++length;
        }
}
// Define the two different types of copier
template<typename T>
struct SimpleCopy<T, false> // false: does not have nothrow move constructor
{
    void operator()(Vector<T>& src, Vector<T>& dst) const
    {
        std::for_each(buffer, buffer + length,
                      [&dst](T const& v){dst.pushBackInternal(v);}
                     );
    }
};
template<typename T>
struct SimpleCopy<T, true> // true: has a nothrow move constructor
{
    void operator()(Vector<T>& src, Vector<T>& dst) const
    {
        std::for_each(buffer, buffer + length,
                      [&dst](T& v){dst.moveBackInternal(std::move(v));}
                     );
    }
};

Resize With NoThrow SFINAE

The above technique has a couple of issues.

The type SimpleClass is publicly available and is a friend of Vector<T>. This makes it susceptible to accidentally being used (even if not explicitly documented). Unfortunately it can’t be included as a member class and also be specialized.

Additionally it looks awful!!

But we can also use SFINAE and method overloading.

SFINAE allows us to define several versions of a method with exactly the same arguments, as long as only one of them is valid at compile time. So in the example below we define two versions of the method SimpleCopy(Vector<T>& src, Vector<T>& dst) but then use std::enable_if to make sure only one version of the function is valid at compile time.

SFINAE method overload
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
template<typename T>
class Vector
{
    public:
        .....
    private:
        void reserveCapacity(std::size_t newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            SimpleCopy<T>(*this, tmpBuffer);

            tmpBuffer.swap(*this);
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::move(value));
            ++length;
        }

        template<typename X>
        // Note: this defines the return type of the function.
        //       But only one has a valid member `type` thus only
        //       one of the following functions is actually valid.
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
        simpleCopy(Vector<T>& src, Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T const& v){dst.pushBackInternal(v);}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
        simpleCopy()(Vector<T>& src, Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T& v){dst.moveBackInternal(std::move(v));}
                         );
        }
}

Final Version

Vector Final Version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
template<typename T>
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;

    struct Deleter
    {
        void operator()(T* buffer) const
        {
            ::operator delete(buffer);
        }
    };

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());

            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
                // If there was an exception then destroy everything
                // that was created to make it exception safe.
                for(int loop = 0; loop < length; ++loop)
                {
                    buffer[length - 1 - loop].~T();
                }

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }
        void push_back(T const& value)
        {
            resizeIfRequire();
            pushBackInternal(value);
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
        void reserve(std::size_t capacityUpperBound)
        {
            if (capacityUpperBound > capacity)
            {
                reserveCapacity(capacityUpperBound);
            }
        }
    private:
        void resizeIfRequire()
        {
            if (length == capacity)
            {
                std::size_t     newCapacity  = std::max(2.0, capacity * 1.5);
                reserveCapacity(newCapacity);
            }
        }
        void reserveCapacity(std::size_t newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            simpleCopy<T>(tmpBuffer);

            tmpBuffer.swap(*this);
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::move(value));
            ++length;
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T const& v){dst.pushBackInternal(v);}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T& v){dst.moveBackInternal(std::move(v));}
                         );
        }
};

Summary

This article has gone over the design of resizing the internal buffer. We have covered a couple of techniques on the way:

  • Move Constructor Concepts
  • Template Class Specialization
  • SFINAE
  • std::is_nothrow_move_constructible<>
  • std::enable_if<>

Vector - Resource Management Copy Swap

| Comments

In the previous article I went over basic allocation for a Vector like class. In this article I want to put some detail around the copy assignment operator and resizing the underlying Vector. Unlike the other methods previously discussed these methods have to deal with both construction and destruction of elements and the potential of exceptions interrupting the processes. The goal is to provide exception safe methods that provide the strong exception guarantee for the object and do not leak resources.

Copy Assignment

First Try

This is a very common first attempt at a copy constructor. It simply calls the destructor on all elements currently in the object. Then uses the existing push_back() method to copy member elements from the source object, thus allowing the object to automatically resize if required.

Copy Assignment (Try 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF
    Vector& operator=(Vector const& copy)
    {
        if (&copy == this)
        {
            // Early exit for self assignment
            return *this;
        }
        // First we have to destroy all the current elements.
        for(int loop = 0; loop < length; ++loop)
        {
            // Destroy in reverse order
            buffer[length - 1 - loop].~T();
        }
        // Now the buffer is empty so reset size to zero.
        length = 0;

        // Now copy all the elements from the source into this object
        for(int loop = 0; loop < copy.length; ++loop)
        {
            push_back(copy.buffer[loop]);
        }
        return *this;
    }
};

Strong Exception Guarantee

The obvious problems about efficiency when a resize is required is a minor issue here. The real problem is that this does not provide the strong exception guarantee. If any of the constructors/destructor throw then the object will be left in an inconsistent state with no way to restore the original state. The strong exception guarantee basically means that the operation works or does not change the state of the object. The easiest technique to achieve this is to create a copy in a new temporary buffer that can be thrown away if things go wrong (leaving the current object untouched). If the copy succeeds then we use it and throw away the original data.

Copy Assignment (Try 2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF
    Vector& operator=(Vector const& copy)
    {
        if (&copy == this)
        {
            // Early exit for self assignment
            return *this;
        }
        // Part-1 Create a copy of the src object.
        std::size_t tmpCap    = copy.length;
        std::size_t tmpSize   = 0;
        T*          tmpBuffer = static_cast<T*>(::operator new(sizeof(T) * tmpCap));

        // Now copy all the elements from the source into the temporary object
        for(int loop = 0; loop < copy.length; ++loop)
        {
            new (tmpBuffer + tmpSize) T(copy.buffer[loop]);
            ++tmpSize;
        }

        // Part-2 Swap the state
        // We have successfully created the new version of this object
        // So swap the temporary and object states.
        std::swap(tmpCap,    capacity);
        std::swap(tmpSize,   length);
        std::swap(tmpBuffer, buffer);

        // Part-3 Destroy the old state.
        // Now we have to delete the old state.
        // If this fails it does not matter the state of the object is consistent
        for(int loop = 0; loop < tmpSize; ++loop)
        {
            tmpBuffer[tmpSize - 1 - loop].~T();
        }
        ::operator delete(tmpBuffer);
        return *this;
    }
};

Copy and Swap

This second attempt is a better attempt. But it still leaks if an exception is throw. But before we add exception handling, let us take a closer look at the three sections of the assignment operator.

Part-1 looks exactly like the copy constructor of Vector.

Copy Assignment Part 1
1
2
3
4
5
6
7
8
9
10
11
    std::size_t tmpCap    = copy.length;
    std::size_t tmpSize   = 0;
    T*          tmpBuffer = static_cast<T*>(::operator new(sizeof(T) * tmpCap));

    // Now copy all the elements from the source into the temporary object
    for(int loop = 0; loop < copy.length; ++loop)
    {
        // This looks exactly like push_back()
        new (tmpBuffer + tmpSize) T(copy.buffer[loop]);
        ++tmpSize;
    }

Part-3 looks exactly like destructor of Vector.

Copy Assignment Part 3
1
2
3
4
5
6
    // Now we have to delete the old state.
    for(int loop = 0; loop < tmpSize; ++loop)
    {
        tmpBuffer[tmpSize - 1 - loop].~T();
    }
    ::operator delete(tmpBuffer);

Using these two observations we have a rewrite of the copy assignment operator.

Copy Assignment (Try 3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF
    Vector& operator=(Vector const& copy)
    {
        if (&copy == this)
        {
            // Early exit for self assignment
            return *this;
        }
        // Part-1 Create a copy
        Vector  tmp(copy);

        // Part-2 Swap the state
        std::swap(tmp.capacity, capacity);
        std::swap(tmp.length,   length);
        std::swap(tmp.buffer,   buffer);

        return *this;
        // Part-3 Destructor called at end of scope.
        // No actual code required here.
    }
};

Copy And Swap Idiom

The copy and swap idiom is about dealing with replacing an object state from another object. It is very commonly used in the copy assignment operator but has application whenever state is being changed and the strong exception guarantee is required.

The above code works perfectly. But in Part-2 the swap looks like a normal swap operation so let’s use that rather than doing it manually. Also self assignment now works without the need for a test (because we are copying into a temporary). So we can remove the check for self assignment. Yes this does make the performance for self assignment worse, but it makes the normal operation even more efficient. Since the occurrence of self assignment is extremely rare I would not prematurely optimize for it but rather make the most common case the best optimized. So one final re-factor of the copy constructor leaves us with this.

Copy Assignment (Try 4)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF
    Vector& operator=(Vector const& copy)
    {
        Vector  tmp(copy);
        tmp.swap(*this);
        return *this;
    }
    void swap(Vector& other) noexcept
    {
        std::swap(other.capacity, capacity);
        std::swap(other.length,   length);
        std::swap(other.buffer,   buffer);
    }
};

Resizing Underlying buffer

When pushing data into the array we need to verify that capacity has not been exceeded. If it has then we need to allocate more capacity then copy the current content into the new buffer and destroy the old buffer after calling the destructor on all elements.

Using Copy and Swap

This operation is exceedingly similar to the description of the copy assignment operator. As a result the best solution looks very similar and uses the Copy and Swap idiom.

Vector Reallocating Buffer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF
    void resizeIfRequire()
    {
        if (length == capacity)
        {
            // Create a temporary object with a larger capacity.
            std::size_t     newCapacity  = std::max(2.0, capacity * 1.5);
            Vector<T>  tmpBuffer(newCapacity);

            // Copy the state of this object into the new object.
            std::for_each(buffer, buffer + length, [&tmpBuffer](T const& item){tmpBuffer.push_back(item);});

            // All the work has been successfully done. So swap
            // the state of the temporary and the current object.
            tmpBuffer.swap(*this);

            // The temporary object goes out of scope here and
            // tidies up the state that is no longer needed.
        }
    }
};

Final Version

Vector Final Version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
template<typename T>
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;

    struct Deleter
    {
        void operator()(T* buffer) const
        {
            ::operator delete(buffer);
        }
    };

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());

            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
                // If there was an exception then destroy everything
                // that was created to make it exception safe.
                for(int loop = 0; loop < length; ++loop)
                {
                    buffer[length - 1 - loop].~T();
                }

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }
        void push_back(T const& value)
        {
            resizeIfRequire();
            pushBackInternal(value);
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
        void reserve(std::size_t capacityUpperBound)
        {
            if (capacityUpperBound > capacity)
            {
                reserveCapacity(capacityUpperBound);
            }
        }
    private:
        void resizeIfRequire()
        {
            if (length == capacity)
            {
                std::size_t     newCapacity  = std::max(2.0, capacity * 1.5);
                reserveCapacity(newCapacity);
            }
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void reserveCapacity(std::size_t newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);
            std::for_each(buffer, buffer + length, [&tmpBuffer](T const& v){tmpBuffer.pushBackInternal(v);});

            tmpBuffer.swap(*this);
        }
};

Summary

This article has gone over the design of the Copy and Swap idiom and shown how it is used in the Copy Assignment Operator and the resize operation.

  • Separation Of Concerns
  • Copy and Swap Idiom
  • Exception Gurantees

Vector - Resource Management Allocation

| Comments

A lot of new developers to C++ attempt to build a Vector like container as a learning processes. Getting a simple version of this working for POD types (like int) is not that complicated. The next step in getting this working for arbitrary data types takes a significant leap forward in thinking in C++ especially when you start looking at efficiency and exception safety. This set of five articles looks at building an efficient Vector implementation. I show some of the common mistakes and explain why and how to resolve the problems:

Note: This is not meant to replace std::vector<> this is simply meant as a teaching process.

Rule of Zero

You will notice that half the attempts below Sources are Vector implementations the other half are for Matrix implementations. I mention both because I want to emphasize the Separation of concerns. An object should be responsible for either business logic or resource management (not both). A lot of the Matrix implementations are trying to mix resource management (memory management) with the business logic of how matrices interact. So if you want to write a matrix class you should delegate resource management to a separate class (In a first pass std::vector<int> would be a good choice).

In C++ the compiler generates a couple of methods for free.

  • Destructor
  • Copy Constructor
  • Copy Assignment Operator
  • Move Constructor
  • Move Assignment Operator

These methods usually work perfectly well; unless your class contains a pointer (or a pointer like resource object). But if your class is doing business logic then it should not contain a pointer. So classes that handle business logic therefore should not be defining any of these compiler generated methods (just let the compiler generated ones work for you). Occasionally you want to delete them, to prevent copying or movement, but it is very unusual for these to need specialized implementations.

Conversely, classes that do resource management usually contain a pointer (or pointer like resource object). These classes should define all the above methods to correctly handle the resource. This is where ownership semantics of the resource are defined. The owner of the resource is responsible for destroying the resource when its lifespan is over (in terms of pointers this means the owner is responsible for calling delete on the pointer, usually in the destructor). If you are not the owner of a resource you should not have access to the resource object directly, as it may be destroyed by the owner without other objects knowing.

Rule of three

The rule of three comes from C++03 where we only had copy semantics.

Version-1 Simple Resource Management

When creating a class to manage resources; the first version created by beginner usually looks like this:

Rule of three first pass
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
class Vector
{
    std::size_t     size;
    T*              buffer;
    Vector(int size = 100)
        : size(size)
        , buffer(new T[size])   // Allocate the resource
    {}
    ~Vector()
    {
        delete [] buffer;       // Clean up the resource
    }
};

The trouble here is that this version has a fundamental flaw because of the way the compiler generated copy constructor and copy assignment operator work with pointers (commonly referred to as the shallow copy problem).

Shallow copy problem.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
    Vector<int>   x;
    Vector<int>   y(x);     // Compiler generate copy constructure does
                            // an element wise shallow copy of each element.
                            // This means both `x` and `y` have a buffer
                            // member that points at the same area in memory.
                            //
                            // When the objects go out of scope both will
                            // try and call delete on the memory resulting
                            // in a double delete of the memory.

    Vector<int>   z;        // Same problem after an assignment.
    z=x;
}

Version-2 Rule of Three

The rule of three simply stated is: If you define any of the methods Destructor/Copy Constructor/Copy Assignment Operator then you should define all three. When done correctly this resolves the shallow copy problem. Vector defines the destructor so we also need to define the copy constructor and copy assignment operator.

I see this as an initial attempt at defining the rule of three for vectors very often.

Rule of three second pass
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template<typename T>
class Vector
{
    std::size_t     size;
    T*              buffer;
    Vector(int size = 100)
        : size(size)
        , buffer(new T[size])
    {}
    ~Vector()
    {
        delete [] buffer;
    }
    Vector(Vector const& copy)
        : size(copy.size)
        , buffer(new T[size])
    {
        // Copy constructor is simple.
        // We create a new resource area of the required size.
        // Then we copy the data from the old buffer to the new buffer.
        std::copy(copy.buffer, copy.buffer + copy.size, buffer);
    }
    Vector& operator=(Vector const& copy)
    {
        // Copy Object
        // This is relatively easy. But I want to cover this in detail in a subsquent post.
        return *this;
    }
};

Version-3 Lazy Construction of elements.

The problem with the previous version is that it forces initialization of all elements in the buffer immediately. This forces the requirement that members of the Vector (i.e. type T) must be default constructable. It also has two efficiency constraints imposed on the Vector:

  • You can’t pre-allocate space for future members.
    • So resizing (larger or smaller) becomes very expensive as each resize requires copy all the elements to the newly re-sized buffer.
    • Alternatively pre-creating all the elements you need can also be expensive especially if construction of T is expensive.
  • The copy constructor is twice as expensive as it should be. Each element must be:
    • Default constructed (when the buffer is created).
    • Then copy constructed with the value from the source vector.

This attempt improves on that by allowing efficient pre-allocating of space (capacity) for the buffer. New members are then added by constructing in-place using placement new.

Rule of three third pass
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
template<typename T>
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    Vector(int capacity)
        : capacity(capacity = 100)
        , length(0)
        // Allocates space but does not call the constructor
        , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        // Useful if the type T has an expensive constructor
        // We preallocate space without initializing it giving
        // room to grow and shrink the buffer without re-allocating.
    {}
    ~Vector()
    {
        // Because elements are constructed in-place using
        // placement new. Then we must manually call the destructor
        // on the elements.
        for(int loop = 0; loop < length; ++loop)
        {
            // Note we destroy the elements in reverse order.
            buffer[length - 1 - loop].~T();
        }
        ::operator delete(buffer);
    }
    Vector(Vector const& copy)
        : capacity(copy.length)
        , length(0)
        , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
    {
        // Copy constructor is simple.
        // We create a new resource area of the required length.
        // But these elements are not initialized so we use push_back to copy them
        // into the new object. This is an improvement because we
        // only construct the members of the vector once.
        for(int loop = 0; loop < copy.length; ++loop)
        {
            push_back(copy.buffer[loop]);
        }
    }
    Vector& operator=(Vector const& copy)
    {
        // Copy Object
        // This is relatively easy. But I want to cover this in detail in a subsquent post.
        return *this;
    }
    void push_back(T const& value)
    {
        // Use placement new to copy buffer into the new buffer
        new (buffer + length) T(value);
        ++length;

        // Note we will handle growing the capacity later.
    }
    void pop_back()
    {
        // When removing elements need to manually call the destructor
        // because we created them using placement new.
        --length;
        buffer[length].~T();
    }
};

Rule of Five

In C++11 the language added the concept of “Move Semantics”. Rather than having to copy an object (especially on return from a function) we could “move” an object. The concept here is that movement is supposed to be much cheaper than copying because you move the internal data structure of an object rather than all the elements. A good example is a std::vector. Before C++11 a return by value meant copying the object. The constructor of the new object allocates a new internal buffer and then copies all the elements from the original object’s buffer to the new object’s buffer. On the other hand a move simply gives the new object the internal buffer of the old object (we just move the pointer to the internal buffer). When an object is moved to another object the old object should be left in a valid state, but for efficiency the standard rarely specifies the state of an object after it has been the source of a move. Thus using an object after a move is a bad idea unless you are setting it to a specific state.

There are two new methods that allow us to specify move semantics on a class.

Vector Move Semantics.
1
2
3
4
5
6
7
8
9
10
11
12
13
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF

    // Move Constructor
    Vector(Vector&& move) noexcept;

    // Move Assignment Operator
    Vector& operator=(Vector&& move) noexcept;
};

Notice the && operator. This donates an r-value reference and means that your object is the destination of a move operation. The parameter passed is the source object and the state you should use to define your new object’s state. After the move the source object must be left in a valid (but can be undefined state). For a vector this means it must no longer be the owner of the internal buffer that you are now using in your buffer.

The simplest way to achieve this goal is to set up the object in a valid (but very cheap to achieve state) and then swap the current object with the destination object.

Vector Move Semantics Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;
    // STUFF

    // Move Constructor
    Vector(Vector&& move) noexcept
        : capacity(0)
        , length(0)
        , buffer(nullptr)
    {
        // The source object now has a nullptr/
        // This object has taken the state of the source object.
        move.swap(*this);
    }

    // Move Assignment Operator
    Vector& operator=(Vector&& move) noexcept
    {
        // In this case simply swap the source object
        // and this object around.
        move.swap(*this);
        return *this;
    }
};

Note I marked both move operators noexcept. Assuming the operations are guaranteed not to throw you should mark them as noexcept. If we know that certain operations are exception safe, then we can optimize resize operations and maintain the strong exception guarantee. This and some other optimizations will be documented in a subsequent post.

Final Version

Vector Final Version
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
template<typename T>
class Vector
{
    std::size_t     capacity;
    std::size_t     length;
    T*              buffer;

    struct Deleter
    {
        void operator()(T* buffer) const
        {
            ::operator delete(buffer);
        }
    };

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());

            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());
                // If there was an exception then destroy everything
                // that was created to make it exception safe.
                for(int loop = 0; loop < length; ++loop)
                {
                    buffer[length - 1 - loop].~T();
                }

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            // Covered in Part 2
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }
        void push_back(T const& value)
        {
            resizeIfRequire();
            new (buffer + length) T(value);
            ++length;
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
    private:
        void resizeIfRequire()
        {
            if (length == capacity)
            {
                // Covered in Part 2
            }
        }
};

Summary

This article has shown how to handle the basic resource management required by a vector. It has covered several important principles for C++ programmers.

  • Separation Of Concerns
  • Rule of Zero
  • Rule of Three
  • Rule of Five
  • Default compiler generated methods
  • Shallow Copy Problem
  • Placement New
  • Exception Guarantees

Sources

Looking at CodeReview.stackexchange.com; reimplementing the vector class is a common goal for a first project.