Dennis Hedegaard's Blog

I’m used to implement tree structures in object oriented languages, which of course is a nice thing to be able to do. For some time now I’ve been doing some coding in C, first the shell to learn more about pipes, forks and so on, this time it’s about implementing a tree structure in C, each node in the tree has 2 parents (a left and a right) and 2 children, the idea is more of a grid where a nodes left child can be the left parents, left childs, right child (if that makes sense).

The idea of this, is to try and take the maximum sum of a path, from the top to the bottom.

More over I’m parsing the tree structure from a file, where the structure is a bit like this (without the spaces at the beginning):

                            75
                          95 64
                        17 47 82
                      18 35 87 10
                    20 04 82 47 65
                  19 01 23 75 03 34
                88 02 77 73 07 63 67
              99 65 04 28 06 16 70 92
            41 41 26 56 83 40 80 70 33
          41 48 72 33 47 32 37 16 94 29
        53 71 44 65 25 43 91 52 97 51 14
      70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
  63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

So for instance if we take 35, which is in the 4. line, it has 17 as left parent, 47 as right parent, 4 as left child and 82 as right child.

The struct I use for this is pretty basic:

struct node {
        int value;
        int sum;
        struct node *parentleft;
        struct node *parentright;
        struct node *left;
        struct node *right;
};

The sum is used to keep intermediate calculations, the value is the number the node repressents, the rest is pretty self self explainatory.

The parsing is done using a pointer for the current node, and a pointer to the top. There are 3 cases, which are all explained here:

1. If we encounter a space (‘ ‘), we move the current node pointer to its parent right, then we check to see if current’s right is null, if so we allocate it, then we check to see if currents right parent isn’t null and that current right parents right child isn’t null, if that’s the case, we then set the new nodes right parent to currents parents rights, right node and the other way around. The we move current to current right, which is the new node (or an existing node) and add 1 to a “rowcount” variable.
2. If we encounter a newline(‘\n’), current now points to the top node of the tree, then we follow the left child down “rowcount” – 1 times and allocate on our way down as necessary. This time we try to set new nodes left parent and vica versa (as described above, just the other direction). Then we reset “rowcount” to 0.
3. If we encounter a number, we then set currents value to that number, if there’s already a part of a number in value, we take that and multiplies it by 10, then adds the new value. So if 3 is in value, and we encounter 4, it’s: 3 * 10 + 4, which is 34.

Now for the recursive iteration through the tree:

The recursion is pretty basic, it simply calculates the sum of the child node to the left and right, returning the maximum of these upwards, the sum variable here stores the result, so if we encounter the same node again (which we will in big trees), we don’t have to calculate the sum again. This gives an extreme speed increase, since all sums only have to be calculated once:

int recursivesum(struct node *node) {
        if (node->sum == 0) {
                int left = 0, right = 0, sum;
                if (node->left != NULL)
                        left = recursivesum(node->left);
                if (node->right != NULL)
                        right = recursivesum(node->right);
                sum = (left > right ? left : right) + node->value;
                node->sum = sum;
                return sum;
        }
        else
                return node->sum;
}

Now there’s an apparent problem here, if the sum of a deep subtree is 0, it’ll get recalculated without the sum.

Now then, since I use malloc for the tree, it means everything in the tree is allocated on the heap. For this I made a function that frees a tree (or subtree), it’s pretty basic since it just checks if both children are NULL, if not we call recursively, then we make sure that the parents (if any) aren’t pointing to this node anymore. Then we free the current node and return.

void freetree(struct node *node) {
        if (node->left != NULL)
                freetree(node->left);
        if (node->right != NULL)
                freetree(node->right);
        if (node->parentleft != NULL)
                node->parentleft->right = NULL;
        if (node->parentright != NULL)
                node->parentright->left = NULL;
        free(node);
}

Now this is how I chose to solve a problem found at project euler, which is why I don’t link the code in it’s full version.

Now, I know assert.h is not meant for unit testing, I know it’s got alot of limitations (like stopping the process on error, no easy way to organize, isolate or initialize test cases alone and so on). But for small function test driven development it’s rather decent, here’s an example of a function that checks if the first string (s) end with the same chars as the second string (t):

#include <assert.h>
#ifndef NULL
#define __DEF_NULL
#define NULL 0
#endif

/**
  * Takes 2 strings, if s ends with t, returns 1, else 0.
  */
int strend(const char *s, const char *t);

int main() {
	assert(strend(NULL, NULL) == 0);
	assert(strend(NULL, "test") == 0);
	assert(strend("test", NULL) == 0);
	assert(strend("hej", "dav") == 0);
	assert(strend("hejsa", "jsa") == 1);
	assert(strend("hej", "davhej") == 0);
	assert(strend("davs", "davs") == 1);
	assert(strend("hejsa", "hejsb") == 0);
	assert(strend("hejsa", "heisa") == 0);
	assert(strend("hejsa", "hejba") == 0);
	assert(strend("jeg er glad", "r glad") == 1);
	assert(strend("hejsa", "ejs") == 0);
	return 0;
}

int strend(const char *s, const char *t) {
	const char *ptrs = s, *ptrt = t;
	if (s == NULL || t == NULL)
		return 0;
	while (*ptrs != '\0')
		ptrs++;
	while (*ptrt != '\0')
		ptrt++;
	while (*ptrs == *ptrt) {
		if (ptrs == s)
			return ptrt == t ? 1 : 0;
		else if (ptrt == t)
			return 1;
		else {
			ptrt--;
			ptrs--;
		}
	}
	return 0;
}

#ifdef __DEF_NULL
#undef NULL
#endif

For real unit testing capabilities in c, I’ll have a loop at cunit or similar.

I’ve used the last week or so programming a simple shell in c, for now it features some internal commands like cd, ls, environ, help, quit, etc.

One of the big challenges in the future of the project is to make it compile on more systems than linux, for instance if reads the absolute executable path with readlink() from /proc/pid/exe, which is very specific.

The shell should still be filled with bugs here and there, I’ll start bug hunting tomorrow.

you can find the project on git as usual, keep in mind that I use cmake instead of autotools.

source: http://git.neo2k.dk/?p=sash.git;a=summary

One of the great things about java was the logging framework under java.util.logging, it was simple, extendable and efficient. I’ve tried to take those properties and implement a logging framework for the .net platform in c#, for now it features a logger with some logging level, these determine if a log event should get filtered, there are the usual: fine, info, warning and severe. For the actually logging you implement something called a handler with a Write method, this method takes a log event with a time, level and message.

This is very similar to java’s implementation, but why change something that works well ?

I’ll be updating it with features (new ready-made handler implementations, info about the method that made the logging etc) and tweaks from time to time, for now it works.

The DEFAULT_LOGGER on the Logger class can be used to log to stderr, without having to create a logger and implement your own handler.

Feel free to try it, feedback is welcome.

git: http://git.neo2k.dk/?p=cs/logging.git;a=summary

dll: http://pub.neo2k.dk/logging/

I’m used to the java way of xml, which is using StAX. In C# there are some default namespaces for xml, these are:

• System.Xml
• System.Xml.Schema
• System.Xml.Serialization
• System.Xml.XPath
• System.Xml.Xsl

For this post I’m only going to use 2 classes from the System.Xml namespace, namely XmlTextWriter and XmlTextReader. These can be used to read and write xml in a way very close to what I’m used to in StAX.

The writer works just as you’d expect, there’s a WriteStartDocument() for witing the xml header, WriteStartElement() for writing start elements, WriteAttributeString() for writing attributes to elements. When closing elements simply used WriteEndDocument() and WriteEndElement().

For the reader there’s a bit of a iterative touch to it, just as with StAX, for instance you usually have an outer while loop, which iterates on Read(). Whenever read is true, you can switch the result with a XmlNodeType. To get elements simply use the Element type, to get an end of an element use EndElement. When inside an element with attributes you go through the attributes with a for loop, counting to the number of attributes, the number is the AttributeCount property on the reader. You move the reader through the properties with the method MoveToAttribute(int i), where i is the number of the attribute (starting from 0 of course).

The reader has a Name and Value property, these change depending on what element the reader currently is at, if the current element is an attribute, then the name and value is the name and value of that attribute. For elements the element name is Name.

Here’s a simple example using this:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml;
using System.IO;

namespace xmltest {
    class Program {
        static void Main(string[] args) {
            XmlTextWriter writer = new XmlTextWriter(new StreamWriter("test.xml"));
            writer.WriteStartDocument();
            writer.WriteStartElement("users");
            writer.WriteStartElement("user");
            writer.WriteAttributeString("name", "svend");
            writer.WriteAttributeString("pass", "1234");
            writer.WriteEndElement();
            writer.WriteEndElement();
            writer.WriteEndDocument();
            writer.Close();
            System.GC.Collect();
            Console.WriteLine("all done.");
            XmlTextReader reader = new XmlTextReader(new StreamReader("test.xml"));
            while (reader.Read()) {
                switch (reader.NodeType) {
                    case XmlNodeType.Element:
                        Console.WriteLine("start: {0}", reader.Name);
                        if (reader.AttributeCount > 0)
                            for (int i = 0;i < reader.AttributeCount;i++) {
                                reader.MoveToAttribute(i);
                                Console.WriteLine("attrib: {0} - value: {1}",
                                    reader.Name, reader.Value);
                            }
                        break;
                    case XmlNodeType.EndElement:
                        Console.WriteLine("end:   {0}", reader.Name);
                        break;
                }
            }
            reader.Close();
            Console.WriteLine("done");
            Console.Read();
            File.Delete("test.xml");
        }
    }
}

The code makes a users element, with a user element with 2 attributes (user and pass). The reads it back, since the user element is empty, it does not contain an end element.

i’ve heard you can dump stuff from ado.net to xml, read entire xml documents with XmlDocument and XmlDataDocument. I suspect the System.Xml.Serialization namespace contains some way to serialize objects to xml, but I’ll have to test that some other time.

Since the next semester will be spend learning some C#, I spend some time researching the language. I came across the term lambda expression, which in terms i an anonymous function or method, it is very similar to lambda calculus which is a way of expressing anonymous functions.

Some of the simpler ways to use these expressions are something like this:

first of we define a delegate, for instance:

delegate int multiply (int a, int b);

an example (static) implementation in lambda expression would be:

multiply multi_impl = (int a, int b) => a * b;

Such uses can be a bit dull, lambda expressions lack recursive behavior, much like lambda calculus is though to do, but using the generic Func class in System.Core one can create a Func object which references a method of itself thereby creating recursion. Here’s an example of a fibonacci calculation:

First the recursive part:

Func<long, object, long> fibonacci_impl = (i, func) => i == 0 ^ i == 1 ? i :
    ((Func<long, object, long>)func)(i - 2, func) +
    ((Func<long, object, long>)func)(i - 1, func);

The object in the middle is the function itself, however since it cannot reference itself explicit we do it this way and start the recursion from another expression, which can be found below:

Func<long, long> fibonacci = i => i < 0 ? -1 : fibonacci_impl(i, fibonacci_impl);

It is important to notice that the fibonacci method only takes one argument and starts the function above that one with the integer and the function itself, moreover the casts from object to fibonacci_impl is necessary since fibonacci_impl is unable to reference itself in the expression.

I some benchmarking comparing it to a normal recursive function, and the normal way is faster. I realize that lambda expressions aren’t meant for recursion just yet, but is another way to minimize code when implementing anonymous methods. It still fun to mess with however =)

For more on lambda calculus: http://en.wikipedia.org/wiki/Lambda_calculus

Under the “recursion and fixed points” section there is the same way of doing recursion, but in lambda calculus. And as is written:

“In lambda calculus, one cannot define a function which includes itself. To get around this, one may start by defining a function, here called g, which takes a function f as an argument.”

Here are some test results from a simple benchmark using vector, list, queue and stack in the c++ stl:

The benchmarks are done on 40.000.000 structs with a string and an int.

With aggressive optimizations (-march=native -funroll-all-loops -fomit-frame-pointer -finline -O9 -ffast-math):

$ ./stacktest
5.59 seconds
$ ./linkedtest
8.05 seconds
$ ./queuetest
5.51 seconds
$ ./vectortest
10 seconds

Without aggressive optimizations:

$ ./stacktest
8.3 seconds
$ ./linkedtest
12.84 seconds
$ ./queuetest
7.82 seconds
$ ./vectortest
12.89 seconds

What’s noteworthy is that a queue and a stack is pretty close in performance, compared to a vector and list.

The code for the project is on git for now:

http://git.neo2k.dk/?p=sum_benchmark.git;a=summary

I’m using cmake for makefiles :>

Printing the current working directory from C proved to be easier than i though.

First of all I use the method getcwd from unistd.h, it takes a char * and a size, if the length of the workdir exceeds the size of the allocated space for the pointer, NULL is returned. NULL is also returned if the directory can’t be determined for some reason.

Here’s how I chose to do it:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define PATH_SIZE 1024

int main(void) {
 char *a = malloc(sizeof(*a) * PATH_SIZE);
 if (!getcwd(a, PATH_SIZE)) {
 fprintf(stderr, "Unable to determine working dir or the workdir was too long.\n");
 exit(1);
 }
 printf("%s\n", a);
 return 0;
}

As you can see, the method is quiet easy to use. If you’re using GNU, you can actually define SIZE as NULL (or 0) and the method will provide a malloc’ed char * with a path.

UPDATE: Some error handling etc:

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

/* Set this parameter to the amount of memory you want to allocate.
 * In terms of numbers of chars*/
#define PATH_SIZE 1024

int main(void) {
 int size = sizeof(char) * PATH_SIZE;
 char *a = malloc(size);
 memset(a, '\0', size);
 if (!a) {
  fprintf(stderr,
   "Unable to allocate memory (%f bytes).\n",
   size);
  exit(1);
 }
 if (!getcwd(a, PATH_SIZE)) {
  fprintf(stderr,
"Unable to determine working dir or the workdir was too long.\n");
  exit(1);
 }
 printf("%s\n", a);
 if (a) {
  free(a);
  a = NULL;
 }
 return 0;
}

I feel like I can use some of the datatypes and different streams in C++ now, I made some code to generate fibonacci numbers in an iteration and streaming it to a file, so I’d for instance generate every fibonacci number between 0 and 10 and put the values in a file.

My fibonacci sollution is recursive, which is rather bad for performance later up in the number (after 40 and so on), so I decided to use a vector to keep numbers in, that way I only have to generate numbers, that I do not know.

Actually a fully iterative approach may not be impossible at all, but I need some sleep now =)

Here’s a link to the sollution on the git repository:

http://git.neo2k.dk/?p=cpp/fibopp.git;a=blob;f=fibopp.cpp;hb=HEAD

UPDATE: since 8fc05da, the sollution is now iterative, which means it generates number up to 100 below 1 second. The problem is that a long long is a bit too small here =)

Here’s a diff on gitweb: http://git.neo2k.dk/?p=cpp/fibopp.git;a=blobdiff;f=fibopp.cpp;h=9e3ef18c5d91cf8b7b9cfbeb872a963204cb884f;hp=f93258e4fa3514ab6b6e8de85acc4e84978a174f;hb=8fc05dabd0db9cac130a7e1c8c65daea973b128d;hpb=fd7bdbc6a27cbaddadc021eeaf1cb4c36dfaab49

I posted an entry some time ago about autoconf and automake, how to configure and use it for C.

Now that my eyes have turned to C++, it’s rather easy to configure to use like this:

an example configure.in:

AC_INIT(test.cpp)
AM_INIT_AUTOMAKE(test, 0.1)
AC_PROG_CXX
CFLAGS="-O2 -pedantic -Wall -ansi"
AC_STDC_HEADERS
AC_OUTPUT(Makefile)

As you might see, all it takes is AC_PROG_CXX instead of AC_PROG_CC.