Implementing ls -R command in linux

Question

I want to know how ls -R implemented in C language. Is it use the recursion algorithm?

Recursing in your case might cause stack - overflow, if you do not skip the directories . and .. — Anirudh Ramanathan
– Anirudh Ramanathan, Commented Oct 22, 2012 at 6:48
There is no single recursion algorithm. But some algorithms (actually, set of functions) may be [co-]*recursive* and recursion is a feature of such algorithms. — Basile Starynkevitch
– Basile Starynkevitch, Commented Oct 22, 2012 at 7:21

Martin R · Accepted Answer · 2012-10-22 06:52:29Z

2

"ls" (at least the implementations that I know of) use fts_open, fts_read ... to traverse a file hierarchy. These are "non-recursive" methods which maintain a list of the visited directories internally.

Use "man fts_read" or http://linux.die.net/man/3/fts_read to get more information about these functions.

edited Oct 22, 2012 at 6:52

answered Oct 22, 2012 at 6:46

Martin R

541k98 gold badges1.3k silver badges1.4k bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ncat · Accepted Answer · 2012-10-22 06:42:06Z

2

Just for completeness, ls is part of GNU coreutils: www.gnu.org/software/coreutils/.

answered Oct 22, 2012 at 6:42

Ncat

4153 silver badges10 bronze badges

Comments

Anirudh Ramanathan · Accepted Answer · 2012-10-22 07:29:51Z

2

Here's the relevant code-block

<includes...>
int f_recursive;        /* ls subdirectories also */
while ((ch = getopt(argc, argv, "1ABCFLRSTWabcdfghiklmnopqrstuwx")) != -1) {
    switch (ch) {
.
.
.
.
case 'R':
    f_recursive = 1;
    break;

Later, the directory listing is done recursively because of the above int flag.

See source here.

Recursing in your case might cause stackoverflow, if you do not skip the directories . and ...

It doesn't seem like any recursion is done within ls.c though. It uses fts-functions, like fts_children to traverse the heirarchies. You could use the same.

edited Oct 22, 2012 at 7:29

answered Oct 22, 2012 at 6:36

Anirudh Ramanathan

46.8k24 gold badges137 silver badges195 bronze badges

4 Comments

Martin R Over a year ago

The variable is called f_recursive, but the implementation is not recursive: the traverse() function (from the linked source) does not call itself recursively.

Anirudh Ramanathan Over a year ago

@MartinR I hadn't looked in detail. Will update answer. Thanks.

Anirudh Ramanathan Over a year ago

@MartinR, fts_children seems to do all the work, fetching the listing, so I guess there isn't any recursion within ls.c but within, fts, there is.

Martin R Over a year ago

I am quite sure that fts does not use recursion internally, but I had written that already in my answer.

Shreevardhan · Accepted Answer · 2015-07-07 11:30:04Z

This is a simple linux ls -R implementation in C. It gives coloured output similar to ls

#include <stdio.h>
#include <dirent.h>
#include <string.h>
#define GREEN   "\x1b[32m"
#define BLUE    "\x1b[34m"
#define WHITE   "\x1b[37m"

void Usage() {
    fprintf(stderr, "\nUsage: exec [OPTION]... [DIR]...\n");
    fprintf(stderr, "List DIR's (directory) contents\n");
    fprintf(stderr, "\nOptions\n-R\tlist subdirectories recursively\n");
    return;
}

void RecDir(char *path, int flag) {
    DIR *dp = opendir(path);
    if(!dp) {
        perror(path);
        return;
    }
    struct dirent *ep;
    char newdir[512];
    printf(BLUE "\n%s :\n" WHITE, path);
    while((ep = readdir(dp)))
        if(strncmp(ep->d_name, ".", 1))
            printf(GREEN "\t%s\n" WHITE, ep->d_name);
    closedir(dp);
    dp = opendir(path);
    while((ep = readdir(dp))) if(strncmp(ep->d_name, ".", 1)) {
        if(flag && ep->d_type == 4) {
            sprintf(newdir, "%s/%s", path, ep->d_name);
            RecDir(newdir, 1);
        }
    }
    closedir(dp);
}

int main(int argc, char **argv)
{
    switch(argc) {
    case 2:
        if(strcmp(argv[1], "-R") == 0) Usage();
        else RecDir(argv[1], 0);
        break;
    case 3:
        if(strcmp(argv[1], "-R") == 0) RecDir(argv[2], 1);
        else Usage();
        break;
    default: Usage();
    }
    return 0;
}

Techie Manoj · Accepted Answer · 2012-10-22 06:45:39Z

1

I think this would help you.

 void listDir(char *dirName)
 {
     DIR* dir;
     struct dirent *dirEntry;
     struct stat inode;
     char name[1000];
     dir = opendir(dirName);
     if (dir == 0) {
        perror ("Eroare deschidere fisier");
        exit(1);
     }
     while ((dirEntry=readdir(dir)) != 0) {
        sprintf(name,"%s/%s",dirName,dirEntry->d_name); 
        lstat (name, &inode);

        // test the type of file
        if (S_ISDIR(inode.st_mode))
           printf("dir ");
        else if (S_ISREG(inode.st_mode))
           printf ("fis ");
        else
          if (S_ISLNK(inode.st_mode))
            printf ("lnk ");
        else;
          printf(" %s\n", dirEntry->d_name);
  }

answered Oct 22, 2012 at 6:45

Techie Manoj

4223 silver badges14 bronze badges

Collectives™ on Stack Overflow

Implementing ls -R command in linux

5 Answers 5

Comments

Comments

4 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related