Knowns and Unknowns

Ubuntu Alarm Clock

noreply@blogger.com (ChiMaster) — Mon, 07 Jul 2014 23:54:00 +0000

I really like the old Ubuntu alarmclock instead of the new alarm-clock-applet. The reason is that alarmclock offers a way to save and load the alarm list which no other apps I know of can do. Today after rebooting, I couldn't see my alarms any more. After a few hours of try-and-error, I found the fix. It turned out that my alarmclock's config for some reason refused to open the app. So I moved ~/.config/alarmclock/alarms.conf to another folder, reinstalled alarmclock and reloaded my alarm list. Everything went to normal now, Hooray!

Adding another file type for ctags parsing

noreply@blogger.com (ChiMaster) — Tue, 01 Jul 2014 18:10:00 +0000

Normal ctags commands to support C++ parsing:

$ ctags -R --c++-kinds=+cdefglmnpstuvx --fields=+iaS --extra=+q

This will generate the ctags database from the following file types under the current directory:

*.c++ *.cc *.cp *.cpp *.cxx *.h *.h++ *.hh *.hp *.hpp *.hxx *.C *.H

(From ctags --list-maps)

If another file type needs to be included for the parsing, for example you want to add *.inl file type to C++ language map, add the following line to ~/.ctags.

--langmap=c++:+.inl

To check:

$ ctags --list-maps | grep C++
C++ *.c++ *.cc *.cp *.cpp *.cxx *.h *.h++ *.hh *.hp *.hpp *.hxx *.C *.H *.inl

Run ctags again to regenerate the database with the support of *.inl files as well.

$ ctags -R --c++-kinds=+cdefglmnpstuvx --fields=+iaS --extra=+q

Using ipset

noreply@blogger.com (ChiMaster) — Wed, 30 Apr 2014 00:19:00 +0000

Finally got it to work. Nobody seems to have a complete and accurate solution for my case... So here it is.

 #include <iostream>  
 #include <thread>     // std::thread  
 #include <mutex>     // std::mutex  
 #include <assert.h>  
 extern "C" {  

 // Debian libipset libary is a C library. All the headers  
 // have to be enclosed in extern "C" brackets to have  
 // proper linkage  
 #include <libipset/session.h>      /* ipset_session_* */  
 #include <libipset/data.h>       /* enum ipset_data */  
 #include <libipset/parse.h>       /* ipset_parse_* */  
 #include <libipset/types.h>       /* struct ipset_type */  
 #include <libipset/ui.h>        /* core options, commands */  
 #include <libipset/utils.h>       /* STREQ */  
 }  
 // debian-ipset is not thread-safe. We're using  
 // a mutex to serialize the ipset calls.  
 std::mutex s_ipsetMutex;  
 // We're only adding a command/an element to the set,  
 // so the restore line no. remains 0  
 #define IPSET_SESSION_LINE_NO 0  
 int  
 ipsetAdd(std::string table, std::string set_type, uint32_t interval)  
 {  
  int32_t ret = 0;  
  const struct ipset_type *type = NULL;  
  enum ipset_cmd cmd = IPSET_CMD_ADD;  
  struct ipset_session *session;  
  // debian-ipset calls are not thread-safe. We're adding  
  // a mutex to serialize the calls.  
  s_ipsetMutex.lock();  
  ipset_load_types();  
  // Initialize an ipset session by allocating a session structure  
  // and filling out with the initialization data.  
  session = ipset_session_init(printf);  
  if (session == NULL)  
  {  
   printf("ipsetAdd: Cannot initialize ipset session for "  
     "set_type %s. aborting.\n", set_type.c_str());  
   ret = 1;  
  }  
  else  
  {  
   // Set session lineno to report parser errors correctly   
   ipset_session_lineno(session, IPSET_SESSION_LINE_NO);  
   // Parse string as a setname.  
   // The value is stored in the data blob of the session.  
   ret = ipset_parse_setname(session, IPSET_SETNAME, table.c_str());  
   if (ret == 0)  
   {  
    type = ipset_type_get(session, cmd);  
    if (!type)  
    {  
     printf("ipsetAdd: Failed to get the set type from Kernel "  
       "set_type=%s table=%s sess=%p cmd=%d\n", set_type.c_str(), table.c_str(),  
       session, cmd);  
     ret = 1;  
    }  
    else  
    {  
     // Parse string as a (multipart) element according to the settype.  
     // The value is stored in the data blob of the session.  
     ret = ipset_parse_elem(session, (ipset_opt)type->last_elem_optional,  
                 set_type.c_str());  
     if (ret == 0)  
     {  
      // Put a given kind of data into the data blob and mark the  
      // option kind as already set in the blob.  
      ret = ipset_data_set(ipset_session_data(session), IPSET_OPT_TIMEOUT, &interval);  
      if (!ret)  
      {  
       // Execute a command  
       ret = ipset_cmd(session, cmd, IPSET_SESSION_LINE_NO);  
       if (ret)  
       {  
        printf("ipsetAdd: WARNING: Failed to execute "  
          "IPSET_CMD_ADD command. ipset exists? ret=%d set_type=%s table=%s\n",  
          ret, set_type.c_str(), table.c_str());  
        // Not an error condition  
        ret = 0;  
       }  
      }  
      else  
      {  
       printf("ipsetAdd: Failed to set timeout option. "  
         "ret=%d set_type=%s table=%s\n", ret, set_type.c_str(), table.c_str());  
      }  
     }  
     else  
     {  
      printf("ipsetAdd: Failed to parse element. "  
        "ret=%d set_type=%s table=%s\n", ret, set_type.c_str(), table.c_str());  
     }  
    }  
   }  
   else  
   {  
    printf("ipsetAdd: Failed to parse setname. "  
      "ret=%d set_type=%s table=%s\n", ret, set_type.c_str(), table.c_str());  
   }  
   // Finish the ipset session  
   if (ipset_session_fini(session) != 0)  
   {  
    printf("ipsetAdd: Failed to destroy ipset "  
      "session. ret=%d set_type=%s table=%s\n", ret, set_type.c_str(),  
      table.c_str());  
   }  
  } // else of if (session == NULL)  
  s_ipsetMutex.unlock();  
  return ret;  
 }  
 int main()  
 {  
  ipsetAdd("my_ipset_table", "127.0.0.1,62142,127.0.0.1", 600);  
  return 0;  
 }  


To build it:
$ g++ myipset.cpp -std=c++0x  -lipset -o myipset

Create your ipset first:
$ sudo ipset create my_ipset_table hash:ip,port,ip family inet maxelem 600000

Due to the fact that some of the ipset commands need special
capability to call or get valid return (e.g. ipset_type_get & ipset_cmd), you have to run it as root.
$ sudo myipset

To check it:
$ sudo ipset -l

Here is the C version of the same function:

 #include <stdio.h>  
 #include <pthread.h>       
 #include <assert.h>  
 #include <libipset/session.h>      /* ipset_session_* */  
 #include <libipset/data.h>       /* enum ipset_data */  
 #include <libipset/parse.h>       /* ipset_parse_* */  
 #include <libipset/types.h>       /* struct ipset_type */  
 #include <libipset/ui.h>        /* core options, commands */  
 #include <libipset/utils.h>       /* STREQ */  
 // debian-ipset is not thread-safe. We're using  
 // a mutex to serialize the ipset calls.  
 pthread_mutex_t s_ipsetMutex;  
 // We're only adding a command/an element to to the set,  
 // so the restore line no. remains 0  
 #define IPSET_SESSION_LINE_NO 0  
 int  
 ipsetAdd(char *table, char *set_type, uint32_t interval)  
 {  
  int32_t ret = 0;  
  const struct ipset_type *type = NULL;  
  enum ipset_cmd cmd = IPSET_CMD_ADD;  
  struct ipset_session *session;  
  // debian-ipset calls are not thread-safe. We're adding  
  // a mutex to serialize the calls.  
  pthread_mutex_lock(&s_ipsetMutex);  
  ipset_load_types();  
  // Initialize an ipset session by allocating a session structure  
  // and filling out with the initialization data.  
  session = ipset_session_init(printf);  
  if (session == NULL)  
  {  
   printf("ipsetAdd: Cannot initialize ipset session for "  
     "set_type %s. aborting.\n", set_type);  
   ret = 1;  
  }  
  else  
  {  
   // Set session lineno to report parser errors correctly   
   ipset_session_lineno(session, IPSET_SESSION_LINE_NO);  
   // Parse string as a setname.  
   // The value is stored in the data blob of the session.  
   ret = ipset_parse_setname(session, IPSET_SETNAME, table);  
   if (ret == 0)  
   {  
    type = ipset_type_get(session, cmd);  
    if (!type)  
    {  
     printf("ipsetAdd: Failed to get the set type from Kernel "  
       "set_type=%s table=%s sess=%p cmd=%d\n", set_type, table,  
       session, cmd);  
     ret = 1;  
    }  
    else  
    {  
     // Parse string as a (multipart) element according to the settype.  
     // The value is stored in the data blob of the session.  
     ret = ipset_parse_elem(session, (enum ipset_opt)type->last_elem_optional,  
                 set_type);  
     if (ret == 0)  
     {  
      // Put a given kind of data into the data blob and mark the  
      // option kind as already set in the blob.  
      ret = ipset_data_set(ipset_session_data(session), IPSET_OPT_TIMEOUT, &interval);  
      if (!ret)  
      {  
       // Execute a command  
       ret = ipset_cmd(session, cmd, IPSET_SESSION_LINE_NO);  
       if (ret)  
       {  
        printf("ipsetAdd: WARNING: Failed to execute "  
          "IPSET_CMD_ADD command. ipset exists? ret=%d set_type=%s table=%s\n",  
          ret, set_type, table);  
        // Not an error condition  
        ret = 0;  
       }  
      }  
      else  
      {  
       printf("ipsetAdd: Failed to set timeout option. "  
         "ret=%d set_type=%s table=%s\n", ret, set_type, table);  
      }  
     }  
     else  
     {  
      printf("ipsetAdd: Failed to parse element. "  
        "ret=%d set_type=%s table=%s\n", ret, set_type, table);  
     }  
    }  
   }  
   else  
   {  
    printf("ipsetAdd: Failed to parse setname. "  
      "ret=%d set_type=%s table=%s\n", ret, set_type, table);  
   }  
   // Finish the ipset session  
   if (ipset_session_fini(session) != 0)  
   {  
    printf("ipsetAdd: Failed to destroy ipset "  
      "session. ret=%d set_type=%s table=%s\n", ret, set_type,  
      table);  
   }  
  } // else of if (session == NULL)  
  pthread_mutex_unlock(&s_ipsetMutex);  
  return ret;  
 }

Update Firefox on Ubuntu

noreply@blogger.com (ChiMaster) — Tue, 15 Apr 2014 23:07:00 +0000

For some strange reason, I couldn't open and see content of any of my yahoo mail using Firefox. I tried it on Chrome. It was working. So it must be something to do with Firefox + yahoo combination. Since I cannot fix yahoo from its setting (it doesn't even open), I in turn focused on fixing Firefox. Anyway I checked my add-ons and plug-ins and found nothing suspicious. So I decided to update my Firefox. I found the version from Help->About Firefox. The version was 20 and there was NO update button/link despite of all the articles on the net saying so. Next I ran


sudo apt-get update
sudo apt-get --purge --reinstall install firefox

Hoping the system will find the updates in the repositories and update Firefox for me. Nope. Firefox was not updated. So I had to do it manually. Here are the steps:

1. Get a Linux 64-bit copy from here and untar/uncompress it.


~/Downloads$ tar xvfj  firefox-28.0.tar.bz2
tar: Record size = 8 blocks
firefox/
firefox/libsoftokn3.so
firefox/chrome.manifest
firefox/mozilla-xremote-client
firefox/crashreporter.ini
firefox/libnspr4.so
firefox/updater
.
.
.

2. Backup your $HOME/.mozilla directory if you want to be careful.


$ cd; cp .mozilla .mozilla.bak

3. Close all Firefox instances.

4. Backup your firefox directory


$ sudo mv /usr/lib/firefox /usr/lib/firefox.bak

5. Move firefox directory you just uncompressed to /usr/lib


$ sudo mv ~/Downloads/firefox /usr/lib

6. Now give it a try by launching it from the launcher or command line.


$ /usr/bin/firefox &

7. One more step, the firefox.png file seems to be missing from the latest Firefox 28 package. You will see a big red cross if this is not done. So to properly show firefox icon in your launcher.


$ sudo cp /usr/lib/firefox.backup/icons/mozicon128.png \ 
/usr/lib/firefox/icons

8. Try yahoo mail again. It works!

9. Now you can delete all the backups if everything works as expected.

In a fairly good mode, so toss in a bonus tip - to open a file with the default application in command line:


xdg-open /usr/lib/firefox/mozicon128.png

Frozen MacOS terminal due ssh session timeout

noreply@blogger.com (ChiMaster) — Sat, 15 Jun 2013 14:06:00 +0000

To get out of a frozen terminal due to ssh timeout. Type the following keys:

enter (return key) ~.

Add the following to your .ssh/config file. It sends a signal to the server every 240 seconds to keep the session.

Host *
ServerAliveInterval 240

Reference: http://www.metachunk.com/blog/dealing-osx-terminal-ssh-timeouts-0

vim 7.x and matchit plugin

noreply@blogger.com (ChiMaster) — Mon, 30 Jul 2012 21:35:00 +0000

For a few months I have been trying to make my vim (7.2.330) in Ubuntu 10.04 work with matchit plugin. But it never wanted to cooperate. The matchit plugin works perfectly with my vim 6.4.6 by simply downloading/unzipping the match.zip from here and adding the following line to ~/.vimrc file.

:source {path_to_matchit_plugin}/matchit.vim

But for vim 7.x, the following line has be to added to ~/.vimrc as well:

:filetype plugin on

Mapping Your Domain Name to Work with Blogger

noreply@blogger.com (ChiMaster) — Fri, 24 Feb 2012 20:27:00 +0000

From GoDaddy support center: http://help.godaddy.com/article/5112#parking

You can establish a more professional identity for your Blogger® blog by configuring it to point to one of the domain names you registered through us. Instead of entering your Blogger URL to view your latest blog post, visitors enter your domain name's URL. For example, by mapping your coolexample.blogspot.com blog to your www.coolexample.com domain name, visitors focus solely on your domain name.
To point your Blogger blog to your domain name, you set up domain name mapping, which configures your blog settings and domain name. You update your settings in your Blogger account and our Domain Manager:

Park the domain name you want to use with your Blogger account on our parked nameservers.
Edit the www CNAME record for the domain name you want to use with your Blogger account. This update tells the Web browser to open your Blogger blog when visitors enter your domain name's URL in the browser address bar.
Forward your domain name to use www. This step ensures your Blogger blog displays for visitors who go to your domain name with or without the www prefix. For example, it displays for visitors who entered both www.coolexample.com and coolexample.com.
Configure your Blogger account to use your domain name.

To Park Your Domain Name

Log in to your Account Manager.
Next to Domains, click Launch.
Select the domain name you want to use with your Blogger account, and then from the Nameservers, select Set Nameservers.
Select I want to park my domains.
Click OK.
Click OK again.

To Edit Your CNAME Record

Log in to your Account Manager.
Next to Domains, click Launch.
From the Tools menu, select DNS Manager. The DNS Dashboard displays.
For the domain name you want to use with your Blogger account, click Edit Zone. The Zone File Editor displays.
In the CNAME (Alias) section, click the www record.
In the Points To field, type ghs.google.com.
Click Save Zone File, and then click OK.

To Forward Your Domain Name

Go to support.google.com.
Click Host my blog on a URL that I already own.
Follow the listed instructions.

To Configure Your Blogger Account

Log in to your Blogger account.
From the Settings tab, select Publishing.
Click Custom Domain.
In the Buy a domain for your blog section, click Switch to advanced settings.
In the Your Domain field, enter your domain name. For example, enter www.coolexample.com.
To specify another location in which to look for files, in the Use a missing files host? section, select Yes and enter the path. If not, select No.
In the Word Verification field, enter the characters as they display in the image above the field.
Click Save Settings.

Any DNS changes you make can take up to 48 hours to reflect on the Internet.

NOTE: As a courtesy, we provide information about how to use certain third-party products, but we do not endorse or directly support third-party products and we are not responsible for the functions or reliability of such products. Blogger® is a registered trademark of Google, Inc. All rights reserved.

Find a process and kill it in a script in Linux

noreply@blogger.com (ChiMaster) — Tue, 17 Jan 2012 19:24:00 +0000

ps -ef | grep process_name | awk '{ print $2; }'| xargs kill -9

Computer Science Terms

noreply@blogger.com (ChiMaster) — Wed, 20 Apr 2011 04:22:00 +0000

Algorithms: Are well-defined procedures for solving problems.

Data Structure: Is a particular way of storing and organizing data in a computer so that it can be used efficiently.

Dangling Pointers: Pointers that point to invalid addresses. Some examples of programming errors that can lead to dangling pointers include casting arbitrary integers to pointers, adjusting pointers beyond the bounds of arrays, and deallocating storage that one or more pointers still reference.

Hash Table or Hash Map

noreply@blogger.com (ChiMaster) — Thu, 10 Mar 2011 20:30:00 +0000

In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number). Thus, a hash table implements an associative array. The hash function is used to transform the key into the index (the hash) of an array element (the slot or bucket) where the corresponding value is to be sought.

Ideally, the hash function should map each possible key to a unique slot index, but this ideal is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are never added to the table after creation). Most hash table designs assume that hash collisions—the situation where different keys happen to have the same hash value—are normal occurrences and must be accommodated in some way.

In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at constant average (indeed, amortized[1]) cost per operation.[2][3]

In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.

Credit for above paragraphs: http://en.wikipedia.org/wiki/Hash_table

Building thrift 0.5.0 on CentOS 5.3

noreply@blogger.com (ChiMaster) — Mon, 22 Nov 2010 19:52:00 +0000

You will need php 5.2 or above to successfully build thrift 0.5.0 or you will see the following error:

'zend_std_get_constructor' was not declared in this scope.

Download php 5.2.14 source from here and go through the usual "configure->make->sudo make install" cycle.

Display Chinese in Firefox on CentOS

noreply@blogger.com (ChiMaster) — Fri, 19 Nov 2010 18:27:00 +0000

1. sudo yum groupinstall chinese-support
2. Restart firefox

Installing CentOS 4.4 using USB

noreply@blogger.com (ChiMaster) — Thu, 04 Nov 2010 19:28:00 +0000

Ok, I know this is an old version. But if for some reasons, your environment still calls for this kind of system.

1. Download the following from http://vault.centos.org/4.4/isos/i386
CentOS-4.4-i386-bin1of4.iso
CentOS-4.4-i386-bin2of4.iso
CentOS-4.4-i386-bin3of4.iso
CentOS-4.4-i386-bin4of4.iso

Windows

2. Use MagicDisc to mount the the ISOes to different drives. Open the the drives and copy all the files to a directory. Overwrite the files that have the same names.
Linux
2. Mount the iso
# mkdir /mnt/iso
# mount -o loop disk1.iso /mnt/iso
Copy all the files to a directory, e.g. centos44
# cp -r /mnt/iso/* centos44
Do the above for all the iso files.

3. Windows: Use MagicISO to write the files to an ISO; Linux:
# mkisofs -o centos44-i386.iso ./centos44

4. Use UNetbootin (http://unetbootin.sourceforge.net) to write the ISO to your USB drive

5. Boot from USB in your system that is to be installed. Select HTTP installation.
Site: vault.centos.org
Direcotry: 4.4/os/i386

The reason why we have to do this instead of using the CentOS-4.4.ServerCD-i386.iso file is that the
Server ISO does not match with the installation directory structure. The installation will not start.

Find out gcc version in a script

noreply@blogger.com (ChiMaster) — Fri, 29 Oct 2010 21:33:00 +0000

user@local$ gcc -v 2>&1 | tail -1 | awk '{print $3}'
4.4.3

Only want the major version number:

gcc -v 2>&1 | tail -1 | awk '{print $3}'|cut -d. -f1
4

log4j and Scribe

noreply@blogger.com (ChiMaster) — Thu, 16 Sep 2010 18:58:00 +0000

Well I thought it should be fairly easy. But it turned out it's not that straightforward especially for a Java newbie like me. Basically we need to make a log4j appender for Scribe. Fortunately it's available from http://github.com/lenn0x/Scribe-log4j-Appender. The package contains scribelog4j.jar already. Just in case you want to build it yourself or change the referencing libraries, here are the instructions. The following were tested on CentOS 5.3 64-bit.

1. Download and extract log4j from http://logging.apache.org/log4j/1.2/download.html

2. Download and extract Scribe 2.2 and Thrift from http://github.com/facebook/scribe/downloads and http://incubator.apache.org/thrift/download (the current version is 0.5.0, I am using 0.2.0 in this example.)

Build Thrift and install. Please refer to Step 14 in Installing & Running Scribe with HDFS support on CentOS article.

3. Download and extract slf4j (Simple Logging Facade for Java) from http://www.slf4j.org/download.html

4. Install latest ant if you haven't. See the previous post: Installing Latest Ant on CentOS. Thrift jar cannot be built using ant 1.6.5 from original CentOS repository.

5. Build libthrift.jar. From top Thrift directory:

[user@localhost:~/pkgs/thrift-0.2.0] cd lib/java
[user@localhost:~/pkgs/thrift-0.2.0/lib/java] ant

You should see libthrift.jar in the current directory.

6. Build libfb303.jar. From top Thrift directory:

[user@localhost:~/pkgs/thrift-0.2.0] cd contrib/fb303/java

Edit build.xml file.

Find "<classpath>" and change the value of "pathelement location" to where your libthrift.jar is.

My thrift is in $HOME/pkgs/thrift-0.2.0 directory. So I add a new property name on the top.

<property name="pkgs.dir" value="${user.home}/pkgs"/>

Also slf4j's api jar has to be added to classpath as well.

The pathelement location lines should look like the following:

<pathelement location="${pkgs.dir}/thrift-0.2.0/lib/java/libthrift.jar"/>

<pathelement location="${pkgs.dir}/slf4j-1.6.1/slf4j-api-1.6.1.jar"/>

Remove FacebookBase.java file. This has to be done or you will get "getStatus() in com.facebook.fb303.FacebookBase cannot implement getStatus() in com.facebook.fb303.FacebookService.Iface; attempting to use incompatible return type" error.

[user@localhost:~/pkgs/thrift-0.2.0/contrib/fb303/java] rm FacebookBase.java

Run ant.
[user@localhost:~/pkgs/thrift-0.2.0/contrib/fb303/java] ant

You should find libfb303.jar in build/lib directory

[user@localhost:~/pkgs/thrift-0.2.0/contrib/fb303/java] ll build/lib/

total 176

drwxr-xr-x 2 user user   4096 Sep 16 12:09 .

drwxr-xr-x 4 user user   4096 Sep 16 11:45 ..

-rw-r--r-- 1 user user 165162 Sep 16 12:09 libfb303.jar

7. Build scribe.jar. From top level scribe directory:

[user@localhost::~/pkgs/scribe] cd if

Edit scribe.thrift
Add the following line in the file.
namespace java scribe

Copy fb303 thrift directory here.
[user@localhost:~/pkgs/scribe/if] cp -r ~/pkgs/thrift-0.2.0/contrib/fb303/ .

And copy fb303's build.xml here as well
[user@localhost:~/pkgs/scribe/if] cp ~/pkgs/thrift-0.2.0/contrib/fb303/java/build.xml .

Edit build.xml to build scribe.jar. The file will look like the following. magenta text indicates the modifications for building scribe.jar.

<!--

Licensed to the Apache Software Foundation (ASF) under one

or more contributor license agreements. See the NOTICE file

distributed with this work for additional information

regarding copyright ownership. The ASF licenses this file

to you under the Apache License, Version 2.0 (the

"License"); you may not use this file except in compliance

with the License. You may obtain a copy of the License at



http://www.apache.org/licenses/LICENSE-2.0



Unless required by applicable law or agreed to in writing,

software distributed under the License is distributed on an

"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY

KIND, either express or implied. See the License for the

specific language governing permissions and limitations

under the License.

-->

<project name="scribe" default="dist" basedir="..">

<!-- project wide settings. All directories relative to basedir -->

<property name="src.dir" value="if"/>

<property name="if.dir" value="if"/>

<property name="thrift_home" value="/usr/local"/>

<property name="pkgs.dir" value="${user.home}/pkgs"/>

<!-- temp build directories -->

<property name="build.dir" value="${src.dir}/build"/>

<property name="build.classes.dir" value="${build.dir}/classes"/>

<property name="build.lib.dir" value="${build.dir}/lib"/>



<!-- final distribution directories -->

<property name="dist.dir" value="/usr/local"/>

<property name="dist.lib.dir" value="${dist.dir}/lib"/>



<!-- make temporary and distribution directories -->

<target name="prepare">

<mkdir dir="${build.dir}"/>

<mkdir dir="${build.classes.dir}"/>

<mkdir dir="${build.lib.dir}"/>

<mkdir dir="${dist.dir}"/>

<mkdir dir="${dist.lib.dir}"/>

</target>



<!-- generate scribe thrift code -->

<target name="scribebuild">

<echo>generating thrift scribe files</echo>

<exec executable="${thrift_home}/bin/thrift"  failonerror="true">

<arg line="--gen java -o ${src.dir} ${src.dir}/../if/scribe.thrift" />

</exec>

<move todir="${src.dir}">

<fileset dir="${src.dir}/gen-java/scribe">

<include name="**/*.java"/>

</fileset>

</move>

</target>



<!-- compile the base and thrift generated code and jar them -->

<target name="dist" depends="prepare,scribebuild">

<echo>Building scribe.jar .... </echo>

<javac srcdir="${src.dir}" destdir="${build.classes.dir}" debug="on">

<classpath>

<pathelement location="${pkgs.dir}/thrift-0.4.0/lib/java/libthrift.jar"/>

<pathelement location="${pkgs.dir}/slf4j-1.6.1/slf4j-api-1.6.1.jar"/>

<pathelement location="${pkgs.dir}/thrift-0.4.0/contrib/fb303/java/build/lib/libfb303.jar"/>



</classpath>

<include name="*.java"/>

<include name="${build.dir}/scribe"/>

</javac>

<jar jarfile="${build.lib.dir}/scribe.jar" basedir="${build.classes.dir}">

</jar>

</target>



<!-- copy the build jar to the distribution library directory -->

<target name="install" depends="dist">

<copy todir="${dist.lib.dir}">

<fileset dir="${build.lib.dir}" includes="scribe.jar"/>

</copy>

</target>



<target name="clean">

<echo>Cleaning old stuff .... </echo>

<delete dir="${build.dir}/classes/com"/>

<delete dir="${build.dir}/lib"/>

<delete dir="${build.dir}"/>

</target>

</project>

Run ant.
[user@localhost:~/pkgs/scribe/if] ant

You will see scribe.jar in build/lib directory.

[user@localhost:~/pkgs/scribe/if] ll build/lib/

total 36

drwxr-xr-x 2 user user  4096 Sep 16 12:55 .

drwxr-xr-x 4 user user  4096 Sep 16 12:55 ..

-rw-r--r-- 1 user user 27002 Sep 16 12:58 scribe.jar

8. Build scribelog4j.jar

First Get Scribe-log4j-Appender using git.

If git is not installed.
yum -y install git

Get the code.
git clone http://github.com/lenn0x/Scribe-log4j-Appender.git

The code will be in Scribe-log4j-Appender directory. Change to the directory.

[user@localhost:~/pkgs/Scribe-log4j-Appender] cd src/java/org/apache/log4j

Copy scribe's build.xml here.
[user@localhost:~/pkgs/Scribe-log4j-Appender/src/java/org/apache/log4j] cp ~/pkgs/scribe/if/build.xml .

Edit build.xml and it should look like the following. Adjust the magenta part if needed.

<project name="scribelog4j" default="dist" basedir="..">



<!-- project wide settings. All directories relative to basedir -->

<property name="src.dir" value="log4j/scribe"/>

<property name="if.dir" value="if"/>

<property name="thrift_home" value="/usr/local"/>

<property name="pkgs.dir" value="${user.home}/pkgs"/>



<!-- temp build directories -->

<property name="build.dir" value="${src.dir}/build"/>

<property name="build.classes.dir" value="${build.dir}/classes"/>

<property name="build.lib.dir" value="${build.dir}/lib"/>



<!-- final distribution directories -->

<property name="dist.dir" value="/usr/local"/>

<property name="dist.lib.dir" value="${dist.dir}/lib"/>



<!-- make temporary and distribution directories -->

<target name="prepare">

<mkdir dir="${build.dir}"/>

<mkdir dir="${build.classes.dir}"/>

<mkdir dir="${build.lib.dir}"/>

<mkdir dir="${dist.dir}"/>

<mkdir dir="${dist.lib.dir}"/>

</target>



<!-- compile the base and thrift generated code and jar them -->

<target name="dist" depends="prepare">

<echo>Building scribelog4j.jar .... </echo>

<javac srcdir="${src.dir}" destdir="${build.classes.dir}" debug="on">

<classpath>

<pathelement location="${pkgs.dir}/thrift-0.2.0/lib/java/libthrift.jar"/>

<pathelement location="${pkgs.dir}/slf4j-1.6.1/slf4j-api-1.6.1.jar"/>

<pathelement location="${pkgs.dir}/thrift-0.2.0/contrib/fb303/java/build/lib/libfb303.jar"/>

<pathelement location="${pkgs.dir}/scribe/if/build/lib/scribe.jar"/>

</classpath>

<include name="*.java"/>

<include name="${build.dir}/scribe"/>

</javac>

<jar jarfile="${build.lib.dir}/scribelog4j.jar" basedir="${build.classes.dir}">

</jar>

</target>



<!-- copy the build jar to the distribution library directory -->

<target name="install" depends="dist">

<copy todir="${dist.lib.dir}">

<fileset dir="${build.lib.dir}" includes="scribelog4j.jar"/>

</copy>

</target>



<target name="clean">

<echo>Cleaning old stuff .... </echo>

<delete dir="${build.dir}/classes/com"/>

<delete dir="${build.dir}/lib"/>

<delete dir="${build.dir}"/>

  </target>

</project>

Run ant.
[user@localhost:~/pkgs/Scribe-log4j-Appender/src/java/org/apache/log4j] ant

You should get scribelog4j.jar in the current directory.

9. Write and run a test program

Here is the test program called scribelog4j_test.java

public class scribelog4j_test {

    private static Logger logger = Logger.getLogger(scribelog4j_test.class);

    public static void main(String[] args) {

        long time = System.currentTimeMillis();

        logger.info("main method called..");

        logger.info("another informative message");

        logger.warn("This one is a warning!");

        logger.log(Level.TRACE,

                "And a trace message using log() method.");

        long logTime = System.currentTimeMillis() - time;



        logger.debug("Time taken to log the previous messages: "

                + logTime + " msecs");



        // Exception logging example:

        try{

            String subs = "hello".substring(6);

        }catch (Exception e){

            logger.error("Error in main() method:", e);

        }

    }

}

Create a file called log4j.properties in the current directory. It should look like this:

log4j.rootLogger=debug, stdout, R, scribe



log4j.appender.stdout=org.apache.log4j.ConsoleAppender

log4j.appender.stdout.layout=org.apache.log4j.PatternLayout



# Pattern to output the caller's file name and line number.

log4j.appender.stdout.layout.ConversionPattern=%5p [%t] (%F:%L) - %m%n



log4j.appender.R=org.apache.log4j.RollingFileAppender

log4j.appender.R.File=example.log



log4j.appender.R.MaxFileSize=100KB

# Keep one backup file

log4j.appender.R.MaxBackupIndex=1



log4j.appender.R.layout=org.apache.log4j.PatternLayout

log4j.appender.R.layout.ConversionPattern=%p %t %c - %m%n



#

# Add this to your log4j.properties

#

log4j.appender.scribe=org.apache.log4j.scribe.ScribeAppender

log4j.appender.scribe.scribe_category=MyScribeCategoryName

log4j.appender.scribe.scribe_host=127.0.0.1

log4j.appender.scribe.layout=org.apache.log4j.PatternLayout

log4j.appender.scribe.layout.ConversionPattern=%5p [%t] %d{ISO8601} %F (line %L) %m%n

For convenience, copy all the necessary jars to a directory called lib.

[user@localhost:~/proj/scribe_log4j] ls lib

libfb303.jar   log4j-1.2.16.jar  scribelog4j.jar      slf4j-log4j12-1.6.1.jar

libthrift.jar  scribe.jar        slf4j-api-1.6.1.jar

To build it:
/usr/bin/javac -classpath .:lib/scribelog4j.jar:lib/log4j-1.2.16.jar ./scribelog4j_test.java

To run it:

Start the Scribe server in a new terminal.
[user@localhost:~/scribe/src] scribed ../examples/example1.conf

In the original terminal, run scribelog4j_test program.

[user@localhost:~/proj/scribe_log4j] /usr/bin/java -classpath .:lib/log4j-1.2.16.jar:lib/scribelog4j.jar::lib/libthrift.jar:lib/slf4j-api-1.6.1.jar:lib/slf4j-log4j12-1.6.1.jar:lib/scribe.jar:lib/libfb303.jar scribelog4j_test

You should find the log file in /tmp/scribetest directory.

Installing Latest Ant on CentOS

noreply@blogger.com (ChiMaster) — Wed, 15 Sep 2010 21:57:00 +0000

To install the latest version of ant (ant-1.7.1-7.jpp5.noarch) from JPackage instead of the version provided by yum (ant-1.6.5-2jpp.2.x86_64). Here are the steps on CentOS 5.3 64-bit system.

1. Download and install JPackage rpm (jpackage-release-5-4.jpp5.noarch.rpm) from JPackage site. This will add jpackage.repo to your /etc/yum.repos.d directory.

2. Use yum to search "ant.", you will see ant.noarch provided by JPackage repo in the list. But right now if you try to install it, the following error would occur.

Error: Missing Dependency: /usr/bin/rebuild-security-providers is needed 
by package java-1.4.2-gcj-compat

Check which package is providing rebuild-security-providers.

rpm -q --whatprovides /usr/bin/rebuild-security-providers
jpackage-utils-1.7.3-1jpp.2.el5

jpackage-utils has been installed in the system.

Looks like this RedHat version of jpackage-utils doesn't work with this latest version of ant from JPackage.

Solution:
a. Uninstall jpackage-utils without uninstalling all the dependencies.
[user@localhost] sudo rpm -e --nodeps jpackage-utils-1.7.3-1jpp.2.el5

b. Install jpackage-utils (jpackage-utils-5.0.0-2.jpp5.noarch.rpm) from JPackage.
[user@localhost] sudo rpm -Uvh jpackage-utils-5.0.0-2.jpp5.noarch.rpm

c. Install ant.noarch
[user@localhost] sudo yum install ant.noarch

Installing & Running Scribe with HDFS support on CentOS

noreply@blogger.com (ChiMaster) — Tue, 31 Aug 2010 20:24:00 +0000

Have being working on Scribe for our logging for a while. Finally feel like writing something about it. The main trigger came from a request to support HDFS. Since I always like to tackle open source project's incompatibilities on different environments, I made this challenge the highest priority (although my boss probably doesn't think so...)

Installing Scribe on CentOS 5.3 64-bit

1. Java SE Development Kit (JDK) 6 latest update - http://www.oracle.com/technetwork/java/javase/downloads/index.html. I used update 20. The java directory is: /usr/java/jdk1.6.0_20.

2. ruby-1.8.5-5.el5_4.8 + ruby-devel-1.8.5-5.el5_4.8 (using yum)

3. python-2.4.3-24.el5 + python-devel-2.4.3-24.el5.x86_64 (using yum)

4. libevent + libevent-devel - libevent-1.4.13-1/libevent-devel-1.4.13-1 (using yum)

5. gcc-c++-4.1.2-46.el5_4.2

6. boost 1.40 - http://downloads.sourceforge.net/project/boost/boost/1.40.0/boost_1_40_0.tar.gz?use_mirror=softlayer

[user@localhost] ./bootstrap.sh

[user@localhost] ./bjam

[user@localhost]  sudo su -

[root@localhost] ./bjam install

7. flex-2.5.4a-41.fc6 (using yum)

8. m4-1.4.15 - ftp.gnu.org/gnu/m4 (do not use the version from yum)

9. imake-1.0.2-3.x86_64 (using yum)

10. autoconf-2.65 - ftp.gnu.org/gnu/autoconf (do not use the version from yum)

11. automake-1.11.1 - ftp.gnu.org/gnu/automake (do not use the version from yum)

12. libtool-2.2.6b - ftp.gnu.org/gnu/libtool (do not use the version from yum)

13. bison-2.3-2.1 (using yum). It actually needs yacc. The following is to make yacc script that actually calls bison.

[root@localhost] more /usr/bin/yacc



#!/bin/sh

exec bison -y "$@"



[root@localhost] chmod +x /usr/bin/yacc

14. Latest version: http://incubator.apache.org/thrift/download
thrift-0.2.0 - http://archive.apache.org/dist/incubator/thrift/0.2.0-incubating
thrift-0.4.0 - http://archive.apache.org/dist/incubator/thrift/0.4.0-incubating

I am using thrift-0.2.0 in this example.

[user@localhost] ./bootstrap.sh
[user@localhost] ./configure

If you see this:
error: ./configure: line 21183: syntax error near unexpected token `MONO,'

Copy pkg.m4 in /usr/share/aclocal to thrift's aclocal directory. From the top-level thrift directory, do the following:

cp /usr/share/aclocal/pkg.m4 aclocal

Then again:

[user@localhost] ./bootstrap.sh

[user@localhost] ./configure

[user@localhost] make

[user@localhost] sudo su -

[root@localhost] make install

[root@localhost] exit

You may see the following error when building thrift 0.4.0 and 0.5.0.

make[4]: Entering directory `/home/user/pkgs/thrift-0.4.0/lib/cpp'
/bin/sh ../../libtool --tag=CXX --mode=compile g++ -DHAVE_CONFIG_H -I. -I../.. -I/usr/local/include -I./src -Wall -g -O2 -MT ThreadManager.lo -MD -MP -MF .deps/ThreadManager.Tpo -c -o ThreadManager.lo `test -f 'src/concurrency/ThreadManager.cpp' || echo './'`src/concurrency/ThreadManager.cpp
libtool: compile: g++ -DHAVE_CONFIG_H -I. -I../.. -I/usr/local/include -I./src -Wall -g -O2 -MT ThreadManager.lo -MD -MP -MF .deps/ThreadManager.Tpo -c src/concurrency/ThreadManager.cpp -fPIC -DPIC -o .libs/ThreadManager.o In file included from src/concurrency/ThreadManager.cpp:20:
src/concurrency/ThreadManager.h:24:26: tr1/functional: No such file or directoryIn file included from src/concurrency/ThreadManager.cpp:20:

Please change line 24 of ThreadManager.h from

#include <tr1/functional>

#include <boost/tr1/tr1/functional>

We also need to compile and install the Facebook fb303 library. From the top-level thrift directory:

[user@localhost] cd contrib/fb303

[user@localhost] ./bootstrap.sh

[user@localhost] ./configure

[user@localhost] make

[user@localhost] sudo su -

[root@localhost] make install

[root@localhost] exit

15. hadoop 0.21.0 - http://www.apache.org/dyn/closer.cgi/hadoop/core/

[user@localhost] cd hadoop-0.21.0/hdfs/src/c++/libhdfs

[user@localhost] ./configure JVM_ARCH=tune=k8 --with-java=/usr/java/jdk1.6.0_20

[user@localhost] make

[user@localhost] sudo su -

[root@localhost] cp .libs/libhdfs.so .libs/libhdfs.so.0 /usr/local/include 

[root@localhost] cp hdfs.h /usr/local/include 

[root@localhost] exit

16. scribe-2.2 - http://github.com/downloads/facebook/scribe/scribe-2.2.tar.gz - have to use scribe-2.1 or above to support HDFS.

[user@localhost] ./bootstrap.sh --enable-hdfs

[user@localhost] ./configure

[user@localhost] make

17. Configure and Run Hadoop (single-node cluster in this tutorial).

a. First we need to modify a few configuration files. From top-level hadoop directory, edit conf/hadoop-env.sh, conf/core-site.xml, conf/hdfs-site.xml and conf/macoded-site.xml files.

[user@localhost] more conf/hadoop-env.sh



export HADOOP_OPTS=-Djava.net.codeferIPv4Stack=true



# Set Hadoop-specific environment variables here.



# The only required environment variable is JAVA_HOME.  All others are

# optional.  When running a distributed configuration it is best to

# set JAVA_HOME in this file, so that it is correctly defined on

# remote nodes.



# The java implementation to use.  Required.

export JAVA_HOME=/usr/java/jdk1.6.0_20

.

.

.



[user@localhost] more conf/core-site.xml



<?xml version="1.0"?>

<?xml-stylesheet type="text/xsl" href="configuration.xsl"?>



<!-- Put site-specific property overrides in this file. -->



<configuration>

<property>

  <name>hadoop.tmp.dir</name>

  <value>/tmp/hadoop</value>

  <description>A base for other temporary directories.</description>

</property>



<property>

  <name>fs.default.name</name>

  <value>hdfs://localhost:9000</value>

  <description>The name of the default file system.  A URI whose

  scheme and authority determine the FileSystem implementation.  The

  uri's scheme determines the config property (fs.SCHEME.impl) naming

  the FileSystem implementation class.  The uri's authority is used to

  determine the host, port, etc. for a filesystem.</description>

</property>

</configuration>



[user@localhost] more conf/hdfs-site.xml



<?xml version="1.0"?>

<?xml-stylesheet type="text/xsl" href="configuration.xsl"?>



<!-- Put site-specific property overrides in this file. -->



<configuration>

<property>

  <name>dfs.replication</name>

  <value>1</value>

  <description>Default block replication.

  The actual number of replications can be specified when the file is created.

  The default is used if replication is not specified in create time.

  </description>

</property>

</configuration>



[user@localhost] more conf/macoded-site.xml



<?xml version="1.0"?>

<?xml-stylesheet type="text/xsl" href="configuration.xsl"?>



<!-- Put site-specific property overrides in this file. -->



<configuration>

<property>

  <name>macoded.job.tracker</name>

  <value>localhost:9001</value>

  <description>The host and port that the Macodeduce job tracker runs

  at.  If "local", then jobs are run in-process as a single map

  and reduce task.

  </description>

</property>

</configuration>

b. Format the namenode. From top-level hadoop directory

[user@localhost] bin/hadoop namenode -format

c. Start hadoop

[user@localhost] start-all.sh

d. Use jps to check if all the processes are started.

[user@localhost] jps

25362 JobTracker

24939 NameNode

25099 DataNode

25506 TaskTracker

25251 SecondaryNameNode

25553 Jps

e. Use netstat to check if port 9000 (set in core-site.xml) is listening.

[user@localhost] sudo netstat -nap | grep 9000

sudo netstat -nap | grep 9000

tcp        0      0 127.0.0.1:9000              0.0.0.0:*                   LISTEN      24939/java         

tcp        0      0 127.0.0.1:9000              127.0.0.1:59957             ESTABLISHED 24939/java         

tcp        0      0 127.0.0.1:9000              127.0.0.1:59960             ESTABLISHED 24939/java         

tcp        0      0 127.0.0.1:59957             127.0.0.1:9000              ESTABLISHED 25099/java         

tcp        0      0 127.0.0.1:59960             127.0.0.1:9000              ESTABLISHED 25251/java

f. Open a browser and type server_ip:50070 to check if it shows 1 Live Nodes in the Cluster Summary. Be patient, sometimes it takes some time (30 seconds to 1 minute) to show. Remember to put the cursor to the address bar and codess enter to refresh the page. For some reason, F5 (Reload) doesn't work for me.

18. Configure and Run Scribe
a. Set up the java class paths for Scribe. I have installed my hadoop 0.21.0 in ~/pkgs/hadoop-0.21.0 directory

[user@localhost] export CLASSPATH=~/pkgs/hadoop-0.21.0/hadoop-hdfs-0.21.0.jar:~/pkgs/hadoop-0.21.0/lib/commons-logging-1.1.1.jar:~/pkgs/hadoop-0.21.0/hadoop-common-0.21.0.jar

b. Edit a Scribe configuration file to use HDFS. Change to scribe src directory

[user@localhost] more scribe_hdfs.conf

port=1463

max_msg_per_second=2000000

check_interval=3



# DEFAULT

<store>

category=default

type=buffer



target_write_size=20480

max_write_interval=1

buffer_send_rate=2

retry_interval=30

retry_interval_range=10



<primary>

type=file

fs_type=hdfs

file_path=hdfs://localhost:9000/scribetest

create_symlink=no

use_hostname_sub_directory=yes

base_filename=thisisoverwritten

max_size=40000000

rotate_period=daily

rotate_hour=0

rotate_minute=5

add_newlines=1

</primary>

<secondary>

type=file

fs_type=std

file_path=/tmp/scribetest

base_filename=thisisoverwritten

max_size=3000000

</secondary>

</store>

c. Run Scribe

[user@localhost] scribed scribe_hdfs.conf

[Thu Sep  9 15:35:22 2010] "setrlimit error (setting max fd size)"

[Thu Sep  9 15:35:22 2010] "STATUS: STARTING"

[Thu Sep  9 15:35:22 2010] "STATUS: configuring"

[Thu Sep  9 15:35:22 2010] "got configuration data from file <scribe_hdfs.conf>"

[Thu Sep  9 15:35:22 2010] "CATEGORY : default"

[Thu Sep  9 15:35:22 2010] "Creating default store"

[Thu Sep  9 15:35:22 2010] "configured <1> stores"

[Thu Sep  9 15:35:22 2010] "STATUS: "

[Thu Sep  9 15:35:22 2010] "STATUS: ALIVE"

[Thu Sep  9 15:35:22 2010] "Starting scribe server on port 1463"

Thrift: Thu Sep  9 15:35:22 2010 libevent 1.4.13-stable method epoll

If it cannot run and complains the following:
libboost_system.so.1.40.0: cannot open shared object

Do the following:

[user@localhost] echo '/usr/local/lib/' >> /etc/ld.so.conf.d/my_boost.conf

/sbin/ldconfig -v

If you see the following output when running scribe:

[user@localhost] scribed scribe_hdfs.conf

[Thu Sep  9 15:39:38 2010] "setrlimit error (setting max fd size)"

[Thu Sep  9 15:39:38 2010] "STATUS: STARTING"

[Thu Sep  9 15:39:38 2010] "STATUS: configuring"

[Thu Sep  9 15:39:38 2010] "got configuration data from file <scribe_hdfs.conf>"

[Thu Sep  9 15:39:38 2010] "CATEGORY : default"

[Thu Sep  9 15:39:38 2010] "Creating default store"

[Thu Sep  9 15:39:38 2010] "configured <1> stores"

[Thu Sep  9 15:39:38 2010] "STATUS: "

[Thu Sep  9 15:39:38 2010] "STATUS: ALIVE"

[Thu Sep  9 15:39:38 2010] "Starting scribe server on port 1463"

[Thu Sep  9 15:39:38 2010] "Exception in main: TNonblockingServer::serve() bind"

[Thu Sep  9 15:39:38 2010] "scribe server exiting"

It may be due to Port 1463 not being available. Run "netstat -nap | grep 1463" to find out which program is using it.

19. Send something to Scribe to log in HDFS
From a different terminal, in top-level Scribe directory:

[user@localhost] echo "hello world" | examples/scribe_cat test

In the terminal that runs Scribe server, you should see the following output:

[Thu Sep  9 15:46:14 2010] "[test] Creating new category from model default"

[Thu Sep  9 15:46:14 2010] "store thread starting"

[Thu Sep  9 15:46:14 2010] "[hdfs] Connecting to HDFS"

[Thu Sep  9 15:46:14 2010] "[hdfs] Before hdfsConnectNewInstance(localhost, 9000)"

Sep 9, 2010 3:46:14 PM org.apache.hadoop.security.Groups 

INFO: Group mapping impl=org.apache.hadoop.security.ShellBasedUnixGroupsMapping; cacheTimeout=300000

[Thu Sep  9 15:46:15 2010] "[hdfs] After hdfsConnectNewInstance"

[Thu Sep  9 15:46:15 2010] "[hdfs] Connecting to HDFS"

[Thu Sep  9 15:46:15 2010] "[hdfs] Before hdfsConnectNewInstance(localhost, 9000)"

[Thu Sep  9 15:46:15 2010] "[hdfs] After hdfsConnectNewInstance"

[Thu Sep  9 15:46:15 2010] "[hdfs] opened for write hdfs://localhost:9000/scribetest/test/localhost.localdomain/test-2010-09-09_00000"

[Thu Sep  9 15:46:15 2010] "[test] Opened file  for writing"

[Thu Sep  9 15:46:15 2010] "[test] Opened file  for writing"

[Thu Sep  9 15:46:15 2010] "[test] Changing state from  to "

Opening Primary

[Thu Sep  9 15:46:15 2010] "[test] successfully read <0> entries from file "

[Thu Sep  9 15:46:15 2010] "[test] No more buffer files to send, switching to streaming mode"

[Thu Sep  9 15:46:15 2010] "[test] Changing state from  to "

20. Check if the message has been logged to HDFS:
Stop Scribe first (either stop Scribe or make the file rotate, otherwise Hadoop won't write it to the filesystem.)

[user@localhost] hadoop fs -lsr /

10/09/09 16:26:02 INFO security.Groups: Group mapping impl=org.apache.hadoop.security.ShellBasedUnixGroupsMapping; cacheTimeout=300000

10/09/09 16:26:03 WARN conf.Configuration: macoded.task.id is decodecated. Instead, use macodeduce.task.attempt.id

drwxr-xr-x   - user supergroup          0 2010-09-09 16:21 /jobtracker

drwxr-xr-x   - user supergroup          0 2010-09-09 16:21 /jobtracker/jobsInfo

drwxr-xr-x   - user supergroup          0 2010-09-09 16:23 /scribetest

drwxr-xr-x   - user supergroup          0 2010-09-09 16:23 /scribetest/test

drwxr-xr-x   - user supergroup          0 2010-09-09 16:23 /scribetest/test/localhost.localdomain

-rw-r--r--   3 user supergroup         13 2010-09-09 16:25 /scribetest/test/localhost.localdomain/test-2010-09-09_00000

drwxr-xr-x   - user supergroup          0 2010-09-09 16:21 /tmp

drwxr-xr-x   - user supergroup          0 2010-09-09 16:21 /tmp/hadoop

drwxr-xr-x   - user supergroup          0 2010-09-09 16:21 /tmp/hadoop/macoded

drwx------   - user supergroup          0 2010-09-09 16:21 /tmp/hadoop/macoded/system

-rw-------   1 user supergroup          4 2010-09-09 16:21 /tmp/hadoop/macoded/system/jobtracker.info

Get the directory out to take a look:

[user@localhost] hadoop fs -get /scribetest test

10/09/09 16:26:47 INFO security.Groups: Group mapping impl=org.apache.hadoop.security.ShellBasedUnixGroupsMapping; cacheTimeout=300000

10/09/09 16:26:47 WARN conf.Configuration: macoded.task.id is decodecated. Instead, use macodeduce.task.attempt.id



[user@localhost] more test/test/localhost.localdomain/test-2010-09-09_00000

hello world

One note about the Secondary store in Scribe configuration file: Scribe opens the files for both Primary and Secondary stores even in the normal situation as long as replay_buffer is true (default). Then it will try to delete the secondary store file when Primary store is handling the messages. This is causing problem because HDFS has not completed its access to the secondary store file. The following exception will happen:

[Thu Sep  9 16:02:03 2010] "[hdfs] deleteFile hdfs://localhost:9000/scribetest1/test/localhost.localdomain/test_00000"

[Thu Sep  9 16:02:03 2010] "[hdfs] Connecting to HDFS"

[Thu Sep  9 16:02:03 2010] "[hdfs] Before hdfsConnectNewInstance(localhost, 9000)"

[Thu Sep  9 16:02:03 2010] "[hdfs] After hdfsConnectNewInstance"

[Thu Sep  9 16:02:03 2010] "[test] No more buffer files to send, switching to streaming mode"

Exception in thread "main" java.io.IOException: Could not complete write to file /scribetest1/test/localhost.localdomain/test_00000 by DFSClient_1545136365

        at org.apache.hadoop.hdfs.server.namenode.NameNode.complete(NameNode.java:720)

        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)

        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)

        at java.lang.reflect.Method.invoke(Method.java:597)

        at org.apache.hadoop.ipc.WritableRpcEngine$Server.call(WritableRpcEngine.java:342)

        at org.apache.hadoop.ipc.Server$Handler$1.run(Server.java:1350)

        at org.apache.hadoop.ipc.Server$Handler$1.run(Server.java:1346)

        at java.security.AccessController.doPrivileged(Native Method)

        at javax.security.auth.Subject.doAs(Subject.java:396)

        at org.apache.hadoop.security.UserGroupInformation.doAs(UserGroupInformation.java:742)

        at org.apache.hadoop.ipc.Server$Handler.run(Server.java:1344)



        at org.apache.hadoop.ipc.Client.call(Client.java:905)

        at org.apache.hadoop.ipc.WritableRpcEngine$Invoker.invoke(WritableRpcEngine.java:198)

        at $Proxy0.complete(Unknown Source)

        at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

        at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)

        at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)

        at java.lang.reflect.Method.invoke(Method.java:597)

        at org.apache.hadoop.io.retry.RetryInvocationHandler.invokeMethod(RetryInvocationHandler.java:82)

        at org.apache.hadoop.io.retry.RetryInvocationHandler.invoke(RetryInvocationHandler.java:59)

        at $Proxy0.complete(Unknown Source)

        at org.apache.hadoop.hdfs.DFSOutputStream.completeFile(DFSOutputStream.java:1406)

        at org.apache.hadoop.hdfs.DFSOutputStream.close(DFSOutputStream.java:1393)

        at org.apache.hadoop.fs.FSDataOutputStream$PositionCache.close(FSDataOutputStream.java:66)

        at org.apache.hadoop.fs.FSDataOutputStream.close(FSDataOutputStream.java:91)

Call to org/apache/hadoop/fs/FSDataOutputStream::close failed!

[Thu Sep  9 16:02:03 2010] "[hdfs] closed hdfs://localhost:9000/scribetest1/test/localhost.localdomain/test_00000"

There is more information about this error in "NameNode Logs" link on http://server_ip:50070/dfshealth.jsp page.

To avoid this problem we should either set replay_buffer to false or make the seconardy store local instead of HDFS (the above configuration file example, scribe_hdfs.conf).

The following configuration is to set replay_buffer to false and both primary and secondary stores to use HDFS.

[user@localhost] more hdfs_both.conf

port=1463

max_msg_per_second=2000000

check_interval=3



# DEFAULT

<store>

category=default

type=buffer

replay_buffer=no

target_write_size=20480

max_write_interval=1

buffer_send_rate=2

retry_interval=30

retry_interval_range=10



<primary>

type=file

fs_type=hdfs

file_path=hdfs://localhost:9000/scribetest

create_symlink=no

use_hostname_sub_directory=yes

base_filename=thisisoverwritten

max_size=40000000

rotate_period=daily

rotate_hour=0

rotate_minute=5

add_newlines=1



</primary>

<secondary>

type=file

fs_type=hdfs

file_path=hdfs://localhost:9000/scribetest1

create_symlink=no

use_hostname_sub_directory=yes

base_filename=thisisoverwritten

max_size=40000000

rotate_period=daily

rotate_hour=0

rotate_minute=5

add_newlines=1

</secondary>



</store>

References:
1. Thomas Dudziak's blog: How to install Scribe with HDFS support on Ubuntu Karmic
2. Agile Testing: Compiling, installing and test-running Scribe
3. Google Scribe server group: Failover when writing to HDFS problems

Key Computer Architecture Techniques - Pipelining

noreply@blogger.com (ChiMaster) — Tue, 17 Aug 2010 21:35:00 +0000

Pipelining
It is an implementation technique where multiple instructions are overlapped in execution. The computer pipeline is divided in stages. Each stage completes a part of an instruction in parallel. The stages are connected one to the next to form a pipe - instructions enter at one end, progress through the stages, and exit at the other end.

Because the pipe stages are hooked together, all the stages must be ready to proceed at the same time. We call the time required to move an instruction one step further in the pipeline a machine cycle . The length of the machine cycle is determined by the time required for the slowest pipe stage.

For example, the classic RISC pipeline is broken into five stages with a set of flip flops between each stage.

1. Instruction fetch
2. Instruction decode and register fetch
3. Execute
4. Memory access
5. Register write back

Pipelining does not help in all cases. There are several possible disadvantages. An instruction pipeline is said to be fully pipelined if it can accept a new instruction every clock cycle. A pipeline that is not fully pipelined has wait cycles that delay the progress of the pipeline.

Advantages of Pipelining:

1. The cycle time of the processor is reduced, thus increasing instruction issue-rate in most cases.

2. Some combinational circuits such as adders or multipliers can be made faster by adding more circuitry. If pipelining is used instead, it can save circuitry vs. a more complex combinational circuit.

Disadvantages of Pipelining:

1. A non-pipelined processor executes only a single instruction at a time. This prevents branch delays (in effect, every branch is delayed) and problems with serial instructions being executed concurrently. Consequently the design is simpler and cheaper to manufacture.

2. The instruction latency in a non-pipelined processor is slightly lower than in a pipelined equivalent. This is due to the fact that extra flip flops (pipeline registers/buffers) must be added to the data path of a pipelined processor.

3. A non-pipelined processor will have a stable instruction bandwidth. The performance of a pipelined processor is much harder to predict and may vary more widely between different programs.

Computer Performance

noreply@blogger.com (ChiMaster) — Fri, 13 Aug 2010 18:02:00 +0000

From Stanford EE282 + Computer Architecture: A Quantitative Approach, 4th Edition

Latency or execution time or response time

Wall-clock time to complete a task

Bandwidth or throughput or execute rate

Number of tasks completed per unit of time

Latency matric: program execution time

CPUTime = Seconds/Program
                = Cycles/Program * Seconds/Cycle
                = Instructions/Program * Cycles/Instruction * Seconds/Cycle
                = IC * CPI * CCT

IC: Instruction Count
CPI: Clock Cycles Per Instruction
CCT: Clock Cycle Time

Amdahl’s Law

Speedup = Execution time for entire task without using the enhancement/Execution time for entire task using the enhancement when possible

It should be greater than 1 (when there is an improvement, that is)

new_execution_time
= (original_execution_time * (1 - enhanced_fraction)) + original_execution_time * enhanced_fraction * (1 / speedup_enhanced)
= (original_execution_time)((1-enhanced_fraction) + enhanced_fraction/speedup_enhanced)

speedup_overall
= original_execution_time / new_execution_time
= 1/((1-enhanced_fraction) + enhanced_fraction/speedup_enhanced)

In the case of parallelization, Amdahl's law states that if enhanced_fraction is the proportion of a program that can be made parallel (i.e. benefit from parallelization), and (1 − enhanced_fraction) is the proportion that cannot be parallelized (remains serial), then the maximum speedup that can be achieved by using N processors (N times faster for the part that can be enhanced = speedup_enhanced) is

speedup_overall

= 1/((1-enhanced_fraction) + enhanced_fraction/speedup_enhanced)

In the limit, as N tends to infinity, the maximum speedup tends to 1 / (1 − enhanced_fraction).

System Diagram of A Modern Laptop

noreply@blogger.com (ChiMaster) — Fri, 06 Aug 2010 22:11:00 +0000

From Wikipedia Intel X58

Intel X58: Intel X58 Chipset
QPI: The Intel QuickPath Interconnect is a point-to-point processor interconnect developed by Intel to compete with HyperTransport
I/O Controller Hub (ICH), also known as Intel 82801, is an Intel southbridge on motherboards with Intel chipsets (Intel Hub Architecture). As with any other southbridge, the ICH is used to connect and control peripheral devices.
EHCI: The Enhanced Host Controller Interface (EHCI) specification describes the register-level interface for a Host Controller for the Universal Serial Bus (USB) Revision 2.0.
DMI: Direct Media Interface (DMI) is point-to-point interconnection between an Intel northbridge and an Intel southbridge on a computer motherboard. It is the successor of the Hub Interface used in previous chipsets. It provides for a 10Gb/s bidirectional data rate.
LPC: The Low Pin Count bus, or LPC bus, is used on IBM-compatible personal computers to connect low-bandwidth devices to the CPU, such as the boot ROM and the "legacy" I/O devices (behind a super I/O chip).
SPI: The Serial Peripheral Interface Bus or SPI (pronounced "ess-pee-i" or "spy") bus is a synchronous serial data link standard named by Motorola that operates in full duplex mode. Devices communicate in master/slave mode where the master device initiates the data frame.
Intel Matrix Storage Technology: It provides new levels of protection, performance, and expandability for desktop and mobile platforms. Whether using one or multiple hard drives, users can take advantage of enhanced performance and lower power consumption. When using more than one drive, the user can have additional protection against data loss in the event of a hard drive failure.
Intel Turbo Memory with User Pinning: An on-motherboard flash card, Intel's Turbo Memory is designed to act as another layer in the memory hierarchy, caching data where possible and improving performance/battery life in notebooks. User pinning offers more options to the user to improve system applications launch time and responsiveness.

Heap Memory

noreply@blogger.com (ChiMaster) — Fri, 06 Aug 2010 07:12:00 +0000

From Stanford CS Ed Library: Pointers and Memory

"Heap" memory, also known as "dynamic" memory, is an alternative to local stack memory. Local memory is quite automatic — it is allocated automatically on function call and it is deallocated automatically when a function exits. Heap memory is different in every way. The programmer explicitly requests the allocation of a memory "block" of a particular size, and the block continues to be allocated until the programmer
explicitly requests that it be deallocated. Nothing happens automatically. So the programmer has much greater control of memory, but with greater responsibility since the memory must now be actively managed.

The advantages of heap memory are...

Lifetime. Because the programmer now controls exactly when memory is allocated and deallocated, it is possible to build a data structure in memory, and return that data structure to the caller. This was never possible with local memory which was automatically deallocated when the function exited.
Size. The size of allocated memory can be controlled with more detail. For example, a string buffer can be allocated at run-time which is exactly the right size to hold a particular string. With local memory, the code is more likely to declare a buffer size 1000 and hope for the best.

The disadvantages of heap memory are...

More Work. Heap allocation needs to arranged explicitly in the code which is just more work.
More Bugs. Because it's now done explicitly in the code, realistically on occasion the allocation will be done incorrectly leading to memory bugs. Local memory is constrained, but at least it's never wrong.

Nonetheless, there are many problems that can only be solved with heap memory, so that's that way it has to be. In languages with garbage collectors such as Perl, LISP, or Java, the above disadvantages are mostly eliminated. The garbage collector takes over most of the responsibility for heap management at the cost of a little extra time taken at run-time.

Classic swap function in C and C++

noreply@blogger.com (ChiMaster) — Thu, 05 Aug 2010 23:47:00 +0000

In C:


void Swap(int* a, int* b) 
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void SwapCaller() 
{
    int x = 1;
    int y = 2;
    // Use & to pass pointers to the int values of interest
    Swap(&x, &y); 
}

In C++:


// The & declares pass by reference
void Swap(int& a, int& b) 
{
    int temp;
    // No *'s required -- the compiler takes care of it    
    temp = a;
    a = b;
    b = temp;
}

void SwapCaller() 
{
    int x = 1;
    int y = 2;
    // No &'s required -- the compiler takes care of it
    Swap(x, y); 
}

How Does Call Stack Work?

noreply@blogger.com (ChiMaster) — Thu, 05 Aug 2010 21:53:00 +0000

From Stanford CS Ed Library: Pointers and Memory

The exact details of the implementation are language and compiler specific. However, the basic structure below is approximates the method used by many different systems and languages...

To call a function such as foo(6, x+1)...

1. Evaluate the actual parameter expressions, such as the x+1, in the caller's context.

2. Allocate memory for foo()'s locals by pushing a suitable "local block" of memory onto a runtime "call stack" dedicated to this purpose. For parameters but not local variables, store the values from step (1) into the appropriate slot in foo()'s local block.

3. Store the caller's current address of execution (its "return address") and switch execution to foo().

4. foo() executes with its local block conveniently available at the end of the call stack.

5. When foo() is finished, it exits by popping its locals off the stack and "returns" to the caller using the previously stored return address. Now the caller's locals are on the end of the stack and it can resume executing.

Algorithms - Sorting

noreply@blogger.com (ChiMaster) — Mon, 12 Jul 2010 23:35:00 +0000

From Wikipedia Sorting Algorithm.

Bubble sort

Bubble sort is a straightforward and simplistic method of sorting data that is used in computer science education. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, then it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass. This algorithm is highly inefficient, and is rarely used^, except as a simplistic example.
Bubble sort average case and worst case are both O(n²).


ResultCode BubbleSort(int a[], int nSize)
{
    ResultCode res = SORT_FAILED;
    int i, j = 0;
    bool bSwap = true;
    int tmp;
    if (a)
    {
        while (bSwap)
        {
            bSwap = false;
            j++;
            for (i = 0; i < (nSize - j); i++)
            {
                if (a[i] > a[i + 1])
                {
                    tmp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = tmp;
                    bSwap = true;
                }
            }
        }
        res = SORT_OK;
    }
    return res;
}

Selection sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.


ResultCode SelectionSort(int numbers[], int array_size)
{
    int i, j;
    int min, temp;
    ResultCode res = SORT_FAILED;
    if (numbers)
    {
        // for each number, find the min from the list of i to the end
        // and then swap the min with i;
        for (i = 0; i < array_size-1; i++)
        {
            // set min to i
            min = i;
            // check each one from i + 1 to the end of the array
            // to find the minimum number from the list of numbers
            // from i+1 to the end
            for (j = i+1; j < array_size; j++)
            {
                // if any number is less than the min, set min to the new index
                if (numbers[j] < numbers[min])
                {
                    min = j;
                }
            }
            // swap the minimum with i
            temp = numbers[i];
            numbers[i] = numbers[min];
            numbers[min] = temp;
        }
         res = SORT_OK;
    }
    return res;
}

Insertion sort

Main article: Insertion sort

Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists, and often is used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one. Shell sort (see below) is a variant of insertion sort that is more efficient for larger lists.



ResultCode InsertionSort(int arr[], int length)

{

    int i, j, tmp;

    ResultCode res = SORT_FAILED;

    if (arr)

    {

        for (i = 1; i < length; i++)

        {

            j = i;

            while (j > 0 && arr[j - 1] > arr[j])

            {

                tmp = arr[j];

                arr[j] = arr[j - 1];

                arr[j - 1] = tmp;

                j--;

            }



        }

        res = SORT_OK;

    }

    return res;

}

Shell sort

Main article: Shell sort

Shell sort was invented by Donald Shell in 1959. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time. One implementation can be described as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort.


ResultCode ShellSort(int num[], int length)
{
    int i, temp, flag = 1;
    int d = length;
    ResultCode res = SORT_FAILED;
    if (num)
    {
        while(flag || (d > 1))
        {
            flag = 0;                     
            d = (d + 1) / 2; // use (d + 1)/2 as the gap
            // starting from positon 0 to length - d - 1, comparing num[i] 
            //and num[i+d]
            for (i = 0; i < (length - d); i++)  
            {
                if (num[i + d] > num[i])
                {
                    // swap positions i+d and i
                    temp = num[i + d];         
                    num[i + d] = num[i];
                    num[i] = temp;
                    // tells swap has occurred
                    flag = 1;                                   }
            }
        }
        res = SORT_OK;
    }
    return res;
}

Binary tree sort


typedef struct tree_el {
   int val;
   struct tree_el * right, * left;
} node;

void BinaryTreeSort(node **tree, node *item)
{
   if(!(*tree)) {
      *tree = item;
      return;
   }
   if(item->val <= (*tree)->val)
      BinaryTreeSort(&(*tree)->left, item);
   else if(item->val>(*tree)->val)
      BinaryTreeSort(&(*tree)->right, item);
}

void printout(node * tree) {
   if(tree->left) printout(tree->left);
   printf("%d\n",tree->val);
   if(tree->right) printout(tree->right);
}

Merge sort

Main article: Merge sort

Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n). Merge sort has seen a relatively recent surge in popularity for practical implementations, being used for the standard sort routine in the programming languages Perl^[5], Python (as timsort^[6]), and Java (also uses timsort as of JDK7^[7]), among others. Merge sort has been used in Java at least since 2000 in JDK1.3.^[8]^[9]


void Merge(int a[], int low, int high, int mid)
{
    int i, j, k, c[high - low];
    i = low;
    j = mid + 1;
    k = 0;

    while((i <= mid) && (j <= high))
    {
        if (a[i] < a[j])
        {
            c[k] = a[i];
            k++;
            i++;
        }
        else
        {
            c[k] = a[j];
            k++;
            j++;
        }
    }
    while (i <= mid)
    {
        c[k] = a[i];
        k++;
        i++;
    }
    while(j <= high)
    {
        c[k] = a[j];
        k++;
        j++;
    }
    for(i = low; i < (high + 1); i++)
    {
        a[i] = c[i - low];
    }
}


ResultCode MergeSort(int a[], int low, int high)
{
    ResultCode res = SORT_FAILED;
    int mid;

    if (a)
    {
        if (low < high)
        {
            mid = (low + high) / 2;
            MergeSort (a, low, mid);
            MergeSort(a, mid + 1, high);
            Merge(a, low, high, mid);
        }
        res = SORT_OK;
    }
    return res;
}

Heapsort

Main article: Heapsort

Heapsort is a much more efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap, a special type of binary tree. Once the data list has been made into a heap, the root node is guaranteed to be the largest(or smallest) element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root. Using the heap, finding the next largest element takes O(log n) time, instead of O(n) for a linear scan as in simple selection sort. This allows Heapsort to run in O(n log n) time, and this is also the worst case complexity.


// node index starts at 0
#define left(i) 2*i+1
#define right(i) 2*i+2

// In computer science, a heap is a specialized tree-based data structure
// that satisfies the heap property: if B is a child node of A, then
// key(A) = key(B). This implies that an element with the greatest key is
// always in the root node, and so such a heap is sometimes called a max-heap.
void max_heapify(int a[],int i,int size)
{
    int l,r,largest,temp;
    l=left(i);
    r=right(i);
    if(l<=size-1 && a[l]>a[i])
        largest = l;
    else largest = i;
    if(r<=size-1 && a[r]>a[largest])
        largest = r;
    if(largest != i)
    {
        temp = a[i];
        a[i]=a[largest];
        a[largest]=temp;
        // since we change the value of the "largest" (index) node,
        // we have to make sure there is still a max heap below that.
        max_heapify(a,largest,size);
    }
}
void build_max_heap(int a[],int size)
{
    int i;
    // starting from rightmost parent going upward.
    for(i=size/2 - 1 ;i>=0;i--)
        max_heapify(a,i,size);
}
ResultCode HeapSort(int a[],int size)
{
    int i,temp;
    ResultCode res = SORT_FAILED;
    if (a)
    {

        build_max_heap(a,size);
        for(i=size-1;i>0;i--)
        {
            // swap the root (largest value) and the end
            temp=a[i];
            a[i]=a[0];
            a[0]=temp;
            size=size - 1;
            max_heapify(a,0,size);
        }
        res = SORT_OK;
    }
    return res;
}

Quicksort

Main article: Quicksort

Quicksort is a divide and conquer algorithm which relies on a partition operation: to partition an array, we choose an element, called a pivot, move all smaller elements before the pivot, and move all greater elements after it. This can be done efficiently in linear time and in-place. We then recursively sort the lesser and greater sublists. Efficient implementations of quicksort (with in-place partitioning) are typically unstable sorts and somewhat complex, but are among the fastest sorting algorithms in practice. Together with its modest O(log n) space usage, this makes quicksort one of the most popular sorting algorithms, available in many standard libraries. The most complex issue in quicksort is choosing a good pivot element; consistently poor choices of pivots can result in drastically slower O(n²) performance, but if at each step we choose the median as the pivot then it works in O(n log n). Finding the median, however, is an O(n) operation on unsorted lists, and therefore exacts its own penalty.


ResultCode QuickSort(int arr[], int left, int right)
{

    int i = left, j = right;
    int tmp;
    ResultCode res = SORT_FAILED;
    if (arr)
    {
        int pivot = arr[(left + right) / 2];
        /* partition */
        while (i <= j)
        {
            while (arr[i] < pivot)
            {
                i++;
            }
            while (arr[j] > pivot)
            {
                j--;
            }
            if (i <= j)
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        };
        /* recursion */
        if (left < j)
        {
            QuickSort(arr, left, j);
        }
        if (i < right)
        {
            QuickSort(arr, i, right);
        }
        res = SORT_OK;
    }
    return res;
}

Counting Sort

Main article: Counting sort

Counting sort is applicable when each input is known to belong to a particular set, S, of possibilities. The algorithm runs in O(|S| + n) time and O(|S|) memory where n is the length of the input. It works by creating an integer array of size |S| and using the ith bin to count the occurrences of the ith member of S in the input. Each input is then counted by incrementing the value of its corresponding bin. Afterward, the counting array is looped through to arrange all of the inputs in order. This sorting algorithm cannot often be used because S needs to be reasonably small for it to be efficient, but the algorithm is extremely fast and demonstrates great asymptotic behavior as n increases. It also can be modified to provide stable behavior.


ResultCode CountingSort (int array[], int size)
{
    int i, min, max;
    ResultCode res = SORT_FAILED;
    if (array)
    {
        min = max = array[0];
        for(i = 1; i < size; i++)
        {
            if (array[i] < min)
                min = array[i];
            else if (array[i] > max)
                max = array[i];
        }
        // under the assumption of range being smaller than size, or it's 
        // not worth it.
        int range = max - min + 1;
        int *count = (int *)malloc(range * sizeof(int));

        for(i = 0; i < range; i++)
        {
            count[i] = 0;
        }
        // count index + 2 is the value,
        // counting freqency of that value.
        for(i = 0; i < size; i++)
        {
            count[ array[i] - min ]++;
        }
        int j, z = 0;
        for(i = min; i <= max; i++)
        {
            for(j = 0; j < count[ i - min ]; j++)
            {
                array[z++] = i;
            }
        }
        free(count);
        res = SORT_OK;
    }
    return res;
}

Bucket sort

Main article: Bucket sort

Bucket sort is a divide and conquer sorting algorithm that generalizes Counting sort by partitioning an array into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. Thus this is most effective on data whose values are limited (e.g. a sort of a million integers ranging from 1 to 1000). A variation of this method called the single buffered count sort is faster than quicksort and takes about the same time to run on any set of data.



// Here array is the array to be sorted and n is the number of buckets to 
// use. The function msbits(x,k) returns the k most significant bits of x 
// (msbits = floor(x/2^(size(x)-k)), floor function returns the largest 
// integral value not greater than x.)
// uucket sort assumes that the input is generated by a random process 
// that distributes elements uniformly over the interval [0, 1), in this 
// code, the range is [0, 999]
ResultCode BucketSort(int *a,int n)
{
    vector bucket[10];
    int i, j;
    int idx = 0;

    ResultCode res = SORT_FAILED;
    if (a)
    {
        for (i = 0; i < n; i++)
        {
            bucket[(a[i]/100)].push_back(a[i]);
        }
        for (i = 0; i < 10; i++)
        {
            // creating a new array.
            int arr[bucket[i].size()];

            // copy the vector data to array because our InsertionSort 
            // accepts array.
            for (j = 0; j < bucket[i].size(); j++)
            {
                arr[j] = bucket[i][j];
            }

            InsertionSort(arr, bucket[i].size());
            // put the sorted bucket to the original array.
            for (j = 0; j < bucket[i].size(); j++)
            {
                a[idx++] = arr[j];
            }
        }
        res = SORT_OK;
    }
    return res;
}

Radix sort

Main article: Radix sort

Radix sort is an algorithm that sorts a list of fixed-size numbers of length k in O(n · k) time by treating them as bit strings. We first sort the list by the least significant bit while preserving their relative order using a stable sort. Then we sort them by the next bit, and so on from right to left, and the list will end up sorted. Most often, the counting sort algorithm is used to accomplish the bitwise sorting, since the number of values a bit can have is minimal - only '1' or '0'.


ResultCode RadixSort(int *a,int n)
{
    int i;
    int b[n], m=0, exp=1;
    ResultCode res = SORT_FAILED;

    if (a)
    {
        // Find the maximum number
        for (i=0;i m)
            {
                m = a[i];
            }
        }

        // starting from the last digit
        while ((m/exp) > 0)
        {
            int bucket[10]={0};

            // put each number in the bucket according to the value in the 
            // inspected digit
            for(i = 0; i < n; i++)
            {
                bucket[(a[i]/exp) % 10]++;
            }

            // accumulate the values to the buckets
            for(i = 1;i < 10; i++)
            {
                bucket[i] += bucket[i-1];
            }

            // smart!
            // use the bucket value - 1 (because it's the sequence!) to 
            // for indices of the new array.
            for(i = n-1;i >= 0; i--)
            {
                b[--bucket[a[i]/exp%10]] = a[i];
            }
            for(i = 0;i < n;i++)
            {
                a[i] = b[i];
            }
            exp*=10;
        }
        res = SORT_OK;

    }

    return res;
}

Name	Average	Worst	Memory	Stable	Method	Notes
Bubble Sort	n²	n²	1	Yes	Exchanging	Tiny code
Selection Sort	n²	n²	1	Depends	Selection	Its stability depends on the implementation. Used to sort this table in Safari or other Webkit web browser
Insertion Sort	n²	n²	1	Yes	Insertion	Average case is also O(n + d), where d is the number of inversions
Shell Sort	-	nlog²n	1	No	Insertion
Binary Tree Sort	nlogn	nlogn	n	Yes	Insertion	When using a self-balancing binary search tree
Merge Sort	nlogn	nlogn	n	Yes	Merging	Used to sort this table in Firefox
Heapsort	nlogn	nlogn	1	No	Selection
Quicksort	nlogn	n²	logn	Depends	Partitioning	Can be implemented as a stable sort depending on how the pivot is handled. Naïve variants use O(n) space

The following table describes sorting algorithms that are not comparison sorts. As such, they are not limited by a O(nlogn) lower bound. Complexities below are in terms of n, the number of items to be sorted, k, the size of each key, and s, the chunk size used by the implementation. Many of them are based on the assumption that the key size is large enough that all entries have unique key values, and hence that n << 2^k, where << means "much less than."

Name	Average	Worst	Memory	Stable	n << 2^k	Notes
Bucket Sort	n * k	n²* k	n * k	Yes	No	Assumes uniform distribution of elements from the domain in the array.
Counting Sort	n + k	n + k	n + 2^k	Yes	Yes	If k = O(n) then RT = O(n)
LSD Radix Sort	n * k/s	n * k/s	n	Yes	No

Installing and building your C++ programs in Cygwin on Windows Vista

noreply@blogger.com (ChiMaster) — Sat, 10 Jul 2010 06:53:00 +0000

Installation:

Run or download setup.exe from this link: http://www.cygwin.com/setup.exe.
Select "Install from Internet" & "Direct Connection" if that's your Internet setting.
Keep the recommended Root Directory and "Install for" if you don't feel like changing them.
Select your Internet connection
On Select Packages window, Open "Devel" to select gdb & open "Editor" to select vim if you want vi (I know, I'm old-fashioned...)

On Windows Vista, browse to "C:\ProgramData\Microsoft\Windows\Start Menu\Programs\Cygwin" directory, press right mouse button on Cygwin Bash Shell file, selection Properties->Advanced. Check "Run as administrator"

Run Cygwin Bash Shell from Programs list.

Building your first C++ program
$ g++ yourprog.cpp

If you see the following error:
“This application has requested the Runtime to terminate it in an unusual way”

Add the following:
export TEMP=/tmp to your ~/.bashrc file

Close and restart your Cygwin Bash Shell.