Modified Preorder Tree Traversal

How do you represent an organizational structure in a SQL data table? When I ask this question in interviews the answer I always get is with an adjacency list (although no one refers to it as that)

An adjaceny list structure would look like this:

EmployeeId, EmployeeName,ManagerId
----------------------------------
         1,          Bob,   
         2,        Frank,        1
         3,         Stan,        1
         4,        James,        3

This structure shoes that Bob is the boss with no manager. Frank and Stan report to Bob, and James reports to Stan. This structure is very common. If you want to list all of Stan's reports, its easy:

select EmployeeName from Employees where ManagerId = (select EmployeeId from Employees where EmployeeName = 'Stan')

But what if you want to list all of Bob's reports? I have yet had anyone answer this question completely to my satisfaction. The typical response is to use a recursive look up. That is all well and good if your tree isn't very deep, but can we do better? Yes!

We can instead structure our table as follows:

EmployeeName,LeftId, RightId
----------------------------------
         Bob,     1,       8
       Frank,     2,       3
        Stan,     4,       7
       James,     5,       6

Huh you ask what did we just do? Let visualize it like this:

  1-bob-8
     /            \
 2-Frank-3      4-Stan-7
                  /
             5 James 6

We start at the left of Bob and assign the first id 1. We move down his org chart and hit Frank and assign him next id of 2. Frank has no children so we go to his right node and assign next id of 3. The next sibling is Stan with id 4. Stan has a child so we go to James with id 5, then work our way back up the tree assigning James Right 6, Stan 7 and Bob 8.

So our algorithm is:

AssignId(Node n)
  n.leftid = nextId()
  foreach(Node child : n.children)
     AssignId(child)
  // No more children assign my right
  n.rightid = nextId()

So what does this accomplish? Lets answer my orignal question. Display all reports of Bob:

(leftid,rightid) =select LeftId,RightId from Employee where EmployeeName = 'Bob'
select * from Employee where lft between $leftid, $rightid;

That's it. With this tree structure you can easily find all the children of a given node. Of course this method has drawbacks. Inserts are more difficult. But if you have a database that is mostly read only you may consider giving this a try.

Enjoy...

Cuda Hello World: Entire Code Listing

/********************************************************************
*  CUDAWin32App10.cu
*  This is a example of the CUDA program.
*********************************************************************/

#include 
#include 
#include 

/************************************************************************/
/* Init CUDA                                                            */
/************************************************************************/
bool InitCUDA(void)
{  
   int count = 0;
   int i = 0;

   cudaGetDeviceCount(&count);
   if(count == 0) {
       fprintf(stderr, "There is no device.\n");
       return false;
   }

   for(i = 0; i <>= 1) {
               break;
           }
       }
   }
   if(i == count) {
       fprintf(stderr, "There is no device supporting CUDA 1.x.\n");
       return false;
   }
   cudaSetDevice(i);
   return true;
}

/************************************************************************/
/* Example                                                              */
/************************************************************************/
__global__ static void HelloCUDA(char* result, int num, clock_t* time,int foo)
{
   int i = 0;
   char p_HelloCUDA[] = "Hello CUDA!";
   clock_t start = clock();
   for(i = 0; i < time =" clock()" device_result    =" 0;" time            =" 0;" time_used        =" 0;">>>(device_result, 11 , time,1);


   cudaMemcpy(&host_result, device_result, sizeof(char) * 11, cudaMemcpyDeviceToHost);
   cudaMemcpy(&time_used, time, sizeof(clock_t), cudaMemcpyDeviceToHost);
   cudaFree(device_result);
   cudaFree(time);

   printf("%s,%d\n", host_result, time_used);

   return 0;
}

Cuda Hello World: part 2

In Part 1 we setup a Visual Studio project to run our first cuda program. In this part we will look deeper into the template and explain what it is doing.

A Cuda program is structured as followed
1) Define a Kernel
2) Copy system memory to GPU memory
3) Execute the Kernel
4) Copy results from GPU memory back to system memory
5) Print our results, and cleanup

We'll look at each part.

Define a Kernel

A kernel is a function that is executed. For our example will follow the sample template from the Visual Studio plugin and create a HelloCuda method.

__global__ static void HelloCUDA(char* result, int num, clock_t* time)
{
 int i = 0;
 char p_HelloCUDA[] = "Hello CUDA!";
 clock_t start = clock();
 for(i = 0; i < num; i++) {
    result[i] = p_HelloCUDA[i];
 }
*time = clock() - start;
}

The __global__ declaration specifier indicates that the procedure is a kernel entry point. Our function takes in an:
array of characters
size of the array
pointer to clock_t structure

The kernel doesn't do much it copies into our character array "Hello CUDA!". As you can probably infer from the assignment of time we are planning on only calling this function one time.

Copy system memory to GPU memory

Now that our kernel is defined we need to prep our data structures such that we can execute the kernel. For this example we'll need to allocate a block of memory to hold the "Hello CUDA!" string, and a clock_t structure for the elapsed time.

To allocate memory on the GPU we use cudaMalloc.

char *device_result = 0;
clock_t  *time   = 0;
cudaMalloc((void**) &device_result, sizeof(char) * 11);
cudaMalloc((void**) &time, sizeof(clock_t));

The memory has now been set aside in the GPU and were ready to execute the kernel

Execute the Kernel

The following code will execute our defined kernel passing in the arguments we just created.

HelloCUDA<<<1, 1, 0&rt;&rt;&rt;(device_result, 11 , time,1);

At this stage the GPU will execute our program and will have our results, we need to copy those results back to the system so we can use them.

Copy results from GPU memory back to system memory

To get our results off of the GPU we use cudaMemcpy and copy the data back into our own storage. To do that we must define a char*, and a clock_t then memcpy the results back.

char  host_result[12] ={0};
clock_t  time_used  = 0;
cudaMemcpy(&host_result, device_result, sizeof(char) * 11, cudaMemcpyDeviceToHost);
cudaMemcpy(&time_used, time, sizeof(clock_t), cudaMemcpyDeviceToHost);

Print Results and Clean up

That's it the GPU has ran our program created a string called 'Hello CUDA!' copied that into the char * result that we have a pointer to called device_result. It has also filled in clock_t struct in gpu memory which we have a pointer to called time.

We've copied the gpu memory into local variables called host_result, and time_used and now can use it like an C program. So lets print it out.

cudaMemcpy(&host_result, device_result, sizeof(char) * 11, cudaMemcpyDeviceToHost);
cudaMemcpy(&time_used, time, sizeof(clock_t), cudaMemcpyDeviceToHost);

The last thing we need to do is free the memory on the device we use cudaFree.

cudaFree(device_result);
cudaFree(time);

That's it! If you run the program you should get output similar to the following:

CUDA initialized.
Hello CUDA!,0
Press any key to continue . . .

Click here for the entire code listing

Miscellaneous tools

This is a short post to preserve some useful tools that I use from time to time but I always forget their names.

1) BackTrack: Very useful linux boot disk based off SLAX. It comes preloaded with a lot of cool tools but I like it so I can just boot into linux off of usb key and run firefox.

2) Driftnet, fun but useless tool. Shows all the images that you access by sniffing your own traffic

3) how to set up linux to connect to wirless network:
ifconfig down
ifconfig up
iwconfig essid 'name of network'
iwconfig key 'name of network'
iwconfig mode managed
dhcpcd

4) Syntax highlight code and covert it to HTML: http://www.tohtml.com/jScript/

5) Visual Assist X claims to to background compilation (crosses fingers) ( didn't work that well)

6) SQLylog Enterprise addition ( has auto complete for sql tables )

7) SiSoftware's SANDRA , useful for analyzing your computer and figuring out what components you have. For examle I couldn't get a used audio card to work. SANDRA identified the chipset then with a quick google I had the driver.

Perl CGI cached parameters.

An intern at work today ran into a problem modifying a perl cgi script. It looked something like this


my $cgi = new CGI;
$cgi->param('foo');


The problem was this value appeared to be cached. Once I accesed the page with http://server/page?foo=bar it would remember bar no matter what I changed the value to.

First I thought it was a cache issue. So we changed the code to output a timestamp. On each page load we would see the time increment but the variable was still cached somehow.

We finally found out that putting the new CGI call inside a function made sure we got a new one each time.

So what happened? I'm not really sure, I'm guessing scope of the perl code is global per apache process? Is this configurable somehow?

Well if anyone knows please add a comment because i this point I'm still baffled by it.

c++ Windows Programing - Creating a window

This tutorial will cover how to create a window. If you haven't already you should read the Hello World tutorial for Windows Programming first.

In the last tutorial I described how to create a windows program that displays a message box. We are going to extend on that tutorial and create a window this time.

This will consists of 4 parts.

1. Register a new windows class (not to be confused with a c++ class)
2. Create the window
3. Display the window
4. Process Events.

Part 1. Registering a new window class

The first step is to fill in a windows structure that describes how your new window will look like. We'll use the WNDCLASSEX structure.


WNDCLASSEX wc;

// clear out the window class for use
ZeroMemory(&wc, sizeof(WNDCLASSEX));

// fill in the struct with the needed information
wc.cbSize = sizeof(WNDCLASSEX);
wc.style = CS_HREDRAW | CS_VREDRAW;
wc.lpfnWndProc = (WNDPROC)WindowProc;
wc.hInstance = hInstance;
wc.hCursor = LoadCursor(NULL, IDC_ARROW);
wc.hbrBackground = (HBRUSH)COLOR_WINDOW;
wc.lpszClassName = L"MyClass";

RegisterClassEx(&wc);

We first declare a new instance and zero out the memory of the instance. We then set appropriate parameters to define how the window will look. For full details on the paremeters you should consult msdn.

The lpfnWndProc is an important property. This defines a function that will be called back whenever this window needs to handle a message. We'll discuss more abot this in Part 4.

Part 2. Creating the window.

Now that we've defined the style of how our new window should look, we want to actually create the window. We'll use the CreateWindowEx function which has the following prototype:


HWND CreateWindowEx(
DWORD dwExStyle,
LPCTSTR lpClassName,
LPCTSTR lpWindowName,
DWORD dwStyle,
int x,
int y,
int nWidth,
int nHeight,
HWND hWndParent,
HMENU hMenu,
HINSTANCE hInstance,
LPVOID lpParam
);


Part 3: Display the Window

Displaying the window is accomplished by calling ShowWindow which has the prototype:


BOOL ShowWindow(
HWND hWnd,
int nCmdShow
);


Part 4: Processing Events

We now have the parts to describe the style of a window, register it, create it, and display it. But if we don't process the windows events nothing will happen. Remember lpfnWndProc from Part 1?

We must define that call back method. Anytime a message is received it will need to run through that method.

So first we need to get message off the messaging queue than define our callback.


// this struct holds Windows event messages
MSG msg;

// wait for the next message in the queue, store the result in 'msg'
while(GetMessage(&msg, NULL, 0, 0))
{
// translate keystroke messages into the right format
TranslateMessage(&msg);

// send the message to the WindowProc function
DispatchMessage(&msg);
}




// this is the main message handler for the program
LRESULT CALLBACK WindowProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
// sort through and find what code to run for the message given
switch(message)
{
// this message is read when the window is closed
case WM_DESTROY:
{
// close the application entirely
PostQuitMessage(0);
return 0;
} break;
}

// Handle any messages the switch statement didn't
return DefWindowProc (hWnd, message, wParam, lParam);
}



Conclusion:

Putting it all together we have a program that looks like this:


#include
#include

LRESULT CALLBACK WindowProc(HWND hwnd,UINT message,WPARAM wParam,LPARAM lParam);

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow) {
//Our window structure.
WNDCLASSEX wc;
ZeroMemory(&wc,sizeof(WNDCLASSEX));

wc.cbSize = sizeof(WNDCLASSEX);
wc.style = CS_HREDRAW | CS_VREDRAW;
wc.lpfnWndProc = (WNDPROC)WindowProc;
wc.hInstance = hInstance;
wc.hCursor = LoadCursor(NULL, IDC_ARROW);
wc.hbrBackground = (HBRUSH)COLOR_3DSHADOW;
wc.lpszClassName = L"WindowClass1";

RegisterClassEx(&wc);

// create the window and use the result as the handle
HWND hWnd = CreateWindowEx(NULL,
L"WindowClass1", // name of the window class
L"Our First Windowed Program", // title of the window
WS_OVERLAPPEDWINDOW, // window style
300, // x-position of the window
300, // y-position of the window
500, // width of the window
400, // height of the window
NULL, // we have no parent window, NULL
NULL, // we aren't using menus, NULL
hInstance, // application handle
NULL); // used with multiple windows, NULL

ShowWindow(hWnd,nCmdShow);

MSG msg;
while(GetMessage (&msg,NULL,0,0)) {
TranslateMessage(&msg);
DispatchMessage(&msg);
}
return msg.wParam;
}

LRESULT CALLBACK WindowProc(HWND hwnd,UINT message,WPARAM wParam,LPARAM lParam)
{
switch(message) {
case WM_DESTROY: {
PostQuitMessage(0);
return 0;
} break;
}
return DefWindowProc(hwnd,message,wParam,lParam);
}


Hello World - c++ Windows Application

In this post I'm going to explain the details of writing a hello world program for windows. To start we should look at the version for a console application:


#include <iostream&rt;
using namespace std;
void main() {
cout << "Hello World" << endl;
}


For windows it isn't much different. But instead of declaring a main we need to instead declare a WinMain.


#include <windows.h&rt;

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShowCmd) {
MessageBox(NULL,L"Hello World",L"MyCaption",MB_ICONINFORMATION | MB_OK);
}


1. We include windows.h to give us access to the windows library functions.

2. The keyword WINAPI instructs the program to reverse the argument list. For our purposes this doesn't matter but under the hood windows needs this.

3. HINSTANCE is a handle to an instance. The main program receives a instance to itself (hinstance) and a handle to a previous instance of the same program. The previous instance is legacy and is NULL for modern applications. But is still provided for legacy code.

4. lpCmdLine is the entire command string that was used to execute the program.

5. nCmdShowCmd are options indicating how the window should open.

6. Once our method is called we can then call MessageBox to display the message.

We can now look into the MessaegBox command in more detail. The signature for the command is:


int MessageBox(HWND hWnd,
LPCTSTR lptext,
LPCTSTR lpcaption,
UINT utype);


The first argument HWND, is a handle to the window the created this message box. In our case we haven't created a window, so we supply NULL which instructs Windows to have the message box originate from the desktop.

lpText is a pointer to the text to display

lpcaption is a pointer to the caption of the message box.

uType is a parameter that specifies what type of message box, exclamation, information, etc. These are set by 'ORing' constant flags together.