Quick Example of Red Black Tree.

In previous articles, FreeBSD AVL tree is ported to Linux and a usage example is presented.
Linux uses red-black tree instead of AVL.  Just searching for rbtree.h in Linux kernel returned so many components such as ext4.  But, rbtree can't be used in user space in kernel source form.  Luckily there is user-space ported rbtree in here.

That code contains a test code.  Here, I post one more example.  My example is the same test written in AVL test code (here).

By the way, using these codes have advantage of efficiency.
Enjoy.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include "rbtree.h"
#include "rbtree_test.h"


void printTree(RBRootType *root)
{
 int count = 0;
 Person *data, *rootdata;
 RBNodeType *cur;

 rootdata = container_of( root->rb_node, Person, node);
 printf("Root node: %s\n", rootdata->name);
 
 cur = rb_first(root);
 while (cur) {
  data = container_of( cur, Person, node);
  printf("%d : %s(%s)\n", count, data->name, data->phone);
  cur = rb_next(cur);
  count++;
 }
 printf("Total nodes in tree: %d\n", count);
 printf("---------------------------------------------------------------------\n");

}

Person* searchPerson(RBRootType *root, char *name)
{
 RBNodeType *curnode = root->rb_node;
 while (curnode) {
  Person *data = container_of(curnode, Person, node);
  int result;

  result = strcmp(name, data->name);

  if (result < 0)
   curnode = curnode->rb_left;
  else if (result > 0)
   curnode = curnode->rb_right;
  else
   return data;
 }
 return NULL;
}

int insertPerson(RBRootType *root, Person *data)
{
 RBNodeType **new = &(root->rb_node), *parent = NULL;
 while (*new) {
  Person *cur = container_of(*new, Person, node);
  int result = strcmp(data->name, cur->name);
  
  parent = *new;
  if (result < 0)
   new = &((*new)->rb_left);
  else if (result > 0)
   new = &((*new)->rb_right);
  else 
   return 0;
 }
 
 // New node
 rb_link_node(&(data->node), parent, new);
 rb_insert_color(&(data->node), root);

 return 1;
}


int main(int argc, char **argv)
{
 RBRootType mytree = RB_ROOT;

 Person a;
 memset(&a, '\0', sizeof a);
 strncpy(a.name, "Micheal Smith", 14);
 strncpy(a.phone, "1112223333", 11);
 insertPerson(&mytree, &a);

 Person b;
 memset(&b, '\0', sizeof b);
 strncpy(b.name, "Jack Stuart", 12);
 strncpy(b.phone, "2223334444", 11);
 insertPerson(&mytree, &b);
 
 
 Person *srch = NULL;
 printTree(&mytree);
 
 if ( (srch = searchPerson(&mytree, "Micheal Smith")) != NULL ) 
  printf("Micheal found: %s\n", srch->phone);
 else
  printf("Micheal not found.\n");

 if ( (srch = searchPerson(&mytree, "Jack Stuart")) != NULL ) 
  printf("Jack found: %s\n", srch->phone);
 else
  printf("Jack not found.\n");
 printf("--------------------------------------------------\n");
 
 /**
  *          Mike
  *          /  
  *        Jack
  */

 // If I add Andrew, it's unbalanced.
 Person c;
 memset(&c, '\0', sizeof c);
 strcpy(c.name, "Andrew Kudos");
 strcpy(c.phone, "3334445555");
 insertPerson(&mytree, &c);

 //traverse!!  root must be Jack.
 printTree(&mytree);

 
 return 0;
}

Sample Usage of AVL, quick and dirty.

So, previous article ported FreeBSD AVL into Linux AVL. (AVL Tree in C )
Here is quick and dirty way of how to use it.
It will be straightforward, except one thing.

Your data struct must be divided into two pieces.  Data part and avl_node_t part.  The Data part size must be multiple of 8.  If not, there will be a puzzling assert((offset & 0x7) == 0).  Here is the usage.  For convinience, I put the link part the first.  This will easy to cast type between (avl_node_t) and (struct person) with the same pointer.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <string.h>
#include <stdint.h>
#include "avl.h"

#define NAME_LEN 36
#define PHONE_LEN 10

// assuming dtype has a link member as node type (avl_node_t)
#define OFFSETOF(data) 0

typedef struct person {
 avl_node_t  my_link; 
 char name[ NAME_LEN + 1];
 char phone[ PHONE_LEN + 1];
} Person;

int comparePerson(const void *a, const void *b) 
{
 Person *_a = (Person *)a;
 Person *_b = (Person *)b;
 if ( strncmp(_a->name, _b->name, NAME_LEN) < 0 )
  return -1;
 else if ( strncmp(_a->name, _b->name, NAME_LEN) > 0 )
  return 1;
 return 0;
}

Person* searchByName(avl_tree_t *tree, const char *name)
{
 Person *cur = AVL_NODE2DATA(tree->avl_root, tree->avl_offset);
 avl_node_t *p;
 while (cur) {
  if (strcmp(cur->name, name) == 0)
   return cur;
  else if (strcmp(name, cur->name) <0) {
   p = AVL_DATA2NODE( cur, tree->avl_offset );
   p = p->avl_child[0];
  }
  else {
   p = AVL_DATA2NODE( cur, tree->avl_offset );
   p = p->avl_child[1];
  }
  cur = p ? AVL_NODE2DATA( p, tree->avl_offset) : NULL;
 }
 return NULL;
}

void printTree(avl_tree_t *tree)
{
 int i = 0;
 Person *cur;

 printf("Total nodes in tree: %ld\n", avl_numnodes(tree));
 printf("Root: %s\n", ((Person *)(AVL_NODE2DATA( tree->avl_root, tree->avl_offset)))->name);

 cur = avl_first(tree);
 while (cur) {
  printf("%d : %s(%s)\n", i, cur->name, cur->phone);
  cur = AVL_NEXT(tree, cur);
  i++;
 }
 printf("---------------------------------------------------------------------\n");
}

int main(int argc, char **argv)
{
 avl_tree_t avl;

 Person a;
 memset(&a, '\0', sizeof a);
 strncpy(a.name, "Micheal Smith", 14);
 strncpy(a.phone, "1112223333", 11);
 avl_create(&avl, comparePerson, sizeof(Person), OFFSETOF(&a));
 avl_add(&avl, &a);

 Person b;
 memset(&b, '\0', sizeof b);
 strncpy(b.name, "Jack Stuart", 12);
 strncpy(b.phone, "2223334444", 11);
 avl_add(&avl, &b);

 //traverse 
 printTree(&avl);

 /**
  *          Mike
  *          /  
  *        Jack
  */

 // If I add Andrew, it's unbalanced.
 Person c;
 memset(&c, '\0', sizeof c);
 strcpy(c.name, "Andrew Kudos");
 strcpy(c.phone, "3334445555");
 avl_add(&avl, &c);

 //traverse!!  root must be Jack.
 printTree(&avl);

 // Searching.
 Person *search;
 search = searchByName(&avl, "Jack Stuart");
 if (search) 
  printf("Jack found: %s\n", search->name);
 else
  printf("Jack not found\n");

 search = searchByName(&avl, "lalalalala");
 if (search)
  printf("lala found:\n");
 else
  printf("lala not found\n");

 return 0;
}

AVL Tree in C

I ported FreeBSD avl implementation into Linux users pace version.
Code is here(github link).

Practically speaking, we don't need AVL tree these days in high level languages like Python.  There are good alternatives in general.  In algorithm perspective, there is a Red Black Tree, the rival of AVL tree.  They mostly serve for the similar purpose.  RBTree is easier to implement, but size is factor of 2 vs. AVL is 1.4.  Linux uses RBTree internally, and FreeBSD had AVL.  (Linux RBTree article)

Well, in day to day life, modern languages provide their own version of "List".  In Python case, we just stuff data into the list, and later call it by index.  For efficient search, we use bisect module.  If we need sort, Python list takes very "Intelligent" approach to be efficient.  I will discuss this later, but listsort.txt in Python source can be referenced.

But, then, why bother AVL tree?
First, it's mentioned more in different algorithm books probably thanks to BST (Binary Search Tree).  And, AVL is a good subject to introduce concepts of algorithm, "let's cover the weakness of a given algorithm."  Second, it's personal.  I just like it with no reason.

When I searched AVL written in C, I found many pages.  First, GNU libavl is an overkill.  Other small projects are not mature enough.  Either it's "not generic", or data allocation logic is "malloc".  This will cost performance.  Modern days, C is chosen by performance in many cases.  So, too many or individual malloc is a bigger penalty.

Interestingly, FreeBSD has avl implementation and they still include it even today.  Probably, former SunOS used avl for kernel data.  This is small.  This only implements AVL algorithm, but comparator is a function pointer which I can attach.  AVL node does not bother the data, but my data suppose to embed avl_node_t.  And, AVL algorithm doesn't do high-level search.  So, I have to provide the high level search, like searchByName(const char *key).  I liked the design  because it is more flexible.  Unfortunately, it's not directly usable in Linux.  So, I tweaked and made it usable in Linux.  There are two files (avl.h and avl.c).  Enjoy.

Experience with FreeBSD

I use Windows Vista on my laptop, but I miss Linux a lot.

Maybe I am not the only one to see these days problems of popular Linux distros.  "Bloated."

My best featured machine is 5-year-old Dell Inspiron 1521 (AMD, 2G mem, 120G disk).  This barely runs modern FC15 without visual effects.  My choice of Desktop, KDE turned down my love with their broken nepomuk indexer.  

I feel like, my laptop is ruled out.  When I found myself disabling default stuffs just to make my user experience not terrible, a question came up.  Aren't there any other distro for small boxes?

Well, there are DamnSmallLinux.  But that's not a major distro.

How about Gentoo?  I used to be a big fan of Gentoo, but now I don't like compiling unless I have to do so.  If Gentoo supports binary packages a little better, that will be the perfect distro.

Then, FreeBSD came.

   1. FreeBSD is a major distro, and actually a traditional unix than Linux.

   2. FreeBSD supports not only source compilation, but also does binary packages.  Very strong and convenient.

   3. If the software works on both FreeBSD and Linux, then most likely its compatibility level is very high already.

However, I just realized that #3 is self-torturing, too much.  

I was about to develop my own patch for screen-4.0.3 on FreeBSD, I ran into a different issue.

Complaint of "sys/stropts.h".

I didn't know what that header file supposed to be... But, well, elite programmers like screen developers use this, and there should be a reason to be used.  So, I searched and learned about how FreeBSD organize compatibility header files.  But, when I looked at binary patch file, disappointed a little bit.

 

--- process.c
+++ process.c
@@ -37,7 +37,7 @@
 #include "config.h"
 
 /* for solaris 2.1, Unixware (SVR4.2) and possibly others: */
-#ifdef SVR4
+#if defined(SVR4) && !defined(__FreeBSD__)
 # include sys stropts.h
 #endif
 




This happens three times in different files.  

In other words, FreeBSD doesn't use this header.  Reading a little more from stackoverflow, surely this is for Sun.  Main source tree not having this patch means, FreeBSD isn't major enough, and I will run into this situations in the future..  This is self-torturing.  

Fine!  Close to 10 years of Development life won't give up this obstacle.  It's tedious, but not difficult.  So, I prepared seperate header directory from /usr/src/sys/compat/svr4/, and renamed its contents.  (svr4_ was prefixed, DAMN!!).  Modified Makefile and compiled.  The next "make" command passed "sys/stropts.h", but another complaint.

utmp.c:731: error: 'struct utmpx' has no member named 'ut_xtime'




struct is difined differently??  From BSD and Linux??

And again, from binary patch file (patch-os.c, patch-utmp.c) read about how to work around utmp problem (the patch was describing how to replace some sections of code, not just lines), I realized that "ENOUGH!!!"  Having compatibility by paying this torturing is costly.  I accepted that "FreeBSD isn't popular enough."

Now, I am not sure if I want to try out Arch Linux.