Graph Implementation in C

A graph is a collection of nodes and edges. These nodes are connected by links(edges).
These edges may be directed or undirected. Moreover these edges can have weights associated with them

So edges can be categorized as :

1. Directed, weighted edges
2. Directed, unweighted edges
3. Undirected, weighted edges
4. Undirected, unweighted edges

Uses of graphs

Graphs are extremely useful. Look everywhere and one can easily find use of graphs. Listed below are a few of the vast set of practical uses of graphs.

Delhi Metro Rail Map

 Each station is a vertex, the distance in between is a weighted edge.

A Maze

 Each corner is a vertex, Line between two corners is and edge.

A tournament fixture
Courtesy: http://www.squadtd.com/

Each team is a vertex, match between the teams is an edge.

Kind of graphs

There are numerous classifications and types of graphs available. I have collected a few of those types from various sources and organized a list of types of graphs:

• Undirected Graphs

Undirected Graph

     Characteristics:

1. Order of vertices doesn't matter
2. 1-2 is same as 2-1

• Directed Graphs

Directed Graph

     Characteristics:

1. Order of vertices does matter
2. 1-2 is not same as 2-1

• Vertex labeled Graphs.

Vertex Labeled Graph

     Characteristics:

1. Each vertex contains additional information. e.g {2,orange}, {4,green}

• Cyclic Graphs.

Cyclic Graph

     Characteristics:

1. Graph contains at least one cycle.

• Edge labeled Graphs.

Edge Labeled Graph

     Characteristics:

1. Edge has labels e.g an edge in the above graph will be represented as {orange,green,{blue,cyan}}

• Weighted Graphs.

Weighted Graph

     Characteristics:

1. Each edge has some weight associated with it.

• Directed Acyclic Graphs.

Direct Acyclic Graph(DAG)

     Characteristics:

1. Graph has no cycles.

• Disconnected Graphs

Disconnected Graph

     Characteristics:

1. Vertices are disconnected 

• Mixed graph

Mixed Graph

     Characteristics:

1. Some edges may be directed and some may be undirected 

• Multigraph

Multigraph

     Characteristics:

1. Multiple edges (and sometimes loops) are allowed

• Quiver

          

     Characteristics:

1. Directed graph which may have more than one arrow from a given source to a given target. A quiver may also have directed loops in it.

Representation of graphs:

Fig. 1: An undirected graph

Fig 2: A directed graph

In order to use Graphs programatically , they need to be somehow represented in code. Following are the most widely used methods of representing a graph.

Adjacency Matrix : 

For N vertices an adjacency matrix is an NxN array A such that
                       A[i][j] = 1 if there is an edge E(i,j)
                                  = 0 otherwise

For an undirected graph, A[i][j] = A[j][i]

For weighted graphs,
                       A[i][j] = weight of the edge, if there is an edge E(i,j)
                                 = a constant representing no edge (e.g a very large or very small value)

For Fig 1, the adjacency matrix would be 

The adjacency matrix for directed graph in Fig 2 would be:

Adjacency List : 

Adjacency matrix representation consume a lot of memory (O[N²]). If the graph is complete or almost complete(i.e. contains most of the edges between the vertices), then this representation is good to use. But if there are very few edges as compared to number of vertices, it will unnecessarily consume extra space. Adjacency list can handle this situation very optimally.

Every vertex has a linked list of the vertices it is connected with.

Adjacency list for Fig 1 would be:

Adjacency list for Fig 2 would be:

Following is code snippet to implement graphs in C using adjacency list.

/*graph.h*/
#ifndef _GRAPH_H_
#define _GRAPH_H_

typedef enum {UNDIRECTED=0,DIRECTED} graph_type_e;

/* Adjacency list node*/
typedef struct adjlist_node
{
    int vertex;                /*Index to adjacency list array*/
    struct adjlist_node *next; /*Pointer to the next node*/
}adjlist_node_t, *adjlist_node_p;

/* Adjacency list */
typedef struct adjlist
{
    int num_members;           /*number of members in the list (for future use)*/
    adjlist_node_t *head;      /*head of the adjacency linked list*/
}adjlist_t, *adjlist_p;

/* Graph structure. A graph is an array of adjacency lists.
   Size of array will be number of vertices in graph*/
typedef struct graph
{
    graph_type_e type;        /*Directed or undirected graph */
    int num_vertices;         /*Number of vertices*/
    adjlist_p adjListArr;     /*Adjacency lists' array*/
}graph_t, *graph_p;

/* Exit function to handle fatal errors*/
__inline void err_exit(char* msg)
{
    printf("[Fatal Error]: %s \nExiting...\n", msg);
    exit(1);
}

#endif

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

/* Function to create an adjacency list node*/
adjlist_node_p createNode(int v)
{
    adjlist_node_p newNode = (adjlist_node_p)malloc(sizeof(adjlist_node_t));
    if(!newNode)
        err_exit("Unable to allocate memory for new node");

    newNode->vertex = v;
    newNode->next = NULL;

    return newNode;
}

/* Function to create a graph with n vertices; Creates both directed and undirected graphs*/
graph_p createGraph(int n, graph_type_e type)
{
    int i;
    graph_p graph = (graph_p)malloc(sizeof(graph_t));
    if(!graph)
        err_exit("Unable to allocate memory for graph");
    graph->num_vertices = n;
    graph->type = type;

    /* Create an array of adjacency lists*/
    graph->adjListArr = (adjlist_p)malloc(n * sizeof(adjlist_t));
    if(!graph->adjListArr)
        err_exit("Unable to allocate memory for adjacency list array");

    for(i = 0; i < n; i++)
    {
        graph->adjListArr[i].head = NULL;
        graph->adjListArr[i].num_members = 0;
    }

    return graph;
}

/*Destroys the graph*/
void destroyGraph(graph_p graph)
{
    if(graph)
    {
        if(graph->adjListArr)
        {
            int v;
            /*Free up the nodes*/
            for (v = 0; v < graph->num_vertices; v++)
            {
                adjlist_node_p adjListPtr = graph->adjListArr[v].head;
                while (adjListPtr)
                {
                    adjlist_node_p tmp = adjListPtr;
                    adjListPtr = adjListPtr->next;
                    free(tmp);
                }
            }
            /*Free the adjacency list array*/
            free(graph->adjListArr);
        }
        /*Free the graph*/
        free(graph);
    }
}

/* Adds an edge to a graph*/
void addEdge(graph_t *graph, int src, int dest)
{
    /* Add an edge from src to dst in the adjacency list*/
    adjlist_node_p newNode = createNode(dest);
    newNode->next = graph->adjListArr[src].head;
    graph->adjListArr[src].head = newNode;
    graph->adjListArr[src].num_members++;

    if(graph->type == UNDIRECTED)
    {
        /* Add an edge from dest to src also*/
        newNode = createNode(src);
        newNode->next = graph->adjListArr[dest].head;
        graph->adjListArr[dest].head = newNode;
        graph->adjListArr[dest].num_members++;
    }
}

/* Function to print the adjacency list of graph*/
void displayGraph(graph_p graph)
{
    int i;
    for (i = 0; i < graph->num_vertices; i++)
    {
        adjlist_node_p adjListPtr = graph->adjListArr[i].head;
        printf("\n%d: ", i);
        while (adjListPtr)
        {
            printf("%d->", adjListPtr->vertex);
            adjListPtr = adjListPtr->next;
        }
        printf("NULL\n");
    }
}

int main()
{
    graph_p undir_graph = createGraph(5, UNDIRECTED);
    graph_p dir_graph = createGraph(5, DIRECTED);
    addEdge(undir_graph, 0, 1);
    addEdge(undir_graph, 0, 4);
    addEdge(undir_graph, 1, 2);
    addEdge(undir_graph, 1, 3);
    addEdge(undir_graph, 1, 4);
    addEdge(undir_graph, 2, 3);
    addEdge(undir_graph, 3, 4);

    addEdge(dir_graph, 0, 1);
    addEdge(dir_graph, 0, 4);
    addEdge(dir_graph, 1, 2);
    addEdge(dir_graph, 1, 3);
    addEdge(dir_graph, 1, 4);
    addEdge(dir_graph, 2, 3);
    addEdge(dir_graph, 3, 4);

    printf("\nUNDIRECTED GRAPH");
    displayGraph(undir_graph);
    destroyGraph(undir_graph);

    printf("\nDIRECTED GRAPH");
    displayGraph(dir_graph);
    destroyGraph(dir_graph);

    return 0;
}

Sources:
http://en.wikipedia.org/wiki/Graph_(mathematics)
http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/Graphs.html
http://msdn.microsoft.com/en-us/library/ms379574(v=vs.80).aspx

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);
}