Category Archives: C

Multi client chat server in C

I implemented a multi client chat server in C using socket programming. In a multi client chat server, N clients are connected to a server and send messages. In this program, one of the clients send messages to the server and it will send back the messages to all other clients. I implemented it using TCP.
A simple Client-Server Interaction


Server:

In the server program, first is the establishment of connection to a port. we get the socket file descriptor ,

int socket(int domain, int type, int protocol);

‘setsockopt’ is used for losing the pesky “Address already in use” error message. Once we have a socket, we might have to associate that socket with a port on our local machine. This can be done by using the ‘bind’.

int bind(int sockfd, struct sockaddr *my_addr, int addrlen);

We want to wait for incoming connections, we use ‘listen’ in this situation.

int listen(int sockfd, int backlog);

sockfd is the usual socket file descriptor from the socket() system call. backlog is the number of connections allowed on the incoming queue .

In the case of a server, it wants to listen for incoming connections as well as keep reading from the connections it already have. select() gives the power to monitor several sockets at the same time. It’ll tell you which ones are ready for reading, which are ready for writing, and which sockets have raised exceptions.

int select(int numfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

If we want to see if we can read from standard input and some socket descriptor, sockfd, just add the file descriptors 0 and sockfd to the set readfds. The parameter numfds should be set to the values of the highest file descriptor plus one. When select() returns, readfds will be modified to reflect which of the file descriptors we

selected which is ready for reading. After ‘select’, it run through the existing connections looking for data to read. If we got one, new connections are handled and the new file descriptor is added to the master set by keeping track of the maximum file descriptor. If there is no need to handle new connection, handle data from a client. If there is any data in the recv_buf, it can be received by using recv().Or , the data is send to all other clients by using the function send().

Client:

In the client program, first is the establishment of connection to the server and running on the localhost. Connection is established by using connect(). Then select() is used for either reading or writing as in the server program. It sends message to the server from the keyboard input using stdin. If there is data in the recv_buf, it receives data using recv().

The code of this program is available in https://bitbucket.org/vidyakv/network-programming/changeset/7f19f9145ab9

Advertisements

Bitwise Operators in C

Bitwise operator is an operator that manipulates individual bits. The bitwise operators are similar to the logical operators, except that they work on a smaller scale — binary representations of data. We need to know about the precedences and associativities of different bitwise operators for efficient and error prone coding. Precedence is the priority for grouping different types of operators with their operands. Associativity is the left-to-right or right-to-left order for grouping operands to operators that have the same precedence. An operator’s precedence is meaningful only if other operators with higher or lower precedence are present. Expressions with higher-precedence operators are evaluated first. The grouping of operands can be forced by using parentheses.

The following table lists C operators in order of precedence (highest to lowest). Their associativity indicates in what order operators of equal precedence in an expression are applied.

Operator Description Associativity
( )[ ].– >

++, —

Parentheses (function call)
Brackets (array subscript)
Member selection via object name
Member selection via pointerPostfix increment/decrement
left-to-right
++  —
+  –
!  ~
(type)
*
&
sizeof
 
Prefix increment/decrement
Unary plus/minus
Logical negation/bitwise complement
Cast (change type)
Dereference
Address
Determine size in bytes
right-to-left
*  /  % Multiplication/division/modulus left-to-right
+  – Addition/subtraction left-to-right
<<  >> Bitwise shift left, Bitwise shift right left-to-right
<  <=
>  >=
Relational less than/less than or equal to
Relational greater than/greater than or equal to
left-to-right
==  != Relational is equal to/is not equal to left-to-right
& Bitwise AND left-to-right
^ Bitwise exclusive OR left-to-right
| Bitwise inclusive OR left-to-right
&& Logical AND left-to-right
| | Logical OR left-to-right
? : Ternary conditional right-to-left
=
+=  -=
*=  /=
%=  &=
^=  |=

<<=  >>=

Assignment
Addition/subtraction assignment
Multiplication/division assignment
Modulus/bitwise AND assignment
Bitwise exclusive/inclusive OR assignment
Bitwise shift left/right assignment
right-to-left
, Comma (separate expressions) left-to-right

Implementation of some graph algorithms in C

A graph is simply a set of points together with a set of lines connecting various points. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. According to wikipedia: In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. Graph algorithms solve problems related to graph theory.

I implemented BFS,DFS, minimum spanning tree, Dijkstra’s and Floyd’s algorithms.

Breadth-First Search(BFS).

BFS begins at the root node and explores all the neighbouring nodes. Then for each of those nearest nodes, it explores their unexplored neighbour nodes, and so on, until it finds the goal.

The following figure illustrates the order in which the nodes are expanded.

The code of this program is available at: https://bitbucket.org/vidyakv/graph-algorithms-in-c/changeset/d00d940c1a8d#chg-bfs2.c

Depth-First Search(DFS)

Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.
The following figure illustrates the order in which the nodes are expanded.


The code of this program is available at: https://bitbucket.org/vidyakv/graph-algorithms-in-c/changeset/d00d940c1a8d#chg-dfs_path.c

Minimum Spanning Tree

A spanning tree of an undirected graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.

The following figure illustrates the minimum spanning tree of a planar graph. Each edge is labeled with its weight, which here is roughly proportional to its length.


The code of this program is available at: https://bitbucket.org/vidyakv/graph-algorithms-in-c/changeset/d00d940c1a8d#chg-min_span_tree.c

Dijkstra’s algorithm

It is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined.

The code of this program is available at: https://bitbucket.org/vidyakv/graph-algorithms-in-c/changeset/d00d940c1a8d#chg-dijkstra.c

Floyd-Warshall algorithm

It is a graph analysis algorithm for finding shortest paths in a weighted graph (with positive or negative edge weights). A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices though it does not return details of the paths themselves. The algorithm is an example of dynamic programming.

The code of this program is available at: https://bitbucket.org/vidyakv/graph-algorithms-in-c/changeset/0772753fa848#chg-floyd1.c

Note: The images used in this post is taken from wikipedia.

AVL Tree (Adelson-Velskii-Landis) – Implementation in C

An AVL tree is a self balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree-rotations.

   The balance factor of a node is the height of its left subtree minus the height of its right subtree (sometimes opposite) and a node with balance factor 1, 0, or −1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.

AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup intensive applications. However, it looks like red-black trees could be faster for insertion and element removal.

Basic operations of an AVL tree involve carrying out the same actions as would be carried out on an unbalanced binary search tree, but modifications are preceded or followed by one or more operations called tree rotations, which help to restore the height balance of the subtree.

Lookup

Lookup in an AVL tree is performed exactly as in an unbalanced binary search tree. Because of the height-balancing of the tree, a lookup takes O(log n) time. No special actions need to be taken, and the tree’s structure is not modified by lookups. If each node additionally records the size of its subtree (including itself and its descendants), then the nodes can be retrieved by index in O(log n) time as well. 

Insertion

After inserting a node, it is necessary to check each of the node’s ancestors for consistency with the rules of AVL. For each node checked, if the balance factor remains −1, 0, or +1 then no rotations are necessary. However, if the balance factor becomes ±2 then the subtree rooted at this node is unbalanced. If insertions are performed serially, after each insertion, at most one of the following cases needs to be resolved to restore the entire tree to the rules of AVL.

There are four cases which need to be considered, of which two are symmetric to the other two. Let P be the root of the unbalanced subtree, with R and L denoting the right and left children of P respectively.

Right-Right case and Right-Left case:

  • If the balance factor of P is -2 then the right subtree outweights the left subtree of the given node, and the balance factor of the right child (R) must be checked. The left rotation with P as the root is necessary.
  • If the balance factor of R is -1, a double left rotation(with respect to P and then R) is needed (Right-Right case).
  • If the balance factor of R is +1, two different rotations are needed. The first rotation is a right rotation with R as the root. The second is a left rotation with P as the root (Right-Left case).

Left-Left case and Left-Right case:

  • If the balance factor of P is +2, then the left subtree outweighs the right subtree of the given node, and the balance factor of the left child (L) must be checked. The right rotation with P as the root is necessary.
  • If the balance factor of L is +1, a double right rotation (with respect to P and then L) is needed (Left-Left case).
  • If the balance factor of L is -1, two different rotations are needed. The first rotation is a left rotation with L as the root. The second is a right rotation with P as the root (Left-Right case). The pictorial representation is given below:

                                                                                                                         

I have done the implementation of AVL tree in C.

The program for rotation is shown below: 

For left-right,  

      

For left-left,

For right-left,

For right-right,

The complete code of implementation of AVL tree in C is available here: https://bitbucket.org/vidyakv/avl-tree/changeset/a112ab2dd2f4 

Deletion

If the node is a leaf or has only one child, remove it. Otherwise, replace it with either the largest in its left subtree (inorder predecessor) or the smallest in its right subtree (inorder successor), and remove that node. The node that was found as a replacement has at most one subtree. After deletion, retrace the path back up the tree (parent of the replacement) to the root, adjusting the balance factors as needed.

Note: The image of tree used in this post is taken from wikipedia.

The WordPress.com Blog

The latest news on WordPress.com and the WordPress community.