Skip to content

Instantly share code, notes, and snippets.

@derrickturk
Created January 8, 2014 17:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save derrickturk/8320178 to your computer and use it in GitHub Desktop.
Save derrickturk/8320178 to your computer and use it in GitHub Desktop.
Some didactic example code, intended to help my brother through a poorly-taught "C++" class. I was a little hamstrung by the fact that the class taught (bad C + "new" and "delete" + bad Java) and called it C++...
#include <cstdio>
#include <cstdlib>
#include <csignal>
#include "unistd.h"
#include "sys/wait.h"
#include "sys/types.h"
#include "sys/time.h"
// I can never remember this...
#define READ_END 0
#define WRITE_END 1
#define MKSTRING(x) _MKSTRING(x)
#define _MKSTRING(x) #x
const int n_children = 3;
int parent(int p2c[][2], int c2p[][2], int n);
void child(int n);
void cleanup_pipes(int p2c[][2], int c2p[][2], int n, int except);
int main()
{
std::signal(SIGPIPE, SIG_IGN);
int ret = EXIT_FAILURE;
// arrays of n_children arrays of 2 ints
// for pipe read/write end fds
// need two pipes per child:
// one that parent writes / child reads
// & one that parent reads / child writes
int p2c_pipes[n_children][2];
int c2p_pipes[n_children][2];
pid_t child_pids[n_children];
// this will make cleanup logic easier
for (int i = 0; i < n_children; ++i) {
p2c_pipes[i][READ_END] = -1;
p2c_pipes[i][WRITE_END] = -1;
c2p_pipes[i][READ_END] = -1;
c2p_pipes[i][WRITE_END] = -1;
child_pids[i] = -1;
}
// acquire a parent->child pipe per child
for (int i = 0; i < n_children; ++i)
if (pipe(p2c_pipes[i]) == -1) {
perror("pipe() at " MKSTRING(__LINE__));
goto CLEANUP_ALL;
}
// acquire a child->parent pipe per child
for (int i = 0; i < n_children; ++i)
if (pipe(c2p_pipes[i]) == -1) {
perror("pipe() at " MKSTRING(__LINE__));
goto CLEANUP_ALL;
}
// fork a process per child
for (int i = 0; i < n_children; ++i) {
switch (fork()) {
case -1: perror("fork() at " MKSTRING(__LINE__));
goto CLEANUP_PARENT;
case 0 : // in the child
// let fd 0 be the child's input
// and fd 1 be the child's output
if (dup2(p2c_pipes[i][READ_END], 0) == -1
|| dup2(c2p_pipes[i][WRITE_END], 1) == -1) {
perror("dup2() at " MKSTRING(__LINE__));
goto CLEANUP_ALL;
}
// close all the other pipes
cleanup_pipes(p2c_pipes, c2p_pipes, n_children, i);
// close our unneeded write end
close(p2c_pipes[i][WRITE_END]);
// close our unneeded read end
close(c2p_pipes[i][READ_END]);
fprintf(stderr,
"about to kick off child #%d with fd 0 <- %d"
" and fd 1 <- %d\n",
i,
p2c_pipes[i][READ_END],
c2p_pipes[i][WRITE_END]);
// launch "child program"
// can replace this with a call to exec()
child(i + 1);
// shouldn't get here: child calls exit
// simulating an exec(), which doesn't return
break;
default: // in the parent
// keep looping until we're done fork()ing
// then proceed
break;
}
}
// close pipes we don't need
for (int i = 0; i < n_children; ++i) {
close(p2c_pipes[i][READ_END]);
p2c_pipes[i][READ_END] = -1;
close(c2p_pipes[i][WRITE_END]);
c2p_pipes[i][WRITE_END] = -1;
}
std::fprintf(stderr, "about to enter parent\n");
// parent returns EXIT_SUCCESS or EXIT_FAILURE
ret = parent(p2c_pipes, c2p_pipes, n_children);
std::fprintf(stderr, "about to cleanup parent\n");
CLEANUP_PARENT:
// wait for any VALID children
for (int i = 0; i < n_children; ++i) {
if (child_pids[i] != -1)
waitpid(child_pids[i], 0, 0);
}
CLEANUP_ALL:
cleanup_pipes(p2c_pipes, c2p_pipes, n_children, -1);
return ret;
}
int parent(int p2c[][2], int c2p[][2], int n)
{
// this represents the main parent "driver" process
// we want to mutiplex input and output across our children
// efficiently. we can do this using select(), which cunningly
// polls several file descriptors and reveals which are ready
// for I/O.
// the program will try to evaluate each child's "computation"
// for each integer up to compute_max.
// for optimal use of each child, we keep a current-max counter
// per child in a dynamically allocated array.
const int compute_max = 4;
struct progress { int read, write; };
progress *current =
static_cast<progress*>(std::malloc(n * sizeof(progress)));
if (!current) {
perror("malloc() at " MKSTRING(__LINE__));
return EXIT_FAILURE;
}
for (int i = 0; i < n; ++i) {
current[i].read = 0;
current[i].write = 0;
}
while (true) {
// prepare descriptions of FDs to be polled
fd_set to_read;
fd_set to_write;
FD_ZERO(&to_read);
FD_ZERO(&to_write);
int highest_fd = -1;
for (int i = 0; i < n; ++i) {
if (current[i].read <= compute_max) {
if (c2p[i][READ_END] > highest_fd)
highest_fd = c2p[i][READ_END];
FD_SET(c2p[i][READ_END], &to_read);
}
if (current[i].write <= compute_max) {
if (p2c[i][WRITE_END] > highest_fd)
highest_fd = p2c[i][WRITE_END];
FD_SET(p2c[i][WRITE_END], &to_write);
}
}
// nothing left to read or write
if (highest_fd == -1) break;
if (select(highest_fd + 1, &to_read, &to_write, 0, 0) == -1) {
perror("select() at " MKSTRING(__LINE__));
std::free(current);
return EXIT_FAILURE;
}
// process... kinda slowly
// additional buffering is left as an exercise to the reader
for (int i = 0; i < n; ++i) {
int result;
if (FD_ISSET(c2p[i][READ_END], &to_read)) {
std::fprintf(stderr, "read %d to child %d\n", current[i].read, i);
if (read(c2p[i][READ_END], &result, sizeof(int))
!= sizeof(int)) {
perror("read() at " MKSTRING(__LINE__));
std::free(current);
return EXIT_FAILURE;
}
std::printf("%d * %d = %d\n", current[i].read, i + 1, result);
++(current[i].read);
}
if (FD_ISSET(p2c[i][WRITE_END], &to_write)) {
std::fprintf(stderr, "write %d to child %d\n", current[i].write, i);
if (write(p2c[i][WRITE_END], &(current[i].write), sizeof(int))
!= sizeof(int)) {
perror("write() at " MKSTRING(__LINE__));
std::fprintf(stderr,
"fail in write to child %d "
"with current write = %d, "
"current read = %d",
" on fd %d\n",
i,
current[i].write,
current[i].read,
p2c[i][WRITE_END]);
std::free(current);
return EXIT_FAILURE;
}
++(current[i].write);
}
}
std::fprintf(stderr, "Just to recap:\n");
for (int i = 0; i < n; ++i)
std::fprintf(stderr, "current[%d] = <%d, %d>\n", i, current[i].read, current[i].write);
}
std::free(current);
return EXIT_SUCCESS;
}
void child(int n)
{
// ok, this function could be a standalone executable
// that we then launch with exec() or friends
// in here, we don't have to worry about anything other
// than taking input on FD 0 and writing output to FD 1
const int buf_sz = 1024;
int in_buf[buf_sz];
int out_buf[buf_sz];
std::fprintf(stderr, "in child%d\n", n - 1);
ssize_t count = 0;
do {
count = read(0, in_buf, buf_sz * sizeof(int));
// process a bunch at once...
for (ssize_t i = 0; i < count; ++i)
out_buf[i] = in_buf[i] * n;
// and write them in bulk for better performance
write(1, out_buf, count * sizeof(int));
} while (count == buf_sz * sizeof(int));
close(0);
close(1);
std::fprintf(stderr, "child %d terminating\n", n - 1);
// we're pretending to be our own executable here...
std::exit(EXIT_SUCCESS);
}
void cleanup_pipes(int p2c[][2], int c2p[][2], int n, int except)
{
// clean up any OPEN fds (this is why we used -1 everywhere)
// except, if we're a child, our own
for (int i = 0; i < n; ++i) {
if (i == except) continue;
if (p2c[i][READ_END] != -1)
close(p2c[i][READ_END]);
if (p2c[i][WRITE_END] != -1)
close(p2c[i][WRITE_END]);
if (c2p[i][READ_END] != -1)
close(c2p[i][READ_END]);
if (c2p[i][WRITE_END] != -1)
close(c2p[i][WRITE_END]);
}
}
/*
* Templates are Fun, Part I
* Function Templates
* dwt 20131125
*
* Templates are a feature of C++ that allows for metaprogramming:
* that is, writing programs that write programs.
*
* They constitute a (Turing-complete!) language that is executed at
* compile time and integrates with the C++ static type system.
*
* Like other metaprogramming facilities (Lisp macros, eval() in many
* dynamic languages...) they allow the avoidance of repetitious boilerplate
* code. In particular, in C++ they are useful for abstracting operations that
* can be performed on many types in a similar fashion, but where the types on
* which to operate are known at compile-time. This is compile-time (or static)
* polymorphism, as opposed to the run-time polymorphism achieved through
* object-oriented programming, subtyping, and virtual dispatch.
*
* Templates can be used to generate both functions (including member
* functions or "methods") and types (classes, structs, unions) parameterized
* by either type or value parameters.
*
* In this file, we'll look at how a template function lets us abstract a
* simple mathematical operation across various types of "number".
*/
#include <iostream>
/* a naughty, naughty old C trick
* only works for statically declared arrays
* i.e. where the size is known at compile time
*/
#define ARR_LEN(arr) ((sizeof(arr) / sizeof(arr[0])))
/* we'll use this class as an example of a non-built-in numeric type.
* there's really nothing special here, but notice that we provide both
* addition operators as well as a print-to-stream operator.
*/
class Complex {
public:
Complex() : re_(0.0), im_(0.0) {}
Complex(double re, double im)
: re_(re), im_(im) {}
double real() const { return re_; }
double imag() const { return im_; }
Complex operator+(const Complex& other) const
{
return Complex(real() + other.real(),
imag() + other.imag());
}
Complex& operator+=(const Complex& other)
{
re_ += other.real();
im_ += other.imag();
return *this;
}
private:
double re_;
double im_;
};
std::ostream& operator<<(std::ostream& os, const Complex& c)
{
return os << "<real: " << c.real() << ", imag: " << c.imag() << '>';
}
/* let's say we're interested in summing "numbers".
* there are easier ways to do this, but I don't want to bring in
* other templates from the standard library just yet.
* we'll also assume our data comes to us in C-style arrays, for similar
* reasons.
* we can obviously write a sum function for each type of interest...
*/
int sum_ints(int arr[], int n)
{
int total = 0;
for (int i = 0; i < n; ++i)
total += arr[i];
return total;
}
/* I'm not going to compile it, but note that we could write:
Complex sum_complex(Complex arr[], int n)
{
Complex total = 0;
for (int i = 0; i < n; ++i)
total += arr[i];
return total;
}
* Notice anything funny? All I had to do is replace the type 'int' with the
* type 'Complex' in a couple of places, because Complex defines the +=
* operator that we need for the code to work.
*
* Function templates let me automate this work. I can write the following
* template, which will act as a sort of "function generator" for sum functions
* that work on any type that supports a default constructor (this includes
* built-in types!) as well as a += operator.
*
* As you can see, the template takes template parameters (in the <> brackets).
* In this case, there's just one parameter: a type ("class" or "typename"
* keywords are equivalent here) N.
*
* In the body of the template, we can use "N" as if it were the name of a type.
* At compile-time, the template will be instantiated (this means an actual
* function will be generated) with whichever concrete type is used as the
* actual template parameter.
*/
template<class N>
N sum(N arr[], int n)
{
N total = N(); // default-construct: for built-in types will set to 0
for (int i = 0; i < n; ++i)
total += arr[i];
return total;
}
int main()
{
// here are some static arrays of data to operate on
int some_ints[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
Complex some_complices[] = {
Complex(1, 2),
Complex(5, 9),
Complex(-2, 7),
Complex(6, -3),
Complex(-7, 3),
Complex(8, 5),
Complex(2, -2),
Complex(-1, 5),
Complex(-4, 6),
Complex(5, 7)
};
// we can, of course, call the ordinary function sum_int on our
// integer array
std::cout << "Sum of some_ints by sum_ints = "
<< sum_ints(some_ints, ARR_LEN(some_ints)) << '\n';
// we can also instantiate our sum function template with int as the
// type parameter. The resulting function is named sum<int>.
std::cout << "Sum of some_ints by sum<int> = "
<< sum<int>(some_ints, ARR_LEN(some_ints)) << '\n';
// likewise for Complex.
std::cout << "Sum of some_ints by sum<Complex> = "
<< sum<Complex>(some_complices, ARR_LEN(some_complices)) << '\n';
// now, a fun feature of function templates (this doesn't exist for
// class templates). often, the compiler can work out the actual type
// parameters from context. here, it knows that we are passing in an
// array of Complex, and so automatically infers that we want sum<Complex>.
std::cout << "Just to prove that type inference works, "
"sum(some_complices, ARR_LEN(some_complices) = "
<< sum(some_complices, ARR_LEN(some_complices)) << '\n';
// fun C++ fact: if you don't write 'return 0' at the end of main,
// it's automatically assumed. don't try this in C...
}
/*
* Templates are Fun, Part II
* Class Templates
* dwt 20131125
*
* OK, we've talked about templates in broad terms and seen
* a function template in action.
*
* However, the bulk of C++ template metaprogramming is used to generate
* new types at compile time. Much of the C++ standard library is built on
* this technique, providing templates for container classes, "smart pointers",
* generic "function objects" and many other useful parametric types.
*
* In this example, we'll look at a really simple "vector-like" class
* and parametrize to store data of arbitrary types with static type safety.
*
*/
#include <iostream>
#include <stdexcept>
// here's a simple 'record' type to use as a concrete example
struct Foo {
int bar;
double baz;
char quux[10];
};
// now, we could write a vector-of-Foo class thus:
// we're going to be silly and use raw pointers etc
// because I'm trying to make a point, not write an actually useful container
// we also expose stack-like push/pop for the heck of it (ok, this is often
// useful for contiguous vector type thingabobs)
// and we'll do checked access, because why not.
class Foo_vector {
public:
// an empty vector of Foos
Foo_vector()
: buf_(new Foo[initial_capacity]()),
capacity_(initial_capacity),
size_(0) {}
// a vector of initial_size default-constructed Foos
Foo_vector(int initial_size)
: buf_(new Foo[initial_capacity > initial_size ?
initial_capacity
: initial_size]()),
capacity_(initial_capacity > initial_size ?
initial_capacity
: initial_size),
size_(initial_size) {}
// copy-construct a Foo_vector from another Foo_vector
Foo_vector(const Foo_vector& other)
: buf_(0),
capacity_(initial_capacity > other.size() ?
initial_capacity
: other.size()),
size_(other.size())
{
buf_ = new Foo[capacity_];
// we have to release the just-acquired buffer
// in the case that copying a contained object
// throws an exception.
// there are better ways to do this, but they distract from
// the points I am trying to make...
try {
for (int i = 0; i < size_; ++i)
buf_[i] = other[i];
} catch (...) {
delete[] buf_;
throw; // rethrow the exception---our construction has failed
}
}
~Foo_vector()
{
delete[] buf_;
}
// assign contents from another Foo vector
Foo_vector& operator=(const Foo_vector& other)
{
// we use a nice trick called 'copy-and-swap' here
// this ensures that we release our held buffer
// in an exception safe way after the assign is complete.
Foo_vector temp(other); // use copy constructor
swap(temp); // now we hold temp's former contents,
// and temp holds ours. when temp goes out of scope,
// it's destructor is called, released its contents
// i.e. our former contents.
//
// nifty, eh?
}
int size() const { return size_; }
Foo& operator[](int index)
{
if (index < 0 || index >= size())
throw std::out_of_range("Invalid index to Foo_vector");
return buf_[index];
}
// we provide this overload for read-only access to a const Foo_vector
const Foo& operator[](int index) const
{
if (index < 0 || index >= size())
throw std::out_of_range("Invalid index to Foo_vector");
return buf_[index];
}
void push(const Foo& foo)
{
if (size() + 1 > capacity_) {
Foo* new_buf = new Foo[capacity_ * 2];
// same as in the copy constructor: we have to release new_buf
// if copy assignment fails for one of our objects
try {
for (int i = 0; i < size_; ++i)
new_buf[i] = buf_[i];
} catch (...) {
delete[] new_buf;
throw;
}
delete[] buf_;
buf_ = new_buf;
}
buf_[size_++] = foo;
}
Foo pop() { return buf_[--size_]; }
private:
static const int initial_capacity = 128;
// note that none of these operations can throw an exception
void swap(Foo_vector& other)
{
Foo* tmp_buf;
int tmp_capacity;
int tmp_size;
tmp_buf = other.buf_;
tmp_capacity = other.capacity_;
tmp_size = other.size_;
other.buf_ = buf_;
other.capacity_ = capacity_;
other.size_ = size_;
buf_ = tmp_buf;
capacity_ = tmp_capacity;
size_ = tmp_size;
}
Foo* buf_;
int capacity_;
int size_;
};
/* You've already guessed where this is going.
* Suppose we want now a container of, say, int that works the same way as our
* Foo_vector. We could copy & paste, and strategically replace "Foo" with
* "int".
*
* Or we could write a class template. Class templates are instructions for
* instantiating classes parametrically on types and values. Syntactically,
* they work just like function templates.
*
* I'm leaving out the comments this time.
*/
template<class T>
class vector {
public:
vector()
: buf_(new T[initial_capacity]()),
capacity_(initial_capacity),
size_(0) {}
vector(int initial_size)
: buf_(new T[initial_capacity > initial_size ?
initial_capacity
: initial_size]()),
capacity_(initial_capacity > initial_size ?
initial_capacity
: initial_size),
size_(initial_size) {}
vector(const vector& other)
: buf_(0),
capacity_(initial_capacity > other.size() ?
initial_capacity
: other.size()),
size_(other.size())
{
buf_ = new T[capacity_];
try {
for (int i = 0; i < size_; ++i)
buf_[i] = other[i];
} catch (...) {
delete[] buf_;
throw;
}
}
~vector()
{
delete[] buf_;
}
vector& operator=(const vector& other)
{
vector temp(other);
swap(temp);
}
int size() const { return size_; }
T& operator[](int index)
{
if (index < 0 || index >= size())
throw std::out_of_range("Invalid index to vector");
return buf_[index];
}
const T& operator[](int index) const
{
if (index < 0 || index >= size())
throw std::out_of_range("Invalid index to vector");
return buf_[index];
}
void push(const T& foo)
{
if (size() + 1 > capacity_) {
T* new_buf = new T[capacity_ * 2];
try {
for (int i = 0; i < size_; ++i)
new_buf[i] = buf_[i];
} catch (...) {
delete[] new_buf;
throw;
}
delete[] buf_;
buf_ = new_buf;
}
buf_[size_++] = foo;
}
T pop() { return buf_[--size_]; }
private:
static const int initial_capacity = 128;
void swap(vector& other)
{
T* tmp_buf;
int tmp_capacity;
int tmp_size;
tmp_buf = other.buf_;
tmp_capacity = other.capacity_;
tmp_size = other.size_;
other.buf_ = buf_;
other.capacity_ = capacity_;
other.size_ = size_;
buf_ = tmp_buf;
capacity_ = tmp_capacity;
size_ = tmp_size;
}
T* buf_;
int capacity_;
int size_;
};
int main()
{
// just to demonstrate that the general approach works
Foo_vector fvec1; // default constructor
Foo_vector fvec2(100); // initial-size constructor
Foo_vector fvec3(fvec2); // copy constructor
fvec2 = fvec1; // copy assignment operator
Foo f { 3, 2.5, "hello" };
std::cout << "fvec2 initial size: " << fvec2.size() << '\n';
fvec2.push(f);
std::cout << "size after push: " << fvec2.size() << '\n';
std::cout << "fvec2[fvec2.size() - 1].quux: "
<< fvec2[fvec2.size() - 1].quux << '\n';
// let's repeat the exercise with our template class
// unlike function templates, these don't do type inference
// so you have to specify the template parameters every time
// (unless they're optional)
vector<Foo> tvec1;
vector<Foo> tvec2(100);
vector<Foo> tvec3(tvec2);
tvec2 = tvec1;
std::cout << "tvec2 initial size: " << tvec2.size() << '\n';
tvec2.push(f);
std::cout << "size after push: " << tvec2.size() << '\n';
std::cout << "tvec2[tvec2.size() - 1].quux: "
<< tvec2[tvec2.size() - 1].quux << '\n';
// and we can instantiate our vector<T> template class for any type
// T we like (ok, it has to have a default constructor)
vector<int> ivec(5);
ivec[0] = 1;
ivec[1] = 2;
ivec[2] = 3;
ivec[3] = 4;
ivec[4] = 5;
for (int i = 0; i < ivec.size(); ++i)
std::cout << "ivec[" << i << "] = " << ivec[i] << '\n';
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment