FreeBSD tree.h Example

Introduction

The FreeBSD Project offers a nice header file called tree.h which provides macro implementations of a few tree-based data structures, including Splay and Red-Black trees. In this article I will introduce installing the header file into a MinGW environment and using it to build a simple sorting program.

Installation and Quickstart

1. Download the required files

tree.h: http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/tree.h
cdefs.h: http://svnweb.freebsd.org/base/user/attilio/membarclean/sys/cdefs.h

2. Install headers into a reasonable place

mkdir "%USERPROFILE%/include/freebsd/"
mkdir "%USERPROFILE%/include/freebsd/sys/" 
cp -v tree.h cdefs.h "%USERPROFILE%/include/freebsd/sys/"

3. Install manpages

(Step omitted - you can find the manpages online and install them locally if you want)

4. Update environment

Add %USERPROFILE%/include/freebsd to CPATH
Add man directory to MANPATH

5. Compile the program (Code listing is below)

gcc -Wall -o mysort mysort.c

6. Run the program

The program works basically the same way sort(1) does. For simplicity it recognizes no options and does only minimal error checking. Example usage:

mysort < input.txt > output.txt

Code Listing: mysort.c

 #include <stdio.h>  
 #include <stdlib.h>  
 #include <string.h>  
 #include <sys/tree.h>  
 #define MAXLINE 1000  
 /******************************************************************************/  
 typedef struct StrList StrList;  
 typedef struct StrListNode StrListNode;  
   
 struct StrListNode {  
     RB_ENTRY(StrListNode) entry_;  
     char buf[];  
 };  
 static int StrListNode_compar(StrListNode *a, StrListNode *b) {  
     char *akey = a->buf;  
     char *bkey = b->buf;  
     int r;  
     if ((r = strcmp(akey, bkey)) == 0)  
         return 1; // force duplicate strings to be stored   
     return r;  
 }  
 RB_HEAD(StrList, StrListNode) StrListHead = RB_INITIALIZER(&StrListHead);  
 RB_GENERATE_STATIC(StrList, StrListNode, entry_, StrListNode_compar);  
 /******************************************************************************/  
   
 #define fatal(...) do{\  
     printf("Fatal error: ");\  
     printf(__VA_ARGS__);\  
     exit(EXIT_FAILURE);\  
 }while(0)  
   
 static char buf[MAXLINE];  
   
 // Read strings from stdin and print them in order  
 int main(int argc, char *argv[])  
 {  
     if (argc != 1) {  
         printf("Syntax: mysort\n");  
         (void)argv;  
         exit(EXIT_SUCCESS);  
     }  
       
     // Read integers into StrList headed by StrListHead  
     StrListNode *sln;  
     while ((fgets(buf, sizeof(buf), stdin)) != NULL) {  
         size_t n = strlen(buf);  
         if ((sln = malloc(sizeof *sln + n + 1)) == NULL) {  
             fatal("memory allocation error\n");  
         }  
         strcpy(sln->buf, buf);  
         RB_INSERT(StrList, &StrListHead, sln);  
     }  
     if (!(feof(stdin))) {  
         fatal("error reading from stdin\n");  
     }  
       
     // Start from the lowest string and print keys in order  
     for (sln = RB_MIN(StrList, &StrListHead); sln != NULL; sln = RB_NEXT(  
             StrList, &StrListHead, sln))   
     {  
         printf("%s", sln->buf);  
     }  
   return EXIT_SUCCESS;  
 }  
   

Explanations

typedef struct StrList StrList;

This typedef basically defines a name which will be used to refer to the tree. Some of the macros in tree.h require this name as a parameter.

typedef struct StrListNode StrListNode;

The StrListNode type defines our custom structure to store our data. It must contain an `entry' member with a type of RB_ENTRY(StrListNode). The name that you choose for the `entry' member must be provided to the tree generation macro.

static int StrListNode_compar(StrListNode *a, StrListNode *b);

This function defines a comparator for objects of type StrListNode. It should work similarly to the compar function provided to bsearch(3) and qsort(3). Normally, the comparator function should return 0 if the objects are equal, and in this case, the tree macros will not re-insert that item. However, in the program listing, I have slightly abused this rule in order to force duplicate strings to be stored in the tree. A more robust implementation would probably instead store a counter along as part of the StrListNode and simply increment the counter when a duplicate string is encountered.

RB_HEAD(StrList, StrListNode) StrListHead = RB_INITIALIZER(&StrListHead);

RB_GENERATE_STATIC(StrList, StrListNode, entry_, StrListNode_compar);

These two lines will generate the struct(s) and function(s) which allow tree.h to do its magic. The name StrListHead is defined here, which will be needed for some macro calls. For compatibility purposes, I have used the RB_GENERATE_STATIC version of the macro in order to limit visibility of this tree structure to file scope.

StrListNode *sln = malloc(sizeof *sln + (n+1));

Allocate a new node which will store a string of length n. In this particular case, I am adding n+1 to the size of the node in order to allow the flexible struct member to store a character string with a string lenth of n characters. A pre-C99 implementation would instead create a struct hack member of 1 byte in size, and then allocate (sizeof *sln + n) bytes, which should be enough to hold the n bytes of the string plus the null terminator.

RB_INSERT(StrList, &StrListHead, sln);

Insert the object pointed to by sln into our StrList headed by StrListHead.

for (sln = RB_MIN(StrList, &StrListHead); sln != NULL; sln = RB_NEXT(StrList, &StrListHead, sln))

Implement an idiomatic "foreach-style loop". The call to RB_MIN returns a pointer to the smallest member, and the call to RB_NEXT advances the pointer to the next item. At the end of the list, the pointer will contain NULL. There is also a RB_FOREACH macro which simplifies this notation. However, in my tests I noticed  that the above version performs better. In addition, the above notation, although a bit lengthy in terms of typing out the symbol names, is easy to follow logically.

References

http://www.unix.com/man-page/freebsd/3/TREE/
http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/tree.h
http://svnweb.freebsd.org/base/user/attilio/membarclean/sys/cdefs.h

Done.