C Programming - Three Beautiful Quicksorts (by Jon Bentley)

This talk describes three of the most beautiful pieces of code that I have ever written: ... all ยป three different implementations of Hoare's classic Quicksort algorithm. The first implementation is a bare-bones function in about a dozen lines of C. The second implementation starts by instrumenting the first program to measure its run time; a dozen systematic code transformations proceed to make it more and more powerful yet more and more simple, until it finally disappears in a puff of mathematical smoke. It therefore becomes the most beautiful program I never wrote. The third program is an industrial-strength C library Qsort function that I built with Doug McIlroy. A theme running through all three implementations is the power of elegance and simplicity. (This talk expands my Chapter 3 in Beautiful Code, edited by Oram and Wilson and published by O'Reilly in July, 2007.)




Labels:

Posted by - at 2:13 am | 0 comments read on

Debugging - Core Dump Management on the Solaris OS

Really cool article on how to manage core files under solaris. Sun has a very nice list of tools like coreadm, pstack and dumpadm.

enjoy debugging!

Labels: ,

Posted by - at 2:09 am | 0 comments read on

C C++ Programming - Useful Tracing and Profiling Tools

I have been searching for few tracing and profiling tools these days. Tracing tools are my fav because we will be able to debug it while it is running and can get an overview of what is happening inside a.out. esp while learning the flow of a prog.

I found the given below tools and links very useful...


Labels: , , , , , ,

Posted by - at 12:02 am | 1 comments read on

Shell Script - Memory Watch for UNIX Platforms

Simple memory profile script for UNIX/LINUX platforms.


#!bin/sh

PROCCHECKDELAY=1
RUNCHECKDELAY=2
PAGEROWS=80
PROCNAME=$1
PROCID=

if [ $# -ne 1 ]
then
echo give program name to watch;
exit 1;
fi

stat_process()
{
PROCID=
_mypid=
while [ true ]
do
_mypid=`ps -e 2>/dev/null|grep $1|head -n1|awk '{ print $1 }'`;
if [ -z "$_mypid" ]
then
echo "$1 is not running"
else
break;
fi
echo "recheck after $RUNCHECKDELAY seconds";
sleep $RUNCHECKDELAY;
done
PROCID=$_mypid;
}

i=$PAGEROWS;
while true;
do
stat_process $PROCNAME;
if [ $i -eq $PAGEROWS ] ;
then
i=0;
UNIX95= ps -p $PROCID -o vsz,pid,ruser,args 2>/dev/null
else
UNIX95= ps -p $PROCID -o vsz,pid,ruser,args 2>/dev/null|tail +2
fi
if [ ! -z "$PROCID" ]
then
i=`expr $i + 1`;
fi
sleep $PROCCHECKDELAY;
done;


please post your valuable comments and suggestions.

Labels: , , , , ,

Posted by - at 3:17 pm | 0 comments read on

C Programming - Path Correction

If you enter any relative path convert that to absolute path removing those dotdot and dot. Assuming that input is following our grammer :)
eg: Input: /a/b/c/.././ and Output: /a/b

The most obvious solution seems to be stack. But i wanted to give a try with an in-place replacement logic. Here is what i came up with.
Lets start from the other end of the string.

#define COLS 2
#define TESTPATHS{{"/asd/..",""}\
,{"/.",""}\
,{"/a/b/cc/d/..","/a/b/cc"}\
,{"/a/b/cc/d/.","/a/b/cc/d"}\
,{"/a/../cc/.././asd","/asd"}\
,{"/r/../c../dc../.././asd","/c../asd"}\
,{"/a/../c.c/.././asd","/asd"}\
,{"/a/../.c.c/.././asd","/asd"}\
,{"/a/../c..c/.././asd","/asd"}\
,{"/a/../c...c/.././asd","/asd"}\
,{"/a/b/c/d/","/a/b/c/d/"}\
,{"/a/b.c/c/../d/","/a/b.c/d/"}\
,{"",""}\
,{".","."}\
,{"..",".."}\
,{"/a/../c.c/.././rs..","/rs.."}}

int check_skip(char *start, char **cur, char *stop)
{
int retcode = -1;
if (**cur != '.')
retcode = -1;
else if ((*cur + 1 <>= start) && (*(*cur + 1) == '/')
&& (*(*cur - 1) == '/')) {
*cur -= 1;
retcode = 0;
} else if ((*cur - 2 >= start) && (*(*cur + 1) == '/')
&& (*(*cur - 1) == '.') && (*(*cur - 2) == '/')) {
retcode = 1;
*cur -= 2;
}
} else if ((*cur + 1 == stop)) {
if ((*cur - 1 >= start) && (*(*cur - 1) == '/')) {
retcode = 0;
*cur -= 1;
} else if ((*cur - 2 >= start) && (*(*cur - 1) == '.')
&& (*(*cur - 2) == '/')) {
retcode = 1;
*cur -= 2;
}
}
return retcode;
}

char *find_first(const char findme, char *start, char *stop, int oper,
int *pcnt)
{
char *iter = NULL;
if (start == NULL)
return stop;

for (iter = start; iter != (stop + oper); iter += oper) {
if (*iter == findme)
-- * pcnt;
if ((*pcnt == 0) || (*iter == '.'))
break;
}
if (iter == (stop + oper))
iter = stop;
return iter;
}

char *dir_path(char *path)
{
char *dirpath = path;
int dirlen = strlen(path);

char *end = dirpath + dirlen;
char *dest = end;
char *iter = NULL;
int skipcount = 0;

//TODO: skip last slash;

for (iter = end - 1; iter != (dirpath - 1); --iter) {
int rc = check_skip(dirpath, &iter, end);
if (rc != -1) {
skipcount += rc;
continue;
} else {
//skip slash
if ((skipcount != 0) && (*iter != '/')) {
iter = find_first('/', iter, dirpath, -1, &skipcount);
continue;
}
//copy
if ((skipcount == 0) && (iter != dest)) {
*--dest = *iter;
}
}
}
if (skipcount != 0)
printf("parsing error detected\n");
return dest;
}

void test_paths()
{
char *input_strings[][COLS] = TESTPATHS;
int input_size = sizeof(input_strings) / (sizeof(char *) * COLS);

for (int i = 0; i < input_size; i++) {
char *input = strdup(input_strings[i][0]);
char *result = dir_path(input);
if (strcmp(result, input_strings[i][1]) != 0) {
printf
("TEST FAILURE: [ input = %-20s expected = %-20s result = %-20s ]\n",
input_strings[i][0], input_strings[i][1], result);
} else
printf("TEST SUCCESS: [ input = %-40s result = %-20s ]\n",
input_strings[i][0], input_strings[i][1]);
free((void *) input);
}

}

int main(int count, char *args[])
{
if (count != 2) {
printf("usage: %s \n", args[0]);
return -1;
}

char *mypath = strdup(args[1]); //for printing

char *dest = dir_path(mypath);
printf("%-20s : %s\n", "entered path", args[1]);
printf("%-20s : %s\n", "final path", dest);

printf("going to run tests\n");
test_paths();

free((void *) mypath);
return 0;
}


please post your valuable comments and thoughts.

Labels:

Posted by - at 2:41 pm | 0 comments read on

Archives

  • May 2011
  • February 2009
  • December 2008
  • November 2008
  • October 2008
  • August 2008
  • April 2008
  • December 2007
  • November 2007
  • January 2007
  • December 2006
  • October 2006
  • September 2006
  • June 2006
  • May 2006
  • April 2006
  • March 2006
  • February 2006
  • January 2006
  • December 2005
  • November 2005
  • October 2005

Links