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.

Serialization using Google protobuf

Protocol buffers (that's what protobuf means :)) are a means to serialize structured data. Now you may be wondering what this 'serialize' means.

To be brief : Serialization is a process of packing the data structures or objects into sequence of bits so that they can be stored in a file or a buffer and transmitted across the network and then can be retrieved on the same or other system environment. Examples include XML, JSON, ASN.1, YAML, ProtoBuf etc.

Advantages :
1. Persistent object creation
2. RPC enabling
3. Are simple
4. Save space on disk
5. Very fast
6. Platform and language independent

ProtoBuf is available freely from Google (http://code.google.com/p/protobuf/). Procedure of installation and compilation is present there.

Everything that needs to be serialized is put in a protocol buffer message (a .proto file). This file tells the compiler how the data is to be serialized.

For each field there are setter and getter functions fieldname() is a getter and set_fieldname() is a setter. Remember to use these functions as the exact way it is told here.
The tutorials for the different languages can be found here

I present a small simple example to use the protobuf library and there is much more than that one can do with the protobuf :)

To make and run the example (on linux) follow the steps :
1. Download the tar.gz package from here
2. Login as root
3. Untar it in your home directory (say user1)
4. Go inside the protobuf directory and run ./configure
5. Add the path /usr/local/lib to the environment variable LD_LIBRARY_PATH
6. Then run :
make
make install
7. You are now ready to use the library.
8. To use protobuf you will need following files (I am explaining for c++ only):
.cc file
.proto file
Makefile
Rest of the files are generated on the fly.

Here is an example of a Vehicle parts which contains three fields , two mandatory and one optional.
-Part ID (mandatory)
-Part Name (mandatory)
-Vendor (optional)

We write this in .proto file

//partbook.proto
package tutorial;

message Part {
  required string name = 1;
  required int32 partid = 2;        // Unique ID number for this part
  optional string vendor = 3;

}

message PartDetails {
  repeated Part part = 1;
}

Then we write a c++ program to use the library and .proto to add serialized data to the data file.

/*add_part.cc*/
#include <iostream>
#include <fstream>
#include <string>
#include "partbook.pb.h"
using namespace std;

/* This function fills in a Part message based on user input.*/
void PromptForPart(tutorial::Part* part) {
  cout << "Enter part ID number: ";
  int partid;
  cin >> partid;
  part->set_partid(partid);
  cin.ignore(256, '\n');

  cout << "Enter part name: ";
  getline(cin, *part->mutable_name());

  cout << "Enter vendor name (blank for none): ";
  string vendor;
  getline(cin, vendor);
  if (!vendor.empty()) {
    part->set_vendor(vendor);
  }

}

/* Main function:  Reads the entire part list from a file,
 * adds one part based on user input, then writes it back out to the same
 *   file.
 */
int main(int argc, char* argv[]) {
  /* Verify that the version of the library that we linked against is
   * compatible with the version of the headers we compiled against.
   */
  GOOGLE_PROTOBUF_VERIFY_VERSION;

  if (argc != 2) {
    cerr << "Usage:  " << argv[0] << " PART_BOOK_FILE" << endl;
    return -1;
  }

  tutorial::PartDetails part_book;

  {
    // Read the existing part book.
    fstream input(argv[1], ios::in | ios::binary);
    if (!input) {
      cout << argv[1] << ": File not found.  Creating a new file." << endl;
    } else if (!part_book.ParseFromIstream(&input)) {
      cerr << "Failed to parse part book." << endl;
      return -1;
    }
  }

  // Add a new part.
  PromptForPart(part_book.add_part());

  {
    // Write the new part book back to disk.
    fstream output(argv[1], ios::out | ios::trunc | ios::binary);
    if (!part_book.SerializeToOstream(&output)) {
      cerr << "Failed to write part book." << endl;
      return -1;
    }
  }

  // Optional:  Delete all global objects allocated by libprotobuf.
  google::protobuf::ShutdownProtobufLibrary();

  return 0;
}

Then we write a c++ program to use the library and .proto to serialize the data.

/*list_parts.cc*/
#include <iostream>
#include <fstream>
#include <string>
#include "partbook.pb.h"
using namespace std;

// Iterates though all parts in the PartDetails and prints info about them.
void ListParts(const tutorial::PartDetails& part_book) {
  for (int i = 0; i < part_book.part_size(); i++) {
    const tutorial::Part& part = part_book.part(i);

    cout << "Part ID: " << part.partid() << endl;
    cout << "  Name: " << part.name() << endl;
    if (part.has_vendor()) {
      cout << "  Vendor: " << part.vendor() << endl;
    }

  }
}

// Main function:  Reads the entire part book from a file and prints all
//   the information inside.
int main(int argc, char* argv[]) {
  // Verify that the version of the library that we linked against is
  // compatible with the version of the headers we compiled against.
  GOOGLE_PROTOBUF_VERIFY_VERSION;

  if (argc != 2) {
    cerr << "Usage:  " << argv[0] << " PART_BOOK_FILE" << endl;
    return -1;
  }

  tutorial::PartDetails part_book;

  {
    // Read the existing data file.
    fstream input(argv[1], ios::in | ios::binary);
    if (!part_book.ParseFromIstream(&input)) {
      cerr << "Failed to parse part book." << endl;
      return -1;
    }
  }

  ListParts(part_book);

  // Optional:  Delete all global objects allocated by libprotobuf.
  google::protobuf::ShutdownProtobufLibrary();

  return 0;
}

#Makefile
#This creates executables for python cpp and java , to create only one language use #'make cpp' or 'make python' or 'make java'

.PHONY: all cpp java python clean

all: cpp java python

cpp:    add_part_cpp    list_parts_cpp
java:   add_part_java   list_parts_java
python: add_part_python list_parts_python

clean:
 rm -f add_part_cpp list_parts_cpp add_part_java list_parts_java add_part_python list_parts_python
 rm -f javac_middleman AddPart*.class ListParts*.class com/example/tutorial/*.class
 rm -f protoc_middleman partbook.pb.cc partbook.pb.h partbook.pb2.py com/example/tutorial/PartBookProtos.java
 rm -f *.pyc
 rmdir com/example/tutorial 2>/dev/null || true
 rmdir com/example 2>/dev/null || true
 rmdir com 2>/dev/null || true

protoc_middleman: partbook.proto
 protoc --cpp_out=. --java_out=. --python_out=. partbook.proto
 @touch protoc_middleman

add_part_cpp: add_part.cc protoc_middleman
 pkg-config --cflags protobuf  # fails if protobuf is not installed
 c++ add_part.cc partbook.pb.cc -o add_part_cpp `pkg-config --cflags --libs protobuf`

list_parts_cpp: list_parts.cc protoc_middleman
 pkg-config --cflags protobuf  # fails if protobuf is not installed
 c++ list_parts.cc partbook.pb.cc -o list_parts_cpp `pkg-config --cflags --libs protobuf`

javac_middleman: AddPart.java ListParts.java protoc_middleman
 javac AddPart.java ListParts.java com/example/tutorial/PartBookProtos.java
 @touch javac_middleman

add_part_java: javac_middleman
 @echo "Writing shortcut script add_part_java..."
 @echo '#! /bin/sh' > add_part_java
 @echo 'java -classpath .:$$CLASSPATH AddPart "$$@"' >> add_part_java
 @chmod +x add_part_java

list_parts_java: javac_middleman
 @echo "Writing shortcut script list_parts_java..."
 @echo '#! /bin/sh' > list_parts_java
 @echo 'java -classpath .:$$CLASSPATH ListParts "$$@"' >> list_parts_java
 @chmod +x list_parts_java

add_part_python: add_part.py protoc_middleman
 @echo "Writing shortcut script add_part_python..."
 @echo '#! /bin/sh' > add_part_python
 @echo './add_part.py "$$@"' >> add_part_python
 @chmod +x add_part_python

list_parts_python: list_parts.py protoc_middleman
 @echo "Writing shortcut script list_parts_python..."
 @echo '#! /bin/sh' > list_parts_python
 @echo './list_parts.py "$$@"' >> list_parts_python
 @chmod +x list_parts_python

Save all these files under <proto-installation-path>/examples/ and run make

To run the example
./add_part_cpp <data-filename>
./list_parts_cpp <data-filename>

Xdotool : Fake Keyboard/Mouse Input Tool

xdotool is a fake keyboard/mouse input tool for linux which is freely available on the internet.
So whatever you keep typing on the keyboard or kept clicking using the mouse , you can do it now with the help of a script.

One can get the tool downloaded from their website for all versions of linux:
http://www.semicomplete.com/projects/xdotool
There are too many uses you can use xdotool for. For example : If you need to open multiple tabs in a terminal you can use -
'xdotool key ctrl+shift+t' for as many times as the no. of tabs you need and to close down those tabs use 'xdotool ctrl+shift+w'

All this can be written on a script and when the script runs you can see all of that happening without even touching the keyboard or mouse.

The whole documentation is present here

Here are some examples :

Example: focus the firefox url bar

WID=`xdotool search "Mozilla Firefox" | head -1`
xdotool windowactivate --sync $WID
xdotool key --clearmodifiers ctrl+l


# As of version 2.20100623, you can do this simpler version of above:
xdotool search "Mozilla Firefox" windowactivate --sync key --clearmodifiers ctrl+l

Example: Resize all visible gnome-terminal windows
WIDS=`xdotool search --onlyvisible --name "gnome-terminal"`
for id in $WIDS; do
  xdotool windowsize $id 500 500
done

# As of version 2.20100623, you can do this simpler version of above:
xdotool search --onlyvisible --classname "gnome-terminal" windowsize %@ 500
500