Trie implementation in C

To implement the kind of storage which stores strings as the search keys , there is a need to have special data structures which can store the strings efficiently and the searching of data based on the string keys is easier, efficient and faster. One such data structure is a tree based implementation called Trie.

Trie is a data structure which can be used to implement a dictionary kind of application. It provides all the functionality to insert a string, search a string and delete a string from the dictionary. The insertion and deletion operation takes O(n) time where n is the length of the string to be deleted or inserted.

Some of the application of tries involve web based search engines, URL completion in autocomplete feature, Spell checker etc.

Structure of Trie(Specific to this implementation):

The trie implemented here consists of nodes. Each node has these fields:

1. Key - Part of the string to be serached,inserted or deleted.
2. Value -  The value associated with a string (e.g In a dictionary it could be the meaning of the word which we are searching)
3. Neighbour node address - It consists of the address of the neighbouring node at the same level.
4. Previous neighbour address - It consists of the address of the previous node at the same level.
5. Children node address - It consists of the address of the child nodes of the current node.
6. Parent node address - It consists of the address of the parent node of the current node.

The additional nodes like Parent and Previous nodes are added to this implementation for making the search, and deletions easier.

Here is a diagrammatical view of a trie nodes I have used in this implementation. The field key is not represented in the diagram due to symmetry purposes.

  

Let us consider an example to understand tries in detail.

Suppose we have to implement a database for the HR department of an organisation in which we have to store an employee's name and their ages. There is an assumption for this example that there each employee's name is unique.So there is a strange policy in this organisation that any new employee which has a name that already exists in the organisation, it would not hire that new employee.

Let's use this hypothetical example just to understand how tries work.

• Consider we have a new employee named Andrew with age 36. Lets populate our trie for "andrew".



• Now add "tina".



• Add "argo".



• Add "tim".



• Add "t".





• Add "amy".



• Add "aramis".



This is the complete Trie with all the entries. Now let us try deleting the names. I am not capturing the trivial cases.

• Lets try deleting Argo.



• Delete Tina



• Delete Andrew



There is also a video from IIT Delhi which explains the tries. Tries Explained.
The implementation for this Trie is given below. Please provide your suggestions to further improve the implementation.

/*trie.h*/
typedef int trieVal_t;

typedef struct trieNode {
    char key;
    trieVal_t value;
    struct trieNode *next;
    struct trieNode *prev;
    struct trieNode *children;
    struct trieNode *parent;
} trieNode_t;

void TrieCreate(trieNode_t **root);
trieNode_t* TrieSearch(trieNode_t *root, const char *key);
void TrieAdd(trieNode_t **root, char *key, int data);
void TrieRemove(trieNode_t **root, char *key);
void TrieDestroy( trieNode_t* root );

/*trie.c*/
#include <stdio.h>
#include "trie.h"
#include <stdlib.h>

trieNode_t *TrieCreateNode(char key, int data);

void TrieCreate(trieNode_t **root)
{
 *root = TrieCreateNode('\0', 0xffffffff);
}

trieNode_t *TrieCreateNode(char key, int data)
{
 trieNode_t *node = NULL;
 node = (trieNode_t *)malloc(sizeof(trieNode_t));

 if(NULL == node)
 {
  printf("Malloc failed\n");
  return node;
 }

 node->key = key;
 node->next = NULL;
 node->children = NULL;
 node->value = data;
 node->parent= NULL;
 node->prev= NULL;
 return node;
}

void TrieAdd(trieNode_t **root, char *key, int data)
{
 trieNode_t *pTrav = NULL;

 if(NULL == *root)
 {
  printf("NULL tree\n");
  return;
 }
#ifdef DEBUG
 printf("\nInserting key %s: \n",key);
#endif
 pTrav = (*root)->children;



 if(pTrav == NULL)
 {
  /*First Node*/
  for(pTrav = *root; *key; pTrav = pTrav->children)
  {
   pTrav->children = TrieCreateNode(*key, 0xffffffff);
   pTrav->children->parent = pTrav;
#ifdef DEBUG
   printf("Inserting: [%c]\n",pTrav->children->key);
#endif
   key++;
  }

  pTrav->children = TrieCreateNode('\0', data);
  pTrav->children->parent = pTrav;
#ifdef DEBUG
  printf("Inserting: [%c]\n",pTrav->children->key);
#endif
  return;
 }

 if(TrieSearch(pTrav, key))
 {
  printf("Duplicate!\n");
  return;
 }

 while(*key != '\0')
 {
  if(*key == pTrav->key)
  {
   key++;
#ifdef DEBUG
   printf("Traversing child: [%c]\n",pTrav->children->key);
#endif
   pTrav = pTrav->children;
  }
  else
   break;
 }

 while(pTrav->next)
 {
  if(*key == pTrav->next->key)
  {
   key++;
   TrieAdd(&(pTrav->next), key, data);
   return;
  }
  pTrav = pTrav->next;
 }

 if(*key)
 {
  pTrav->next = TrieCreateNode(*key, 0xffffffff);
 }
 else
 {
  pTrav->next = TrieCreateNode(*key, data);
 }

 pTrav->next->parent = pTrav->parent;
 pTrav->next->prev = pTrav;

#ifdef DEBUG
 printf("Inserting [%c] as neighbour of [%c] \n",pTrav->next->key, pTrav->key);
#endif

 if(!(*key))
  return;

 key++;

 for(pTrav = pTrav->next; *key; pTrav = pTrav->children)
 {
  pTrav->children = TrieCreateNode(*key, 0xffffffff);
  pTrav->children->parent = pTrav;
#ifdef DEBUG
  printf("Inserting: [%c]\n",pTrav->children->key);
#endif
  key++;
 }

 pTrav->children = TrieCreateNode('\0', data);
 pTrav->children->parent = pTrav;
#ifdef DEBUG
 printf("Inserting: [%c]\n",pTrav->children->key);
#endif
 return;
}

trieNode_t* TrieSearch(trieNode_t *root, const char *key)
{
 trieNode_t *level = root;
 trieNode_t *pPtr = NULL;

 int lvl=0;
 while(1)
 {
  trieNode_t *found = NULL;
  trieNode_t *curr;

  for (curr = level; curr != NULL; curr = curr->next)
  {
   if (curr->key == *key)
   {
    found = curr;
    lvl++;
    break;
   }
  }

  if (found == NULL)
   return NULL;

  if (*key == '\0')
  {
   pPtr = curr;
   return pPtr;
  }

  level = found->children;
  key++;
 }
}

void TrieRemove(trieNode_t **root, char *key)
{
 trieNode_t *tPtr = NULL;
 trieNode_t *tmp = NULL;

 if(NULL == *root || NULL == key)
  return;

 tPtr = TrieSearch((*root)->children, key);

 if(NULL == tPtr)
 {
  printf("Key [%s] not found in trie\n", key);
  return;
 }

#ifdef DEBUG
 printf("Deleting key [%s] from trie\n", key);
#endif

 while(1)
 {
  if( tPtr->prev && tPtr->next)
  {
   tmp = tPtr;
   tPtr->next->prev = tPtr->prev;
   tPtr->prev->next = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
   break;
  }
  else if(tPtr->prev && !(tPtr->next))
  {
   tmp = tPtr;
   tPtr->prev->next = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
   break;
  }
  else if(!(tPtr->prev) && tPtr->next)
  {
   tmp = tPtr;
   tPtr->parent->children = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
   break;
  }
  else
  {
   tmp = tPtr;
   tPtr = tPtr->parent;
   tPtr->children = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
 }

#ifdef DEBUG
 printf("Deleted key [%s] from trie\n", key);
#endif
}


void TrieDestroy( trieNode_t* root )
{
 trieNode_t *tPtr = root;
 trieNode_t *tmp = root;

    while(tPtr)
 {
  while(tPtr->children)
   tPtr = tPtr->children;

  if( tPtr->prev && tPtr->next)
  {
   tmp = tPtr;
   tPtr->next->prev = tPtr->prev;
   tPtr->prev->next = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
  else if(tPtr->prev && !(tPtr->next))
  {
   tmp = tPtr;
   tPtr->prev->next = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
  else if(!(tPtr->prev) && tPtr->next)
  {
   tmp = tPtr;
   tPtr->parent->children = tPtr->next;
   tPtr->next->prev = NULL;
   tPtr = tPtr->next;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
  else
  {
   tmp = tPtr;
   if(tPtr->parent == NULL)
   {
    /*Root*/
    free(tmp);
    return;
   }
   tPtr = tPtr->parent;
   tPtr->children = NULL;
#ifdef DEBUG
   printf("Deleted [%c] \n", tmp->key);
#endif
   free(tmp);
  }
 }

}

/*triedriver.c*/
/*
 * To Compile : gcc -o trie trie.c triedriver.c
 * To run: ./trie
 */
#include <stdio.h>
#include <stdlib.h>
#include "trie.h"

int main()
{
    trieNode_t *root;
    printf("Trie Example\n");
    
    /*Create a trie*/
    TrieCreate(&root);
    
    TrieAdd(&root, "andrew", 1);
    TrieAdd(&root, "tina", 2);
    TrieAdd(&root, "argo", 3);
    TrieAdd(&root, "timor", 5);
    TrieRemove(&root, "tim");
    TrieAdd(&root, "tim", 6);
    TrieRemove(&root, "tim");
    TrieAdd(&root, "ti", 6);
    TrieAdd(&root, "amy", 7);
    TrieAdd(&root, "aramis", 8);

    /*Destroy the trie*/
    TrieDestroy(root);
}

In order to print the debug messages, use -DDEBUG while compiling with gcc:

gcc -o trie trie.c triedriver.c -DDEBUG

Abstract Binary Search Tree Implementation in C

There are several ways to store data using different data structures like Array, Linked Lists , Trees, Graphs, Hashmaps etc. The choice of the data structure depends on the application which extracts that data. On searching the web , one can easily find out which data structure is required for their application. Binary Search Tree is one such data structure which is generally used for storing data.

A binary search tree consists of members called as nodes which have the data embedded in them. Generally, a BST node contains address fields and data field. The structure of a BST is something like this :

Each node can have a left subtree and right subtree which may or may not have any nodes.

Binary Search tree has some properties which identifies it :

• The left subtree members have a value which is always less than the value at the root node
• The right subtree members have a value which is always greater than the value at the root node
• Both the subtrees must be also a BST.

The implementation provided in this post uses an abstract data type (void). To use this implementation as it is, one must implement these two functions 

1. Comparison Function - This function compares the data between two nodes. This function must return -1, 0 or 1 only.  The signature for this function is int <function-name> (void * data1, void * data2).
1. Function should return 1 when data1 is greater than data2.
2. Function should return -1 when data1 is lesser than data2.  
3. Function should return 0 when data1 is equal to data2.  
2. Display Function - This function is used for display purposes only. It displays the node data.

A sample implementation of these two functions is presented in the driver example(bstdriver.c) for the BST. This sample implementation uses int type as data.

 
/*bst.h*/
typedef struct bstNode
{
    struct bstNode *left;       /*Left Child*/
    struct bstNode *right;      /*Right Child*/
    struct bstNode *parent;     /*Parent Child*/
    void *data;                 /*Data*/
}BSTNode;

void BSTDestroy(BSTNode *root);
void BSTInsert(BSTNode **root, void *data, int (*cmp_fn)(void *, void *));
void BSTDelete(BSTNode **root, void *data, int (*cmp_fn)(void *, void *));
BSTNode* BSTSearch(BSTNode *root, void *data, int (*cmp_fn)(void *, void *));
void BSTDisplay(BSTNode *root, void (*display_fn)(BSTNode *));

 
/*bst.c*/
#include <stdio.h>
#include <stdlib.h>

#include "bst.h"

/* @brief Function to determine if a child is a left child or right child in a BST
 * @param data Pointer to the data to be used
 * @return LEFT - if left child
 *         RIGHT - if right child
 */
static inline const char* BSTFindChildLoc(BSTNode *parent, BSTNode *child)
{
    return (((parent->left)==(child))?"LEFT":"RIGHT");
}

/* @brief Function to swap data between two nodes in a BST
 * @param data Pointer to the data to be used
 * @return void
 */
static inline void BSTSwapNodeData(BSTNode **node1, BSTNode **node2 )
{
    void *tmp;
    tmp = (*node1)->data;
    (*node1)->data = (*node2)->data;
    (*node2)->data = tmp;
}

/* @brief Function to create a node in a BST
 * @param data Pointer to the data to be used
 * @return Address of the node created
 */
BSTNode* BSTCreateNode(void *data)
{
    /*Allocate memory*/
    BSTNode* node= (BSTNode*)malloc(sizeof(BSTNode));

    if(NULL == node)
    {
        printf("Error: Memory Allocation could not be completed\n");
        return NULL;
    }

    /*Initialize links*/
    node->left = NULL;
    node->right= NULL;
    node->parent= NULL;
    node->data = data;

    printf("Allocated Node with address %p\n", node);
    return node;
}

/* @brief Function to destroy all nodes in a BST
 * @param root Pointer to the root of the BST
 * @return void
 */
void BSTDestroy(BSTNode *root)
{
    if(root)
    {
        /*Traverse down the left subtree*/
        if(root->left)
            BSTDestroy(root->left);
        /*Traverse down the right subtree*/
        if(root->right)
            BSTDestroy(root->right);
        /*Free the memory*/
        free(root);
        printf("DeAllocated Node with address %p\n", root);
    }
}

/* @brief Function to insert a node in a BST
 * @param root Pointer to pointer to the root of the BST
 * @param data Pointer to the data to be inserted
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return void
 */
void BSTInsert(BSTNode **root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *tmp = NULL;
    BSTNode *ptr = NULL;

    if(NULL == root)
    {
        printf("Error: Null root\n");
        return;
    }


    if(!(*root))
    {
        /*Create a node*/
        tmp = BSTCreateNode(data);

        if(NULL == tmp)
        {
            printf("Error: Node insertion failed\n");
            return;
        }

        /*Root Node*/
        *root = tmp;
        return;
    }

    ptr = *root;

    /*If data is greater than the current node's data*/
    if(cmp_fn(data,ptr->data) == 1)
    {
        /*data > ptr->data : Insert to right*/
        if(ptr->right == NULL)
        {
            /*Create a node*/
            tmp = BSTCreateNode(data);

            if(NULL == tmp)
            {
                printf("Error: Node insertion failed\n");
                return;
            }

            tmp->parent = ptr;
            ptr->right = tmp;
            return;
        }
        else
        {
            BSTInsert(&(ptr->right), data, cmp_fn);
        }
    }
    /*If data is lesser than the current node's data*/
    else if(cmp_fn(data,ptr->data) == -1)
    {
        /*data > ptr->data : Insert to right*/
        if(ptr->left == NULL)
        {
            tmp = BSTCreateNode(data);

            if(NULL == tmp)
            {
                printf("Error: Node insertion failed\n");
                return;
            }

            tmp->parent = ptr;
            ptr->left = tmp;
            return;
        }
        else
        {
            BSTInsert(&(ptr->left), data, cmp_fn);
        }
    }
    /*If data is equal to the current node's data*/
    else
        printf("Error: Duplicate\n");
}

/* @brief Function to find the minimum valued node in the left subtree of a node
 * @param node Pointer to the node whose min valued child in left subtree has to be found
 * @return Address of the minimum valued node in the left subtree
 */
static BSTNode* BSTMinVal(BSTNode* node)
{
    BSTNode* current = node;

  /*Go to the leftmost member of the tree */
  while (current->left != NULL)
  {
    current = current->left;
  }
  return current;
}

/* @brief Function to find the Inorder successor of a node in a BST
 * @param node Pointer to the node whose inorder successor has to be found
 * @return Address of the Inorder successor
 */
static BSTNode* BSTInorderSuccessor(BSTNode* node)
{
    BSTNode *inOrdSucc = NULL;
    if(NULL == node)
        return NULL;

    /*Traverse the right subtree and find the minimum value */
    if( node->right != NULL )
        return BSTMinVal(node->right);

    inOrdSucc = node->parent;

    while(inOrdSucc != NULL && node == inOrdSucc->right)
    {
        node = inOrdSucc;
        inOrdSucc = inOrdSucc->parent;
    }
    return inOrdSucc;

}

/* @brief Helper Function to update the parent node links in a BST
 * @param node Pointer to pointer to the node whose parent will be updated
 * @param ptr Target Link
 * @return void
 */
static inline void updateParent(BSTNode **node, BSTNode *ptr)
{
    /*If the child is a left child*/
    if(BSTFindChildLoc((*node)->parent, *node) == "LEFT")
    {
        (*node)->parent->left = ptr;
    }
    /*If the child is a right child*/
    else
    {
        (*node)->parent->right = ptr;
    }
}

/* @brief Function to delete a node in a BST
 * @param root Pointer to pointer to the root of the BST
 * @param data Pointer to the data to be searched
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return void
 */
void BSTDelete(BSTNode **root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *ptr = NULL;
    BSTNode *tmp = NULL;

    if(NULL == root)
    {
        printf("Error: Null root\n");
        return;
    }

    /*Search if the node exists in the BST*/
    ptr = BSTSearch(*root, data, cmp_fn);

    if(NULL == ptr)
    {
        printf("Error: Node not found\n");
        return;
    }

    /*If the node has no children*/
    if(ptr->left == NULL && ptr->right == NULL)
    {
        /*No children*/
         tmp = ptr;

         /*Non-Root Node*/
         if(ptr->parent)
            updateParent(&ptr, NULL);   /*Update the parent's link*/
         /*Root Node*/
         else
             *root = NULL;

         ptr = NULL;
         free(tmp);
         printf("DeAllocated Node with address %p\n", tmp);
    }
    /*If the node has single child*/
    else if((ptr->left != NULL && ptr->right == NULL) || (ptr->left == NULL && ptr->right != NULL))
    {
        tmp = ptr;

        /*Single Child*/
        if((ptr->left != NULL) && (ptr->right == NULL))
        {
            ptr->left->parent = ptr->parent;

            /*Non-Root Node*/
            if(ptr->parent)
                updateParent(&ptr, ptr->left);   /*Update the parent's link*/
            /*Root Node*/
            else
                *root = ptr->left;
        }
        else
        {
            ptr->right->parent = ptr->parent;   /*Update the parent's link*/
            /*Non-Root Node*/
            if(ptr->parent)
                updateParent(&ptr, ptr->right);
            /*Root Node*/
            else
                *root = ptr->right;
        }

        free(tmp);
        printf("DeAllocated Node with address %p\n", tmp);
    }
    /*If the node has two children*/
    else if((ptr->left != NULL) && (ptr->right != NULL))
    {
        /*Find the inorder successor of the node*/
        BSTNode *inOrdSucc = BSTInorderSuccessor(ptr);

        /*Swap the node's data with inorder successor's data*/
        BSTSwapNodeData(&ptr, &inOrdSucc);

        /*Delete the inorder successor node*/
        BSTDelete(&inOrdSucc, data, cmp_fn);
    }
}

/* @brief Function to search a data in a BST
 * @param root Pointer to the root of the BST
 * @param data Pointer to the data to be searched
 * @param cmp_fn Funtion Pointer to the comparison function for BST[Provided by user]
 * @return Address of the node found
 *         NULL if node not found
 */
BSTNode* BSTSearch(BSTNode *root, void *data, int (*cmp_fn)(void *, void *))
{
    BSTNode *ptr = NULL;

    if(NULL == root)
        return NULL;

    ptr = root;

    /*If the data is found*/
    if(cmp_fn(data, ptr->data) == 0)
    {
        return ptr;
    }
    /*If data is greater than the current node's data*/
    else if(cmp_fn(data, ptr->data) == 1)
    {
        return BSTSearch(ptr->right, data, cmp_fn);
    }
    /*If data is lesser than the current node's data*/
    else if(cmp_fn(data, ptr->data) == -1)
    {
        return BSTSearch(ptr->left, data, cmp_fn);
    }

    return NULL;
}

/* @brief Function to traverse all nodes in a BST in InOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTInOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    if(root->left)
        BSTInOrder(root->left, display_fn);

    printf("[%p]",root->data);
    display_fn(root);

    if(root->right)
        BSTInOrder(root->right, display_fn);

}

/* @brief Function to traverse all nodes in a BST in PostOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTPostOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    if(root->left)
        BSTPostOrder(root->left, display_fn);

    if(root->right)
        BSTPostOrder(root->right, display_fn);

    printf("[%p]",root->data);
    display_fn(root);
}

/* @brief Function to traverse all nodes in a BST in PreOrder
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
static void BSTPreOrder(BSTNode *root, void (*display_fn)(BSTNode *))
{
    if(NULL == root)
    {
        printf("Error: NULL root\n");
        return;
    }

    printf("[%p]",root->data);
    display_fn(root);

    if(root->left)
        BSTPreOrder(root->left, display_fn);

    if(root->right)
        BSTPreOrder(root->right, display_fn);

}

/* @brief Function to display all nodes in a BST
 * @param root Pointer to the root of the BST
 * @param display_fn Funtion Pointer to the display function for BST[Provided by user]
 * @return void
 */
void BSTDisplay(BSTNode *root, void (*display_fn)(BSTNode *))
{
    printf("InOrder ->",root->data);
    BSTInOrder(root,display_fn);
    printf("\n",root->data);

    printf("PreOrder ->",root->data);
    BSTPreOrder(root,display_fn);
    printf("\n",root->data);

    printf("PostOrder ->",root->data);
    BSTPostOrder(root,display_fn);
    printf("\n",root->data);
}

 
/*bstdriver.c*/
/*
 * Compile: gcc -o test bst.c bstdriver.c
 * Run: ./test
 */
#include <stdio.h>
#include "bst.h"

int data[]={9,1,6,3,8,4,2,5,7};

/*Comparison function*/
int cmp_fn(void *data1, void *data2)
{
    if(*((int*)data1) > *((int*)data2))
        return 1;
    else if(*((int*)data1) < *((int*)data2))
        return -1;
    else
        return 0;
}

/*Display Function*/
static void displayNode(BSTNode *node)
{
    if(node)
        printf("%d ",*((int*)node->data));
}

int main()
{
    BSTNode *root = NULL;

    int i,sVal=-1;
    int size = sizeof(data)/sizeof(data[0]);

    for(i=0; i < size; i++)
        BSTInsert(&root, &data[i], cmp_fn);

    BSTDisplay(root, displayNode);

    printf("Search Value : ");
    scanf("%d", &sVal);

    if(NULL == BSTSearch(root, &sVal, cmp_fn))
        printf("Not Found\n");
    else
        printf("Found\n");

    printf("Delete Value : ");
    scanf("%d", &sVal);
    BSTDelete(&root, &sVal, cmp_fn);
    BSTDisplay(root, displayNode);

    BSTDestroy(root);
}

FTP implementation in C

Most of the beginners would wonder how the known services work. Well this post will give an overview of one of the well-written services in C , the FTP application. I thought that there is no need to re-invent the wheel and use this code as is from Apple's open source initiative.The code is written in C.

I am providing the code only for the main file which contains FTP specific functions. The rest of the supporting files including the Makefile can be downloaded from here.

Disclaimer : This code is taken from Apple Opensource . I don't want Apple to sue me ;)

 /*ftp.c*/

/*
 * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * "Portions Copyright (c) 1999 Apple Computer, Inc.  All Rights
 * Reserved.  This file contains Original Code and/or Modifications of
 * Original Code as defined in and that are subject to the Apple Public
 * Source License Version 1.0 (the 'License').  You may not use this file
 * except in compliance with the License.  Please obtain a copy of the
 * License at http://www.apple.com/publicsource and read it before using
 * this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License."
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
 * Copyright (c) 1985, 1989, 1993, 1994
 * The Regents of the University of California.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 * This product includes software developed by the University of
 * California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */


#include <sys/param.h>
#include <sys/stat.h>
#include <sys/ioctl.h>
#include <sys/socket.h>
#include <sys/time.h>
#include <sys/file.h>

#include <netinet/in.h>
#include <netinet/in_systm.h>
#include <netinet/ip.h>
#include <arpa/inet.h>
#include <arpa/ftp.h>
#include <arpa/telnet.h>

#include <ctype.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <netdb.h>
#include <pwd.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <stdarg.h>

#include "ftp_var.h"

extern int h_errno;

struct sockaddr_in hisctladdr;
struct sockaddr_in data_addr;
int data = -1;
int abrtflag = 0;
jmp_buf ptabort;
int ptabflg;
int ptflag = 0;
struct sockaddr_in myctladdr;
off_t restart_point = 0;

FILE *cin, *cout;

char *
hookup(host, port)
 char *host;
 int port;
{
 struct hostent *hp = 0;
 int s, len, tos;
 static char hostnamebuf[80];

 memset((char *)&hisctladdr, 0, sizeof (hisctladdr));
 hisctladdr.sin_addr.s_addr = inet_addr(host);
 if (hisctladdr.sin_addr.s_addr != -1) {
  hisctladdr.sin_family = AF_INET;
  (void) strncpy(hostnamebuf, host, sizeof(hostnamebuf));
 } else {
  hp = gethostbyname(host);
  if (hp == NULL) {
   warnx("%s: %s", host, hstrerror(h_errno));
   code = -1;
   return ((char *) 0);
  }
  hisctladdr.sin_family = hp->h_addrtype;
  memmove((caddr_t)&hisctladdr.sin_addr,
    hp->h_addr_list[0], hp->h_length);
  (void) strncpy(hostnamebuf, hp->h_name, sizeof(hostnamebuf));
 }
 hostname = hostnamebuf;
 s = socket(hisctladdr.sin_family, SOCK_STREAM, 0);
 if (s < 0) {
  warn("socket");
  code = -1;
  return (0);
 }
 hisctladdr.sin_port = port;
 while (connect(s, (struct sockaddr *)&hisctladdr, sizeof (hisctladdr)) < 0) {
  if (hp && hp->h_addr_list[1]) {
   int oerrno = errno;
   char *ia;

   ia = inet_ntoa(hisctladdr.sin_addr);
   errno = oerrno;
   warn("connect to address %s", ia);
   hp->h_addr_list++;
   memmove((caddr_t)&hisctladdr.sin_addr,
     hp->h_addr_list[0], hp->h_length);
   fprintf(stdout, "Trying %s...\n",
    inet_ntoa(hisctladdr.sin_addr));
   (void) close(s);
   s = socket(hisctladdr.sin_family, SOCK_STREAM, 0);
   if (s < 0) {
    warn("socket");
    code = -1;
    return (0);
   }
   continue;
  }
  warn("connect");
  code = -1;
  goto bad;
 }
 len = sizeof (myctladdr);
 if (getsockname(s, (struct sockaddr *)&myctladdr, &len) < 0) {
  warn("getsockname");
  code = -1;
  goto bad;
 }
#ifdef IP_TOS
 tos = IPTOS_LOWDELAY;
 if (setsockopt(s, IPPROTO_IP, IP_TOS, (char *)&tos, sizeof(int)) < 0)
  warn("setsockopt TOS (ignored)");
#endif
 cin = fdopen(s, "r");
 cout = fdopen(s, "w");
 if (cin == NULL || cout == NULL) {
  warnx("fdopen failed.");
  if (cin)
   (void) fclose(cin);
  if (cout)
   (void) fclose(cout);
  code = -1;
  goto bad;
 }
 if (verbose)
  printf("Connected to %s.\n", hostname);
 if (getreply(0) > 2) {  /* read startup message from server */
  if (cin)
   (void) fclose(cin);
  if (cout)
   (void) fclose(cout);
  code = -1;
  goto bad;
 }
#ifdef SO_OOBINLINE
 {
 int on = 1;

 if (setsockopt(s, SOL_SOCKET, SO_OOBINLINE, (char *)&on, sizeof(on))
  < 0 && debug) {
   warn("setsockopt");
  }
 }
#endif /* SO_OOBINLINE */

 return (hostname);
bad:
 (void) close(s);
 return ((char *)0);
}

int
login(host)
 char *host;
{
 char tmp[80];
 char *user, *pass, *acct;
 int n, aflag = 0;

 user = pass = acct = 0;
 if (ruserpass(host, &user, &pass, &acct) < 0) {
  code = -1;
  return (0);
 }
 while (user == NULL) {
  char *myname = getlogin();

  if (myname == NULL) {
   struct passwd *pp = getpwuid(getuid());

   if (pp != NULL)
    myname = pp->pw_name;
  }
  if (myname)
   printf("Name (%s:%s): ", host, myname);
  else
   printf("Name (%s): ", host);
  (void) fgets(tmp, sizeof(tmp) - 1, stdin);
  tmp[strlen(tmp) - 1] = '\0';
  if (*tmp == '\0')
   user = myname;
  else
   user = tmp;
 }
 n = command("USER %s", user);
 if (n == CONTINUE) {
  if (pass == NULL)
   pass = getpass("Password:");
  n = command("PASS %s", pass);
 }
 if (n == CONTINUE) {
  aflag++;
  acct = getpass("Account:");
  n = command("ACCT %s", acct);
 }
 if (n != COMPLETE) {
  warnx("Login failed.");
  return (0);
 }
 if (!aflag && acct != NULL)
  (void) command("ACCT %s", acct);
 if (proxy)
  return (1);
 for (n = 0; n < macnum; ++n) {
  if (!strcmp("init", macros[n].mac_name)) {
   (void) strcpy(line, "$init");
   makeargv();
   domacro(margc, margv);
   break;
  }
 }
 return (1);
}

void
cmdabort()
{

 printf("\n");
 (void) fflush(stdout);
 abrtflag++;
 if (ptflag)
  longjmp(ptabort,1);
}

int command(const char *fmt, ...)
{
 va_list ap;
 int r;
 sig_t oldintr;

 abrtflag = 0;
 if (debug) {
  printf("---> ");
  va_start(ap, fmt);
  if (strncmp("PASS ", fmt, 5) == 0)
   printf("PASS XXXX");
  else 
   vfprintf(stdout, fmt, ap);
  va_end(ap);
  printf("\n");
  (void) fflush(stdout);
 }
 if (cout == NULL) {
  warn("No control connection for command");
  code = -1;
  return (0);
 }
 oldintr = signal(SIGINT, cmdabort);
 va_start(ap, fmt);
 vfprintf(cout, fmt, ap);
 va_end(ap);
 fprintf(cout, "\r\n");
 (void) fflush(cout);
 cpend = 1;
 r = getreply(!strcmp(fmt, "QUIT"));
 if (abrtflag && oldintr != SIG_IGN)
  (*oldintr)(SIGINT);
 (void) signal(SIGINT, oldintr);
 return (r);
}

char reply_string[BUFSIZ];  /* last line of previous reply */

int
getreply(expecteof)
 int expecteof;
{
 int c, n;
 int dig;
 int originalcode = 0, continuation = 0;
 sig_t oldintr;
 int pflag = 0;
 char *cp, *pt = pasv;

 oldintr = signal(SIGINT, cmdabort);
 for (;;) {
  dig = n = code = 0;
  cp = reply_string;
  while ((c = getc(cin)) != '\n') {
   if (c == IAC) {     /* handle telnet commands */
    switch (c = getc(cin)) {
    case WILL:
    case WONT:
     c = getc(cin);
     fprintf(cout, "%c%c%c", IAC, DONT, c);
     (void) fflush(cout);
     break;
    case DO:
    case DONT:
     c = getc(cin);
     fprintf(cout, "%c%c%c", IAC, WONT, c);
     (void) fflush(cout);
     break;
    default:
     break;
    }
    continue;
   }
   dig++;
   if (c == EOF) {
    if (expecteof) {
     (void) signal(SIGINT,oldintr);
     code = 221;
     return (0);
    }
    lostpeer();
    if (verbose) {
     printf("421 Service not available, remote server has closed connection\n");
     (void) fflush(stdout);
    }
    code = 421;
    return (4);
   }
   if (c != '\r' && (verbose > 0 ||
       (verbose > -1 && n == '5' && dig > 4))) {
    if (proxflag &&
       (dig == 1 || dig == 5 && verbose == 0))
     printf("%s:",hostname);
    (void) putchar(c);
   }
   if (dig < 4 && isdigit(c))
    code = code * 10 + (c - '0');
   if (!pflag && code == 227)
    pflag = 1;
   if (dig > 4 && pflag == 1 && isdigit(c))
    pflag = 2;
   if (pflag == 2) {
    if (c != '\r' && c != ')')
     *pt++ = c;
    else {
     *pt = '\0';
     pflag = 3;
    }
   }
   if (dig == 4 && c == '-') {
    if (continuation)
     code = 0;
    continuation++;
   }
   if (n == 0)
    n = c;
   if (cp < &reply_string[sizeof(reply_string) - 1])
    *cp++ = c;
  }
  if (verbose > 0 || verbose > -1 && n == '5') {
   (void) putchar(c);
   (void) fflush (stdout);
  }
  if (continuation && code != originalcode) {
   if (originalcode == 0)
    originalcode = code;
   continue;
  }
  *cp = '\0';
  if (n != '1')
   cpend = 0;
  (void) signal(SIGINT,oldintr);
  if (code == 421 || originalcode == 421)
   lostpeer();
  if (abrtflag && oldintr != cmdabort && oldintr != SIG_IGN)
   (*oldintr)(SIGINT);
  return (n - '0');
 }
}

int
empty(mask, sec)
 struct fd_set *mask;
 int sec;
{
 struct timeval t;

 t.tv_sec = (long) sec;
 t.tv_usec = 0;
 return (select(32, mask, (struct fd_set *) 0, (struct fd_set *) 0, &t));
}

jmp_buf sendabort;

void
abortsend()
{

 mflag = 0;
 abrtflag = 0;
 printf("\nsend aborted\nwaiting for remote to finish abort\n");
 (void) fflush(stdout);
 longjmp(sendabort, 1);
}

#define HASHBYTES 1024

void
sendrequest(cmd, local, remote, printnames)
 char *cmd, *local, *remote;
 int printnames;
{
 struct stat st;
 struct timeval start, stop;
 int c, d;
 FILE *fin, *dout = 0, *popen();
 int (*closefunc) __P((FILE *));
 sig_t oldintr, oldintp;
 long bytes = 0, hashbytes = HASHBYTES;
 char *lmode, buf[BUFSIZ], *bufp;

 if (verbose && printnames) {
  if (local && *local != '-')
   printf("local: %s ", local);
  if (remote)
   printf("remote: %s\n", remote);
 }
 if (proxy) {
  proxtrans(cmd, local, remote);
  return;
 }
 if (curtype != type)
  changetype(type, 0);
 closefunc = NULL;
 oldintr = NULL;
 oldintp = NULL;
 lmode = "w";
 if (setjmp(sendabort)) {
  while (cpend) {
   (void) getreply(0);
  }
  if (data >= 0) {
   (void) close(data);
   data = -1;
  }
  if (oldintr)
   (void) signal(SIGINT,oldintr);
  if (oldintp)
   (void) signal(SIGPIPE,oldintp);
  code = -1;
  return;
 }
 oldintr = signal(SIGINT, abortsend);
 if (strcmp(local, "-") == 0)
  fin = stdin;
 else if (*local == '|') {
  oldintp = signal(SIGPIPE,SIG_IGN);
  fin = popen(local + 1, "r");
  if (fin == NULL) {
   warn("%s", local + 1);
   (void) signal(SIGINT, oldintr);
   (void) signal(SIGPIPE, oldintp);
   code = -1;
   return;
  }
  closefunc = pclose;
 } else {
  fin = fopen(local, "r");
  if (fin == NULL) {
   warn("local: %s", local);
   (void) signal(SIGINT, oldintr);
   code = -1;
   return;
  }
  closefunc = fclose;
  if (fstat(fileno(fin), &st) < 0 ||
      (st.st_mode&S_IFMT) != S_IFREG) {
   fprintf(stdout, "%s: not a plain file.\n", local);
   (void) signal(SIGINT, oldintr);
   fclose(fin);
   code = -1;
   return;
  }
 }
 if (initconn()) {
  (void) signal(SIGINT, oldintr);
  if (oldintp)
   (void) signal(SIGPIPE, oldintp);
  code = -1;
  if (closefunc != NULL)
   (*closefunc)(fin);
  return;
 }
 if (setjmp(sendabort))
  goto abort;

 if (restart_point &&
     (strcmp(cmd, "STOR") == 0 || strcmp(cmd, "APPE") == 0)) {
  int rc;

  switch (curtype) {
  case TYPE_A:
   rc = fseek(fin, (long) restart_point, SEEK_SET);
   break;
  case TYPE_I:
  case TYPE_L:
   rc = lseek(fileno(fin), restart_point, SEEK_SET);
   break;
  }
  if (rc < 0) {
   warn("local: %s", local);
   restart_point = 0;
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
  if (command("REST %ld", (long) restart_point)
   != CONTINUE) {
   restart_point = 0;
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
  restart_point = 0;
  lmode = "r+w";
 }
 if (remote) {
  if (command("%s %s", cmd, remote) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   if (oldintp)
    (void) signal(SIGPIPE, oldintp);
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
 } else
  if (command("%s", cmd) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   if (oldintp)
    (void) signal(SIGPIPE, oldintp);
   if (closefunc != NULL)
    (*closefunc)(fin);
   return;
  }
 dout = dataconn(lmode);
 if (dout == NULL)
  goto abort;
 (void) gettimeofday(&start, (struct timezone *)0);
 oldintp = signal(SIGPIPE, SIG_IGN);
 switch (curtype) {

 case TYPE_I:
 case TYPE_L:
  errno = d = 0;
  while ((c = read(fileno(fin), buf, sizeof (buf))) > 0) {
   bytes += c;
   for (bufp = buf; c > 0; c -= d, bufp += d)
    if ((d = write(fileno(dout), bufp, c)) <= 0)
     break;
   if (hash) {
    while (bytes >= hashbytes) {
     (void) putchar('#');
     hashbytes += HASHBYTES;
    }
    (void) fflush(stdout);
   }
  }
  if (hash && bytes > 0) {
   if (bytes < HASHBYTES)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (c < 0)
   warn("local: %s", local);
  if (d < 0) {
   if (errno != EPIPE) 
    warn("netout");
   bytes = -1;
  }
  break;

 case TYPE_A:
  while ((c = getc(fin)) != EOF) {
   if (c == '\n') {
    while (hash && (bytes >= hashbytes)) {
     (void) putchar('#');
     (void) fflush(stdout);
     hashbytes += HASHBYTES;
    }
    if (ferror(dout))
     break;
    (void) putc('\r', dout);
    bytes++;
   }
   (void) putc(c, dout);
   bytes++;
 /*  if (c == '\r') {      */
 /*  (void) putc('\0', dout);  // this violates rfc */
 /*   bytes++;    */
 /*  }                             */ 
  }
  if (hash) {
   if (bytes < hashbytes)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (ferror(fin))
   warn("local: %s", local);
  if (ferror(dout)) {
   if (errno != EPIPE)
    warn("netout");
   bytes = -1;
  }
  break;
 }
 if (closefunc != NULL)
  (*closefunc)(fin);
 (void) fclose(dout);
 (void) gettimeofday(&stop, (struct timezone *)0);
 (void) getreply(0);
 (void) signal(SIGINT, oldintr);
 if (oldintp)
  (void) signal(SIGPIPE, oldintp);
 if (bytes > 0)
  ptransfer("sent", bytes, &start, &stop);
 return;
abort:
 (void) signal(SIGINT, oldintr);
 if (oldintp)
  (void) signal(SIGPIPE, oldintp);
 if (!cpend) {
  code = -1;
  return;
 }
 if (data >= 0) {
  (void) close(data);
  data = -1;
 }
 if (dout)
  (void) fclose(dout);
 (void) getreply(0);
 code = -1;
 if (closefunc != NULL && fin != NULL)
  (*closefunc)(fin);
 (void) gettimeofday(&stop, (struct timezone *)0);
 if (bytes > 0)
  ptransfer("sent", bytes, &start, &stop);
}

jmp_buf recvabort;

void
abortrecv()
{

 mflag = 0;
 abrtflag = 0;
 printf("\nreceive aborted\nwaiting for remote to finish abort\n");
 (void) fflush(stdout);
 longjmp(recvabort, 1);
}

void
recvrequest(cmd, local, remote, lmode, printnames)
 char *cmd, *local, *remote, *lmode;
 int printnames;
{
 FILE *fout, *din = 0;
 int (*closefunc) __P((FILE *));
 sig_t oldintr, oldintp;
 int c, d, is_retr, tcrflag, bare_lfs = 0;
 static int bufsize;
 static char *buf;
 long bytes = 0, hashbytes = HASHBYTES;
 struct timeval start, stop;
 struct stat st;

 is_retr = strcmp(cmd, "RETR") == 0;
 if (is_retr && verbose && printnames) {
  if (local && *local != '-')
   printf("local: %s ", local);
  if (remote)
   printf("remote: %s\n", remote);
 }
 if (proxy && is_retr) {
  proxtrans(cmd, local, remote);
  return;
 }
 closefunc = NULL;
 oldintr = NULL;
 oldintp = NULL;
 tcrflag = !crflag && is_retr;
 if (setjmp(recvabort)) {
  while (cpend) {
   (void) getreply(0);
  }
  if (data >= 0) {
   (void) close(data);
   data = -1;
  }
  if (oldintr)
   (void) signal(SIGINT, oldintr);
  code = -1;
  return;
 }
 oldintr = signal(SIGINT, abortrecv);
 if (strcmp(local, "-") && *local != '|') {
  if (access(local, 2) < 0) {
   char *dir = strrchr(local, '/');

   if (errno != ENOENT && errno != EACCES) {
    warn("local: %s", local);
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
   if (dir != NULL)
    *dir = 0;
   d = access(dir ? local : ".", 2);
   if (dir != NULL)
    *dir = '/';
   if (d < 0) {
    warn("local: %s", local);
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
   if (!runique && errno == EACCES &&
       chmod(local, 0600) < 0) {
    warn("local: %s", local);
    (void) signal(SIGINT, oldintr);
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
   if (runique && errno == EACCES &&
      (local = gunique(local)) == NULL) {
    (void) signal(SIGINT, oldintr);
    code = -1;
    return;
   }
  }
  else if (runique && (local = gunique(local)) == NULL) {
   (void) signal(SIGINT, oldintr);
   code = -1;
   return;
  }
 }
 if (!is_retr) {
  if (curtype != TYPE_A)
   changetype(TYPE_A, 0);
 } else if (curtype != type)
  changetype(type, 0);
 if (initconn()) {
  (void) signal(SIGINT, oldintr);
  code = -1;
  return;
 }
 if (setjmp(recvabort))
  goto abort;
 if (is_retr && restart_point &&
     command("REST %ld", (long) restart_point) != CONTINUE)
  return;
 if (remote) {
  if (command("%s %s", cmd, remote) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   return;
  }
 } else {
  if (command("%s", cmd) != PRELIM) {
   (void) signal(SIGINT, oldintr);
   return;
  }
 }
 din = dataconn("r");
 if (din == NULL)
  goto abort;
 if (strcmp(local, "-") == 0)
  fout = stdout;
 else if (*local == '|') {
  oldintp = signal(SIGPIPE, SIG_IGN);
  fout = popen(local + 1, "w");
  if (fout == NULL) {
   warn("%s", local+1);
   goto abort;
  }
  closefunc = pclose;
 } else {
  fout = fopen(local, lmode);
  if (fout == NULL) {
   warn("local: %s", local);
   goto abort;
  }
  closefunc = fclose;
 }
 if (fstat(fileno(fout), &st) < 0 || st.st_blksize == 0)
  st.st_blksize = BUFSIZ;
 if (st.st_blksize > bufsize) {
  if (buf)
   (void) free(buf);
  buf = malloc((unsigned)st.st_blksize);
  if (buf == NULL) {
   warn("malloc");
   bufsize = 0;
   goto abort;
  }
  bufsize = st.st_blksize;
 }
 (void) gettimeofday(&start, (struct timezone *)0);
 switch (curtype) {

 case TYPE_I:
 case TYPE_L:
  if (restart_point &&
      lseek(fileno(fout), restart_point, SEEK_SET) < 0) {
   warn("local: %s", local);
   if (closefunc != NULL)
    (*closefunc)(fout);
   return;
  }
  errno = d = 0;
  while ((c = read(fileno(din), buf, bufsize)) > 0) {
   if ((d = write(fileno(fout), buf, c)) != c)
    break;
   bytes += c;
   if (hash) {
    while (bytes >= hashbytes) {
     (void) putchar('#');
     hashbytes += HASHBYTES;
    }
    (void) fflush(stdout);
   }
  }
  if (hash && bytes > 0) {
   if (bytes < HASHBYTES)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (c < 0) {
   if (errno != EPIPE)
    warn("netin");
   bytes = -1;
  }
  if (d < c) {
   if (d < 0)
    warn("local: %s", local);
   else
    warnx("%s: short write", local);
  }
  break;

 case TYPE_A:
  if (restart_point) {
   int i, n, ch;

   if (fseek(fout, 0L, SEEK_SET) < 0)
    goto done;
   n = restart_point;
   for (i = 0; i++ < n;) {
    if ((ch = getc(fout)) == EOF)
     goto done;
    if (ch == '\n')
     i++;
   }
   if (fseek(fout, 0L, SEEK_CUR) < 0) {
done:
    warn("local: %s", local);
    if (closefunc != NULL)
     (*closefunc)(fout);
    return;
   }
  }
  while ((c = getc(din)) != EOF) {
   if (c == '\n')
    bare_lfs++;
   while (c == '\r') {
    while (hash && (bytes >= hashbytes)) {
     (void) putchar('#');
     (void) fflush(stdout);
     hashbytes += HASHBYTES;
    }
    bytes++;
    if ((c = getc(din)) != '\n' || tcrflag) {
     if (ferror(fout))
      goto break2;
     (void) putc('\r', fout);
     if (c == '\0') {
      bytes++;
      goto contin2;
     }
     if (c == EOF)
      goto contin2;
    }
   }
   (void) putc(c, fout);
   bytes++;
 contin2: ;
  }
break2:
  if (bare_lfs) {
   printf("WARNING! %d bare linefeeds received in ASCII mode\n", bare_lfs);
   printf("File may not have transferred correctly.\n");
  }
  if (hash) {
   if (bytes < hashbytes)
    (void) putchar('#');
   (void) putchar('\n');
   (void) fflush(stdout);
  }
  if (ferror(din)) {
   if (errno != EPIPE)
    warn("netin");
   bytes = -1;
  }
  if (ferror(fout))
   warn("local: %s", local);
  break;
 }
 if (closefunc != NULL)
  (*closefunc)(fout);
 (void) signal(SIGINT, oldintr);
 if (oldintp)
  (void) signal(SIGPIPE, oldintp);
 (void) fclose(din);
 (void) gettimeofday(&stop, (struct timezone *)0);
 (void) getreply(0);
 if (bytes > 0 && is_retr)
  ptransfer("received", bytes, &start, &stop);
 return;
abort:

/* abort using RFC959 recommended IP,SYNC sequence  */

 if (oldintp)
  (void) signal(SIGPIPE, oldintr);
 (void) signal(SIGINT, SIG_IGN);
 if (!cpend) {
  code = -1;
  (void) signal(SIGINT, oldintr);
  return;
 }

 abort_remote(din);
 code = -1;
 if (data >= 0) {
  (void) close(data);
  data = -1;
 }
 if (closefunc != NULL && fout != NULL)
  (*closefunc)(fout);
 if (din)
  (void) fclose(din);
 (void) gettimeofday(&stop, (struct timezone *)0);
 if (bytes > 0)
  ptransfer("received", bytes, &start, &stop);
 (void) signal(SIGINT, oldintr);
}

/*
 * Need to start a listen on the data channel before we send the command,
 * otherwise the server's connect may fail.
 */
int
initconn()
{
 char *p, *a;
 int result, len, tmpno = 0;
 int on = 1;
 int a0, a1, a2, a3, p0, p1;

 if (passivemode) {
  data = socket(AF_INET, SOCK_STREAM, 0);
  if (data < 0) {
   perror("ftp: socket");
   return(1);
  }
  if ((options & SO_DEBUG) &&
      setsockopt(data, SOL_SOCKET, SO_DEBUG, (char *)&on,
          sizeof (on)) < 0)
   perror("ftp: setsockopt (ignored)");
  if (command("PASV") != COMPLETE) {
   printf("Passive mode refused.\n");
   goto bad;
  }

  /*
   * What we've got at this point is a string of comma
   * separated one-byte unsigned integer values.
   * The first four are the an IP address. The fifth is
   * the MSB of the port number, the sixth is the LSB.
   * From that we'll prepare a sockaddr_in.
   */

  if (sscanf(pasv,"%d,%d,%d,%d,%d,%d",
      &a0, &a1, &a2, &a3, &p0, &p1) != 6) {
   printf("Passive mode address scan failure. "
          "Shouldn't happen!\n");
   goto bad;
  }

  bzero(&data_addr, sizeof(data_addr));
  data_addr.sin_family = AF_INET;
  a = (char *)&data_addr.sin_addr.s_addr;
  a[0] = a0 & 0xff;
  a[1] = a1 & 0xff;
  a[2] = a2 & 0xff;
  a[3] = a3 & 0xff;
  p = (char *)&data_addr.sin_port;
  p[0] = p0 & 0xff;
  p[1] = p1 & 0xff;

  if (connect(data, (struct sockaddr *)&data_addr,
       sizeof(data_addr)) < 0) {
   perror("ftp: connect");
   goto bad;
  }
#ifdef IP_TOS
  on = IPTOS_THROUGHPUT;
  if (setsockopt(data, IPPROTO_IP, IP_TOS, (char *)&on,
          sizeof(int)) < 0)
   perror("ftp: setsockopt TOS (ignored)");
#endif
  return(0);
 }

noport:
 data_addr = myctladdr;
 if (sendport)
  data_addr.sin_port = 0; /* let system pick one */ 
 if (data != -1)
  (void) close(data);
 data = socket(AF_INET, SOCK_STREAM, 0);
 if (data < 0) {
  warn("socket");
  if (tmpno)
   sendport = 1;
  return (1);
 }
 if (!sendport)
  if (setsockopt(data, SOL_SOCKET, SO_REUSEADDR, (char *)&on, sizeof (on)) < 0) {
   warn("setsockopt (reuse address)");
   goto bad;
  }
 if (bind(data, (struct sockaddr *)&data_addr, sizeof (data_addr)) < 0) {
  warn("bind");
  goto bad;
 }
 if (options & SO_DEBUG &&
     setsockopt(data, SOL_SOCKET, SO_DEBUG, (char *)&on, sizeof (on)) < 0)
  warn("setsockopt (ignored)");
 len = sizeof (data_addr);
 if (getsockname(data, (struct sockaddr *)&data_addr, &len) < 0) {
  warn("getsockname");
  goto bad;
 }
 if (listen(data, 1) < 0)
  warn("listen");
 if (sendport) {
  a = (char *)&data_addr.sin_addr;
  p = (char *)&data_addr.sin_port;
#define UC(b) (((int)b)&0xff)
  result =
      command("PORT %d,%d,%d,%d,%d,%d",
        UC(a[0]), UC(a[1]), UC(a[2]), UC(a[3]),
        UC(p[0]), UC(p[1]));
  if (result == ERROR && sendport == -1) {
   sendport = 0;
   tmpno = 1;
   goto noport;
  }
  return (result != COMPLETE);
 }
 if (tmpno)
  sendport = 1;
#ifdef IP_TOS
 on = IPTOS_THROUGHPUT;
 if (setsockopt(data, IPPROTO_IP, IP_TOS, (char *)&on, sizeof(int)) < 0)
  warn("setsockopt TOS (ignored)");
#endif
 return (0);
bad:
 (void) close(data), data = -1;
 if (tmpno)
  sendport = 1;
 return (1);
}

FILE *
dataconn(lmode)
 char *lmode;
{
 struct sockaddr_in from;
 int s, fromlen = sizeof (from), tos;

 if (passivemode)
  return (fdopen(data, lmode));

 s = accept(data, (struct sockaddr *) &from, &fromlen);
 if (s < 0) {
  warn("accept");
  (void) close(data), data = -1;
  return (NULL);
 }
 (void) close(data);
 data = s;
#ifdef IP_TOS
 tos = IPTOS_THROUGHPUT;
 if (setsockopt(s, IPPROTO_IP, IP_TOS, (char *)&tos, sizeof(int)) < 0)
  warn("setsockopt TOS (ignored)");
#endif
 return (fdopen(data, lmode));
}

void
ptransfer(direction, bytes, t0, t1)
 char *direction;
 long bytes;
 struct timeval *t0, *t1;
{
 struct timeval td;
 float s;
 long bs;

 if (verbose) {
  tvsub(&td, t1, t0);
  s = td.tv_sec + (td.tv_usec / 1000000.);
#define nz(x) ((x) == 0 ? 1 : (x))
  bs = bytes / nz(s);
  printf("%ld bytes %s in %.3g seconds (%ld bytes/s)\n",
      bytes, direction, s, bs);
 }
}

/*
void
tvadd(tsum, t0)
 struct timeval *tsum, *t0;
{

 tsum->tv_sec += t0->tv_sec;
 tsum->tv_usec += t0->tv_usec;
 if (tsum->tv_usec > 1000000)
  tsum->tv_sec++, tsum->tv_usec -= 1000000;
}
*/

void
tvsub(tdiff, t1, t0)
 struct timeval *tdiff, *t1, *t0;
{

 tdiff->tv_sec = t1->tv_sec - t0->tv_sec;
 tdiff->tv_usec = t1->tv_usec - t0->tv_usec;
 if (tdiff->tv_usec < 0)
  tdiff->tv_sec--, tdiff->tv_usec += 1000000;
}

void
psabort()
{

 abrtflag++;
}

void
pswitch(flag)
 int flag;
{
 sig_t oldintr;
 static struct comvars {
  int connect;
  char name[MAXHOSTNAMELEN];
  struct sockaddr_in mctl;
  struct sockaddr_in hctl;
  FILE *in;
  FILE *out;
  int tpe;
  int curtpe;
  int cpnd;
  int sunqe;
  int runqe;
  int mcse;
  int ntflg;
  char nti[17];
  char nto[17];
  int mapflg;
  char mi[MAXPATHLEN];
  char mo[MAXPATHLEN];
 } proxstruct, tmpstruct;
 struct comvars *ip, *op;

 abrtflag = 0;
 oldintr = signal(SIGINT, psabort);
 if (flag) {
  if (proxy)
   return;
  ip = &tmpstruct;
  op = &proxstruct;
  proxy++;
 } else {
  if (!proxy)
   return;
  ip = &proxstruct;
  op = &tmpstruct;
  proxy = 0;
 }
 ip->connect = connected;
 connected = op->connect;
 if (hostname) {
  (void) strncpy(ip->name, hostname, sizeof(ip->name) - 1);
  ip->name[strlen(ip->name)] = '\0';
 } else
  ip->name[0] = 0;
 hostname = op->name;
 ip->hctl = hisctladdr;
 hisctladdr = op->hctl;
 ip->mctl = myctladdr;
 myctladdr = op->mctl;
 ip->in = cin;
 cin = op->in;
 ip->out = cout;
 cout = op->out;
 ip->tpe = type;
 type = op->tpe;
 ip->curtpe = curtype;
 curtype = op->curtpe;
 ip->cpnd = cpend;
 cpend = op->cpnd;
 ip->sunqe = sunique;
 sunique = op->sunqe;
 ip->runqe = runique;
 runique = op->runqe;
 ip->mcse = mcase;
 mcase = op->mcse;
 ip->ntflg = ntflag;
 ntflag = op->ntflg;
 (void) strncpy(ip->nti, ntin, 16);
 (ip->nti)[strlen(ip->nti)] = '\0';
 (void) strcpy(ntin, op->nti);
 (void) strncpy(ip->nto, ntout, 16);
 (ip->nto)[strlen(ip->nto)] = '\0';
 (void) strcpy(ntout, op->nto);
 ip->mapflg = mapflag;
 mapflag = op->mapflg;
 (void) strncpy(ip->mi, mapin, MAXPATHLEN - 1);
 (ip->mi)[strlen(ip->mi)] = '\0';
 (void) strcpy(mapin, op->mi);
 (void) strncpy(ip->mo, mapout, MAXPATHLEN - 1);
 (ip->mo)[strlen(ip->mo)] = '\0';
 (void) strcpy(mapout, op->mo);
 (void) signal(SIGINT, oldintr);
 if (abrtflag) {
  abrtflag = 0;
  (*oldintr)(SIGINT);
 }
}

void
abortpt()
{

 printf("\n");
 (void) fflush(stdout);
 ptabflg++;
 mflag = 0;
 abrtflag = 0;
 longjmp(ptabort, 1);
}

void
proxtrans(cmd, local, remote)
 char *cmd, *local, *remote;
{
 sig_t oldintr;
 int secndflag = 0, prox_type, nfnd;
 char *cmd2;
 struct fd_set mask;

 if (strcmp(cmd, "RETR"))
  cmd2 = "RETR";
 else
  cmd2 = runique ? "STOU" : "STOR";
 if ((prox_type = type) == 0) {
  if (unix_server && unix_proxy)
   prox_type = TYPE_I;
  else
   prox_type = TYPE_A;
 }
 if (curtype != prox_type)
  changetype(prox_type, 1);
 if (command("PASV") != COMPLETE) {
  printf("proxy server does not support third party transfers.\n");
  return;
 }
 pswitch(0);
 if (!connected) {
  printf("No primary connection\n");
  pswitch(1);
  code = -1;
  return;
 }
 if (curtype != prox_type)
  changetype(prox_type, 1);
 if (command("PORT %s", pasv) != COMPLETE) {
  pswitch(1);
  return;
 }
 if (setjmp(ptabort))
  goto abort;
 oldintr = signal(SIGINT, abortpt);
 if (command("%s %s", cmd, remote) != PRELIM) {
  (void) signal(SIGINT, oldintr);
  pswitch(1);
  return;
 }
 sleep(2);
 pswitch(1);
 secndflag++;
 if (command("%s %s", cmd2, local) != PRELIM)
  goto abort;
 ptflag++;
 (void) getreply(0);
 pswitch(0);
 (void) getreply(0);
 (void) signal(SIGINT, oldintr);
 pswitch(1);
 ptflag = 0;
 printf("local: %s remote: %s\n", local, remote);
 return;
abort:
 (void) signal(SIGINT, SIG_IGN);
 ptflag = 0;
 if (strcmp(cmd, "RETR") && !proxy)
  pswitch(1);
 else if (!strcmp(cmd, "RETR") && proxy)
  pswitch(0);
 if (!cpend && !secndflag) {  /* only here if cmd = "STOR" (proxy=1) */
  if (command("%s %s", cmd2, local) != PRELIM) {
   pswitch(0);
   if (cpend)
    abort_remote((FILE *) NULL);
  }
  pswitch(1);
  if (ptabflg)
   code = -1;
  (void) signal(SIGINT, oldintr);
  return;
 }
 if (cpend)
  abort_remote((FILE *) NULL);
 pswitch(!proxy);
 if (!cpend && !secndflag) {  /* only if cmd = "RETR" (proxy=1) */
  if (command("%s %s", cmd2, local) != PRELIM) {
   pswitch(0);
   if (cpend)
    abort_remote((FILE *) NULL);
   pswitch(1);
   if (ptabflg)
    code = -1;
   (void) signal(SIGINT, oldintr);
   return;
  }
 }
 if (cpend)
  abort_remote((FILE *) NULL);
 pswitch(!proxy);
 if (cpend) {
  FD_ZERO(&mask);
  FD_SET(fileno(cin), &mask);
  if ((nfnd = empty(&mask, 10)) <= 0) {
   if (nfnd < 0) {
    warn("abort");
   }
   if (ptabflg)
    code = -1;
   lostpeer();
  }
  (void) getreply(0);
  (void) getreply(0);
 }
 if (proxy)
  pswitch(0);
 pswitch(1);
 if (ptabflg)
  code = -1;
 (void) signal(SIGINT, oldintr);
}

void
reset(argc, argv)
 int argc;
 char *argv[];
{
 struct fd_set mask;
 int nfnd = 1;

 FD_ZERO(&mask);
 while (nfnd > 0) {
  FD_SET(fileno(cin), &mask);
  if ((nfnd = empty(&mask,0)) < 0) {
   warn("reset");
   code = -1;
   lostpeer();
  }
  else if (nfnd) {
   (void) getreply(0);
  }
 }
}

char *
gunique(local)
 char *local;
{
 static char new[MAXPATHLEN];
 char *cp = strrchr(local, '/');
 int d, count=0;
 char ext = '1';

 if (cp)
  *cp = '\0';
 d = access(cp ? local : ".", 2);
 if (cp)
  *cp = '/';
 if (d < 0) {
  warn("local: %s", local);
  return ((char *) 0);
 }
 (void) strcpy(new, local);
 cp = new + strlen(new);
 *cp++ = '.';
 while (!d) {
  if (++count == 100) {
   printf("runique: can't find unique file name.\n");
   return ((char *) 0);
  }
  *cp++ = ext;
  *cp = '\0';
  if (ext == '9')
   ext = '0';
  else
   ext++;
  if ((d = access(new, 0)) < 0)
   break;
  if (ext != '0')
   cp--;
  else if (*(cp - 2) == '.')
   *(cp - 1) = '1';
  else {
   *(cp - 2) = *(cp - 2) + 1;
   cp--;
  }
 }
 return (new);
}

void
abort_remote(din)
 FILE *din;
{
 char buf[BUFSIZ];
 int nfnd;
 struct fd_set mask;

 /*
  * send IAC in urgent mode instead of DM because 4.3BSD places oob mark
  * after urgent byte rather than before as is protocol now
  */
 sprintf(buf, "%c%c%c", IAC, IP, IAC);
 if (send(fileno(cout), buf, 3, MSG_OOB) != 3)
  warn("abort");
 fprintf(cout,"%cABOR\r\n", DM);
 (void) fflush(cout);
 FD_ZERO(&mask);
 FD_SET(fileno(cin), &mask);
 if (din) { 
  FD_SET(fileno(din), &mask);
 }
 if ((nfnd = empty(&mask, 10)) <= 0) {
  if (nfnd < 0) {
   warn("abort");
  }
  if (ptabflg)
   code = -1;
  lostpeer();
 }
 if (din && FD_ISSET(fileno(din), &mask)) {
  while (read(fileno(din), buf, BUFSIZ) > 0)
   /* LOOP */;
 }
 if (getreply(0) == ERROR && code == 552) {
  /* 552 needed for nic style abort */
  (void) getreply(0);
 }
 (void) getreply(0);
}

SSC Combined Graduate Level Examination 2012 Admit Card

This would be helpful to those candidates who are having trouble finding their Admit Card for  SSC Combined Graduate Level Examination 2012.

Please visit your local(state) SSC website and download the list of eligible candidates from there.
You can find your Roll No. Enlisted there and then it could be used to retrieve the Admit Card from the same site.

For Example, In Karntaka roll no. can be found using following steps:

1. Visit http://www.ssckkr.kar.nic.in/
2. On the homepage find the link
1.'"Click here to see the Roll NO. of the list of the provisionally eligible candidates for Combined Graduate Level Exam, 2012".
3. Then try to search your name in the list.
4. Then visit the link 1.Download Duplicate Admission Certificates for Combined Graduate Level EXAMINATION 2012 scheduled to be held on 01.07.2012
5. Enter your roll no. there and download your admit card.

This steps is valid for Karnataka State Candidates, It might be valid for other states too but somebody will have to check.

These are sites for various regions

SSC Northern Region Delhi (SSCNR)

SSC North Western Region Chandigarh

SSC Central Region (SSCCR) Allahabad

SSC Eastern Region Kolkata (SSCER)

SSC North Eastern Region (SSCNER) Guwahati

SSC Madhya Pradesh Region (SSCMPR)

SSC Southern Region (SSCSR) (Forenoon) || (Afternoon)

SSC Western Region (SSCWR) Maharashtra

SSC Kerala, Karnataka Region (SSCKKR)

 

Whereever you have filled the centre of examination , that will be you region

 

libconfig to read configuration files in C/C++

There are so many open-source libraries already available for parsing configuration files in c/c++ , but still we there are some which make their place up than rest of the others. One such library is libconfig . The reason being its simplicity and much lesser memory footprint. Most of the library for configuration files are XML based , but this library is text based and the structure of the configuration files is pretty simple.
e.g. In its simplest form a configuration file can look like :

port = 5000;

It can provide even more simpler configuration file for much complex data group. For example :

books = ( "inventory",
          { title  = "Treasure Island";
            author = "Robert Louis Stevenson";
            price  = 29.99;
            qty    = 5; },
          { title  = "Snow Crash";
            author = "Neal Stephenson";
            price  = 9.99;
            qty    = 8; }, 

{ } );

Here there is a set of data for the inventory of books with multiple fields for each book.

One of the most important feature of this library is that it supports a fully re-entrant parser which means that different configurations can be parsed in concurrent threads at the same time. Moreover the APIs are available for both C and C++ languages and there are hooks provided in the library to facilitate its use in other programming languages too.


The detailed documentation of this library can be found at Libconfig Manual. It supports multiple platforms such as Windows, Linux , Mac OS X and Solaris (POSIX compliant platforms).

To use it in a C/C++ program one just needs to add a single preprocessor directive

#include <libconfig.h>      /*For C*/  

#include <libconfig.h++>    /*For C++*/

For dynamic linking -lconfig/-lconfig++ must be used for C/C++ respectively. Otherwise the libraries can be statically linked using the static linking option during the compilation. 


e.g. ( -static $(LIBPTHREAD_INSTALL_DIR)/libpthread.a) 


Issues as per the libconfig website: 

• Libconfig is fully reentrant; the functions in the library do not make use of global variables and do not maintain state between successive calls. Therefore two independent configurations may be safely manipulated concurrently by two distinct threads.
• Libconfig is not thread-safe. The library is not aware of the presence of threads and knows nothing about the host system's threading model. Therefore, if an instance of a configuration is to be accessed from multiple threads, it must be suitably protected by synchronization mechanisms like read-write locks or mutexes; the standard rules for safe multithreaded access to shared data must be observed.
• Libconfig is not async-safe. Calls should not be made into the library from signal handlers, because some of the C library routines that it uses may not be async-safe.
• Libconfig is not guaranteed to be cancel-safe. Since it is not aware of the host system's threading model, the library does not contain any thread cancellation points. In most cases this will not be an issue for multithreaded programs. However, be aware that some of the routines in the library (namely those that read/write configurations from/to files or streams) perform I/O using C library routines which may potentially block; whether or not these C library routines are cancel-safe depends on the host system.

We will provide a simple example of how to read from a configuration file using libconfig:

 
/*config.c*/
/*
To compile : gcc -o config config.c -lconfig
To run     : ./config
*/
#include 
#include 

int main()
{
    config_t cfg;               /*Returns all parameters in this structure */
    config_setting_t *setting;
    const char *str1, *str2;
    int tmp;

    char *config_file_name = "config.txt";

    /*Initialization */
    config_init(&cfg);

    /* Read the file. If there is an error, report it and exit. */
    if (!config_read_file(&cfg, config_file_name))
    {
        printf("\n%s:%d - %s", config_error_file(&cfg), config_error_line(&cfg), config_error_text(&cfg));
        config_destroy(&cfg);
        return -1;
    }

    /* Get the configuration file name. */
    if (config_lookup_string(&cfg, "filename", &str1))
        printf("\nFile Type: %s", str1);
    else
        printf("\nNo 'filename' setting in configuration file.");

    /*Read the parameter group*/
    setting = config_lookup(&cfg, "params");
    if (setting != NULL)
    {
        /*Read the string*/
        if (config_setting_lookup_string(setting, "param1", &str2))
        {
            printf("\nParam1: %s", str2);
        }
        else
            printf("\nNo 'param1' setting in configuration file.");

        /*Read the integer*/
        if (config_setting_lookup_int(setting, "param2", &tmp))
        {
            printf("\nParam2: %d", tmp);
        }
        else
            printf("\nNo 'param2' setting in configuration file.");

        printf("\n");
    }

    config_destroy(&cfg);
}

And corresponding configuration file :

 
//config.txt
// Basic Information:
filename = "Sample Configuration File";

// Parameters
params = 
{
param1 = "Hello";

param2 = 1234;
};

Articles needed !

Due to lack of time, I am not being able to write more posts. If anyone feels that they have some good topic to write about, please write to me and after moderation i can publish it on the blog.