Rapid Listing, alphabetically sorting, dir/files sorting in C ?

Xeratul · 11-01-2014, 08:56 AM

Hello Guys,

I would like to list files to data[] and sort them, with first the directories and after the files (listed alphabetically).

I have tried several ways, but still all of them are so slow.

Sorting with bubble is slow, and checking whether it is a directory or a file is even slower. So I end up with 2-4 sec for a large dir of files.

Code:

  if (  ( fdirent ==1 ) && (  dir = opendir(   dirsource    )) != NULL) {
         while (( ent = readdir (dir)) != NULL)  {
             {
                   strncpy( data[ i ] , ent->d_name, PATH_MAX);
             }

         }
      }
  closedir( dir );

Any help would be greatly helpful.

thank you

ember1205 · 11-01-2014, 09:06 AM

What's your end goal? This kind of functionality is already available is 'ls'. You're re-inventing the wheel.

Xeratul · 11-01-2014, 09:08 AM

Quote:

Originally Posted by ember1205

What's your end goal? This kind of functionality is already available is 'ls'. You're re-inventing the wheel.

My end goal is to list the files from getcwd(cwd,PATH_MAX) to the data[] (sorted and fast).

ember1205 · 11-01-2014, 09:09 AM

Use a system call to ls, then.

ntubski · 11-01-2014, 09:55 AM

Quote:

Originally Posted by Xeratul

Sorting with bubble is slow

Well yes, obviously. Have you tried using libc's qsort()?

Xeratul · 11-01-2014, 11:36 AM

Quote:

Originally Posted by ember1205

Use a system call to ls, then.

yeah why not popen to LS or FIND?

I believe that it is the most crazy solution ever.

Xeratul · 11-01-2014, 07:41 PM

Quote:

Originally Posted by ntubski

Well yes, obviously. Have you tried using libc's qsort()?

thank you. It is in progress...

I found this example

Code:

/* 
   The JitterBug bug tracking system
   list handling utility functions

   Copyright (C) Dan Shearer 1997
   Copyright (C) Andrew Tridgell 1997

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

   This module handles simple lists of strings terminated by a NULL string

*/

#include "weblist.h"

/* These constants are a bit silly because add_item() only knows about 
MAX_LIST */
#define MAX_DIR 10000
#define MAX_LINES 10000
#define MAX_LIST 10000

static int namecmp(char **s1, char **s2)
{
	return strcmp(*s1, *s2);
}


/* load a directory into a list of strings. Only filenames
   which match the passed function are loaded */
char **load_dir_list(char *name, int (*fn)(char *name))
{
	char **ret;
	int i=0;
	DIR *dir;
	struct dirent *d;
	ret = (char **)malloc(MAX_DIR*sizeof(ret[0]));
	if (!ret) return NULL;

	dir = opendir(name);
	if (!dir) {
		free(ret);
		return NULL;
	}

	while ((d = readdir(dir))) {
		char *dname = d_name(d);
		if (dname[0] == '.')
			continue;
		if (fn && !fn(dname)) continue;
		ret[i] = strdup(dname);
		if (!ret[i]) {
			fatal("strdup failed\n");
			return NULL;
		}
		i++;
		if (i == MAX_DIR-1)
			break;
	}
	ret[i] = NULL;

	closedir(dir);

	if (i > 1)
		qsort(ret, i, sizeof(ret[i]), namecmp);

	return ret;
}

/* load a file into a list of strings. Only strings
   which match the passed function are loaded */
char **load_file_list(char *name,int (*fn)(char *name))
{
	char **ret;
	int i=0;
	FILE *f;
	char buf[100];

	ret = (char **)malloc(MAX_LINES*sizeof(ret[0]));
	if (!ret) return NULL; /*should have proper fatal() for util.c*/

	f = fopen(name,"r");
	if (!f) return NULL; /*ditto fatal*/

	while (fgets(buf, sizeof(buf)-1, f)) {
		if (buf[strlen(buf)-1] == '\n')
			buf[strlen(buf)-1] = 0;
		if (!*buf || (fn && !fn(buf))) continue;
		ret[i] = strdup(buf);
		if (!ret[i]) {
		  fatal("strdup failed\n");
		  return NULL;
		}
		i++;
	}
	fclose(f);

	ret[i] = NULL;

	if (i > 1)
		qsort(ret, i, sizeof(ret[i]), namecmp);

	return ret;
}

/* free a list load_dir_list, load_file_list or new_list has created. Relies 
on last member being NULL so use qsort elsewhere to avoid holes */
void free_list(char **list)
{
	int i;
	if (!list) return;
	for (i=0;list[i];i++)
		free(list[i]);
	free(list);
}

/* write a file with supplied mode from a list of strings. Only strings
   which match the passed function are written. Relies on last item==NULL 
   Deletes file if no entries in the list and mode is "w".
*/
int write_list(char *fname,char *mode,char **list,int (*fn)(char *name))
{
	int i;
	FILE *f;

	if (!list || !list[0]) return 0;

	for (i=0;list[i];i++);

	if (!mode || !*mode || !(f=fopen(fname,mode))) return 1;

	if (strcmp(mode,"w")==0 && i==0) {
	        unlink(fname);
	} else {
	        for (i=0;list[i];i++) {
		        if (!fn(list[i])) continue;
			fprintf(f,"%s\n",list[i]);
		}
        }
	fclose(f);

	return 0;
}

void debug_print_list(char **list)
{
        int i;

        if (!list || !list[0]) {
	        printf("debug_print_list: empty list\n");
	        return;
	}

        for (i=0;list[i];i++);
	printf("debug_print_list: there are %d items\n",i);

	for (i=0;list[i];i++) {
                printf("%s<br>\n",list[i]);
	}
}


/* free first line containing item from null-terminated list of strings */
int delete_list_item(char **list,char *item)
{
        int i,j;
	
	if (!item || !*item) return 1;
	
	for (i=0; list[i]; i++) {
		if (strcmp(list[i],item)==0) {
			free(list[i]);
			for (j=i; list[j]; j++)
				list[j] = list[j+1];
			return 0;
		}
	}

	return 1;
}

/* create a new list */
char **new_list(void)
{
        char **ret;

        ret = (char **)malloc(MAX_LIST*sizeof(ret[0]));
        if (!ret) return NULL;
        ret[0] = NULL;
	return ret;
}

/* append an item to a null-terminated list of strings */
int add_list_item(char **list,char *item)
{
        int i;

	if (!item || !*item) return 1;

	if (!list) return 1; /*caller's responsibility to make **list's */

	for (i=0; list[i]; i++);
	if (i == MAX_LIST) return 1;

	if (!(list[i]=strdup(item))) {
	        fatal("strdup failed\n");
		return 1;
	}

	if (i > 1)
		qsort(list, i, sizeof(list[i]), namecmp);
	list[i+1] = NULL;

	return 0;
}


int valid_list(char **list, char *name)
{
	int i;
	if (!name || !*name || !list) return 0;

	for (i=0;list[i];i++)
		if (strcmp(name, list[i]) == 0) return 1;
	return 0;
}

ember1205 · 11-01-2014, 09:05 PM

Quote:

Originally Posted by Xeratul

yeah why not popen to LS or FIND?

I believe that it is the most crazy solution ever.

Why? Because it's a simple solution to a problem you didn't define? I asked what the goal was, but you only asked the question again.

Xeratul · 11-02-2014, 01:09 AM

Quote:

Originally Posted by ember1205

Why? Because it's a simple solution to a problem you didn't define? I asked what the goal was, but you only asked the question again.

Actually the question was to use C and probably not external methods, such as system( "ls ... "). Or it could be call C too.

But probably, my thread shall have been better and I should I have given more information.

Thank you.

Anyhow, I am glad that you contributed. Thank you. More on a subject could mean more results, ideas, ...

bigearsbilly · 11-06-2014, 02:38 AM

well chief, some things are just slow and this is one of them.
you are doing lots of disk reads, which is about as slow as it gets.
(apart from disk writes probably)

Xeratul · 11-20-2014, 01:09 PM

Quote:

Originally Posted by ntubski

Well yes, obviously. Have you tried using libc's qsort()?

Dear ntubski, I would definitely need your help. I spent really several days, reading, testing,... I still get an error at the line corresponding below where is "qsort".

Please I would be very pleased if you could give me an hand.

thank you in advance !! Greetings,
X.

Code:

char mylist[4000][PATH_MAX];

int qstrcmp(const void *a, const void *b) {
  return strcmp(*(const char **)a, *(const char **)b);
}
int dir2dat_qsort( char *dirsource ) {
  int i ; 
  DIR *dir ; 
  char line[PATH_MAX]; 
  int county = 0 ; 

  int fdirent, freader, counter1 ; 
  fdirent = 1 ; 
  size_t count;

  listmax=0; 
  if (  ( fdirent ==1 ) && (  dir = opendir(   dirsource    )) != NULL) {
         while (( ent = readdir (dir)) != NULL)  {
           counter1++;
           freader =1;

           if ( strcmp( ent->d_name , "." ) == 0 ) 
                freader = 0;

           if ( strcmp( ent->d_name , ".." ) == 0 ) 
                freader = 0;

           if ( freader == 1 ) {
                   county++;
                   listmax++;
                   strncpy( mylist[ listmax] , ent->d_name, PATH_MAX);
             }

         }
      }
  closedir( dir );


  i = listmax; 
  qsort( mylist , listmax-1 , PATH_MAX , qstrcmp);

  return county ; 
}

ntubski · 11-20-2014, 07:27 PM

Quote:

Originally Posted by Xeratul

I still get an error at the line corresponding below where is "qsort".

A compile error? I don't.

dirs.c:

Code:

#include <dirent.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
enum { PATH_MAX = 4096 };

char mylist[4000][PATH_MAX];

int qstrcmp(const void *a, const void *b) {
  return strcmp(*(const char **)a, *(const char **)b);
}
int dir2dat_qsort( char *dirsource ) {
  int i ; 
  DIR *dir ; 
  char line[PATH_MAX]; 
  int county = 0 ; 

  int fdirent, freader, counter1 ;
  fdirent = 1 ; 
  size_t count;

  int listmax=0; 
  if (  ( fdirent ==1 ) && (  dir = opendir(   dirsource    )) != NULL) {
      struct dirent *ent;
      while (( ent = readdir (dir)) != NULL)  {
          counter1++;
          freader =1;

          if ( strcmp( ent->d_name , "." ) == 0 ) 
              freader = 0;

          if ( strcmp( ent->d_name , ".." ) == 0 ) 
              freader = 0;

          if ( freader == 1 ) {
              county++;
              listmax++;
              strncpy( mylist[ listmax] , ent->d_name, PATH_MAX);
          }

      }
  }
  closedir( dir );


  i = listmax; 
  qsort( mylist , listmax-1 , PATH_MAX , qstrcmp);

  return county ; 
}

Only some warnings:

Code:

make -k dirs.o
gcc -Wall -Wextra -Wformat=2 -ggdb -pedantic -std=c99   -c -o dirs.o dirs.c
dirs.c: In function ‘dir2dat_qsort’:
dirs.c:20:10: warning: unused variable ‘count’ [-Wunused-variable]
   size_t count;
          ^
dirs.c:15:8: warning: unused variable ‘line’ [-Wunused-variable]
   char line[PATH_MAX]; 
        ^
dirs.c:13:7: warning: variable ‘i’ set but not used [-Wunused-but-set-variable]
   int i ; 
       ^

You should probably be sorting an array of pointers, not an array of char arrays though, for efficiency.

NevemTeve · 11-21-2014, 12:48 AM

(Anyways, forget PATH_MAX, always use dynamic allocation (strdup) when processing dirent.d_name)

Xeratul · 11-22-2014, 04:24 AM

i = listmax;

Code:

  qsort( mylist , listmax-1 , PATH_MAX , qstrcmp);

I have just compiled your code just above and it returns a :

"Segmentation fault"

Any help would be very very welcome !
Yours sincerely.
X.

turtleli · 11-22-2014, 07:45 AM

I believe that originally came from your code. The 2nd and 3rd parameters are wrong.

There's a few things that haven't been mentioned yet.

Code:

  int county = 0 ; 
  int fdirent, freader, counter1 ;
  fdirent = 1 ; 
  size_t count;

  int listmax=0; 
  if (  ( fdirent ==1 ) && (  dir = opendir(   dirsource    )) != NULL) {
      struct dirent *ent;
      while (( ent = readdir (dir)) != NULL)  {
          counter1++;
          freader =1;

          if ( strcmp( ent->d_name , "." ) == 0 ) 
              freader = 0;

          if ( strcmp( ent->d_name , ".." ) == 0 ) 
              freader = 0;

          if ( freader == 1 ) {
              county++;
              listmax++;
              strncpy( mylist[ listmax] , ent->d_name, PATH_MAX);
          }

      }
  }
  closedir( dir );

1. What is the purpose of fdirent?
2. What is the purpose of freader? Something called "continue" comes to mind.
3. Purpose of counter1, county and count?
4. I'm pretty sure arrays start from index 0, yet mylist uses listmax as an index, which starts from 1.
5. Is this some sort of learning C exercise?