From: Rainer Weikusat on
pjb(a)informatimago.com (Pascal J. Bourguignon) writes:

[...]

> I didn't hide anything. Some programming language are actually high
> level programming language, and use normal integer arithmetic, not
> modulo 2^w arithmetic.

There is no such thing as 'normal integer arithmetic' and definitions
of particular algebraic operations such as +, including the sets they
operate on, are not structural properties of programming languages.
From: Scott Lurndal on
frank <frank(a)example.invalid> writes:
>Jan Seiffert wrote:
>
>[lots of code, so big snips]
>
>No. I don't want to recurse through. I may not have said that
>succinctly that but do so now.
>
>> But i would not use an array for that, instead a linked list, saves you the
>> 3-star programming and reallocations. If you really want an array, you can
>> transform the list to an array afterward, but then you will know how many
>> entries you will need etc.

Rather than a linked list, how about using the standard tsearch function?

$ cc -g -D_GNU_SOURCE -D_XOPEN_SOURCE=500 -o /tmp/d dir.c
$ /tmp/d .
..
../.ca.C.swp
../.dir.c.swp
../.port.h.swp
../Makefile
../aquareg.c
../arima_mail.htm
../btree.c
../ca.C
../ca.h
../ca.o
../calc_ht_route.cpp
../chip.h
../conn-eth.c
../cpuid_test.c
../debugger.cpp
../dir.c
../elf64-x86-64.c.diff
../fpga_test.c
../header-lookaside.c
../ht_route_print.c
../htest.c
../sm.C
../sm.h
../sm.o
../srat.c
../switch.h
../test_getnode.c
../test_protection.c
../umt.c
../vni.c
../vvga.cpp
../vvga.h

-------------[begin code]--------------------------------------

#include <errno.h>
#include <ftw.h>
#include <memory.h>
#include <search.h>
#include <string.h>
#include <stdio.h>

void *root = NULL;
const char *myname;

/**
* tsearch(3) comparison function. The keys are nul-terminated
* arrays of type char.
*
* @param a The key being searched for
* @param b A key in the tree to compare against.
* @returns -1 if a collates before b
* 0 if a and b collate identically.
* +1 if a collates after b
*/
int
path_compare(const void *a, const void *b)
{
return strcmp((const char *)a, (const char *)b);
}

/**
* Print a tree node. The key for each node is a pathname.
*
* @param np A pointer to the node.
* @param which Point in tree traversal
* @param depth Depth of the tree.
*/
void
path_print(const void *np, const VISIT which, const int depth)
{
struct _node {
const char *key;
} *kp = (struct _node *)np;

switch (which) {
case preorder:
case endorder:
break;
case postorder:
case leaf:
fprintf(stdout, "%s\n", kp->key);
break;
}
}

/**
* nftw(3) callback function. Insert the provided path
* into the tree. Use the appropriate return value to
* avoid descending into subdirectories if desired.
*
* @param path The pathname for a directory entry.
* @param sp The corresponding struct stat
* @param typeflag Metadata
* @param ftwbuf Basename offset and path depth
* @returns FTW_STOP To stop walking the filesystem tree
* FTW_CONTINUE Continue walking the tree
* FTW_SKIP_SUBTREE Don't walk into this directory
*/
int
ftw_callback(const char *path, const struct stat *sp,
int typeflag, struct FTW* ftwbuf)
{
void *key = strdup(path);

if (key == NULL) {
fprintf(stderr, "%s: Unable to allocate memory for tree node: %m\n",
myname);
return FTW_STOP;
}

key = tsearch(key, &root, path_compare);
if (key == NULL) {
fprintf(stderr, "%s: Unable to allocate memory for tree node: %m\n",
myname);
return FTW_STOP;
}

return FTW_CONTINUE;
}

/**
* Walk a file system directory and insert the entries into a red-black
* tree.
*/
int
main(int argc, char **argv, char **envp)
{
int diag;

myname = argv[0];

diag = nftw(argv[1], ftw_callback, 20, 0);
if (diag == -1) {
fprintf(stderr, "%s: Unable to walk filesystem tree: %m\n", argv[0]);
return 1;
}

twalk(root, path_print);

return 0;
}
/* vim: sw=4 sts=4 sta ts=8:
*
From: Pascal J. Bourguignon on
Rainer Weikusat <rweikusat(a)mssgmbh.com> writes:

> pjb(a)informatimago.com (Pascal J. Bourguignon) writes:
>
> [...]
>
>> I didn't hide anything. Some programming language are actually high
>> level programming language, and use normal integer arithmetic, not
>> modulo 2^w arithmetic.
>
> There is no such thing as 'normal integer arithmetic'

Of course. Ask anybody in the street how much is 4294967295 + 1.


Arithmetic and integer are things that are defined in mathematic. When
you use them unqualified, you have an infinite number of integers:

0 in Integer
x in Integer => succ(x) in Integer

and the arithmetical operations + and * have the whole Integer set as
image, not just a subset.



> and definitions
> of particular algebraic operations such as +, including the sets they
> operate on, are not structural properties of programming languages.

Of course they are.

C specifies that its + is actually addition modulo 2^w.

On the other hand, Lisp specifies that its + is the mathematic plus
(restricted to the size of the memory).




(On the other hand, if the syntax of C was defined as:

int a = b + c [2^(sizeof(int)*CHAR_BIT)];

instead of:

int a = b + c;

a lot less bugs would be written in C.)


--
__Pascal Bourguignon__
From: Moi on
On Wed, 27 Jan 2010 00:21:30 -0700, frank wrote:

> Hello again comp.unix.programer,gnu.gcc.help
>

> What follows is the readdir() I understand best and then working code
> from unleashed that has a 2-d resizable array.
>
> Jens Thoerring has given me the best design idea that I have right now,
> but if you think you have a better one given the source below, then I'm
> all ears.

Ok, I cleaned it up a bit, removing the need for multidimentional arrays
and ***pointers. (it does use the struct hack, but that is still allowed in c89/c90 ;-)

Sorry for the mixed indentation ...

*****************************/

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

#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>

char * strdup ( const char *org ); /* sorry! */
ssize_t readlink(const char *path, char *buf, size_t bufsiz); /* sorry */

#define MOI AvK
#define SHOW_BAGS 0
#define SHOW_PROGRESS 0
#define PATH_SIZE 4096

struct bag {
unsigned used;
unsigned size;
char *data[1]; /* struct hack here ... */
};

struct bag * bag_add( struct bag * bag, char *str );
char * bag_del( struct bag * bag );
struct bag * bag_resize( struct bag * old, unsigned size );
struct bag * get_files( struct bag *dirs );

/* NB: this program does about the same as "find arg[1]... arg[n] -type f"
* (except for some details, such as ordering and the handling of symlinks)
*/
int main( int argc, char *argv[] )
{
struct bag *todo=NULL, *result=NULL;
unsigned iter;

while( argc-- > 1 ) {
#if SHOW_PROGRESS
fprintf( stderr, "Add to todo list[%d]: %s\n", argc, argv[argc] );
#endif
todo = bag_add ( todo, strdup( argv[argc] ) );
}

result = get_files ( todo );

if ( result ) for ( iter = 0; iter < result->used; iter++ ) {
fprintf( stdout, "[%u]: %s\n", iter, result->data[iter] );
}
return 0;
}

struct bag * get_files( struct bag *dirs )
{
DIR *dir = NULL;
struct dirent *dp = NULL;
char *dirname, *fullpath ;
size_t dirlen, namelen;
struct bag *files = NULL;
int rc;
for ( ; dirname = bag_del(dirs) ; free(dirname) ) {
/* Open the given directory, if we can. */
#if SHOW_PROGRESS
fprintf ( stderr, "Processing %s\n", dirname );
#endif
dir = opendir ( dirname );
if ( !dir ) {
fprintf ( stderr, "Error opening %s: %d(%s)\n", dirname, errno, strerror (errno));
continue;
}

dirlen = strlen( dirname );
while ( dp = readdir(dir )) {
struct stat sst;

if ( !strcmp ( dp->d_name, "." ) || !strcmp ( dp->d_name, ".." ) ) continue;
namelen = strlen( dp->d_name );

fullpath = malloc( dirlen + 1 + namelen +1 );
if ( !fullpath ) {
fprintf( stderr,"Name too long: %u+1+%u+1 %s/%s\n"
, (unsigned) dirlen, (unsigned) namelen, dirname, dp->d_name );
continue; }
memcpy ( fullpath, dirname, dirlen );
fullpath[dirlen] = '/';
memcpy ( fullpath+dirlen+1, dp->d_name, namelen +1 );

if ( lstat ( fullpath, &sst ) == -1 ) { /* stat() failed, let's party */
fprintf ( stderr, "Error statting %s: %s\n", fullpath, strerror (errno)); continue; }

if ( S_ISDIR ( sst.st_mode )) { /* directory */
#if SHOW_PROGRESS
fprintf ( stderr, "\tAdding Dir %s:/\n", fullpath );
#endif
dirs = bag_add( dirs, fullpath );
continue; }

if ( S_ISREG ( sst.st_mode )) { /* regular file */
#if SHOW_PROGRESS
fprintf ( stderr, "\t%s has %lld bytes\n"
, fullpath, (long long) sst.st_size );
#endif
files = bag_add( files, fullpath );
continue; }

if ( S_ISLNK ( sst.st_mode )) { /* symbolic link */
char targetName[PATH_SIZE + 1];
if ( readlink ( fullpath, targetName, PATH_SIZE ) == -1) {
fprintf ( stderr, "\t%s -> (invalid symbolic link!)\n", fullpath );
goto skip; }

#if SHOW_PROGRESS
strcpy( targetName+PATH_SIZE-3, "/.." );
fprintf ( stderr, "\t%s -> %s\n", fullpath, targetName);
#endif
goto skip; }

fprintf ( stderr, "\t%s :Strange Mode: 0x%x\n", fullpath, sst.st_mode);
skip:
free( fullpath);
}

rc = closedir ( dir );
if (rc == -1) fprintf ( stderr, "Error closdir(%s): %s", dirname, strerror (errno));
}
return files;
}

/***************/
struct bag * bag_add( struct bag * bag, char *str )
{

#if SHOW_BAGS
fprintf( stderr, "Bag_add(%u+%s)\n", bag?bag->used:0, str );
#endif

if ( !bag || !bag->size ) bag = bag_resize( bag, 2 );
else if ( bag->used > bag->size ) bag = bag_resize( bag, 2 * bag->size );

if ( !bag || bag->used > bag->size ) {
fprintf( stderr, "The bag got robbed.\n" );
return bag;
}
bag->data[bag->used++] = str;
return bag;
}

char * bag_del( struct bag * bag )
{

#if SHOW_BAGS
fprintf( stderr, "Bag_del(%u --> %s )\n"
, bag?bag->used:0
, bag && bag->used ? bag->data[bag->used-1] : "NoNe" );
#endif

if ( !bag || !bag->used ) return NULL;

return bag->data[--bag->used] ;
}

struct bag * bag_resize( struct bag * old, unsigned size )
{
struct bag * new;
unsigned used;

#if SHOW_BAGS
fprintf( stderr, "Bag_resize(%u -->> %u)\n", old?old->size:0, size );
#endif
if ( !size ) { free ( old ); return NULL; }new = malloc ( sizeof *new + size * sizeof new->data[0] );
if ( !new ) {
fprintf( stderr, "Bag_resize: Malloc(%u) went wrong\n"
, (unsigned) sizeof *new + size * sizeof new->data[0] );
return old;
}
used = old ? size < old->used ? size : old->used : 0;
if ( used ) memcpy ( new->data, old->data, used * sizeof new->data[0] );
new->used = used;
new->size = size;
for ( ; used < size; used++ ) new->data[used] = NULL;
free ( old );
return new;
}
/*****

HTH,
AvK

From: Rainer Weikusat on
pjb(a)informatimago.com (Pascal J. Bourguignon) writes:
> Rainer Weikusat <rweikusat(a)mssgmbh.com> writes:
>
>> pjb(a)informatimago.com (Pascal J. Bourguignon) writes:
>>
>> [...]
>>
>>> I didn't hide anything. Some programming language are actually high
>>> level programming language, and use normal integer arithmetic, not
>>> modulo 2^w arithmetic.
>>
>> There is no such thing as 'normal integer arithmetic'
>
> Of course. Ask anybody in the street how much is 4294967295 + 1.

Since when is the belief of a majority of ignorants (ignorant on this
particular topic) a proof?

> Arithmetic and integer are things that are defined in mathematic.
> When you use them unqualified, you have an infinite number of
> integers:

An operator is something which performs a somehow defined operation on
the members of a particular set. The combination of some operators the
set they operate on is a so-called algebraic structure. That you have
learnt something about certain algebraic structures in school doesn't
make these more 'normal' (with the presumably intended sense of
'proper') than other algebraic structures. Also, that you usually only
refer to integer arithmetic in the context of a particular set does
not mean I (or anyone else) does this, especially since this wouldn't
be particularly sensible because 'integer arithmetic' on a computer
usually refers to calculations using operators defined a different
set, a so-called [dictionary translation] 'residue class ring which
has a finite number of members. Your special preference for refering to
irreal things (like sets with an infinite number of members) as
'normal', implicitly deriding real things (like CPUs capable of doing
integer arithmetic') as somehow 'not normal' is neither universal
nor normative. It's just a not exactly elaborate philosophical opinion.

[...]

>> and definitions
>> of particular algebraic operations such as +, including the sets they
>> operate on, are not structural properties of programming languages.
>
> Of course they are.
>
> C specifies that its + is actually addition modulo 2^w.

Mostly, yes (the C-standard only specifies this for unsigned
integers). But 'the meaning of things' in language is the semantic and
what you were writing about ('high-level language' as opposed to
'machine language') is a structural propery of the language itself,
that is, its syntax and grammar. Amusingly, the usual LISP-syntax
(s-expressions) was originally intended to be a machine language (for
a virtual machine) and the m-expression notation which was supposed to
become the high-level pendant of it fell almost completely in disuse.

> On the other hand, Lisp specifies that its + is the mathematic plus
> (restricted to the size of the memory).

As I already wrote above: The +-operator as defined on the set of
integers modulo 2 to the 32th power (for instance) is as 'mathematic'
as any other mathematical operator defined on some set.

[...]

> (On the other hand, if the syntax of C was defined as:
>
> int a = b + c [2^(sizeof(int)*CHAR_BIT)];
>
> instead of:
>
> int a = b + c;
>
> a lot less bugs would be written in C.)

Substituting actual learning for the student-routine of memoize -
forget - memoize - forget - memoize - forget could help a lot with this
too, since this is really basic linear algebra. OTOH, discussing if
the rule of three is mathematically correct with graduate students of
the TU Dresden (happened to me once) has its very own charme ...
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: Reading /proc/<pid>/maps
Next: Code and Creation 73169