Thursday, August 5, 2010

C++ STL: Iterators and Containers

This article was contributed by Eric Sanchez
Environment: ANSI C++
As one explores further into the standard template library, there must be a basic understanding of a few trivial terms. Perhaps the two most important are containers and iterators.
Container Classes
As the name implies, instances of container classes are objects that “contain” other objects. C++ STL comes with a rich set of such components that aid in storing collection of values. Although not all, it includes a vast majority of the main non-primitive and significant data structures.
List of STL’s containers:
Container Class: Brief Information:
String Met in previous part.
Vector Indexed. Very similar to conventional arrays. Rapid
insertion and removal of back elements.
Deque Similar to vectors with the exception of fast insertion
to the front.
List Linked Lists. Sequential. Rapid insertion\deletion of
elements from any position.
Stack LIFO protocol. Insertion Elements added\removed only
from front.
Queue FIFO., just like queues in downloading progs. Removal
from back only.
Priority Queue Fast removal of largest element.
Map Dictionary style structure. Keys are paired with values.
Multimap Multiple elements can be paired to the same key.
Iterators
As most data structures, containers would be rendered useless if there were no methods to retrieve or cycle through the elements. Here’s where iterators come in handy. As the name suggests, iterators are used to iterate through the objects and thus provide an opportunity to have access to the elements stored in a container.
Each container class permits the use of certain types of iterators depending on the mechanism used to store the items. Among these are the widely known Random Access Iterator. Just as arrays, it allows quick access to a given element by simply providing the index. However, if you are familiar with linked lists and a few other types of strucutres, you will know that it is not possibe to have access to a specific element without sequentially scrolling though the list. For this, given a base location, we can move through by using the Forward Iterator. There are a few additional types, such as Trivial Iter and Bidirectional.
With that in mind, as later we go through the different container classes, you will begin grasping the concept of iterators in more details. However, there are still few basics worth knowing for now.
When dealing with containers that permit random access, such as vectors and deques, one can simply access the elements in a similar way as arrays.
For example, if My_vecs is a vector that will hold integers, we could access the value in the 8th position by treating it as if it was an array:

int val = My_vec[7];

* Do not forget that the indexes begin at 0.
Non random access operators and even those that permit rand access contain two basic functions: begin() and end(). The first one returns an iterator pointing to the first element while the latter signals the end. It is what is known as the past-the-end value, meaning it will point to the position right after the last element, and not to the last element.
The way to declare an iterator object is by:

container :: iterator name;

For example to get the first position of My_vec, we would:

vector::iterator pos = My_vec.begin();

Although with vectors it is not necessary, suppose it was a list instead. To obtain the pointer to the next item, we could use the advance function, found in #include .

advance(pos,1);

Where 1 is the amount of positions to move the iterator through. Now pos would point to the second element. Most of the time, we could alternatively use pos++ rather than advance.
Finally, as in pointers, to get the actual value of the iterator, we use *. For example, if My_vec was a vector and advance was performed, int r = *pos, would assign the value 1 to r.
More about iterators will be discussed as needed.
Vectors
A vector is a container used to store a series of related data values. Abstractly, it can thought of as an advanced and more useful array of the same object. Imagine an array of integers:

int demo[]={1,2,3};

What would happen if you had to increase or decrease the size of the array, insert or remove elements, assign one array to another, etc. You might have to deal with messy operations such as new and delete. A vector helps in many these issues. A vector could be created to hold the same elements, it can be copied, elements added to it, resized, and so on very easily. A vector stores the data in a sequential order and thus it permits random access.
There are various ways to create a vector.
As usual, you have to include the header, in this case #include . You proceed by adding using namespace std or specifying std:: before the container.
The constructur I most frequently use is:

vector name;

Where T represents the name of an object and name the variable name. E.g.:

vector cool;
vector cool1;

Initially, the vector would be emptry. To add elements to the back of the vector, one generally uses the member function push_back(value). To add 1,2,3 to the vector:

vector abc; //abc = .


abc.push_back(1); //abc = 1.
abc.push_back(2); //abc = 1,2.
abc.push_back(3); //abc = 1,2,3.

Notice how push_back automatically resizes the vector by one. Push_back is usually O(1) if no reallocation of the buffer is necessary. However, if we know the number of elements the vector will have, by specifying the size of the vector initially, we would avoid the resizing done by push_back and thus slightly increase its efficiency. To do this, we may use the constructor vector name (int); where int represents the number of elements it will have.

vectorBOTW(3);
BOTW.push_back(1);
BOTW.push_back(2);
BOTW.push_back(3);

Since it was resized initially, not additionally resizing is done by using push_back. It is random access and the size is already established, and thus we could use subscripts to add the values:

vector VMC(3);
for (int i=1;i<4; i++)VMC [i] = i;

Equally, to get the element of a given index, we can use subscripts.

int num = VMC[0];

You might have wondered if there was an easier way to initialize the values so that if we have tons of item, we don’t have a million a push_backs or []. There a few ways to this. Obviously, you could create an array with the values and use a loop to insert it into the vector. However, an alternative way exists:

string programmers[] = {”Hussainweb”, “BOTW”, “VMC”, “Ziggy^3″, “Ray45512″,
“Mallowman”, “PRTSoft”, “MaxK”,”Pelican”, “Moonie”, “Ruudje”, “And Many More”};
//To add all these elements to a vector, we can simply to do it as:
vector prog (programmers, programmers + sizeof(programmers)/sizeof(string));

As you know, we can use indexes to get and set values. However, that will not prevent you from accessing memory outsize the boundaries of the vector. To display a message if this happens, we can use .at(index);

string name = prog.at(12);
prog.at(12) = name;

Suppose 12 is outside the vector, the program would come to a halt.

Finally to delete the last element, we use pop_back().

prog.pop_back();

Some other useful member functions:
Function: Brief Description: Example:
A = B Copy vector A to B N/A
.front() Returns the value of the front element string name1 = prog.front();
.back() Value of last element string name_l = prog.back();
.swap(vector) Swap the two vectors values vectorA;
A.push_back("none");
prog.swap(A);
.size() Returns the # of elements in the vector int len = prog.size();
.resize() Resizes the vector prog.resize(23);
.empty() Returns true if the vec is empty if (prog.empty()) cout<<" GRRRrrr…";
.clear() Clears all values of the vector. Size = 0. ): prog.clear();
.erase(iterator)
.erase(iterator, iterator)
Erases the element or range specified by iterator prog.erase(prog.begin()+1, prog.begin()+4);
That’s only a few of the many other functions of vectors, not to mention algorithms that can be performed.

C++ Streaming Input and Output Manipulation

Simple Prompt Input and Output

Most commonly used programs use a combination of both input and output to interact and present users with meaningful information (output) from their data (input). Any program without input or output facilitates no use!
Command line input and output is a textual interaction between a program and user. Although a Command Line interface is quite dull, to say the least, it is the most basic and quickest to implement.
There are several ways that a C++ program can perform input and output, the most common is via the use of streams. The intuition for the word stream is that a program “sees” only the input or output and not the origin (source) or destination of the data. A common analogy is the flow of water past your feet - you see the water at your feet but might not know where the water has come from nor where it is going.
An output example.

#include

namespace std { };
using namespace std;

int main() {

cout << "Hello, world.\n"; // The simple "Hello World" example.

return 0;
}

Using cout with insertion operators (”<<") should always display to the terminal screen.
Inputting is just as easy as outputting when using cin in conjunction with the extraction operators (">>”). cin is best thought as syntax for getting input from a keyboard. However, when using the cin approach with the extraction operators all white space is ignored and skipped. Using multiple extraction operators for user input may yield unexpected run-time effects when dealing with characters - commonly referred to as buffer problems - due to the unpredicability of users and their quirky input.
The extraction operators are best reserved for numeric input or for predictable formatted input - usually from a prepared file.
cout is derived from the ostream class and cin is derived from the istream class. Inheritance is of great use and is explained latter.
The safest way to acquire user input is by use of the overloaded member function get() which is common practice amongst programmers.

/* File: lab2002.cpp; Mode: C++; Tab-width: 3; Author: Simon Flannery; */
#include

namespace std { };
using namespace std;

int main() {

char unit; bool boolExit = true;
do {
cout << "Enter Compass Direction: ";
cin.get(unit); // Get a single character.
while (cin.get() != '\n'); // Clear Buffer.
switch (unit) {
case 'n':
case 'N': cout << "North."; break;
case 's':
case 'S': cout << "South."; break;
case 'e':
case 'E': cout << "East."; break;
case 'w':
case 'W': cout << "West."; break;
default: cout << "Check Your Compass.\n"; boolExit = false; break;
}
} while (!boolExit);
return 0;
}

In the preceding example the program requests user input, where the program expects a single character. However, users would not be aware of this single character requirement and it is therefore the role of the programmer to foresee and handle all possible input - including “silly” user input.
In the example, only the users first character entry is stored and validated. All other trailing characters are “eaten” thanks to the line: while (cin.get() != ‘\n’);. This will help to avoid buffer issues and stop the do… while loop being iterated again (and again and again) getting each character one at a time from a long string entry and therefore preventing a dump of “Check Your Compass”.
It should be clear that without clearing the buffer undesirable run-time effects can be encountered. Be astute when working with streams as buffer errors are very common. Remember to always clear the buffer!
Programs should also be able to handle user input of different character lengths and store input in a memory efficient manner. This can be achieved via the use of pointers.
Remember that a pointer is just a variable which holds the address of a starting block (the first address) of memory which has its size reserved on the heap at run-time. A pointer can “point” to any type of variable. A pointer can even reference another pointer.

#include
#include

namespace std { };
using namespace std;

int main() {

char buffer[101], * said;
cout << "Enter: ";
cin.get(buffer, 101, '\n');
while (cin.get() != '\n');
said = new char[strlen(buffer) + 1];
strcpy(said, buffer);
cout << "Echo: " << said;
delete [] said;
return 0;
}

The preceding example first declares a normal cstring, buffer, with a generous size. Next, the size of a new dynamic cstring is assigned by determining the length of buffer via the strlen() function and one is added to allow for the null terminating character. Clearly this saves memory if there are multiple cstrings to be stored, as opposed to assigning the same fixed length to each cstring.
Since output may want to be “streamed” to different destinations, for example, to the humble screen or text file, inheritance is of use.

#include
#include

namespace std { };
using namespace std;

void stream2(ostream& os, char*);

int main() {

stream2(cout, "Hello World.\n");

char* say = "And Hello again.\n";
stream2(cout, say);

ofstream outFile;
outFile.open("sample.txt");
stream2(outFile, say);
outFile.close();
return 0;
}

void stream2(ostream& os, char* say) {

os << char2Say;

return;
}

In the preceding example the ostream class is used as a parameter for the function stream2(). This is because of inheritance which allows many output streams, including file streams of type ofstream and the standard cout which is of type ostream, to the passed into the function body.
Also some may be familiar with char say[] = “Whatever”; rather than char* say = “Whatever”;. Most people would say that is no difference between these code fragments. So, is there a difference between these? Yes. Using the array notation 9 bytes of storage in the static memory block are used, one for each character and one for the NULL character. However, in the pointer notation the same 9 bytes are required, plus a couple of bytes to store the pointer variable reference char2Say.
One powerful feature of C++ is inheritance, which is the use of derived classes. Put simply, a derived class uses an existing class but adds unique functions (for extra features) to form a new class. For example, both cout and ofstream were derived from the ostream class - the ofstream class adds extra member functions such as open() and close(). And both cin and ifstream were derived from the istream class.
Notice that a stream may be an argument to a function with the only restriction being that the function formal parameter must be a call-by-reference, not a call-by-value.
A summary of some useful stream control functions:
istream::get() will extract and return a single character from the istream - including a white space character.
istream::get(char&) will extract a single character from the istream and store the character to the reference argument alias. Again, this includes white space characters.
istream::get(char*, int, char) will extract consecutive characters from the istream until either the integer limit - 1 is reached, the delimiter character is found, or the end of the istream is reached. The extracted characters are stored in the given cstring followed by the null terminator. If the delimiter is found, it is not extracted nor stored. Again, this includes white space characters.
ostream::put(char) will put a single character into the ostream.
istream::putback(char) will “put back” a character into the istream. This character must be the character previously extracted, else the result is undefined.

Manipulators and flags for Formatting
Manipulators are function calls which are normaly placed after the insertion operator (”<<") just as if the manipulator were a item to output which the output stream identifies. Manipulators aid with formatting output by changing the state of a stream.
Flags also aid with the dressing of input and output. A flag is an instruction to do something in one of two possible ways. The history of the term "flag" is thought to have been derived from saying "do this, when the flag is up (or down)".

#include
#include // For setw(), setfill() and setprecision().

int main() {
using namespace std;

double num, mult;

cout << "Pleae Enter two Numbers: ";
cin >> num >> mult;

cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.setf(ios::showpos);

cout << "The product of " << num << " and " << mult << " equals "
<< setfill('*') << setw(10) << setprecision(3)
<< num * mult << "."
// Output product in a width
// of ten '*'s (right aligned is default)
// with decimal point, three decimal places
// and positive or negative sign.
<< endl;

return 0;
}

setfill(), setw(), setprecision() and endl are common examples of output stream manipulators. When setfill() and setw() are called respectively, a width of characters, set via setw(), is filled with the character given in setfill(). Valid output must be placed after these calls for the effect to be visible.
Useful Predefined output Manipulators, from header file
endl - When inserted into an output stream, a newline character is placed in the stream and then the buffer is flushed.
ends - When inserted into an output stream, a null-terminator character is placed in the stream.
So what’s the difference between endl, ‘\n’ and “\n”? Timing. The main performance difference relates to time. ‘\n’ is a little faster than “\n” and is faster than endl. The reason why endl costs time is that it flushes the current output buffer (via expensive write calls) as well as streams a humble newline character.
Useful Predefined output Manipulators, from header file
setw(int) - Sets the field width for following output, where a mono-spaced character is the width of one unit.
setfill(char) - Sets a fill character to be used as padding in the width set by setw(). Usually called before setw().
setprecision(int) - Enforces or restricts the decimal part of the value to a set number of decimal places.
setbase(int) - Converts all integers (in any base) in post output stream calls to the assigned base. Seems to only work for integers.
Input streams may also have manipulators, but they are not as common. One of the only standard input manipulators is ws which skips all white space when using the extraction operators - however, this feature is automatic when using the extraction operators.
Calls to the member function setf() (and unsetf()), are inherited from the ios class, and used to set (and unset) flags for streams in future stream calls. ios::showpos is an example of an enumerator representing a particular flag value.
Useful Flags (setting and unsetting), from header file
ostream::setf(ios::fixed)
ostream::unsetf(ios::fixed) - When set, floating point numbers are not expressed in e-notation.
ostream::setf(ios::scientific)
ostream::unsetf(ios::scientific) - When set, floating point numbers are express in e-notation.
ostream::setf(ios::showpoint)
::ostream::unsetf(ios::showpoint) - When set, a decimal point and trailing zeros are always shown. Normally used with ios::fixed and precision().
ostream::setf(ios::showpos)
ostream::unsetf(ios::showpos) - When set, the plus symbol is output before a positive value.
ostream::setf(ios::right)
ostream::unsetf(ios::right) - This is set by default, and when set, aligns output called after the setw() manipulator to the right of the field.
ostream::setf(ios::left)
ostream::unsetf(ios::left) - When set, aligns output to the left of a field called after the setw() manipulator.
ostream::setf(ios::boolalpha)
ostream::unsetf(ios::boolalpha)
Custom manipulators can be defined, for example as follows.

#include

namespace std {

ostream& tail(ostream& os) {
return os << "...";
}

}

int main() {

std::cout << "Hello" << std::tail << " World." << std::endl;

return 0;
}

In the preceding example, a globally defined manipulator called “tail”, which takes an ostream reference argument, is defined to insert three periods into any output stream. Since streams are changed by reading or writing, the call-by-reference parameter syntax is used.
The return type of the function was also of type ostream because this allows “chains” of “<<" to be called.
For example, std::cout << "Hello" << std::tail << " World." << std::endl;
is really, (((std::cout << "Hello") << std::tail) << " World.") << std::endl; where the contents of each parentheses returns an object of type ostream (cout) for the following "<<" to use. Also "<<" is just a normal function call.

Inputting and Outputting Objects Types
Object Types (Classes), at first, don’t seem to integrate well with stream input and output since an object is a group of smaller variables called member variables and functions called member functions (or “methods” if your background is Java). A variable of a defined object cannot be simply placed in an input or output stream because the related function calls “<<" and ">>” have not been overloaded to accept these new and custom types.
It would, however, be more convenient and effective to simply input or output a defined object with all or just a select few of its member values! The ability of overloading makes this possible and very easy. In this case, the extraction (”>>”) and insertion (”<<") operators is overloaded.

#include
#include
#include

namespace std { };
using namespace std;

class person {

public:
person();
~person();
friend ostream& operator<<(ostream&, const person&);
friend istream& operator>>(istream&, person&);

private:
char* title, * name;
int age;
};

person::person(): title(NULL), name(NULL), age(0)
{
}

person::~person()
{
delete [] title;
delete [] name;
}

const int LF = '\n'; // New Line, or Line Feed.

istream& operator>>(istream& is, person& p) {

char buffer[101];

cout << "Please Enter Title: ";
is.get(buffer, 101, LF);
while (is.get() != LF);
p.title = new char[strlen(buffer) + 1];
strcpy(p.title, buffer);

cout << "Please Enter Name: ";
is.get(buffer, 101, LF);
while (is.get() != LF);
p.name = new char[strlen(buffer) + 1];
strcpy(p.name, buffer);

cout << "Please Enter the Age of "
<< p.title << " "
<< p.name << ": ";

is.get(buffer, 4, LF);
while (is.get() != LF);
p.age = atoi(buffer);

return is;

}

ostream& operator<<(ostream& os, const person& p) {

return os << p.title << " "
<< p.name << ", is of age "
<< p.age << "." << endl;
}

int main() {

person p;

cin >> p; // Now, this is easy!
cout << "Input Information: " << p << endl;

return 0;
}

In the preceding example, the standard input and output streams have been overloaded to accept arguments of type istream and ostream and the developers defined type of person. Now, a variable of type person can be used in the same way as the standard data types when they are placed in an input or output stream.
The advantages should be clear. Placing a type of object independent of its member variables in an input or output stream not only reduces code but makes it easier to interpret and understand.

Simple File Input and Output
Most peripheral input and output, such as keyboard and screen, deal with temporary data. Once the program exits, all data is lost. Files, however, provide a way to store data in a permanent state (in secondary storage). Files that a program utilises may exist both before and after a program is run and exited. Files may also be created or destroyed when a program is run.
A common misconception is that defines cin and cout. However, does not define cout and cin. In earlier versions of C++, , and used to define cout, cin and so on.
Opening and retrieving data from a file is easy.

#include
#include // or fstream.h

namespace std { };
using namespace std;

int main(int argc, char** argv) {

if (argc < 2) { // If no (file) argument...

return 0; // ...Clean Exit.
}

double get = 0, total = 0;

ifstream inFile;
inFile.open(argv[1]);

while (!inFile.fail() && inFile >> get) {

total += get;
}

inFile.close();

cout << "The total Summation of the file: " << total << "." << endl;

return 0;
}

The preceding example opens a file and expects numeric data from the file. Due to the nature of extraction operators, and by default, all white space is skipped.
The advantage of skipping all white space is that the numeric data within the file could be separated by either new lines, spaces or by both a messy combination of new lines and spaces!
The while statement terminates when all consecutive numeric data has been read. The extraction operators can be used to terminate a control loop because they technically return a boolean value - true or false. The extraction operators preform best for numeric input, and characters.
Copying files is a popular task, but there is a trick. The actual file buffer must be referenced, not the class buffer.

#include

namespace std {};
using namespace std;

int main() {

ifstream inFile("in.txt");
ofstream outFile("out.txt");

if (inFile.fail() || outFile.fail()) { return 0; }

// outFile << infile; // Would seem correct, but Fails!
outFile << inFile.rdbuf(); // The correct method.

inFile.close();
outFile.close();

return 0;
}

It is important to observe that the provided stream classes are text-oriented - To be Universial and Fair for the sake portability.
When saving (outputting) to an external file, the external file is automatically created or replaced by default.
If, however, a file is not to be created or replaced, it must be known if the file already exists. To test if the file exists the file could be opened for input (in the normal way using open()) and checked if it has been successfully opened by calling the member function fail(). If the check fails (returns true) the file does not exist, else it does exist. And from this test it may now be decided what to do with the file (create or replace it by opening the new or existing file for output).
In the example the file streams were declared as ifstream for input and ofstream for output. There is also a general file stream class: fstream.
All three - ifstream, ofstream and fstream (and there are more) - allow a second argument when calling the open() member function or the constructor which allows the developer to specify an open mode.

/* File: genFreq.cpp; Mode: C++; Tab-width: 3; Author: Simon Flannery; */

#include
#include
#include // or iomanip.h

namespace std { }
using namespace std;

int main(int argc, char** argv) {

cout << "File Frequency Table Generator." << endl;

if (argc < 2)
{
cout << "No Input File.";
return 0; // No file, Exit.
}

int intFreq[256] = {0};
char cGet;

char* charDefn[] = {”NUL”, “SOH”, “STX”, “ETX”, “EOT”, “ENQ”, “ACK”, “BEL”,
“BS “, “HT “, “LF “, “VT “, “FF “, “CR “, “SO “, “SI “,
“DLE”, “DC1″, “DC2″, “DC3″, “DC4″, “NAK”, “SYN”, “ETB”,
“CAN”, “EM “, “SUB”, “ESC”, “FS “, “GS “, “RS “, “US ” };

fstream inFile; inFile.open(argv[1], ios::binary | ios::in);

if (inFile.fail())
{
cout << "Input File Error." << endl;
return 0; // File error, Exit.
}

while (inFile.get(cGet))
{
intFreq[int(cGet)]++;
}

inFile.close();

ofstream outFile; outFile.open("out.txt");

if (outFile.fail())
{
cout << "Output File Error." << endl;
return 0; // File error, Exit.
}

for (int i = 0; i < 256; ++i)
{
if (i < 32)
{
outFile << setw(16) << charDefn[i];
}
else
{
outFile << setw(8) << char(i) << setw(8) << " ";
}

outFile << setw(8) << i << setw(8) << intFreq[i] << endl;
}

outFile.close();

cout << "Successful Runnel." << endl;

return 0;
}

The main visible effect of Opening an ASCII file in binary mode is that the new line character ‘\n’ is not automatically mapped as both the new line character and the appropriate system end-of-line sequence. For example, just LF on Unix, CRLF on DOS and CR on Macintosh. “Binary mode is not supposed to suddenly give you a bitstream…” - DJGPP.
The optional ios mode can be:
Mode Meaning
ios::app Append output at end of file.
ios::ate Goto to EOF when opened.
ios::binary Open the file in binary mode.
ios:in Open the file for reading.
ios::out Open file for writing.
ios::trunc Overwrite the existing file.
If the ios mode is not any of the following combination of flags shown in the table then the open method fails.
A summary of some useful file stream control functions:
i/o fstream::open(char*) loads the file name (from relative or absolute path).
istream::getline(char*, int, char) will extract consecutive characters from the istream until either the integer limit - 1 is reached, the delimiter character is found, or the end of the istream is reached. The extracted characters are stored in the given cstring followed by the null terminator. If the delimiter is found, it is extracted but not stored.
Remember that all the overloaded istream::get() functions, neither extracts nor stores the delimiter character.
i/o fstream::close(). It’s polite to close the file i/o stream when all related processing is finished.
i/o fstream::fail() returns true if the file has failed to load and is normally called immediately after a call to open().
i/o fstream::is_open() returns true if the file i/o stream is currently open, else false when the file stream is closed (or failed to open).
ifstream::eof() is an abbreviation for “End of File”. Returns true when the end of the file stream has been reached. Most commonly used to terminate a control loop.
Another common method when testing for the end of a file stream is to test for negative one (-1). Note that this is the number -1 and not the characters ‘-’ and ‘1′. Although this method will almost work in all cases, the -1 end of file marker is not a universal agreement across all platforms! One known platform has the end of file marker as -42. This is why both the member function eof() and the macro EOF exists, which tries to cater for a wide range of platforms. So use ‘em and not -1.
A very common question amongst beginners (and some graduates) is “How can I open a file and insert a new line between two other existing lines?” In short, it is not possible. It must first be understood that this is not a limitation of C++ or any operation system - it’s a hardware limitation. Since files (all the little bits and bytes) are stored consecutively (normally on a disk) there is no “space” left to insert the new line nor a “link” pointing to a new disk cluster and back again. However, the long answer, it can be done. First load the file and all contents (possibly into memory), then rewrite the whole file and the new line where desired.

Dissecting Input Example (Date Validation)
When programming, and when dealing with unpredictable users and their input, an important skill is the ability to separate (or dissect) data into constituent pieces of information.

/* File: getDate.cpp; Mode: C++; Tab-width: 3; Author: Simon Flannery; */

#include

namespace std {}
using namespace std;

/* Return users answer. */

bool booleanResponse(const char*);

/* Validates a char array for a date Representation. */

bool isDate(const char*);

int main() { // Main construct.

char buffer[101];
const int LF = ‘\n’; // New Line, or Line Feed.

do {
cout << "Please Enter a Valid Date: ";
cin.get(buffer, 101, LF); cin.get(); // Get that Last LF!

if (isDate(buffer)) {
cout << "\nThe date " << buffer << " is Valid." << endl;
} else {
cout << "\nThe date " << buffer << " is invalid!" << endl;
}

} while (booleanResponse("\nDo you wish to Enter Another Date? "));

return 0;

} // main.

bool booleanResponse(const char* prompt) {

const int LF = '\n'; // New Line, or Line Feed.
bool result = false;
char input;

do {
cout << prompt;
cin.get(input);
while (cin.get() != LF); // Clear Buffer.

input |= 0x20; // 32. Bit "or" convert.

} while (input != 'y' && input != 'n');

cout << endl;

if (input == 'y') { result = true; }

return result; // Else false.
}

bool isDate(const char *_s) {

const char* p = _s;
int element = 0, date[3] = {0};
int lastDayOfMonth[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

if (!_s) { return false; }

while (*p) {

if (*p >= '0' && *p <= '9') {

date[element] *= 10;
date[element] += *p - ‘0′;
} else {

if (*p == '/') {

element++;
} else {

return false;
}
}

if (element > 2) { return false; }
p++;
}

if (!date[1] || date[1] > 12) { return false; } // Month range check.
// Leap Year check.
if ((date[2] % 4 == 0) && date[1] == 2 && date[0] == 29) { return true; }
// Date range check.
if (!date[0] || date[0] > lastDayOfMonth[date[1] - 1]) { return false; }

return true;
}

The preceding example requests the user to enter a formatted date in the form dd:mm:yy for validation. The isDate() function illustrates a robust procedure for validating and dissecting the given ASCII cstring.

Writing log file in c++

void saveLog(int n,double timeelapsed1,double timeelapsed2)
{

ofstream SaveFile("logsort.txt",ios::app);
SaveFile << "No. of elements : "<<n<<endl;
SaveFile << "Time taken by bubblesort : "<<timeelapsed1<<endl;
SaveFile << "Time taken by quicksort : "<<timeelapsed2<<endl;
SaveFile.close();

}

File IO in c++ 2

Checking the I/O status - Flags
I won’t be explaining what flags are. But even if you don’t know about them, reading this chapter to the end may give you some idea, and I believe you will understand the theory. Even so, if you don’t know about the flags in C++, I recommend you to find some reading on this subject.
Okay, let’s start!
The Input/Output system in C++, holds information about the result of every I/O operation. The current status is kept in an object from type io_state, which is an enumerated type (just like open_mode) that has the following values:
godbitNo errors.
eofbitEnd of file has been reached
failbitNon-fatal I/O error
badbitFatal I/O error
There are two ways, to receive information about the I/O status. One of them is by calling the function rdstate(). It returns the current status of the error-flags (the above mentioned). For example, the rdstate() function will return goodbit if there were no errors.
The other way to check the I/O status is by using any of the following function:

bool bad();
bool eof(); //remember this one? "Read until the end of the file has been reached!"
bool fail(); //and this one, too… Check if the file opening was successfull
bool good();

The function bad() returns true, if the badbit flag is up. The fail() function returns true if the failbit flag is up. The good() function returns true if there were no errors (the goodbit flag is up). And the eof() function returns true if the end of the file has been reached (the eofbit flag is up).
If an error occurred, you will have to clear it if you want your program to continue properly. To do so, use the clear() function, which takes one parameter. The parameter should be the flag you want to put to be the current status. If you want your program to continue “on clear”, just put ios::goodbit as parameter. But notice that the clear() function can take any flag as parameter. You will see that in the code examples bellow.
I will now show you some example code that will confirm your knowledge.
Example 1: Simple status check

//Replace FileStream with the name of the file stream handle
if(FileStream.rdstate() == ios::eofbit)
cout << "End of file!\n";
if(FileStream.rdstate() == ios::badbit)
cout << "Fatal I/O error!\n";
if(FileStream.rdstate() == ios::failbit)
cout << "Non-fatal I/O error!\n";
if(FileStream.rdstate() == ios::goodbit)
cout << "No errors!\n";

Example 2: The clear() function

#include


void main()
{
ofstream File1("file2.txt"); //create file2.txt
File1.close();
//this bellow, will return error, because I use the ios::noreplace
//open_mode, which returns error if the file already exists.
ofstream Test("file2.txt",ios::noreplace);
//The error that the last line returned is ios::failbit, so let's show it
if(Test.rdstate() == ios::failbit)
cout << "Error...!\n";
Test.clear(ios::goodbit); //set the current status to ios::goodbit
if(Test.rdstate() == ios::goodbit) //check if it was set correctly
cout << "Fine!\n";
Test.clear(ios::eofbit); //set it to ios::eofbit. Useless.
if(Test.rdstate() == ios::eofbit) //and check again if it is this flag indeed
cout << "EOF!\n";
Test.close();
}

Instead using flags, you can use a function that actually does the same- checks if specific flag is up. The functions were mentioned before, so I won’t mention them again. If you are not sure how to use them, just check out the place of the tutorial, where I showed few ways to check if file opening was successful or not. There, I used the fail() function.
Dealing with Binary files
Although, the files with formatted text (all that I talked about so far) are very useful, sometimes you may need to work with unformatted files- binary files. They have the same look as your program itself, and it is much different from what comes after using the << and >> operators. The functions that give you the possibility to write/read unformatted files are get() and put(). To read a byte, you can use get() and to write a byte, use put(). You should remember of get()… I have already used it before. You wonder why even using it, the file looks formatted? Well, it is because I used the << and >> operators, I suppose.
get() and put() both take one parameter- a char variable or character.
If you want to read/write whole blocks of data, then you can use the read() and write() functions. Their prototypes are:

istream &read(char *buf, streamsize num);
ostream &write(const char *buf, streamsize num);

For the read() function, buf should be an array of chars, where the read block of data will be put. For the write() function, buf is an array of chars, where is the data you want to save in the file. For the both functions, num is a number, that defines the amount of data (in symbols) to be read/written.
If you reach the end of the file, before you have read “num” symbols, you can see how many symbols were read by calling the function gcount(). This function returns the number of read symbols for the last unformatted input operation.
And before going to the code examples, I have to add, that if you want to open a file for binary read/write, you should pass ios::binary as an open mode.
Now, let me give you some code examples, so that you can see how stuff works.
Example 1: Using get() and put()

#include


void main()
{
fstream File("test_file.txt",ios::out | ios::in | ios::binary);
char ch;
ch='o';
File.put(ch); //put the content of ch to the file
File.seekg(ios::beg); //go to the beginning of the file
File.get(ch); //read one character
cout << ch << endl; //display it
File.close();
}

Example 2: Using read() and write()

#include
#include


void main()
{
fstream File("test_file.txt",ios::out | ios::in | ios::binary);
char arr[13];
strcpy(arr,”Hello World!”); //put Hello World! into the array
File.write(arr,5); //put the first 5 symbols into the file- “Hello”
File.seekg(ios::beg); //go to the beginning of the file
static char read_array[10]; //I will put the read data, here
File.read(read_array,3); //read the first 3 symbols- “Hel”
cout << read_array << endl; //display them
File.close();
}

Some useful functions
tellg() - Retunrs an int type, that shows the current position of the inside-pointer. This one works only when you read a file. Example:

#include


void main()
{
//if we have "Hello" in test_file.txt
ifstream File("test_file.txt");
char arr[10];
File.read(arr,10);
//this should return 5, as Hello is 5 characters long
cout << File.tellg() << endl;
File.close();
}

tellp() - The same as tellg() but used when we write in a file. To summarize: when we read a file, and we want to get the current position of the inside-pointer, we should use tellg(). When we write in a file, and we want to get the current position of the inside-pointer, we should use tellp(). I won’t show a code example for tellp() as it works absolutely the same way as tellg().
seekp() - Remember seekg()? I used it, when I was reading a file, and I wanted to go to specified position. seekp() is the same, but it is used when you write in a file. For example, if I read a file, and I want to get 3 characters back from the current position, I should call FileHandle.seekg(-3). But if I write in a file, and for example, I want to overwrite the last 5 characters, I have to go back 5 characters. Then, I should use FileHandle.seekp(-5).
ignore() - Used when reading a file. If you want to ignore certain amount of characters, just use this function. In fact, you can use seekg() instead, but the ignore() function has one advantage- you can specify a delimiter rule, where the ignore() function will stop. The prototype is:

istream& ignore( int nCount, delimiter );

Where nCount is the amount of characters to be ignored and delimiter is what its name says. It can be EOF if you want to stop at the end of the file. This way, this function is the same as seekg(). But it can also be ‘\n’ for example, which will stop on the first new line. Here is example:

#include

void main()
{
//if we have "Hello World" in test_file.txt
ifstream File("test_file.txt");
static char arr[10];
//stop on the 6th symbol, if you don’t meet “l”
//in case you meet “l”- stop there
File.ignore(6,’l');
File.read(arr,10);
cout << arr << endl; //it should display "lo World!"
File.close();
}

getline() - I have already mentioned about this one. But there is something I didn’t tell you about. This function can be used to read line-by-line, but it can be set to stop reading if it met a certain symbol. Here is how you should pass the parameters to it:

getline(array,array_size,delim);

And here is a code example:

#include


void main()
{
//if we have "Hello World" in test_file.txt
ifstream File("test_file.txt");
static char arr[10];
/*read, until one of these happens:
1) You have read 10
2) You met the letter “o”
3) There is new line
*/
File.getline(arr,10,’o');
cout << arr << endl; //it should display "Hell"
File.close();
}

peek() - This function will return the next character from an input file stream, but it won’t move the inside-pointer. I hope you remember, that get() for example, returns the next character in the stream, and after that, it moves the inside-pointer, so that the next time you call the get() function, it will return the next character, but not the same one. Well, using peek() will return a character, but it won’t move the cursor. So, if you call the peek() function, two times in succession, it will return a same character. Consider the following code example:

#include


void main()
{
//if we have "Hello World" in test_file.txt
ifstream File("test_file.txt");
char ch;
File.get(ch);
cout << ch << endl; //should display "H"
cout << char(File.peek()) << endl; //should display "e"
cout << char(File.peek()) << endl; //should display "e" again
File.get(ch);
cout << ch << endl; //should display "e" again
File.close();
}

And by the way, I forgot to mention- the peek() function actually returns the ASCII code of the char, but not the char itself. So, if you want to see the character itself, you have to call it the way I did, in the example.
_unlink() - Deletes a file. Include io.h in your program, if you are going to use this function. Here is a code example:

#include
#include


void main()
{
ofstream File;
File.open("delete_test.txt"); //creates the file
File.close();
_unlink("delete_test.txt"); //deletes the file
//tries to open the file, but if it does not exists
//the function will rreturn error ios::failbit
File.open("delete_test.txt",ios::nocreate);
//see if it returned it
if(File.rdstate() == ios::failbit)
cout << "Error...!\n"; //yup,it did
File.close();
}

putback() - This function will return the last read character, and will move the inside-pointer, one with -1 char. In other words, if you use get() to read a char, then use putback(), it will show you the same character, but it will set the inside-pointer with -1 char, so the next time you call get() again, it will again show you the same character. Here is a code example:

#include


void main()
{
//test_file.txt should have this text- "Hello World"
ifstream File("test_file.txt");
char ch;
File.get(ch);
cout << ch << endl; //it will display "H"
File.putback(ch);
cout << ch << endl; //it will again display "H"
File.get(ch);
cout << ch << endl; //it will display "H" again
File.close();
}

flush() - When dealing with the output file stream, the date you save in the file, is not actually immediately saved in it. There is a buffer, where it is kept, and when the buffer gets filled, then the data is put in the real file (on your disk). Then the buffer is emptied, and so on.
But if you want to save the data from the buffer, even if the buffer is still not full, use the flush() function. Just call it this way- FileHandle.flush(). And the data from the buffer will be put in the physical file, and the buffer will be emptied.
And something in addition (advanced)- The flush() function calls the sync() function of the associated streambuf. (The last sentence is from MSDN).
Conslusion
Well, I hope you can now do your File I/O programs! I covered everything I remembered of! I think it is more than enough for most of you! Even so, there are things I didn’t cover… but things I think you will never need. So, if you need even more advanced information on specific topic, search the web. Try google.com for example! But don’t ask me! I won’t answer any e-mails, asking me how to do certain program or else.
If you liked this tutorial, or not, I would be very happy to see your comments.
For more C++ tutorials, visit CPP Home

Wednesday, August 4, 2010

Socket Programming In C

Today we will discuss about Sockets programming paradigm, elements of Sockets applications, and the Sockets API. The Sockets API allows to develop applications that communicate over a network. The network can be a local private network or the public Internet. An important item about Sockets programming is that it's neither operating system specific nor language specific. Sockets applications can be written in the Ruby scripting language on a GNU/Linux host or in C on an embedded controller. This freedom and flexibility are the reasons that the BSD4.4 Sockets API is so popular.


Layered Model of Networking



Sockets programming uses the layered model of packet communication as shown in the figure below. At the top is the application layer, which is where the applications exist (those that utilize Sockets for communication). Below is the application layer defines the Sockets layer. This isn't actually a layer, but it is shown to illustrate where the API is located. The Sockets layer sits on top of the transport layer. The transport layer provides the transport protocols. Next is the network layer, which provides among other things routing over the Internet. This layer is occupied by the Internet Protocol, or IP. Finally, is the physical layer driver, which provides the means to introduce packets onto the physical network.



Sockets API Summary



The networking API for C provides a mixed set of functions for the development of client and server applications. Some functions are used by only server-side sockets, whereas others are used solely by client-side sockets (most are available to both).

Creating and Destroying Sockets

The first step of any Sockets-based application is to create a socket.The socket function provides the following prototype:

Code:
int socket( int domain, int type, int protocol );
The socket object is represented as a simple integer and is returned by the socket function. Three parameters must be passed to define the type of socket to be created. Right now, you are interested primarily in stream (TCP) and datagram (UDP) sockets, but many other types of sockets can be created. In addition to stream and datagram, a raw socket is also illustrated by the following code snippets:

Code:
myStreamSocket = socket( AF_INET, SOCK_STREAM, 0 );
myDgramSocket = socket( AF_INET, SOCK_DGRAM, 0 );
myRawSocket = socket( AF_INET, SOCK_RAW, IPPROTO_RAW );
The AF_INET symbolic constant indicates that we are using the IPv4 Internet protocol. After this, the second parameter (type) defines the semantics of communication. For stream communication (using TCP), you use the SOCK_STREAM type, and for datagram communication (using UDP), you specify SOCK_DGRAM. The third parameter can define a particular protocol to use, but only the types exist for stream and datagram, so this third parameter is left as zero in those cases.

When we've finished with a socket, we must close it. The close prototype is defined as follows:

Code:
int close( sock );
After close is called, no further data can be received through the socket. Any data queued for transmission is given some amount of time to be sent before the connection physically closes.

Socket Addresses

For socket communication over the Internet (domain AF_INET), we use the sock-addr_in structure for naming purposes.

Code:
struct sockaddr_in 
{
int16_t sin_family;
uint16_t sin_port;
struct in_addr sin_addr;
char sin_zero[8];
};
struct in_addr
{
uint32_t s_addr;
};
For Internet communication, we use AF_INET solely for sin_family. Field sin_port defines your specified port number in network byte order. Therefore, we must use htons to load the port and ntohs to read it from this structure. Field sin_addr is, through s_addr, a 32-bit field that represents an IPv4 Internet address.IPv4 addresses are 4-byte addresses. Often the sin_addr is set to INADDR_ANY, which is the wildcard. When you're accepting connections (server socket), this wildcard accepts connections from any available interface on the host. For client sockets, this is commonly left blank. For a client, sin_addr is set to the IP address of a local interface, this restricts outgoing connections to that interface.

Now let us take look at a quick example of addressing for both a client and a server. First, in this example we create the socket address (later to be bound to your server socket) that permits incoming connections on any interface and port 48000.
Code:
int servsock;
struct sockaddr_in servaddr;
servsock = socket( AF_INET, SOCK_STREAM, 0);
memset( &servaddr, 0, sizeof(servaddr) );
servaddr.sin_family = AF_INET;
servaddr.sin_port = htons( 48000 );
servaddr.sin_addr.s_addr = inet_addr( INADDR_ANY );
Next, we create a socket address that permits a client socket to connect to your previously created server socket.

Code:
int clisock;
struct sockaddr_in servaddr;
clisock = socket(AF_INET, SOCK_STREAM, 0);
memset(&servaddr, 0, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_port = htons(48000);
servaddr.sin_addr.s_addr = inet_addr("192.168.1.1");
Note the similarities between these two code segments. The difference,is that the server uses the address to bind to itself as an advertisement. The client uses this information to define to whom it wants to connect.

Socket Primitives



Now I will look at a number of other important server-side socket control primitives.

bind

The bind function provides a local naming capability to a socket. This can be used to name either client or server sockets, but it is used most often in the server case.

The bind function is provided by the following prototype:

Code:
int bind( int sock, struct sockaddr *addr, int addrLen );
The socket to be named is provided by the sock argument, and the address structure previously defined is defined by addr. Note that the structure here differs from the address structure discussed previously. The bind function can be used with a variety of different protocols, but when we are using a socket created with AF_INET, we must use the sockaddr_in. Therefore, as shown in the following example, we cast our sockaddr_in structure as sockaddr.

Code:
err = bind( servsock, (struct sockaddr *)&servaddr,sizeof(servaddr));
Using the address structure created in the server example in the previous address section, we bind the name defined by servaddr to our server socket servsock.

Recall that a client application can also call bind to name the client socket. This isn't used often, because the Sockets API dynamically assigns a port to us.

listen

Before a server socket can accept incoming client connections, it must call the listen function to declare this willingness. The listen function is provided by the following function prototype:

Code:
int listen( int sock, int backlog );
The sock argument represents the previously created server socket, and the backlog argument represents the number of outstanding client connections that might be queued. Within GNU/Linux, the backlog parameter (post 2.2 kernel version) represents the number of established connections pending on accept for the application layer protocol. Other operating systems might treat this differently.

accept

The accept call is the final call made by servers to accept incoming client connections. Before accept can be called, the server socket must be created, a name must be bound to it, and listen must be called. The accept function returns a socket descriptor for a client connection and is provided by the following function prototype:

Code:
int accept( int sock, struct sockaddr *addr, int *addrLen );
In practice, two examples of accept are commonly seen. The first represents the case in which we need to know who connected to us. This requires the creation of an address structure that is not initialized.
Code:
struct sockaddr_in cliaddr;
int cliLen;
cliLen = sizeof( struct sockaddr_in );
clisock = accept( servsock, (struct sockaddr *)cliaddr, &cliLen );
The call to accept blocks until a client connection is available. Upon return, the clisock return value contains the value of the new client socket, and cliaddr represents the address for the client peer (host address and port number).

The alternate example is commonly found when the server application isn't interested in the client information. This one typically appears as follows:

Code:
cliSock = accept( servsock, (struct sockaddr *)NULL, NULL );
In this case, NULL is passed for the address structure and length. The accept function then ignores these parameters.

connect

The connect function is used by client Sockets applications to connect to a server. Clients must have created a socket and then defined an address structure containing the host and port number to which they want to connect. The connect function is provided by the following function prototype:

Code:
int connect( int sock, (struct sockaddr *)servaddr, int addrLen );
The sock argument represents the client socket, created previously with the Sockets API function. The servaddr structure is the server peer to which you want to connect . Finally, we must pass in the length of your servaddr structure so that connect knows we are passing in a sockaddr_in structure.

The following code shows a complete example of connect:

Code:
int clisock;
struct sockaddr_in servaddr;
clisock = socket( AF_INET, SOCK_STREAM, 0);
memset( &servaddr, 0, sizeof(servaddr) );
servaddr.sin_family = AF_INET;
servaddr.sin_port = htons( 48000 );
servaddr.sin_addr.s_addr = inet_addr( "192.168.1.1" );
connect( clisock, (struct sockaddr_in *)&servaddr, sizeof(servaddr) );
The connect function blocks until either an error occurs or the three-way handshake with the server finishes. Any error is returned by the connect function.

Sockets I/O



A variety of API functions exist to read data from a socket or write data to a socket. Two of the API functions (recv, send) are used exclusively by sockets that are connected (such as stream sockets), whereas an alternative pair (recvfrom, sendto) is used exclusively by sockets that are unconnected (such as datagram sockets).

Connected Socket Functions

The send and recv functions are used to send a message to the peer socket endpoint and to receive a message from the peer socket endpoint. These functions have the following prototypes:

Code:
int send( int sock, const void *msg, int len, unsigned int flags );
int recv( int sock, void *buf, int len, unsigned int flags );
The send function takes as its first argument the socket descriptor from which to send the msg. The msg is defined as a (const void *) because the object referenced by msg is not altered by the send function. The number of bytes to be sent in msg is contained by the len argument. Finally, a flags argument can alter the behavior of the send call. An example of sending a string through a previously created stream socket is shown as follows:

Code:
strcpy( buf, "Hello\n");
send( sock, (void *)buf, strlen(buf), 0);
In this example, our character array is initialized by the strcpy function. This buffer is then sent through sock to the peer endpoint, with a length defined by the string length function, strlen. To see flags use let us take a look at one side effect of the send call. When send is called, it can block until all of the data contained within buf has been placed on the socket's send queue. If not enough space is available to do this, the send function blocks until space is available. If we want to avoid this blocking behavior and instead want the send call to simply return if sufficient space is available, we can set the MSG_DONTWAIT flag, such as follows:

Code:
send( sock, (void *)buf, strlen(buf), MSG_DONTWAIT);
The return value from send represents either an error (less than 0) or the number of bytes that were queued to be sent. Completion of the send function does not imply that the data was actually transmitted to the host, only that it is queued on the socket's send queue waiting to be transferred.
The recv function mirrors the send function in terms of an argument list. Instead of sending the data pointed to be msg, the recv function fills the buf argument with the bytes read from the socket. We must define the size of the buffer so that the network protocol stack doesn't overwrite the buffer, which is defined by the len argument. Finally, we can alter the behavior of the read call using the flags argument. The value returned by the recv function is the number of bytes now contained in the msg buffer, or -1 on error. An example of the recv function is as follows:

Code:
#define MAX_BUFFER_SIZE        50
char buffer[MAX_BUFFER_SIZE+1];
...
numBytes = recv( sock, buffer, MAX_BUFFER_SIZE, 0);
At completion of this example, numBytes contains the number of bytes that are contained within the buffer argument.
We can peek at the data that's available to read by using the MSG_PEEK flag. This performs a read, but it doesn't consume the data at the socket. This requires another recv to actually consume the available data. An example of this type of read is illustrated as follows:

Code:
numBytes = recv( sock, buffer, MAX_BUFFER_SIZE, MSG_PEEK);
This call requires an extra copy (the first to peek at the data, and the second to actually read and consume it). More often than not, this behavior is handled instead at the application layer by actually reading the data and then determining what action to take.

Unconnected Socket Functions

The sendto and recvfrom functions are used to send a message to the peer socket endpoint and receive a message from the peer socket endpoint. These functions have the following prototypes:

Code:
int sendto( int sock, const void *msg, int len,unsigned int flags,const struct sockaddr *to, int tolen );
int recvfrom( int sock, void *buf, int len,unsigned int flags,struct sockaddr *from, int *fromlen );
The sendto function is used by an unconnected socket to send a datagram to a destination defined by an initialized address structure. The sendto function is similar to the previously discussed send function, except that the recipient is defined by the to structure. An example of the sendto function is shown in the following code:

Code:
struct sockaddr_in destaddr;
int sock;
char *buf;
...
memset( &destaddr, 0, sizeof(destaddr) );
destaddr.sin_family = AF_INET;
destaddr.sin_port = htons(581);
destaddr.sin_addr.s_addr = inet_addr("192.168.1.1");
sendto( sock, buf, strlen(buf), 0,(struct sockaddr *)&destaddr, sizeof(destaddr) );
In this example, the datagram (contained with buf) is sent to an application on host 192.168.1.1, port number 581. The destaddr structure defines the intended recipient for the datagram.
As with the send function, the number of characters queued for transmission is returned, or -1 if an error occurs.

The recvfrom function provides the ability for an unconnected socket to receive datagrams. The recvfrom function is again similar to the recv function, but an address structure and length are provided. The address structure is used to return the sender of the datagram to the function caller. This information can be used with the sendto function to return a response datagram to the original sender.

An example of the recvfrom function is shown in the following code:

Code:
#define MAX_LEN 100
struct sockaddr_in fromaddr;
int sock, len, fromlen;
char buf[MAX_LEN+1];
...
fromlen = sizeof(fromaddr);
len = recvfrom( sock, buf, MAX_LEN, 0,(struct sockaddr *)&fromaddr, &fromlen );
This blocking call returns when either an error occurs (represented by a -1 return) or a datagram is received (return value of 0 or greater). The datagram is contained within buf and has a length of len. The fromaddr contains the datagram sender, specifically the host address and port number of the originating application.

Socket Options

Socket options permit an application to change some of the modifiable behaviors of sockets and the functions that manipulate them. For example, an application can modify the sizes of the send or receive socket buffers or the size of the maximum segment used by the TCP layer for a given socket.

The functions for setting or retrieving options for a given socket are provided by the following function prototypes:

Code:
int getsockopt( int sock, int level, int optname,void *optval, socklen_t *optlen );
int setsockopt( int sock, int level, int optname,const void *optval, socklen_t optlen );
First, we define the socket of interest using the sock argument. Next, we must define the level of the socket option that is being applied.

The level argument can be :
  • SOL_SOCKET for socket-layer options,
  • IPPROTO_IP for IP layer options, and
  • IPPROTO_TCP for TCP layer options.
The specific option within the level is applied using the optname argument. Arguments optval and optlen define the specifics of the value of the option. optval is used to get or set the option value, and optlen defines the length of the option. This slightly complicated structure is used because structures can be used to define options.

Now let us take a look at an example for both setting and retrieving an option. In the first example, we retrieve the size of the send buffer for a socket.

Code:
int sock, size, len;
...
getsockopt( sock, SOL_SOCKET, SO_SNDBUF, (void *)&size,
(socklen_t *)&len );
printf( "Send buffer size is &d\n", size );
Now let us take a look at a slightly more complicated example. In this case, we're going to set the [b]Socket linger option[b]. Socket linger allows you to change the behavior of a stream socket when the socket is closed and data is remaining to be sent. After close is called, any data remaining attempts to be sent for some amount of time. If after some duration the data cannot be sent, then the data to be sent is abandoned. The time after the close when the data is removed from the send queue is defined as the linger time. This can be set using a special structure called linger, as shown in the following example:

Code:
struct linger ling;
int sock;
...
ling.l_onoff = 1; /* Enable */
ling.l_linger = 10; /* 10 seconds */
setsockopt( sock, SOL_SOCKET, SO_LINGER,(void *)&ling, sizeof(struct linger) );
After this call is performed, the socket waits 10 seconds after the socket close before aborting the send.

Other Miscellaneous Functions

Now it's time to look at a few miscellaneous functions from the Sockets API and the capabilities they provide. The three function prototypes discussed in this section are shown in the following code:

Code:
struct hostent *gethostbyname( const char *name );
int getsockname( int sock, struct sockaddr *name, socklen_t*namelen );
int getpeername( int sock, struct sockaddr *name, socklen_t*namelen );
Function gethostbyname provides the means to resolve a host and domain name (otherwise known as a fully qualified domain name, or FQDN) to an IP address. For example, the FQDN of www.microsoft.com might resolve to the IP address 64.4.31.252. Converting an FQDN to an IP address is important because all of the Sockets API functions work with number IP addresses (32-bit addresses) rather than FQDNs.

An example of the gethostbyname function is shown below:

Code:
struct hostent *hptr;
hptr = gethostbyname( "www.microsoft.com");
if (hptr == NULL) // can't resolve...
else
{
printf("Binary address is %x\n", hptr-> h_addr_list[0]);
}
Function gethostbyname returns a pointer to a structure that represents the numeric IP address for the FQDN (hptr->h_addr_list[0]). Otherwise, gethostbyname returns a NULL, which means that the FQDN could not be resolved by the local resolver. This call blocks while the local resolver communicates with the configured DNS servers.

Function getsockname permits an application to retrieve information about the local socket endpoint. This function, for example, can identify the dynamically assigned ephemeral port number for the local socket.

An example of its use is shown in the following code:

Code:
int sock;
struct sockaddr localaddr;
int laddrlen;
// Socket for sock created and connected.
...
getsockname( sock, (struct sockaddr_in *)&localaddr, &laddrlen );
printf( "local port is %d\n", ntohs(localaddr.sin_port) );
The reciprocal function of getsockname is getpeername. This permits you to gather addressing information about the connected peer socket. An example, similar to the getsockname example, is shown in the following code:

Code:
int sock;
struct sockaddr remaddr;
int raddrlen;
// Socket for sock created and connected.
...
getpeername( sock, (struct sockaddr_in *)&remaddr, &raddrlen );
printf( "remote port is %d\n", ntohs(remaddr.sin_port) );
In both examples, the address can also be extracted using the sin_addr field of the sockaddr structure.

Memory Management Basics

Memory is central to the operation of a modern computer System. Memory consists of a large array of words or bytes each with its own address. The CPU fetches instructions from memory according to the value of the program counter. These instructions may cause additional loading from and storing to specific memory addresses. I have discussed a typical instruction-execution cycle in the previous article. In this article I will discuss on basic hardware issues, the binding of symbolic memory addresses to actual physical addresses and distinguishing between logical and physical addresses.

Basic Hardware

Main memory and the registers built into the processor itself are the only storage that the CPU can access directly. There are machine instructions that take memory addresses as arguments, but none that take disk addresses. Therefore, any instructions in execution, and any data being used by the instructions, must be in one of these direct-access storage devices. If the data are not in memory, they must be moved there before the CPU can operate on them.

Registers that are built into the CPU are generally accessible within one cycle of the CPU clock. Most CPU can decode instructions and perform simple operations on register contents at the rate of one or more operations per clock tick. The same cannot be said of main memory, which is accessed via a transaction on the memory bus. Memory access may take many cycles of the CPU clock to complete, in which case the processor normally needs to stall, since it does not have the data required to complete the instruction that it is executing. The situation is intolerable because of the frequency of memory accesses. The remedy is to add fast memory between the CPU and main memory. A memory buffer used to accommodate a speed differential is called a cache.

Main memory is divided into two parts. One part is to hold the operating system instructions, where as the other part will hold the program which is currently being executed by the user (i.e., in a uni-programming). In a multiprogramming system, the user part is further subdivided, for accommodating multiple processes. The task of subdivision is carried out dynamically by the operating system is known as memory management. Memory management module of an Operating System is concerned with organization of main memory. Memory management is concerned with:
  • keeping track of the status of each memory location i.e. allocated or free.
  • determining allocation policy for memory.
  • reclaiming previously allocated memory.


Memory Management Schemes



There are two memory management schemes:
  • Single User Case-Mono Programming
  • Multiple User Case-Multi Programming
Single User-Mono Programming

It is a simple memory management scheme and associated with simple microcomputers. In this scheme memory is divided up between the OS and a single user process. The OS is protected from user programs (to prevent user program overwriting OS code).

Advantages
  • Simplicity
  • Small OS
Disadvantages
  • Poor utilization of memory. It is wasteful.
  • Poor utilization of processor.
  • User address space may contain information that is never used.
  • Low flexibility. User's job limited to the size of available memory.
Multiple Users-Multiprogramming

It is a memory management scheme in which a user can operate on more than one job at a time. Resources are distributed among jobs. In this scheme there are two problems- relocation and protection. The solution to this problem is to use register-base and limit register. We need to maximize the degree of multiprogramming i.e. the number of processes in memory.

Memory-Management Requirements



Memory management should satisfy the following requirements:
  • Relocation
  • Sharing
  • Protection
  • Logical organization
  • Physical organization.
Relocation

Relocation is a basic requirement of memory management. For simplification purposes let us assume that the process image occupies a contiguous region of main memory. The operating system need to know the location of:
  • Process control information
  • Execution stack
  • Entry point to begin the execution of a program.
    • ‘Processor’ must deal with memory references within the program.
    • ‘Branch instructions’ contain an address to reference the instruction to be executed next.
    • ‘Data reference instructions’ contain the address of the byte or word of data referenced.
The figure below depicts the above concept:



Sharing

Any protection mechanism must have the flexibility to allow several processes to access the same portion of main memory.

E.g., if numbers of processes are executing the same program then it is advantageous to allow each process to access the same copy of the program rather than its own separate copy.

Protection

Once we have two programs in memory at the same time there is a danger that one program can write to the address space of another program. Every process should be protected against unwanted interference by other processes. Satisfaction of the relocation requirement increases the difficulty of satisfying the protection requirement.CPU tend to support absolute addressing which means that code runs differently when loaded in different places.

It is not possible to check the absolute address at compile time. Most of the programming languages allow the dynamic calculation of address at run time.

Logical Organization

Main memory is organized as a linear or one-dimensional address space that consists of sequence of bytes or words. Secondary memory at its physical level is similarly organized. Most of the programs are organized into modules.

Advantages of Modules
  • Modules can be written and compiled independently
  • Protection (such as read-only, execute-only) is given to different modules.
  • Introduce mechanism by which modules can be shared among processes.
Physical Organization

Computer memory is organized into two levels:
  • Main memory - Main memory is a volatile memory and it provides fast access at relatively high cost.
  • Secondary memory - Secondary memory is a non-volatile memory and it is slower and cheaper than main memory.
The organization of the flow of information between main memory and secondary memory is a major system concern. It is impractical for the programmer, because of the following reasons.
  • Main memory available for a program plus its data, may be insufficient. In this case programmer must use the mechanism known as "overlaying". That is keep in memory only those instructions and data that are needed at any given time.
  • In a multiprogramming environment, programmer does not know how much space is available and that space is at where at the time of coding.
There are two main ways to make code relocatable:
  • We can have the compiler/linker mark all the address in the code and rewrite them all when the program is loaded. This adds start up overhead.
  • Use only relative addressing and require the OS to set a base register to the beginning of the code. This is particularly useful in base/limit protected system because the same base register can be used for relocation and protection.
  • Relocation without protection is dangerous. It is possible to create an absolute addressing instruction and use it to access some other processes memory.
  • A solution which solves both the relocation and protection problem is to use two registers called base and limit registers. The base register stores the start address of the position and the limit register holds the length of the portions.
  • Any address that is generated by the program has the base register added to it. In addition all addresses are checked to ensure that they are within the range of partition.
  • An additional benefit of this scheme is that if a program is moved within memory only its base register need to be amended.
Address Binding

Usually, a program resides on a disk as a binary executable file. To be executed, the program must be brought into memory and placed within a process. Depending on the memory management in use, the process may be moved between disk and memory during its execution. The processes on the disk that are waiting to be brought into memory for execution from the input queue.

The normal procedure is to select one of the processes in the input queue and to load that process into memory. As the process is executed, it accesses instructions and data from memory. Eventually, the process terminates, and its memory space is declared available.

Most systems allow a user process to reside in any part of the physical memory. Thus, although the address space of the computer starts at 00000, the first address of the user process need not be 00000. This approach affects the addresses that the user program can use. In most cases, a user program will go through several steps- some of which may be optional- before being executed. Addresses in the source program are generally symbolic (such as count). a compiler will typically bind these symbolic addresses to relocatable addresses(such as "14 bytes from the beginning of this module"). The linkage editor or loader will in turn bind the relocatable addresses to absolute addresses (such as 74014). Each binding is mapping from one address space to another.

Address Binding is a process which fixes a physical address to the logical address of a process' address space. There are various types of binding as below:
  • Compile time binding - If the program location is fixed and it is known at compile time where the process will reside in memory is called compile time binding. If at some later time the starting location changes then it will be necessary to recompile this code. The MS-DOS .COM format programs are bound at compile time.
  • Load time binding - If it is not known at compile time where the process will reside in memory, then the compiler must generate relocatable code. In this case, final binding is delayed until load time. If the starting address changes, we need only reload the user code to incorporate this changed value.
  • Execution time binding - If the process can moved during its execution from one memory segment to another, then binding must be delayed until run time. Special hardware must be available for this scheme to work. Most general-purpose operating systems use this method.

Logical & Physical Address Space



The concept of logical address space that is bound to a separate physical address space is central to proper memory management.

Logical address is the address that is generated by the CPU. It is also referred to as virtual address.

Physical address is the address as seen by the memory management unit that is the one that is loaded into the memory address register of the memory.

For example, P2 is a program, with size 256 KB. But program is loaded in the main memory from 13000 to 13256 KB; this address is called physical address.



Physical address space = Logical address space + relocation register value

13256 = 256 + 13000

In compile-time and load-time address-binding schemes logical and physical addresses are same. Whereas in execution-time the address-binding schemes will differ. Here logical address is virtual-address.

The set of all logical addresses (generated by a program) is referred ta as Logical address space. The set of all Physical addresses corresponding to these logical addresses is referred to as physical address space. The run-time mapping from logical (virtual) to physical addresses is done by the MMU (memory-management unit), which is a hardware device.We can choose from many different methods to accomplish such mapping. This will be discussed in the next article.

Base register is called relocation register. User program never sees the real physical addresses. User program deals with the logical addresses only.