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.

Metronome for Linux in Python

I changed my metronome.c in python to work with Windows. ( Initially, I made a mistake which errored in Windows.) I didn't distinguish binary/text mode in Windows, which doesn't matter in Linux. After adding sys.platform condition, it works, but looks a little clumsy.

To use this,

$ python metronome.py [sample_file] [bpm] [duration in sec]

For example, this command will generate "a.wav" which has 120 BPM beat for 15 sec. s3.wav is a simple beep wav in 44100 wav encode.

$ python metronome.py s3.wav 120 15

Here is the code:

#!/usr/bin/env python

import os
import sys
import struct

empty_sound = struct.pack('bbbbbbbb', *( 4,0,0,0,6,0,6,0 ))

class WavHeader(object):
    def __init__(self, rawdata):
        self.tup = struct.unpack("iiiiihhiihhii", rawdata)
        self.chunk_id        = self.tup[0]
        self.chunk_sz        = self.tup[1]
        self.format          = self.tup[2]
        self.sub_chunk1_id   = self.tup[3]
        self.sub_chunk1_sz   = self.tup[4]
        self.audio_format    = self.tup[5]
        self.num_channel     = self.tup[6]
        self.sample_rate     = self.tup[7]
        self.byte_rate       = self.tup[8]
        self.block_align     = self.tup[9]
        self.bits_per_sample = self.tup[10]
        self.sub_chunk2_id   = self.tup[11]
        self.sub_chunk2_sz   = self.tup[12]

    def pack(self):
        return struct.pack("iiiiihhiihhii",  self.chunk_id, self.chunk_sz,
                                             self.format  , self.sub_chunk1_id,
                                             self.sub_chunk1_sz , self.audio_format,
                                             self.num_channel   , self.sample_rate ,
                                             self.byte_rate     , self.block_align ,
                                             self.bits_per_sample, self.sub_chunk2_id,
                                             self.sub_chunk2_sz )

ONE_SEC = 88200
def bytes_for_beat(bpm):
    ratio = bpm/60.0
    bytes_per_beep = ONE_SEC / ratio
    return int(bytes_per_beep)


def main():
    sample_fname = sys.argv[1]
    tempo = int(sys.argv[2])
    if tempo < 40:
        print >> sys.stderr, "Invalid tempo:    Make it between 40 - MAX"
        print >> sys.stderr, "   * longer the sample length, smaller the MAX"
        sys.exit(1)
    dura = int(sys.argv[3])
    if dura <= 0:
        print >> sys.stderr, "Invalid duration:  Make it greater than 0"
        sys.exit(2)

    # Reading sample header
    if sys.platform == 'win32':
        rd = open(sample_fname, "rb")
    else:
        rd = open(sample_fname, "r")
    sample_hdr = WavHeader(rd.read(44))
    sample_data = rd.read()
    rd.close()

    # Generating Beat data as WAV, storing temp file 't.wav'
    if sys.platform == 'win32':
        bdata = open("t.wav", "wb")
    else:
        bdata = open("t.wav", "w")
    tot_beats = dura * (tempo/60.0);
    bps = bytes_for_beat(tempo);
    tot_bytes = 0;
    for i in range( int(tot_beats)):
        bdata.write( sample_data )
        tot_bytes += sample_hdr.sub_chunk2_sz;
        for j in range( (bps - sample_hdr.sub_chunk2_sz)/8):
            bdata.write( empty_sound )
            tot_bytes += len(empty_sound)
    bdata.close()

    # Overwrite new size, and Generate output wav file 'a.wav'
    sample_hdr.sub_chunk2_sz = tot_bytes
    if sys.platform == 'win32':
        outf = open("a.wav", 'wb')
    else:
        outf = open("a.wav", 'w')
    outf.write( sample_hdr.pack() )
    if sys.platform == 'win32':
        outf.write( open('t.wav', 'rb').read() )
    else:
        outf.write( open('t.wav').read() )
    outf.close()


if __name__ == '__main__':
    main()

Metronome for Linux

A solution for "Metoronome" is a very simple algorithm

 def metronome(bpm, how_long):  
  while how_long > 0:  
   beep()  
   time.sleep( 60.0 / bpm )  
   how_long -= 60.0/bpm  

Unfortunately, this wouldn't work on regular OS like Linux or Windows on PC, since they are not real time OS. To make the matter worse, sleep() operation will definitely context switch out the process, and coming back will not be in consistent interval.

I needed a metronome. I knew that there are softwares doing "Metronome", mostly commercial.

So, dig through, and found one open source solution (open metronome), written in MFC. Since my computer for music is Linux, I just read and learned its brilliant idea. It generates WAV file for beeping. I wrote a program, doing so.

 #include <stdio.h>  
 #include <stdlib.h>  
 #include <stdint.h>  
 #include <sys/types.h>  
 #include <sys/stat.h>  
 #include <fcntl.h>  
 #include <string.h>  
 char empty_sound[8] = { 4, 0, 0, 0, 6, 0, 6, 0 };  
 struct wav_header {  
   // "RIFF" chunk descriptor  
   int32_t  chunk_id;  
   int32_t  chunk_sz;  
   int32_t  format;  
   // "fmt (header)" sub-chunk  
   int32_t  sub_chunk1_id;  
   int32_t  sub_chunk1_sz;  
   int16_t  audio_format;  
   int16_t  num_channel;  
   int32_t  sample_rate;  
   int32_t  byte_rate;  
   int16_t  block_align;  
   int16_t  bits_per_sample;  
   // "data (easily, music)" sub-chunk  
   int32_t  sub_chunk2_id;  
   int32_t  sub_chunk2_sz;  
   char   *data;  
 };  
 #define ONE_SEC 88200  // bytes  
 static void print_header(struct wav_header *hdr)  
 {  
   printf("(0) chunk id  : %x\n", hdr->chunk_id);  
   printf("(4) chunk size : %d\n", hdr->chunk_sz);  
   printf("(8) format   : %x\n\n", hdr->format);  
   printf("(12) sub chunk1 id  : %d\n", hdr->sub_chunk1_id);  
   printf("(16) sub chunk1 size : %d\n", hdr->sub_chunk1_sz);  
   printf("(20) audio format  : %d\n", hdr->audio_format);  
   printf("(22) num channels  : %d\n", hdr->num_channel);  
   printf("(24) sample rate   : %d\n", hdr->sample_rate);  
   printf("(28) byte rate    : %d\n", hdr->byte_rate);  
   printf("(32) block align   : %d\n", hdr->block_align);  
   printf("(34) bits per sample : %d\n\n", hdr->bits_per_sample);  
   printf("(36) sub chunk2 id  : %d\n", hdr->sub_chunk2_id);  
   printf("(40) sub chunk2 size : %d\n", hdr->sub_chunk2_sz);  
   printf("(44 -- ) DATA\n\n");  
 }  
 static int bytes_for_sec(int bpm)  
 {  
   float ratio = bpm/60.0;  
   float bytes_per_beep = ONE_SEC / ratio;  
   return (int)bytes_per_beep;  
 }  
 int main(int argc, char **argv)  
 {  
   char *sample_fname;  
   int tempo, dura, bps;  
   int rfd;       // Sample file descriptor  
   int wfd;       // Output file descriptor  
   int rc, i, j, tot_beats;  
   char buf[512 + 1];   // Sample hdr buffer  
   char *sample_buf, *ptr;  
   struct wav_header *hdr;  
   struct wav_header new_hdr;  
   if (argc < 3) {  
     printf("USAGE: %s <sample_wav> <tempo in BPM> <duration in sec>\n", argv[0] );  
     printf(" * sample_wav must be aligned by sample. Random clip of data may make a noise.\n");  
     printf(" example: $ %s s3.wav 120 60\n", argv[0]);  
     printf("  This will make an output of 'a.wav', using s3.wav as sample, 120 bps for 60sec.\n");  
     exit(0);  
   }  
   sample_fname = argv[1];  
   tempo = atoi(argv[2]);  
   if (tempo < 40) {  
     printf("Invalid tempo:  Make it between 40 - MAX, which is the fastest from sample\n");  
     exit(1);  
   }  
   dura = atoi(argv[3]);  
   if (dura == 0) {  
     printf("Invalid duration: Make it greater than 0.\n");  
     exit(2);  
   }  
   rfd = open(sample_fname, O_RDONLY);  
   rc = read(rfd, buf, 44);  
   if (rc < 0) {  
     perror("Sample read error\n");  
     exit(3);  
   }  
   hdr = (struct wav_header *)buf;  
   if ( NULL == (sample_buf = malloc( hdr->sub_chunk2_sz )) ) {  
     perror("Mem alloc failed (1)\n");  
     exit(4);  
   }  
   // copying sample data  
   ptr = sample_buf;  
   while ( 0 < (rc = read(rfd, ptr, 512)) ) {  
     ptr += rc;  
   }  
   wfd = open("t.wav" , O_WRONLY | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);  
   if (wfd < 0) {  
     perror("Error opening write file");  
   }  
   tot_beats = dura * (tempo/60.0);  
   bps = bytes_for_sec(tempo);  
   int tot_bytes = 0;  
   for (i =0; i<tot_beats; ++i) {  
     write(wfd, sample_buf, hdr->sub_chunk2_sz);  
     tot_bytes += hdr->sub_chunk2_sz;  
     for (j = 0; j< (bps - hdr->sub_chunk2_sz)/8; ++j) {  
       write(wfd, empty_sound, 8);  
       tot_bytes += 8;  
     }  
   }  
   close(wfd);  
   memcpy(&new_hdr, hdr, 44);  
   new_hdr.sub_chunk2_sz=tot_bytes;  
   wfd = open("h.wav", O_WRONLY | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);  
   write(wfd, &new_hdr, 44);  
   close(wfd);  
   system("/bin/cat h.wav t.wav > a.wav");  
   return 0;  
 }  

Finally, I generated 30 sec of each speed (40, 44, 48, .... 208), and converted them into mp3. For example, 160 bpm wav (160.wav) is converted to 160.mp3 in 128 bit encoding.

 $ lame -h -b 128  160.wav  160.mp3

Now, if I need 5 min of 160 bpm, I just feed this 10 times in mpg123.

My favorite application of this was "speed trainer." For example, made 30 secs of 160, 161, 162, 163, 164 bpm and played it.

$ mpg123 16[0-4].mp3

Or making a 15 minute mp3 beat file isn't bad. Roughly 1 meg for 1 min, so 15 min is less than 15 meg byte. If it is encoded 64bit, the size will be even smaller.

Drupal menu disappeared.

I am not an expert of Drupal. Actually, I am new to Drupal. Somehow, someway, our team selected Drupal for our interactive method to collaborate with entire company. Make sense because we don't want to spend whole lot of time just for method. We want the result.

While I was enabling "Views" module in drupal, it acted up. Views did not show up. So, I disabled Views and tried to re-install. But, right after disabling Views, menu is screwed up. Like this.





I couldn't administer menu, modules, and theme any more! That is a disaster for admin user. I was so tempted to re-install drupal, but then, migrating old database to new one is another challenge. Old one was in dev, but we already collected some data. And, old site were configured too.
So, only option is "FIX". But, fixing a software that I never deal with was a quite discouraging moment. I prepared fresh install of drupal, and diff'd the files. Files looked similar. Then, all modification must be in the database.
So, I wrote a database diff tool.

Successfully, I found it is because menu_router table is corrupted. I restored.
Here is the sample code that I used:

#!/usr/bin/env python                                                                                                                

import MySQLdb
import os
import sys

def main():
    try:
        cn1 = MySQLdb.connect(host="172.16.136.114", db="drupal_prod")
        cn2 = MySQLdb.connect(host="172.16.136.114", db="drupal_dev")
    except:
        print >>sys.stderr, "ERROR: connection"
        sys.exit(1)

    while 1:
        table = raw_input("Table name: ")
        sql = "select count(*) from %s" % table

        cur1 = cn1.cursor()
        cur1.execute(sql)
        cur2 = cn2.cursor()
        cur2.execute(sql)

        r1 = cur1.fetchone()
        r2 = cur2.fetchone()
        if r1[0] == r2[0] == 0:
            print "SAME!"
            continue

        if r1[0] == r2[0]:
            print "Same COUNT! "
        else:
            print "DIFF Found! "

        inp = raw_input("specific sql? ")
        if inp.strip() == '':
            sql = "select * from %s" % table
        else:
            sql = inp
        print "SQL used:      %s; " % sql
        cur1.execute(sql)
        cur2.execute(sql)

        try:
            while 1:
                r1 = cur1.fetchone()
                r2 = cur2.fetchone()

                if r1 is None and r2 is None:
                    break

                if r1.__str__() != r2.__str__():
                    print "* ", r1, "\n", "# ", r2
        except:
            pass

        print "Repeat- SQL Used:\n%s;" % sql


if __name__ == '__main__':
    main()