Why is this blog called 'techniko'?

'techniko' is a take on the word tekniko which means technics or technique in Esperanto. Esperanto is a constructed international language designed for international communication. The basic rules and words of Esperanto were proposed by L. L. Zamenhof at the end of the 19th century.

Since this blog primarily deals with technology, I think 'techniko' is a apt (and it sounds pretty cool too!).

Check this site out if you want to early Esperanto.

Follow @virup

Use of Dog-tag Fields to Check for Corrupted Memory

Tweet

Often times in a program, memory needs to be allocated and subsequently deleted. A program might be fatally affected if a deleted memory is reused, or if a memory is deleted more than once. "Dog-tag" fields are used to detect corruption. A tag field is attached to memory structure for error checking and if the tag does not have the expected value, then the data is corrupted.

Lets say you want to request 10 bytes. We will use a tag field of 4 bytes. It works in the following manner:

1. Allocate a total of 10 + 4 = 14 bytes

2. Set the first 4 bytes to a tag value.  For our purpose, we will assume INUSE tag equal to 1. Any other value indicates corruption.

3. Return a pointer to the memory which starts AFTER the tag field

Deletion:

When deleting, follow these steps:

1. Check the tag. If the tag value is equal to INUSE, then set it to FREED (assumed to be 0 in our case).

2. Delete the whole 14 bytes

That's it!

Implementation:

The following code is an implementation of the above concept in C. It has two function: safe_malloc() and safe_delete() which when used in pair performs the above strategy.

	#include <stdlib.h>
	#include <stdio.h>
	#define INUSE 1
	#define FREED 0
	void *safe_malloc(unsigned int length)
	{
	int *tag;
	char *actualStartPt;
	void *data = calloc(length + 4,1);
	// If no memory
	if(data == NULL)
	return NULL;
	// Put value in dog-tag
	tag = (int*)data;
	tag = INUSE;
	actualStartPt = (char*)data + 4;
	return (void *)actualStartPt;
	}
	unsigned int safe_free(void *data)
	{
	int *tag = (int*)data;
	tag = tag - 1;
	if(*tag == FREED)
	return 0;
	if(*tag == INUSE)
	{
	*tag = FREED;
	void *startingPoint = tag;
	free(startingPoint);
	return 1;
	}
	return 0;
	}
	int main()
	{
	// Allocate memory using safe_malloc
	char *temp = (char *)safe_malloc(10);
	// Perform tasks with the *temp pointer
	// ...
	// .....
	// Perform safe free'ing of memory
	safe_free(temp);
	// Does not create corruption
	safe_free(temp);
	return 0;
	}

view raw dog_tag.c hosted with ❤ by GitHub

Get interesting code ideas from me on twitter Follow @virup

Book Review: India Calling: An Intimate Portrait of a Nation's Remaking

I recently completed reading India Calling: An Intimate Portrait of a Nation's Remaking by Anand Giridharadas. Giridharadas writes the "Currents" column for the International Herald Tribune and The New York Times online. A child of immigrant parents, he worked in Mumbai as a management consultant until 2005, when he began reporting from that city for the Herald Tribune and the Times. 

The book traces the new found freedom and ambition among the people of India. Giridharadas contrasts the current Indian society with the time when his parents moved from India to US for better prospects. At that time Giridharadas notes, the move from India to the US was a necessity unlike now. He provides a bewildered foreigner's perspective on the rapidly developing, fast paced, increasingly westernized India and he finds it difficult to reconcile the Indian story that he heard from his parents when he was young.

Watch his interview with Jon Stewart about his book here : 

The Daily Show with Jon Stewart	Mon - Thurs 11p / 10c
Anand Giridharadas
www.thedailyshow.com
Daily Show Full Episodes Political Humor & Satire Blog The Daily Show on Facebook

If you like my blog, make sure you follow my on twitter for more interesting stuff.
Follow @virup

How to Install Oracle's SQL*Plus in Ubuntu Without Instaling Oracle

SQL*Plus is an Oracle command-line utility program that can run SQL and PL/SQL commands interactively or from a script. Programmers and DBAs commonly use it as the default available fundamental interface in almost any Oracle software installation

Oracle does not provide .deb packages which are recognized by Ubuntu. Instead they provide .rpm packages. This tutorial tells how to install SQL*Plus without installing Oracle and using the .rpm packages in Ubuntu.

Follow these steps : 

1. Download the following .rpm packages from Oracle's website.

         a. Choose either 32 bit or 64 bit versions 
         b. Download Instant Client Package - Basic: All files required to run OCI, OCCI, and JDBC-OCI applications
         c. Download Instant Client Package - SQL*Plus: Additional libraries and executable for running SQL*Plus with Instant Client
         Remember to download the .rpm versions and NOT the .zip versions

2. Install the application alien to convert the .rpm packages to .deb. Install it by executing:

$ sudo apt-get install alien

3. CD to the folder containing the .rpm file

$ sudo alien -k oracle-instantclient*.rpm

4. The .deb files have been generated. Install them using 

$ sudo dpkg -i oracle-instantclient*basic*.deb $ sudo dpkg -i oracle-instantclient*sqlplus*.deb

5. Add the library to classpath. 

$ vim ~/.bashrc

6. Add this line at the end of the file. Replace $version$ with the correct number.

$ export LD_LIBRARY_PATH=/usr/lib/oracle/$version$/client/lib

Now you can connect to any oracle installation using the command : 

       $ sqlplus username/password@hostname/orcl




Replace username, password, hostname, and orcl. Mostly the orcl will be "orcl" only.




Finding Shortest Path in a Graph inside PostgreSQL Database

Tweet

@cegme and I recently tackled this interesting problem of finding the shortest route between two nodes in a graph from inside a database.

We have a list of research papers and their citations which we call "links". The idea is to start from a given paper and follow its links recursively till reach the specified destination paper. This is a typical graph problem and can be solved using well known shortest-path finding algorithms. However our data was in the database consequently we wanted to solve the problem using SQL queries which was a challenge.

We solved this problem inside the database using WITH queries (Common Table Expressions) which was introduced in PostgreSQL version 8.4. The following extract explains WITH keyword.

WITH provides a way to write subqueries for use in a larger SELECT query. The subqueries, which are often referred to as Common Table Expressions or CTEs, can be thought of as defining temporary tables that exist just for this query. One use of this feature is to break down complicated queries into simpler parts.

This is how we went about solving the problem:

We have the following table (in a PostgresSQL database):
Reference(pid integer, citation integer);         // paper "pid" cites paper "citation"

We created a User Defined Function (UDF) called:
search_path(start integer, destination integer)

Where start is the paper id of the starting paper and destination is the paper id of the last paper.

	CREATE OR REPLACE FUNCTION search_path(start integer, destination integer)
	RETURNS TABLE(depth integer, path integer[]) AS $$
	BEGIN
	RETURN QUERY
	WITH RECURSIVE search_paper(id, link, data, depth, route, cycle) AS (
	SELECT r.pid, r.citation, 'data', 1,
	ARRAY[r.pid],
	false
	FROM reference r where r.pid=start
	UNION ALL
	SELECT r.pid, r.citation, 'data', sp.depth+1,
	route || r.pid,
	r.pid = ANY(route)
	FROM reference r, search_paper sp
	WHERE r.pid = sp.link AND NOT cycle
	)
	SELECT sp.depth, (sp.route || sp.link) AS route
	FROM search_paper AS sp
	WHERE link = destination AND NOT cycle ORDER BY depth ASC;
	END;
	$$ LANGUAGE plpgsql;

view raw search_path.sql hosted with ❤ by GitHub

Detailed Explanation

Let me explain what happens in this UDF:

1. We declare a UDF :

CREATE OR REPLACE FUNCTION search_path(start integer, destination integer)

2. It returns a table.

RETURNS TABLE(depth integer, path integer[]) AS $$

3. We use the WITH RECURSIVE keyword available in Postgres and form a table containing the starting paper (id), the next paper in the path (link), the length of the path (depth), the list of traversed paper (route), and a boolean cycle variable to keep a note of whether we are forming a cycle or not.

WITH RECURSIVE search_paper(id, link, data, depth, route, cycle)

4. We start off with the starting paper id. This is the base case and gets executed only once.

SELECT r.pid, r.citation, 'data', 1,

ARRAY[r.pid],
false
FROM reference r WHERE r.pid=start

5. We recursively add the next link in the path, check if a cycle is formed or not, increase the depth. If a cycle is formed, we immediately exit the loop. This is controlled by the cycle variable. This piece of code gets executed multiple times until cycle != true.

SELECT r.pid, r.citation, 'data', sp.depth+1, route || r.pid,
r.pid = ANY(route)
FROM reference r, search_paper sp
WHERE r.pid = sp.link AND NOT cycle

6. Finally if we hit our destination paper id in the search, we exit the loop. We only select the depth and the route (as an array of integers) and display it. Note that we order the result with increasing depth since we may obtain more than one route.

SELECT sp.depth, (sp.route || sp.link) AS route FROM search_paper AS sp
WHERE link = destination AND NOT cycle ORDER BY depth ASC;

Embedding Code Snippets in a Blog

Recently I have been searching for an easy way to put snippets of code in blog posts which is also attractive looking (including syntax highlighting etc).

I think embedding code from gist is a very convenient way to do it.

These are the steps to do exactly that :

1. Go to http://gist.github.com
2. Past the code you want to post (add optional descriptions and file name)
3. Click on "Create Public Gist"
4. Click on "Embed All Files : show embed"
5. Copy the embed tag HTML code
6. Go back to blogger and create a new post
7. Select "Edit Html" 
8. Paste the embed tag anywhere into your post.

Thats it!  This is my C++ Hello World program :