Directory implementation

The selection of directory-allocation and directory-management algorithms significantly affects the efficiency, performance, and reliability of the file system. In this section, we discuss the trade-offs involved in choosing one of these algorithms.

Linear List

The simplest method of implementing a directory is to use a linear list of file names with pointers to the data blocks. This method is simple to program but time-consuming to execute. To create a new file., we must first search the directory to be sure that no existing file has the same name. Then, we add a new entry at the end of the directory. To delete a file, we search the directory for the named file, then release the space allocated to it.

To reuse the directory entry, we can do one of several things. We can mark the entry as unused (by assigning it a special name, such as an all-blank name, or with a used-unused, bit in each entry), or we can attach it to a list of free directory entries. A third alternative is to copy the last entry in the directory into the freed location and to decrease the length of the directory. A linked list can also be used to decrease the time required to delete a file.

The real disadvantage of a linear list of directory entries is that finding a file requires a linear search. Directory information is used frequently, and users will notice if access to it is slow. In fact, many operating systems implement a software cache to store the most recently used directory information. A cache hit avoids the need to constantly reread the information from disk. A sorted list allows a binary search and decreases the average search time.

However, the requirement that the list be kept sorted may complicate creating and deleting files, since we may have to move substantial amounts of directory information to maintain a sorted directory. A more sophisticated tree data structure, such as a B-tree, might help here. An advantage of the sorted list is that a sorted directory listing can be produced without a separate sort step.

 Hash Table

Another data structure used for a file directory is a hash table. With this method, a linear list stores the directory entries, but a hash data structure is also used. The hash table takes a value computed from the file name and returns a pointer to the file name in the linear list. Therefore, it can greatly decrease the directory search time. Insertion and deletion are also fairly straightforward, although some provision must be made for collisions—situations in which two file names hash to the same location.

The major difficulties with a hash table are its generally fixed size and the dependence of the hash function on that size. For example, assume that we make a linear-probing hash table that holds 64 entries. The hash function converts file names into integers from 0 to 63, for instance, by using the remainder of a division by 64. If we later try to create a 65th file, we must enlarge the directory hash table—say, to 128 entries. As a result, we need a new hash function that must map file names to the range 0 to 127, and we must reorganize the existing directory entries to reflect their new hash-function values. Alternatively, a chained-overflow hash table can be used. Each hash entry can be a linked list instead of an individual value, and we can resolve collisions by adding the new entry to the linked list. Lookups may be somewhat slowed, because searching for a name might require stepping through a linked list of colliding table entries. Still, this method is likely to be much faster than a linear search through the entire directory.

binary files

library function programe

1. #include <iostream>
2. #include <cmath>
3. using namespace std;
5. int main()
6. {
7. double x = 10.25, result;
8. result = sqrt(x);
9. cout << "Square root of " << x << " is " << result << endl;
11. return 0;
12. }

The pow() function computes a base number raised to the power of exponent number.

#include <iostream>
#include <cmath>
using namespace std;

int main ()
{
	long double base = 4.4, result;
	int exponent = -3;
	result = pow(base, exponent);
	cout << base << "^" << exponent << " = " << result << endl;
	
	
	// Both arguments int
	// pow() returns double in this case
	int intBase = -4, intExponent = 6;
	double answer;
	answer = pow(intBase, intExponent);
	cout << intBase << "^" << intExponent << " = " << answer;
	
	return 0;
}

When you run the program, the output will be:

4.4^-3 = 0.0117393
-4^6 = 4096 

The abs() function in C++ returns the absolute value of the argument.

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    double x = -87.91, result;
    
    result = abs(x);
    cout << "abs(" << x << ") = |" << x << "| = " << result << endl;

    return 0;
}


























When you run the program, the output will be:

abs(-87.91) = |-87.91| = 87.91
The strlen() function in C++ returns the length of the given string.

#include <cstring>
#include <iostream>

using namespace std;

int main()
{
    char str1[] = "This a string";
    char str2[] = "This is another string";
    
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    cout << "Length of str1 = " << len1 << endl;
    cout << "Length of str2 = " << len2 << endl;
    if (len1 > len2)
        cout << "str1 is longer than str2";
    else if (len1 < len2)
        cout << "str2 is longer than str1";
    else
        cout << "str1 and str2 are of equal length";

    return 0;
}



When you run the program, the output will be:
Length of str1 = 13
Length of str2 = 22
str2 is longer than str1
The toupper() function in C++ converts a given character to uppercase.

#include <cctype>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

int main()
{
    char str[] = "John is from USA.";

    cout << "The uppercase version of \"" << str << "\" is " << endl;

    for (int i=0; i<strlen(str); i++)
        putchar(toupper(str[i]));
    
    return 0;
}



When you run the program, the output will be:
The uppercase version of "John is from USA." is 
JOHN IS FROM USA.


The isupper() function in C++ checks if the given character is a uppercase character or not.

#include <cctype>
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    char str[] = "This Program Converts ALL UPPERCASE Characters to LOWERCASE";

    for (int i=0; i<strlen(str); i++)
    {
        if (isupper(str[i]))
            /*  Converting uppercase characters to lowercase  */
            str[i] = str[i] + 32;
    }

    cout << str;
    return 0;
}



When you run the program, the output will be:
this program converts all uppercase characters to lowercase