0

I am writing a C program like,

void printdir (char*);

int main () {
    printf ("Directory scan of /home: \n");
    printdir ("/home/fahad/");
    exit (0);
}

void printdir (char *dir) {
    struct dirent *entry;
    DIR *dp = opendir (dir);

    if (dp == NULL) {
        fprintf (stderr, "Cannot open dir:%s\n", dir);
        return;
    }

    chdir (dir);
    while ((entry = readdir(dp)) != NULL)
        printf ("%s\n",entry -> d_name);
    closedir (dp);
}

Interestingly, it shows output in an unexpected way. Considering the fact that whenever a directory is created in UNIX. First two entries are created inside this directory one is . and other is ... So basically their inode numbers should be less than the directory entries created through mkdir () or open () (for directory and file respectively).

My question is, in what order readdir () system call reads the directory entries? Because I don't get first who entries . and ... Why is that so?

Fahad Siddiqui
  • 1,829
  • 1
  • 19
  • 41
  • 4
    The order of directory entries is unspecified. Often depends on the file system, and on many platforms will appear absolutely random. – nos May 14 '14 at 19:51
  • It means there isn't some specific structure of directory entries? How readdir () works? – Fahad Siddiqui May 14 '14 at 19:59
  • 3
    Yes that's what it means. readdir() retreives directory entries from the kernel, which asks the file system to return it, which looks up the directory entries in a platform and filesystem specific way, The entries could be stored in a B\* tree, a linked list etc. - the details which are far to complicated to easily be understood without reading the source code. – nos May 14 '14 at 20:04
  • 2
    There's no guarantee that the inode numbers of the files will be larger than the inode number of the directory. On a clean disk where you've not deleted anything, then it probably will be like that, but after files have been deleted, there's no guarantee about the ordering. I don't know whether it is written in stone, but de facto, the first two entries in a directory are `.` and `..`, and since they're never removed until the directory is removed, those entries are effectively always the first two. After that, the order is undefined. It seems improbable that they aren't printed. – Jonathan Leffler May 14 '14 at 20:17
  • 1
    There is probably only one single thing you can learn from this: never assume anything that isn't explicitely documented. – mfro Jun 18 '14 at 13:29

3 Answers3

3

Try skipping the "." and ".." entries, as follows:

DIR* dirp;
struct dirent  *dp=NULL;
char* fname;
if( !(dirp=opendir(dname)) ) {
    int ec=errno;
    printf("completed:-1:cannot opendir %s (%d)\n",dname,ec);
    return(-1);
}
while ((dp = readdir(dirp)) != NULL) {
    if( strcmp(dp->d_name,".")==0 ) continue;
    if( strcmp(dp->d_name,"..")==0 ) continue;
    fname=dp->d_name;
    sprintf(pathname,"%s/%s",dname,fname);
}

See this answer which notes that since the order is not stated as predictable, one should not assume any order. The above code will gives a sample of how to handle (avoid) these entries (in the typical use-case of traversing a directory hierarchy). The order is probably based upon the order of the files appearing in the directory inodes.

Community
  • 1
  • 1
ChuckCottrill
  • 4,360
  • 2
  • 24
  • 42
  • 1
    This wasn't my question. I don't want to skip the "." and "..". I wan't to know the order in which readdir parse the whole directory entries one by one. – Fahad Siddiqui May 14 '14 at 19:56
  • The order is unspecified. It could be the first in the list, or the last in the list or anywhere in between. It could change depending on the OS reading the device (Windows might present a different order to Linux), or different between OS versions or device drivers. Your code will have to handle those situations, and the above answer does that. – Neil Jun 18 '14 at 10:22
2

readdir() doesn't return entries in any particular order. As others mentioned, the order will depend on the particular file system in question.

For example, the Berkeley UFS file system uses an unsorted linked-list. See the description of the direct structure on page 744 of http://ptgmedia.pearsoncmg.com/images/0131482092/samplechapter/mcdougall_ch15.pdf. The binary content of a directory consists of a stream of variable-length records, each of which contains the inode number, record length, string length (of the filename) and the string data itself. readdir() works by walking the linked list (using the record length to know where each record begins relative to the previous record) and returning whatever it finds.

The list of records is not typically optimized, so filenames appear on the list (more or less) in the order the files were created. But not quite, because holes (resulting from deleted files) will be filled with new filenames if they are small enough to fit.

Now, not all file systems represent directories the way UFS does. A file system that keeps directory data in a binary tree may choose to implement readdir() as an in-order traversal of that tree, which would present files sorted by whatever attributes it uses as key for the tree. Or it might use a pre-order traversal, which would not return the records in a sorted order.

Because applications can not know the nature of the file system's implementation (and that each mounted volume can potentially use a different file system), applications should never assume anything about the order of entries that readdir() returns. If they require the entries to be sorted, they must read the entire directory into memory and do their own sorting.

This is why, for example, the ls command can take a long time to display output when run against a large directory. It needs to sort the entire list of names (and determine the longest name, in order to compute the column width) before it can display any output. This is also why ls -1U (disable sorting and display in one column) will produce output immediately on such directories.

David C.
  • 777
  • 8
  • 18
2

First two entries are created inside this directory one is . and other is ... So basically their inode numbers should be less than the directory entries created through mkdir () or open ()(for directory and file respectively).

Yes, your understanding about the inode numbers is correct. To validate this we can write simple c++ program to store the inode/name in map.

 std::map<ino_t, std::string>  entries;
 std::pair<ino_t, std::string> en;
 while ((entry = readdir(dp)) != NULL) {
          en.first = entry->d_ino;
          en.second = entry->d_name;
          entries.insert(en);
        printf ("%s\n",entry -> d_name);
  }


  "entries in GDB"
  ================
  [5114862] = "..",
  [5114987] = ".",
  [5115243] = "taop",
  [5115623] = "c++11_study",
  [5115651] = "volume-3",
  [5115884] = "gtkmm",
  [5116513] = "basic",
  [5116733] = "program",
  [5116794] = "bakwas",
  [5116813] = "a.out",
  [5116818] = "foo",

This way we can validate about the order of inode number and "." & ".." are the less than other directory & file entry.

My question is, in what order readdir () system call reads the directory entries? Because I don't get first who entries . and ... Why is that so?

From The Book "Advanced Programming in the UNIX® Environment by W. Richard Stevens", we can get the following:

The opendir function initializes things so that the first readdir reads the first entry in the directory. The ordering of entries within the directory is implementation dependent and is usually not alphabetical. So their order are not defined and for the above program, readdir() gave in the following order.

Output from readdir()
=====================
c++11_study
taop
volume-3
basic
.
gtkmm
foo
program
a.out
..
bakwas
Mantosh Kumar
  • 5,659
  • 3
  • 24
  • 48