[9fans] breadth first walking

[9fans] breadth first walking

[Tim Newsham]

someone mentioned in the thread that it would be nice to be able
to walk directory trees in breadth-first manner:
   http://www.thenewsh.com/~newsham/x/9/walk.c

Tim Newsham | www.thenewsh.com/~newsham | thenewsh.blogspot.com

Re: [9fans] breadth first walking

[Bruce Ellis]

yep, use a scape tree. ozi is full of them. no hash tables here,
except for my coffee table.

brucee

On 1/4/10, Tim Newsham <newsham@lava.net> wrote:
> someone mentioned in the thread that it would be nice to be able
> to walk directory trees in breadth-first manner:
>  http://www.thenewsh.com/~newsham/x/9/walk.c
>
> Tim Newsham | www.thenewsh.com/~newsham | thenewsh.blogspot.com
>
>

Re: [9fans] breadth first walking

[roger peppe]

what's a scape tree?

2010/1/4 Bruce Ellis <bruce.ellis@gmail.com>:
> yep, use a scape tree. ozi is full of them. no hash tables here,
> except for my coffee table.
>
> brucee
>
> On 1/4/10, Tim Newsham <newsham@lava.net> wrote:
>> someone mentioned in the thread that it would be nice to be able
>> to walk directory trees in breadth-first manner:
>>  http://www.thenewsh.com/~newsham/x/9/walk.c
>>
>> Tim Newsham | www.thenewsh.com/~newsham | thenewsh.blogspot.com
>>
>>
>
>

Re: [9fans] breadth first walking

[roger peppe]

[-- Attachment #1: Type: text/plain, Size: 693 bytes --]

2010/1/4 Tim Newsham <newsham@lava.net>:
> someone mentioned in the thread that it would be nice to be able
> to walk directory trees in breadth-first manner:
>  http://www.thenewsh.com/~newsham/x/9/walk.c

that's potentially useful, thanks.

BTW, any robust file tree walker in plan 9 should
cope with cycles in the tree. maybe just a linear list of
parents with refcounted nodes might work best for
this implementation.

something like the attached modification to walk.c, perhaps?

walk.c should also eliminate duplicate entries
from union mounts - either by sorting the directory
entries or using a little hash table of names for each directory.
or... use a scape tree?

[-- Attachment #2: walk.c --]
[-- Type: application/octet-stream, Size: 2523 bytes --]

#include <u.h>
#include <libc.h>

struct node {
	struct node *next;
	char *name;
	Dir dir;
	int depth;
	struct node *parent;
	int refcount;
};

struct node *hd, *tl;

int
samedir(Dir *d0, Dir *d1)
{
	Qid *q0, *q1;
	q0 = &d0->qid;
	q1 = &d1->qid;
	return q0->path == q1->path &&
		q0->type == q1->type &&
		d0->type == d1->type &&
		d0->dev == d1->dev;
}

struct node *
next(void)
{
	struct node *n;

	n = hd;
	if(hd)
		hd = hd->next;
	if(hd == nil)
		tl = nil;
	return n;
}

void
freenode(struct node *n)
{
	struct node *x;
	while(n != nil) {
		if(--n->refcount != 0)
			return;
		x = n->parent;
		free(n->name);
		free(n);
		n = x;
	}
}

void
insert(char *name, int depth, Dir *db, int tail, struct node *parent)
{
	struct node *n;

	/*
	 * check we're not in a loop
	 */
	for(n = parent; n != nil; n = n->parent)
		if(samedir(db, &n->dir))
			return;

	n = malloc(sizeof *n);
	if(!n)
		exits("no memory");
	n->name = name;
	n->depth = depth;
	n->dir = *db;
	n->refcount = 1;
	n->parent = parent;
	if(n->parent != nil){
		n->parent->refcount++;
	}
	if(tail) {
		n->next = nil;
		if(tl)
			tl->next = n;
		else
			hd = n;
		tl = n;
	} else {
		n->next = hd;
		hd = n;
		if(!tl)
			tl = n;
	}
}

int
addwalk(char *name)
{
	struct Dir *db;

	db = dirstat(name);
	if(!db) {
		fprint(2, "walk: %s: %r\n", name);
		return 1;
	}
	insert(strdup(name), 0, db, 1, nil);
	free(db);
	return 0;
}

int
walk(int breadth, int maxdepth)
{
	struct node *x;
	Dir *db;
	char *name;
	int fd, err, i, cnt;

	err = 0;
	while((x = next()) != nil) {
		print("%s\n", x->name);
		if((x->dir.qid.type & QTDIR) == 0 || (maxdepth && x->depth >= maxdepth))
			continue;
		fd = open(x->name, OREAD);
		if(fd == -1)
			goto error;
		cnt = dirreadall(fd, &db);
		close(fd);
		if(cnt == -1)
			goto error;
		for(i = 0; i < cnt; i++) {		
			name = smprint("%s/%s", x->name, db[i].name);
			insert(name, x->depth + 1, &db[i], breadth, x);
		}
		free(db);
		freenode(x);
		continue;

error:
		err = 1;
		fprint(2, "walk: %s: %r\n", x->name);
		freenode(x);
	}
	return err;
}

void
usage(void)
{
	fprint(2, "usage: walk [-b] [-d maxdepth] [file ...]\n");
	exits("usage");
}

void
main(int argc, char *argv[])
{
	int breadth, depth, err, i;
	depth = 0;
	breadth = 0;
	err = 0;
	ARGBEGIN {
	case 'b':
		breadth ++;
		break;
	case 'd':
		depth = atoi(EARGF(usage()));
		break;
	default:
		usage();
	} ARGEND
	if(argc == 0)
		err = addwalk(".");
	else for(i = 0; i < argc; i++)
		err |= addwalk(argv[i]);
	err |= walk(breadth, depth);
	exits(err ? "errors" : 0);
}

Re: [9fans] breadth first walking

[Bruce Ellis]

you were talking and not listening.

On 1/4/10, roger peppe <rogpeppe@gmail.com> wrote:
> what's a scape tree?
>
> 2010/1/4 Bruce Ellis <bruce.ellis@gmail.com>:
> > yep, use a scape tree. ozi is full of them. no hash tables here,
> > except for my coffee table.
> >
> > brucee
> >
> > On 1/4/10, Tim Newsham <newsham@lava.net> wrote:
> >> someone mentioned in the thread that it would be nice to be able
> >> to walk directory trees in breadth-first manner:
> >>  http://www.thenewsh.com/~newsham/x/9/walk.c
> >>
> >> Tim Newsham | www.thenewsh.com/~newsham | thenewsh.blogspot.com
> >>
> >>
> >
> >
>
>