Binary-tree test

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <time.h>

/* 
 Helper function that allocates a new node with the given data and NULL left and right pointers. 
*/ 


typedef struct node {
 int data;
 struct node *left;
 struct node *right;
} NodeT;


NodeT* NewNode(int data);
void BTreeLog(const char *fmt, ...);

typedef int (*BTreeCompFunc)(NodeT* node, void *data);

NodeT* BTreeNewNode(int data) 
{ 
 NodeT* node = (NodeT*)malloc(sizeof(NodeT));    // "new" is like "malloc" 
 node->data = data; 
 node->left = NULL; 
 node->right = NULL;
 BTreeLog("BTreeNewNode: new node=0x%X, data=%d\n", node, data);
    return(node); 
} 
     

void BTreeLog(const char *fmt, ...)
{
#ifdef __ENABLE_LOG__  
 char buf[256];
 va_list ap;
 int n;
 
 va_start(ap, fmt);
 n = vsnprintf(buf, sizeof(buf), fmt, ap);
 printf("%s", buf);
 va_end(ap);
#endif 
}


int BTreeCompare(NodeT* node, void *data)
{
 if (*((int*)data) < node->data)
  return -1;
 if (*((int*)data) > node->data)
  return 1;
 return 0;
}  
/* 
  Give a binary search tree and a number, BTreeInserts a new node 
  with the given number in the correct place in the tree. 
  Returns the new root pointer which the caller should 
  then use (the standard trick to avoid using reference 
  parameters). 
*/ 

NodeT* BTreeInsert(NodeT* node, int data, BTreeCompFunc comp)
{ 
 // 1. If the tree is empty, return a new, single node 
 if (NULL == node) 
 { 
  BTreeLog("New Entry: %d\n", data);
  return BTreeNewNode(data); 
    } 
 else { 
  // 2. Otherwise, recur down the tree 
     if (comp(node, &data) == -1) {
   /*BTreeLog("BTreeInsert: left; data=%d, node=0x%X, left=0x%X, right=0x%X\n", 
       data, node, node->left, node->right);
   */    
   node->left = BTreeInsert(node->left, data, comp); 
  } 
  else {
   /* 
   BTreeLog("BTreeInsert: right; data=%d, node=0x%X, left=0x%X, right=0x%X\n", 
       data, node, node->left, node->right);
   */    
   node->right = BTreeInsert(node->right, data, comp);
  } 
 }
 return(node); // return the (unchanged) node pointer 
}


void BTreeDeleteAll(NodeT* pNode)
{
 if (pNode)
 {
  if (pNode->left)
  {
   BTreeDeleteAll(pNode->left);
  } 
  if (pNode->right)
  {
   BTreeDeleteAll(pNode->right);
  } 
  BTreeLog("BTreeDeleteAll: pNode=0x%X, data=%d\n", pNode, pNode->data);
  free(pNode);
  //pNode->left = NULL;
  //pNode->right = NULL;
 }
}

NodeT *BTreeSearch(NodeT* pNode, int data, BTreeCompFunc comp)
{
 int cmp; 
 if (pNode) {
  cmp = comp(pNode, &data); 
  if (cmp == 0)
   return pNode;
  else 
  if (cmp == -1)
  {
   /* data < pnode->data */
   pNode = BTreeSearch(pNode->left, data, comp); 
  }
  else {
   pNode = BTreeSearch(pNode->right, data, comp);
  } 
 }
 //BTreeLog("Comp...\n");
 return pNode;
}


int main(int argc, char *argv[])
{
 NodeT* root = NULL;
 NodeT* node;
 unsigned int n,i;
 int data1, data2;
 unsigned int count;

 srand(time(NULL));
 BTreeLog("BTree demo\n");
 n = rand() % 100;
 root = BTreeInsert(root, n, BTreeCompare);
 data2 = 4750;
 n = 10000000;
 for (i=0, count=0; i<n; i++)
 {
  data1 = rand()%n;
  /* insert unique entry */
  if (BTreeSearch(root, data1, BTreeCompare) == NULL) {
   BTreeInsert(root, data1, BTreeCompare);
   count++;
  } 
 }
 BTreeInsert(root, data2, BTreeCompare);
 printf("Just inserted %d entries into Binary-tree\n", count+1);
 node = BTreeSearch(root, data2, BTreeCompare);
 printf("\n\n\n\n");
 if (node) {
  printf("!!!!!!!!!!!!!!!!!!!!!!!!Found node=0x%X for data=%d\n", node, data2);
 }
 printf("\n\n\n\n");
 BTreeDeleteAll(root);
}

Linux Init

LINUX INIT
--------------
This is the mother of all other userspace's processes.

Where to find it?
In the util-linux package (to be found at ftp.*.kernel.org) for simpleinit or in the sysvinit package for SysV init.

Probably also in [sunsite|metalab].unc.edu or ftp.debian.org


Title: sysvinit and utilities
Version: 2.78
Entered-Date: 11FEB2000
Description: This is the Linux System V init.
                The source package has the debian build files included.
                This version can be compiled with glibc 2.0.6 and up.
Author: miquels@cistron.nl (Miquel van Smoorenburg)
Primary-Site: sunsite.unc.edu /pub/Linux/system/daemons/init
                109K sysvinit-2.78.tar.gz
Alternate-Site: ftp.cistron.nl /pub/people/miquels/software
                109K sysvinit-2.78.tar.gz
Alternate-Site: ftp.debian.org /debian/dists/potato/main/source/base
                108K sysvinit_2.78-X.tar.gz
Copying-Policy: GPL
Keywords: init shutdown halt reboot
End


ftp.debian.org:/debian/dists/potato/main/source/base/sysvinit_2.78-2.tar.gz

https://build.opensuse.org/package/files?package=sysvinit&project=YaST%3AWeb

Some properties:

#define VT_MASTER "/dev/tty0"         /* Virtual console master */
#define CONSOLE "/dev/console"     /* Logical system console */
#define SECURETTY "/etc/securetty"     /* List of root terminals */
#define SDALLOW "/etc/shutdown.allow" /* Users allowed to shutdown */
#define INITTAB "/etc/inittab"     /* Location of inittab */
#define INIT "/sbin/init"     /* Location of init itself. */
#define NOLOGIN "/etc/nologin"     /* Stop user logging in. */
#define FASTBOOT "/fastboot"         /* Enable fast boot. */
#define FORCEFSCK "/forcefsck"     /* Force fsck on boot */
#define SDPID "/var/run/shutdown.pid" /* PID of shutdown program */
#define SHELL "/bin/sh"         /* Default shell */
#define SULOGIN "/sbin/sulogin"     /* Sulogin */
#define INITSCRIPT "/etc/initscript"     /* Initscript. */
#define PWRSTAT_OLD "/etc/powerstatus"     /* COMPAT: SIGPWR reason (OK/BAD) */
#define PWRSTAT "/var/run/powerstatus" /* COMPAT: SIGPWR reason (OK/BAD) */

#if 0
#define INITLVL "/etc/initrunlvl"     /* COMPAT: New runlevel */
#define INITLVL2 "/var/log/initrunlvl" /* COMPAT: New runlevel */
                            /* Note: INITLVL2 definition needs INITLVL */
#define HALTSCRIPT1 "/etc/init.d/halt"     /* Called by "fast" shutdown */
#define HALTSCRIPT2 "/etc/rc.d/rc.0"     /* Called by "fast" shutdown */
#define REBOOTSCRIPT1 "/etc/init.d/reboot" /* Ditto. */
#define REBOOTSCRIPT2 "/etc/rc.d/rc.6" /* Ditto. */



- It exits if UID is != 0 (root)
- It exits if PID != 1 (the first process in Kernel's userspace)
- It check command-line args:
    "single", "-s"      : dfl_level is set to 'S'
    "-a", "auto"        : set environment "AUTOBOOT=YES"
    "-b", "emergency"   : emerg_shell = 1
    "-z"                : ignore -z xxxx
    any of [0-9],[sS]   : dfl_level is set accordingly to that level

- set default environment PATH to "/sbin:/usr/sbin:/bin:/usr/bin"
- say "@(#) init version 2.89  DATE 26-Mar-2010  miquels@cistron.nl booting" into syslog
- spawn/fork to emergency shell if emerg_shell == 1
- read inittab and configure setting based on the settings stored in INITTAB

init.c: main() ---> setproctitle()
    |
    |
    V
init_main() ----------------------------> read_inittab()
 |  |   |
 |  |   |
 |  |   V
 |  |   init_reboot(BMAGIC_SOFT)
 |  |
 |  |
 |  V
 | ioctl(f, KDSIGACCEPT, SIGWINCH): tell kernel SIGACCEPT
 |
 +---> set a bunch of signals' flags
 |
 +----> console_init(), open /dev/CONSOLE (or otherwise if specified in env "CONSOLE") for O_RDONLY
 |
 +----> console_stty() : Set terminal settings to reasonable defaults
 |
 +----> set default environment PATH to "/sbin:/usr/sbin:/bin:/usr/bin"
 |
 loop forever by doing this stuf:
    1) boot transitions
    2) Read from the init FIFO by calling check_init_fifo():
        2.1) try to create /dev/initctl if not present.
        2.2) If /dev/initctl is open, stat the file to see if it is still the _same_ inode
        2.3) try to open /dev/initctl
        2.4) Read data from the pipe, return on EINTR
        2.5) console_init
        2.6) process requests (e.g., runlevel change request, power fail request, set env)

    3) check the 'failing' flags
    4) process any signal:
        4.1) SIGPWR event/signal
        4.2) SIGINT
        4.3) SIGWINCH
        4.4) SIGALRM
        4.5) SIGCHLD
        4.6) SIGHUP
    5) See whether we need to start up (again)




BOOT TRANSITION FSM
--------------------



        '#' (SYSINIT) --+-----> '*' (BOOT) ------> (NORMAL)
                        |              ^
                        |              |
           newlevel=='S'|              | !did_boot && newlevel != 'S'
                        |              |
                        +-----> 'S' (INIT)
                                       ^
                                       |
                                       |
                                   start here

Interactive map of Linux kernel

Interactive map of Linux kernel

Are We Ready with e-Magazine?

Today Apple's Steve Jobs announced the subscription service for magazine subscription is now supported.  The similar service has been available in Amazon for its Kindle for sometime.  But regardless the availability, Dol we really want to read magazines on an electronic gadget?

Here's my experience using different e-readers, both on PC, iPhone, iPad and Kindle.  First of all, reading magazines on iPad has the most interesting experience because its bigger footprint than iPhone and interactivity thru its touch screen.  For the easiness to our eyes, Kindle prevails, but with no color as its main downside.  Reading on PC's monitor is also a good experience, except it's too bulky to carry notebook during travel, let alone reading on desktop.

Another aspect we need to pay attention is the cost of subscription (and yes, this is really a turnoff, at least for me).  For example, I subscribe to Reader's Digest for about $2 a year, while on Amazon they charge about $2 per edition (one magazine a year, so total subscription is about $20).  A paper TIME magazine subscription, through Ad subsidy, only charge me about $15/year.  Amazon charges about $2 per magazine.  I bet Apple will charge about the same.  It's so non-sense and doesn't make sense! Both Apple, Amazon and the publishers want to rip us off and trick us to pay so much for less!  Publishing an e-Magazine costs almost nothing (99.9% of the cost is from the operational costs including the editors/writers, unlike paper-based magazines where they have to print it and distribute it).

Another issue with e-Magazine is the magazines we already one are unsharable, unless they are DRM-free.  With paper magazine, we can lend the magazine to friends and let them read free-of-charge and as long as we let them borrow it.  Some e-book readers have this borrow-a-book feature, but it is still limited and not convenience to use.  Also, format compatibility is a big issue right now, at least between Amazon's AZW and others' EPUB (iBook uses EPUB as well as Nook and other majority of e-readers). If we buy a magazine from Amazon, it cannot be read on iPad, unless we install Kindle-for-iPad/iPhone application for it.

The only benefit of subscribing to e-Magazine right now is that it reduces clutters of magazines.  A Kindle can store thousands of magazines (depends on the content.  If the magazine has alot of pictures, the size will be bigger), iPad can even store much more.

So, the bottom line is that we're (or at least me) not ready to migrate to read e-magazine yet.  Maybe some people can take some advantages of reading an e-magazine, but for most people it is not cost-effective yet.  Once it's become so ubiquitous and ads are everywhere in the e-magazines to offset the cost, perhaps it's the time we shall migrate to this environment-friendly magazine.  Oh, don't forget also by reading paper e-magazine, we support many people's live too, from workers at printing facilities, paper companies, newstand guys to truck drivers!

Android vs iOS based Tablets

Many web sites do comparison between Android-based tablets and iPad, but unfortunately almost none of them mention about one important thing: upward/downward binary-compatibility.

What does that mean? OK, we now that a software or an application is actually stored in file.  On desktop operating systems (Windows, Mac, Linux etc.), these files are executable on their respective O/S, but only for specific machine.

iPad (or iPhone) Applications are actually binary applications similar the ones we find on Windows or Mac in that they contain machine instructions directly instruct each step to be taken by CPU.  The instruction set is specific to the CPU it is built on (for example, iPad app cannot run on Windows or Linux, unless we have an emulator to translate the machine code on-the-fly).

The mechanism of running application is Android is slightly different.  Although Android O/S kernel is based on Linux, its applications run on top of a Java virtual machine called "Dalvik".  It specifies its own instruction set, outside the platform it runs on (Linux).  It acts as a new realm in a realm. The benefit is that we can run Android application on any machine we like (as long as we have the Android O/S compiled and run on the specific CPU).  theoritically, an application built for Android running on MIPS CPU can also run on Intel CPU so on.

Why it is important? because developers are no more tied to develop an application specific to a CPU.  They can just develop once and it will run on various machines.

Query syntax in Google Spreadsheet

I was calculating my expenses related to medical for the purpose of Tax report. All my data is recorded in a spreadsheet in Google Spreadsheet. After experimenting, I am now pleased with its formula, especially the power of query syntax (similar to SQL syntax).


Assume a spreadsheet named "2010" where it contains tax-deductible data. Row 1 cells contain title. Actual data starts from row 2 to row 419 (range is A2 to J419)


Cells in column G contains expenses related to medical. Each Cell in column J contain text, where for medical-related expense it should contain "medical" etc.


Now, to calculate the sum of all medical-related expenses, we can put the following formula somewhere in empty cell down below as:


=query('2010'!$G$2:$J$419;"select sum(G) where J contains 'edical' "; 0)


contains query is not exact-matching, so the logic is still TRUE even if we have "medical" or "Medical".


The reason I omit "m" in "medical" is to avoid case-sensitive query (I might put "Medical" instead of "medical" in my data). We can also put LOWER() function for J to force case-insensitive matching so it will still match any case of the letters, for example:

=query('2010'!$G$2:$J$419;"select sum(G) where LOWER(J) contains 'medical' "; 0)

In this case, I put the formula in another spreadsheet (that's why you see prefix '2010' there to refer to spreadsheet named "2010").


To do logical NOT, the syntax is "NOT J contains 'edical". If you want to do logical AND, put AND in front of NOT, so it will be: "NOT J contains 'medical' AND NOT J contains 'dental' "

The best so far is as below:


=ArrayFormula(IFERROR(query('2010'!$G$2:$J$419;"select sum(G) where LOWER(J) contains 'medical'"), 0))



and the next row will fill with:


=iferror(CONTINUE(B2, 2, 1))



There are many more formulas we can experiment: MATCH(), FILTER() and so on.