Downloading a Web page in C using a Windows socket

/* Link with Ws2_32.lib */
#ifndef WIN32_LEAN_AND_MEAN
#define WIN32_LEAN_AND_MEAN
#endif

#include <stdio.h>
#include <windows.h>
#include <winsock2.h>
#include <ws2tcpip.h>


int main(void)
{
	WSADATA wsaData;
	WORD wVersion;
	SOCKET sock;
	char host[] = "www.martinbroadhurst.com";
	char port[] = "80";
	struct addrinfo hints, *res;
	char message[] = "GET / HTTP/1.1\nHost: www.martinbroadhurst.com\n\n";
	char buf[1024];
	int bytes_read;
	int status;

	wVersion = MAKEWORD(1, 1);
	if (WSAStartup(wVersion, &wsaData) != 0) {
		printf("Couldn't initialise WinSock\n");
		return 1;
	}

	ZeroMemory(&hints, sizeof hints);
	hints.ai_family = AF_INET;
	hints.ai_socktype = SOCK_STREAM;
	status = getaddrinfo(host, port, &hints, &res);
	if (status != 0) {
		perror("getaddrinfo");
        WSACleanup();
		return 1;
	}
	sock = socket(AF_INET, SOCK_STREAM, 0);

	status = connect(sock, res->ai_addr, res->ai_addrlen);
	if (status == SOCKET_ERROR) {
		perror("connect");
        WSACleanup();
		return 1;
	}

	send(sock, message, sizeof(message), 0);

    do {
		bytes_read = recv(sock, buf, sizeof(buf), 0);
		if (bytes_read == SOCKET_ERROR) {
			perror("recv");
		}
		else {
			printf("%.*s", bytes_read, buf);
		}
	} while (bytes_read > 0);

	closesocket(sock);
	WSACleanup();
    return 0;
}

Reference: Using Winsock

Downloading a Web page in C using a socket

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h> /* close() */
#include <sys/socket.h>
#include <netdb.h>

int main(void)
{
    int sock;
	char host[] = "www.martinbroadhurst.com";
	char port[] = "80";
	struct addrinfo hints, *res;
	char message[] = "GET / HTTP/1.1\nHost: www.martinbroadhurst.com\n\n";
	unsigned int i;
    char buf[1024];
    int bytes_read;
	int status;

	memset(&hints, 0, sizeof hints);
	hints.ai_family = AF_INET;
	hints.ai_socktype = SOCK_STREAM;
	status = getaddrinfo(host, port, &hints, &res);
	if (status != 0) {
		perror("getaddrinfo");
		return 1;
	}
	sock = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
	if (sock == -1) {
		perror("socket");
		return 1;
	}
	status = connect(sock, res->ai_addr, res->ai_addrlen);
    if (status == -1) {
		perror("connect");
		return 1;
    }
	freeaddrinfo(res);
    send(sock, message, strlen(message), 0);

    do {
		bytes_read = recv(sock, buf, 1024, 0);
		if (bytes_read == -1) {
			perror("recv");
		}
        else {
		    printf("%.*s", bytes_read, buf);
        }
    } while (bytes_read > 0);

    close(sock);

    return 0;
}

AVL Tree in C

An AVL tree is a height-balanced binary search tree in which the heights of a node’s two sub-trees are not allowed to differ by more than one.
For example, the first tree below is balanced, while the other two are unbalanced because they are "heavy" on one side or the other:

                   A                          C
                    \                        /
      B              B                      B
     / \               \                   /
    A   C               C                 A
                          
   Balanced      Not Balanced          Not Balanced        
                 "Right Heavy"         "Left Heavy"         

If a tree becomes unbalanced by an addition or deletion, the balance can be restored by rotations, which change the shape of the tree, but preserve the BST property. Below are a left rotation at A, and a right rotation at C:

        A                                    C
         \                                  /
           B      -->      B               B      -->      B
            \             / \            /                / \
             C           A   C          A                A   C     

            Left Rotation                     Right Rotation          

Some unbalanced trees cannot be balanced by a single rotation.
For example, the two trees below are simply converted into each other by a single rotation of the top node:

   C         -->        A     
  /      Rotate Right    \
 B                        C
  \         <--          /
    A    Rotate Left    B

In this case we need to do a double rotation:

  • A double left rotation is a left rotation on the left subtree followed by a right rotation on the root
  • A double right rotation is a right rotation on the right subtree followed by a left rotation on the root

For example, here is a double left rotation:

   C               C            
  /               /
 A      -->      B      -->      B      
  \             /               / \
   B           A               A   C

1. Rotate Left at A   2. Rotate Right at C

Here is the header file:

#ifndef AVLTREE_H
#define AVLTREE_H

#include <stdlib.h>

struct avltreenode
{
	struct avltreenode * left;
	struct avltreenode * right;
	struct avltreenode * parent;
	unsigned int leftheight;
	unsigned int rightheight;
	void * data;
};

typedef struct avltreenode avltreenode;

typedef int (*avltree_cmpfn)(const void*, const void*);
typedef void (*avltree_forfn)(void*);

struct avltree {
	avltreenode * root;
	size_t count;
	avltree_cmpfn compare;
};

typedef struct avltree avltree;

avltree * avltree_create(avltree_cmpfn compare);
void avltree_delete(avltree * tree);
void avltree_for_each(const avltree * tree, avltree_forfn fun);
void* avltree_add(avltree * tree, void * data);
void* avltree_find(const avltree * tree, const void* data);
void* avltree_remove(avltree * tree, const void* data);
void avltree_empty(avltree * tree);
size_t avltree_get_count(const avltree *tree);

#endif /* AVLTREE_H */

The implementation:

#include <stdlib.h>

#include <avltree.h>

avltree * avltree_create(avltree_cmpfn compare)
{
	avltree * tree = malloc(sizeof(avltree));
	if (tree != NULL) {
		tree->root = NULL;
		tree->compare = compare;
		tree->count = 0;
	}
	return tree;
}

static void avltreenode_delete(avltreenode *node)
{
	free(node);
}

static void avltree_empty_recursive(avltreenode * root)
{
	if (root->left) {
		avltree_empty_recursive(root->left);
	}
	if (root->right) {
		avltree_empty_recursive(root->right);
	}
	avltreenode_delete(root);
}

void avltree_empty(avltree * tree)
{
    if (tree->root) {
        avltree_empty_recursive(tree->root);
        tree->root = NULL;
        tree->count = 0;
    }
}

void avltree_delete(avltree * tree)
{
	if (tree) {
		avltree_empty(tree);
		free(tree);
	}
}

static void avltree_for_each_recursive(const avltreenode * root, avltree_forfn fun)
{
	if (root->left != NULL) {
		avltree_for_each_recursive(root->left, fun);
	}
	fun(root->data);
	if (root->right != NULL) {
		avltree_for_each_recursive(root->right, fun);
	}
}

void avltree_for_each(const avltree * tree, avltree_forfn fun)
{
    if (tree->root) {
        avltree_for_each_recursive(tree->root, fun);
    }
}

struct avlsearchresult
{
	avltreenode *node;
	avltreenode *parent;
};
typedef struct avlsearchresult avlsearchresult;

static int avltree_search(const avltree *tree, avlsearchresult *result, const void *data)
{
	int found = 0;

	result->node = tree->root;
	while (!found && result->node != NULL) {
		int rv = tree->compare(result->node->data, data);
		if (rv == 0) {
			found = 1;
		}
		else {
			result->parent = result->node;
			if (rv > 0) {
				result->node = result->node->left;
			}
			else if (rv < 0) {
				result->node = result->node->right;
			}
		}
	}
	return found;
}

static avltreenode * avltreenode_create(void * data)
{
	avltreenode * node = malloc(sizeof(avltreenode));
	if (node) {
		node->left = NULL;
		node->right = NULL;
		node->parent = NULL;
		node->leftheight = 0;
		node->rightheight = 0;
		node->data = data;
	}
	return node;
}

static int avltreenode_get_max_height(const avltreenode *node)
{
	int height;
	if (node->leftheight > node->rightheight) {
		height = node->leftheight;
	}
	else {
		height = node->rightheight;
	}
	return height;
}

static void avltreenode_fix_height(avltreenode *node)
{
	node->leftheight = 0;
	node->rightheight = 0;
	if (node->left) {
		node->leftheight = avltreenode_get_max_height(node->left) + 1;
	}
	if (node->right) {
		node->rightheight = avltreenode_get_max_height(node->right) + 1;
	}
}

static void avltree_rotate_left(avltree *tree, avltreenode *node)
{
	avltreenode *right = node->right;
	if (node == tree->root) {
		tree->root = right;
	}
	else if (node == node->parent->left) {
		node->parent->left = right;
	}
	else {
		node->parent->right = right;
	}
    right->parent = node->parent;
	if (right->left) {
		node->right = right->left;
        node->right->parent = node;
	}
	else {
		node->right = NULL;
	}
	right->left = node;
    node->parent = right;
	avltreenode_fix_height(node);
	avltreenode_fix_height(right);
}

static void avltree_rotate_right(avltree *tree, avltreenode *node)
{
	avltreenode *left = node->left;
	if (node == tree->root) {
		tree->root = left;
	}
	else if (node == node->parent->left) {
		node->parent->left = left;
	}
	else {
		node->parent->right = left;
	}
    left->parent = node->parent;
	if (left->right) {
		node->left = left->right;
        node->left->parent = node;
	}
	else {
		node->left = NULL;
	}
	left->right = node;
    node->parent = left;
	avltreenode_fix_height(node);
	avltreenode_fix_height(left);
}

static int avltreenode_get_balance_factor(const avltreenode *node)
{
	return node->leftheight - node->rightheight;
}

static void avltree_rebalance(avltree *tree, avltreenode *node)
{
	avltreenode *current = node;
	while (current != NULL) {
        avltreenode *parent = current->parent;
		int balance;
		avltreenode_fix_height(current);
		balance = avltreenode_get_balance_factor(current);
		if (balance == -2) {
			/* Right heavy */
			const int rightbalance = avltreenode_get_balance_factor(current->right);
			if (rightbalance < 0) {
				avltree_rotate_left(tree, current);
			}
			else {
				avltree_rotate_right(tree, current->right);
				avltree_rotate_left(tree, current);
			}
		}
		else if (balance == 2) {
			/* Left heavy */
			const int leftbalance = avltreenode_get_balance_factor(current->left);
			if (leftbalance > 0) {
				avltree_rotate_right(tree, current);
			}
			else {
				avltree_rotate_left(tree, current->left);
				avltree_rotate_right(tree, current);
			}
		}
        current = parent;
	}
}

void* avltree_add(avltree * tree, void * data)
{
	void *temp = NULL;
	avlsearchresult result;
	result.node = NULL;
	result.parent = NULL;

	if (avltree_search(tree, &result, data)) {
		temp = result.node->data;
		result.node->data = data;
	}
	else {
		avltreenode *node = avltreenode_create(data);
		if (result.node == tree->root) {
			tree->root = node;
		}
		else {
			int rv = tree->compare(data, result.parent->data);
			if (rv < 0) {
				result.parent->left = node;
			}
			else {
				result.parent->right = node;
			}
			node->parent = result.parent;
            avltree_rebalance(tree, node);
		}
		tree->count++;
	}
	
	return temp;
}

void* avltree_find(const avltree * tree, const void* data)
{
	void *temp = NULL;
	avlsearchresult result;
	result.node = NULL;
	result.parent = NULL;

	if (avltree_search(tree, &result, data)) {
		temp = result.node->data;
	}
	return temp;
}

static avltreenode *avltreenode_find_min(avltreenode *node)
{
	avltreenode *current = node;

	while (current->left) {
		current = current->left;
	}
	return current;
}

static void avltree_remove_node(avltree *tree, avltreenode *node)
{
	if (node->left && node->right) {
        /* Node with 2 children */
		avltreenode *successor = avltreenode_find_min(node->right);
		node->data = successor->data;
		avltree_remove_node(tree, successor);
	}
	else {
        avltreenode *parent = node->parent;
		if (node->left) {
            /* Node with only left child */
			if (node->parent) {
                if (node == node->parent->left) {
				    node->parent->left = node->left;
				    node->parent->left->parent = node->parent;
                }
                else {
				    node->parent->right = node->left;
				    node->parent->right->parent = node->parent;
                }
			}
			else {
				tree->root = node->left;
				tree->root->parent = NULL;
			}
		}
		else if (node->right) {
            /* Node with only right child */
			if (node->parent) {
                if (node == node->parent->left) {
                    node->parent->left = node->right;
                    node->parent->left->parent = node->parent;
                }
                else {
                    node->parent->right = node->right;
                    node->parent->right->parent = node->parent;
                }
			}
			else {
				tree->root = node->right;
				tree->root->parent = NULL;
			}
		}
		else {
            /* Node with no children */
			if (node->parent) {
				if (node == node->parent->left) {
					node->parent->left = NULL;
				}
				else {
					node->parent->right = NULL;
				}
			}
			else {
				tree->root = NULL;
			}
		}
		avltreenode_delete(node);
        avltree_rebalance(tree, parent);
		tree->count--;
	}
}

void* avltree_remove(avltree * tree, const void* data)
{
	void *temp = NULL;
	avlsearchresult result;
	result.node = NULL;
	result.parent = NULL;

	if (avltree_search(tree, &result, data)) {
		temp = result.node->data;
		avltree_remove_node(tree, result.node);
	}
	return temp;
}

size_t avltree_get_count(const avltree *tree)
{
    return tree->count;
}

Here is an example program:

#include <stdio.h>
#include <string.h>

#include <avltree.h>

int main(void)
{
    avltree * tree;
    const char * result;
    unsigned int e;
    char * elements[] = {"orange", "apple", "pear", "grapefruit", "cherry", "plum"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    tree = avltree_create((avltree_cmpfn)strcmp);
    for (e = 0; e < n; e++) {
        avltree_add(tree, elements[e]);
    }
    avltree_for_each(tree, (avltree_forfn)puts);
    for (e = 0; e < n; e++) {
        result = avltree_find(tree, elements[e]);
        if (result) {
            printf("Found: %s\n", result); 
        }
        else {
            printf("Couldn't find %s\n", elements[e]);
        }
    }
    for (e = 0; e < n; e++) {
        result = avltree_remove(tree, elements[e]);
        if (result) {
            printf("Removed: %s\n", result);
        }
        else {
            printf("Couldn't remove %s\n", elements[e]);
        }
    }
    avltree_delete(tree);

    return 0;
}

Typedef super

A useful addition to a derived class is a typedef aliasing the base class as super:

class Derived : public Base
{
private:
    typedef Base super;
};

This allows you to use super to call the base class constructor from the derived class:

    Derived(int i, int j)
        : super(i), j_(j)
    {
    }

You can also use super to call the base class version of a virtual function in a derived class override:

 virtual void Show()
{
    super::Show();
    std::cout << "Derived Show()\n";
}

It means that if you need to add another layer of inheritance, you only need to change the inheritance part of the class declaration and this typedef.

class Derived : public Intermediate
{
private:
    typedef Intermediate super;
};

You should make the typedef private, to prevent it from being inherited and accidentally used from derived classes that do not declare it.

Visual C++ has a non-standard extension __super: __super.

It is available in Java: Using the Keyword super.

Nowadays you should probably use using:

class Derived : public Base
{
private:
    using super = Base;
};

So it should probably be called the "using super =" idiom.

Finding a substring in C++

Say we have the following string:

std::string str = "The quick brown fox jumps over the lazy dog";

And we want to find "fox"

Method 1: Use std::string::find

bool found = str.find("fox") != str.npos;

This returns an iterator pointing at the beginning of the substring if found, or std::string::npos otherwise.

Method 2: Use boost::contains

#include <boost/algorithm/string/predicate.hpp>
found = boost::contains(str, "fox");

This has the advantage of returning a boolean.

Reference: Function contains

Method 3: Use pystring::find

#include <pystring.h>
found = pystring::find(str, "fox") != -1;

Reference: imageworks/pystring

Default operator== in C++

At first sight, it seems surprising that there is no compiler-generated default operator== in C++, when there is a compiler-generated default assignment operator and copy constructor. It could simply do a memberwise comparison, just as the assignment operator and copy constructor do a memberwise copy.

The reason is out of compatibility with C. In C, struct comparison is illegal, so a default operator== in C++ would have made C code that shouldn’t compile as C compile, and potentially changed its behaviour. Compatibility is the same reason why C++ does have a default assignment operator and copy constructor, which is ironic given that those are rarely wanted and are often disabled by making them private.

There is a proposal to include default comparison operators in C++17, as described here: A bit of background for the default comparison proposal — Bjarne Stroustrup.

Looping over the keys and values in a map

Say we have this map:

#include <map>
#include <string>

typedef std::map<std::string, unsigned int> map_string_to_uint;
const size_t n = 12;

map_string_to_uint monthdays;
const char *months[] 
        = {"JAN", "FEB", "MAR", "APR", "MAY", "JUN", "JUL", "AUG", "SEP", "OCT", "NOV", "DEC"};
unsigned int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
for (int m = 0; m < n; ++m) {
    monthdays[months[m]] = days[m];
}

And we want to loop over the keys and values.

Method 1: Use an iterator

    for (map_string_to_uint::const_iterator it = monthdays.begin(); it != monthdays.end(); ++it) {
        std::cout << it->first << ": " << it->second << "\n";
    }

Method 2: Use a range-based for loop (C++11)

    for (const auto& pair : monthdays) {
        std::cout << pair.first << ": " << pair.second << "\n";
    }

Method 3: Use Boost.Foreach

#include <boost/foreach.hpp>

BOOST_FOREACH(const map_string_to_uint::value_type& pair, monthdays) {
    std::cout << pair.first << ": " << pair.second << "\n";
}

Reference: Boost.Foreach

Why STL iterator ranges go [begin, end)

At first sight, it seems strange that STL iterators go [begin, end), including begin but not end in the range, but when you think about it more you realise that this is exactly the way conventional loops work.

STL iteration loop

A typical STL iteration loop goes:

for (it = begin; it != end; ++it) {
    // do something with *it
}

Note that:

  • The iterator end is not part of the range processed
  • After the end of the loop it is equal to end, i.e., one past the end of the range
  • The size of range traversed is endbegin

Now consider the following loops:

Loop over an array with an index

    int numbers[] = {1, 2, 3, 4, 5, 6};
    const size_t n = sizeof(numbers) / sizeof(int);
    int i;
    for (int i = 0; i < n; ++i) {
        std::cout << numbers[i] << "\n";
    }
    std::cout << i << "\n";

Here, our range of indices processed is [0, n).

  • numbers[n] is not part of the range processed
  • After the end of the loop, i is n, i.e., one past the end of the range
  • The size of range traversed is n - 0 = n , i.e., the end – the beginning

Loop over a string


    const char str[] = "The quick brown fox jumps over the lazy dog";
    for (i = 0; str[i] != '\0'; ++i) {
        std::cout << str[i] << "\n";
    }
    for (const char* c = str; c != '\0'; ++c) {
        std::cout << *str << "\n";
    }

A string is defined by [str[0], '\0'), or [*str, '\0')

  • The '\0' character is not part of the string
  • After the end of the loop, the pointer or index points to the '\0'.
  • The size of range traversed is (position of the '\0') – 0 = strlen(str), i.e., the end – the beginning

Loop over an array of pointers with sentinel

    const char* strings[] = {"apples", "pears", "bananas", "cherries", NULL};
    for (i = 0; strings[i] != NULL; ++i) {
        std::cout << strings[i] << "\n";
    }
    for (const char** pc = strings; *pc != NULL ; ++pc) {
        std::cout << *pc << "\n";
    }

Similarly, here the range is [strings[0], NULL), or [*strings, NULL)

  • The NULL is not considered part of the range processed
  • After the end of the loop, the pointer or index points to the NULL
  • The size of range traversed is (position of the NULL) – 0 = the position of the NULL, i.e., the end – the beginning

Hopefully, this has demonstrated that STL iterators have exactly the same semantics as ordinary loop variables.

I’ll leave the last word to E. W. Dijkstra, with his explanation of Why numbering should start at zero.

Getting the date and time in C++

I use this little function to get a nicely formatted date and time:

#include <ctime>
#include <string>
#include <vector>

std::string stringftime(const char* format = "%c", const struct tm* tm = NULL)
{
    if (tm == NULL) {
        time_t t = std::time(NULL);
        tm = std::localtime(&t);
    }
    const size_t size = 256;
    std::vector<char> vtime(size);
    if (std::strftime(&vtime[0], size, format, tm) == 0) {
        vtime[0] = '\0';
    }
    return &vtime[0];
}

Example of its use:

#include <iostream>

int main (void)
{
    std::cout << stringftime() << "\n";
    std::cout << stringftime("Today is %A, %B %d.") << "\n";
    std::cout << stringftime("The time is %I:%M %p.") << "\n";
}
Fri Sep  9 16:07:58 2016
Today is Friday, September 09.
The time is 04:07 PM.

The format specifiers accepted are listed here: strftime.

Template specialisation with a non-type template parameter

The problem

Say you have a generic matrix class like this with non-type template parameters for the number of rows and columns:

template <typename ElementType, size_t Rows, size_t Columns>
class Matrix
{
    ElementType entries_[Rows][Columns];
    // etc...
};

You would like to create a specialization for a column vector, where the number of columns is always 1. However, the following typedef doesn’t compile:

typedef Matrix<size_t, Rows, 1> ColumnVector;

C++03

In C++03, you have 2 options.
Firstly, you can use inheritance:

template <typename ElementType, size_t Rows>
class ColumnVector : public Matrix<ElementType, Rows, 1>
{
};

Secondly, you could use a class with a nested typedef:

template <typename ElementType, size_t Rows>
struct ColumnVector
{
    typedef Matrix<ElementType, Rows, 1> type;
};

In this case, you could declare a column vector with:

ColumnVector<int, 3>::type vec;

C++11

In C++11, you can use an alias declaration to solve the problem more neatly:

template <typename ElementType, size_t Rows>
using ColumnVector = Matrix<ElementType, Rows, 1>;

This is a good example of how much more powerful the new alias declarations with using are than typedefs.