Recursion and linked lists in C

Question

I'm working to create a function that takes in a path and reads all the files within it and creates a linked lists. Reading the directory works well but I'm having difficulty creating and storing the relevant information in a linked list for use later.

Heres the structure I'm using currently:

typedef struct searchPool searchPool;
struct searchPool{

    char * path;
    char * fileName;
    char *pathFile;

    searchPool * next;

};

The function to create a new element of the type 'SearchPool' is defined as such:

searchPool * mallocStructPool (char * path, char * fileName, char * filePath ) {

    searchPool * element = (searchPool*)malloc(sizeof(searchPool));
    element->path = malloc(sizeof(char * ));
    element->fileName = malloc(sizeof(char * ));
    element->pathFile = malloc(sizeof(char * ));

    element->path = path;
    element->fileName = fileName;
    element->pathFile = filePath;

    element->next = NULL;

    return element;
}

Finally the recursive function that take the list's head is written as such (code commented if you scroll to the right):

void listDir(char * path, searchPool * head){
    DIR * d = opendir(path);        // open the path

    searchPool * element;                                                                   // create new Element of type SearchPool
    struct dirent * dir;                                                                    // for the directory entries

    while ((dir = readdir(d)) != NULL) {                                                    // if we were able to read somehting from the directory
        if(dir-> d_type != DT_DIR) {                                                        // if the type is not directory just print it with blue

            char * s = malloc(sizeof(char*)+1);                                             // variable to concatenate
            s = concat(path, dir->d_name);                                                  // concatenate path and filename together
            //printf("%s\n",s);

            element = mallocStructPool(dir->d_name, path, s);                               // malloc new element and set variables

            head->next = element;
            element->next = NULL;

            free(s);

        } else 
        if(dir -> d_type == DT_DIR && strcmp(dir->d_name,".")!=0 && strcmp(dir->d_name,"..")!=0 ) {// if it is a directory
            char d_path[255];                                                               // here I am using sprintf which is safer than strcat
            sprintf(d_path, "%s/%s", path, dir->d_name);
            listDir(d_path, element);                                                       // recall with the new path
        }
    }
    closedir(d);                                                                            // finally close the directory
}

The problem is that when the function listDir() is called it only ends up printing the first path that I give it in it's parameters and the rest is ignored. Do I have to return the new element in listDir() after each run? I don't see where I'm going wrong.

Any help is appreciated. Thanks for your time.

You are using malloc(sizeof(char*)) incorrectly, leaking memory. — user3185968
– user3185968, Commented Jan 14, 2017 at 17:23
@user100000 I re-evaluated. So you have a head outside the function. Call it h_ptr1. You pass it to your function, which makes a copy. Call that h_ptr2. You add several elements to the copy, h_ptr2. You return, and you've lost access to h_ptr2, leaving only the h_ptr1 (still points to NULL) and a memory leak. See stackoverflow.com/questions/7271647/… — synchronizer
– synchronizer, Commented Jan 14, 2017 at 17:33
@synchronizer I didnt realize I was making a copy of head when I was passing it to my listDir function. Ill look into this. Thank you. — user100000
– user100000, Commented Jan 14, 2017 at 17:39

Community · Accepted Answer · 2017-05-23 10:29:21Z

3

Your code don't make sense. You don't need to allocate a struct and his members. Plus don't cast the return of malloc. You don't check the return of malloc(). And you don't copy the strings.

In your second function you should return the linked list and check return function of opendir().

Here a example:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <dirent.h>

typedef struct searchPool searchPool;
struct searchPool {
  char *path;
  char *fileName;
  char *pathFile;
  searchPool *next;
};

static searchPool *mallocStructPool(char *path, char *fileName) {

  searchPool *element = malloc(sizeof *element);
  if (element == NULL) {
    goto error;
  }

  size_t path_size = strlen(path);
  element->path = malloc(path_size + 1);
  if (element->path == NULL) {
    goto free_element;
  }

  size_t fileName_size = strlen(fileName);
  element->fileName = malloc(fileName_size + 1);
  if (element->fileName == NULL) {
    goto free_path;
  }

  element->pathFile = malloc(path_size + 1 + fileName_size + 1);
  if (element->pathFile == NULL) {
    goto free_fileName;
  }

  memcpy(element->path, path, path_size);
  element->path[path_size] = '\0';

  memcpy(element->fileName, fileName, fileName_size);
  element->fileName[fileName_size] = '\0';

  memcpy(element->pathFile, path, path_size);
  element->pathFile[path_size] = '/';
  memcpy(element->pathFile + path_size + 1, fileName, fileName_size);
  element->pathFile[path_size + 1 + fileName_size] = '\0';

  return element;
free_fileName:
  free(element->fileName);
free_path:
  free(element->path);
free_element:
  free(element);
error:
  return NULL;
}

searchPool *listDir(char *path);

static searchPool *listDir_aux(char *path, struct dirent *dirent) {
  if (dirent->d_type == DT_DIR && dirent->d_type != DT_LNK &&
      strcmp(dirent->d_name, ".") != 0 && strcmp(dirent->d_name, "..") != 0) {
    size_t path_size = strlen(path);
    size_t name_size = strlen(dirent->d_name);
    char *d_path = malloc(path_size + 1 + name_size + 1);
    if (d_path == NULL) {
      return NULL;
    }

    memcpy(d_path, path, path_size);
    d_path[path_size] = '/';
    memcpy(d_path + path_size + 1, dirent->d_name, name_size);
    d_path[path_size + 1 + name_size] = '\0';

    searchPool *ret = listDir(d_path);

    free(d_path);

    return ret;
  }
  return mallocStructPool(path, dirent->d_name);
}

searchPool *listDir(char *path) {
  printf("%s\n", path);
  DIR *dir = opendir(path);
  if (dir == NULL) {
    perror("dir()");
    return NULL;
  }

  searchPool *head = NULL;

  struct dirent *dirent;
  while ((dirent = readdir(dir)) != NULL) {
    searchPool *elem = listDir_aux(path, dirent);
    if (elem != NULL) {
      elem->next = head;
      head = elem;
    }
  }
  closedir(dir);

  return head;
}

int main(void) {
  searchPool *head = listDir("/tmp");
  searchPool *tmp;
  for (searchPool *elem = head; elem != NULL; elem = tmp) {
    printf("%s, %s, %s\n", elem->path, elem->fileName, elem->pathFile);
    free(elem->path);
    free(elem->fileName);
    free(elem->pathFile);
    tmp = elem->next;
    free(elem);
  }
}

edited May 23, 2017 at 10:29

CommunityBot

11 silver badge

answered Jan 14, 2017 at 18:29

Stargateur

27.1k9 gold badges73 silver badges99 bronze badges

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

6 Comments

chux Over a year ago

Use of goto has its limited usefulnesses. Error handle like this is one of them.

user100000 Over a year ago

@Stargateur This function works well but doesn't print out all the files in the subfolder. Since you separated the listDir into 2 functions I don't know where to look to fix this. Can you help me please?

Stargateur Over a year ago

@user100000 this work for me rextester.com/SRCHF77522. You can change the behavior in listDir_aux() in the if you have the recursive else you add the file in the list.

user100000 Over a year ago

@Stargateur I realised I asked my question a little wrong. EN faite, I would like to print the files inside every directory too. Where in ListDirAux can I do this?

user100000 Over a year ago

@Stargateur in listDir_aux if I put the line (before the IF) if(dirent-> d_type != DT_DIR) printf("%s\n", dirent->d_name); then it shows the file names as well but I would like to add this to the linked list in fileName. Can you help me please?

|

Malcolm McLean · Accepted Answer · 2017-01-14 18:46:28Z

0

To add an element to the tail

 searchPool *ptr;
 searchPool *prev = 0;
 searchPool *head = something;

 for(ptr = head; ptr != NULL; ptr = ptr->next)
   prev = ptr;
 element->next = 0;
 prev->next = element;

To add to the head (faster)

 element->next = head;
 head = element;

Note head is not stable now.

To add one after the head

element->next = head->next;
head->next = element

Note that head is now probably a dummy node without any data in it, which exists for the sake of having a stable and constant "head" pointer to the linked list;

answered Jan 14, 2017 at 18:46

Malcolm McLean

6,4201 gold badge19 silver badges18 bronze badges

Collectives™ on Stack Overflow

Recursion and linked lists in C

2 Answers 2

6 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related