Tuesday, October 30, 2012

implementing doubly linked list using single pointer


The problem with single linked list is that, we cant back traverse, only forward traversal is allowed because current node contains the address of the next node.  To traverse back wards we need another pointer to store the previous address and that concept is called doubly linked list.

We can implement back traversal by storing previous and next node address in the single pointer. For this we need to use the concept of XOR operation.

XOR Operations: let’s see the beauty of XOR operation.

If you perform XOR operation on any two input values, you will get some result. And if you perform again XOR operation with result and any one of the two input values, you will get other input value. We are going to use this logic to store the prev and next node values. See the example below.

  a ^ b = c
  c ^ b = a
  c ^ a = b

So while creating the linked list, we need to perform XOR operation to get the next node value.  The key point in this process is, we need to maintain the prev node value to make the XOR operation.

Creating and storing the next pointer value:  The value which we are going to store in the next pointer is the XOR operation of prev and new nodes. So next pointer of the node should not points to the next node, instead of that, its having some value which is a combination of prev and next nodes as shown in the picture. For complete code click here.



If the list contains single node, as prev pointer value is initially NULL, so there wont be any problem.

Forward traversing: to move the pointer from current node to next node, the sample code is given below. For complete C implementation click here.

current = current->next ^ prev

Before Operation:
After Operation:

After executing above statement, the current node moves to the next node as shown below.

Backward traversal:  Assume that below is the scenario and we are at current node and we know the address of temp, so to get the prev node of the current node, the sample code is below. For complete C code click here.

while(temp!=h)
 {
   printf("%d->",temp->info);
   prev = prev->next ^ temp;
   temp = tempPrev;
   tempPrev = prev;
 }

Before operation:

After operation:

In this way, we  need to do the operations to get the prev node and next node addresses. And there are more statements to maintain prev and next node pointers. Click here for the complete working C Implementation.

Note: XOR operation can be performed only on integer or char data type. And XOR is not allowed on structure as it is user defined data type. To perform the XOR operation, we need to type cast it to long int.


Saturday, October 20, 2012

git-upload-pack: command not found

Recently we planned to use git version control system. So I tried to setup the git server in the server machine, and everything went  well from the server side. While making local copy in the the local machine we got the below error.

$ git clone ssh://remotehost:/git-path/git/root.git
Cloning into root...
Password:
bash: git-upload-pack: command not found
fatal: The remote end hung up unexpectedly

The reason for this is, it is not finding the path for the git-upload-pack. you need to specify the path manually. For that just use -u option for the git clone command and specify the path of git-upload-pack path in the server.

$ git clone -u /usr/local/git/bin/git-upload-pack ssh://remotehost:/git-path/git/root.git
Cloning into 'root'...
Password:
remote: Counting objects: 408, done.
remote: Compressing objects: 100% (330/330), done.
remote: Total 408 (delta 90), reused 379 (delta 69)
Receiving objects: 100% (408/408), 27.00 MiB | 47.22 MiB/s, done.
Resolving deltas: 100% (90/90), done.

To get the path of the git-upload-pack in the server, login to the server and run which git-upload-pack command as shown below.

$ which git-upload-pack
/usr/local/git/bin/git-upload-pack

when you do git pull or git push , you may get this error.

$ git pull
bash: git-upload-pack: command not found
fatal: The remote end hung up unexpectedly

$git push
bash: git-receive-pack: command not found
fatal: The remote end hung up unexpectedly

To solve that problem, you can either run the below commands or  modify the config file in .git directory.

$ git config remote.origin.uploadpack /usr/local/git/bin/git-upload-pack

$ git config remote.origin.receivepack /usr/local/git/bin/git-receive-pack


or you can edit the .git/config file and add the content in the below form.

[remote "origin"]

        fetch = +refs/heads/*:refs/remotes/origin/*
        url = remote_host:/path/git/root.git
        uploadpack = /usr/local/git/bin/git-upload-pack
        receivepack = /usr/local/git/bin/git-receive-pack

Then you can able to clone the git repository, you can able to pull/push the code from/to the remote server. 


Popular Posts