Plan 9 from Bell Labs’s /usr/web/sources/contrib/nemo/octopus/port/mero/merotree.b

Copyright © 2021 Plan 9 Foundation.
Distributed under the MIT License.
Download the Plan 9 distribution.


# File hierarchy handling code, and related tools for omero
#

implement Merotree;

include "sys.m";
	sys: Sys;
	millisec, sprint, QTFILE, DMDIR, DMEXCL, Qid, Dir, QTDIR, fprint: import sys;
include "styx.m";
include "styxservers.m";
	Styxserver, Eexists, Enotfound: import Styxservers;
include "daytime.m";
	daytime: Daytime;
	now: import daytime;
include "dat.m";
	dat: Dat;
	Qdir, Qctl, Qdata, Qimage: import Dat;
	mnt, debug, appl, user, slash: import dat;
include "string.m";
	str: String;
include "names.m";
	names: Names;
	rooted, elements, dirname: import names;
include "error.m";
	err: Error;
	checkload, panic, stderr: import err;
include "tbl.m";
	tbl: Tbl;
	Table: import tbl;
include "mpanel.m";
	panels: Panels;
	Panel, Repl, Trepl, Tappl, qid2ids, mkqid, Amax: import panels;
include "rand.m";
	rand: Rand;
include "merotree.m";

srv: ref Styxserver;
fstab: array of ref Fholder;

NOQID: con big ~0;
Aorder: con Amax;

Fholder: adt {
	parentqid:	big;
	d:		Sys->Dir;
	child:	cyclic ref Fholder;
	sibling:	cyclic ref Fholder;
	hash:	cyclic ref Fholder;
};


init(d: Dat): chan of ref Styxservers->Navop
{
	dat = d;
	sys = dat->sys;
	err = dat->err;
	str = dat->str;
	srv = dat->srv;
	daytime = dat->daytime;
	panels = dat->panels;
	names = dat->names;
	rand = checkload(load Rand Rand->PATH, Rand->PATH);
	rand->init(millisec());
	fstab = array[101] of ref Fholder;
	c := chan of ref Styxservers->Navop;
	spawn navproc(c);
	return c;
}

navproc(c: chan of ref Styxservers->Navop)
{
	while((m:= <-c) != nil){
		(q, reply) := (m.path, m.reply);
		pick rq := m {
		Stat =>
			fh := findfile(q);
			if (fh == nil)
				reply <-= (nil, Enotfound);
			else
				reply <-= (ref fh.d, nil);
		Walk =>
			sq := fwalk1(q, rq.name);
			if (sq == NOQID)
				reply <-= (nil, Enotfound);
			else {
				fh := findfile(sq);
				reply <-= (ref fh.d, nil);
			}
		Readdir =>
			fh := findfile(q);
			if (fh == nil)
				reply <-= (nil, Enotfound);
			else {
				(start, end) := (rq.offset, rq.offset + rq.count);
				fh = fh.child;
				for (i := 0; i < end && fh != nil; i++) {
					if (i >= start)
						reply <-= (ref fh.d, nil);
					fh = fh.sibling;
				}
				reply <-= (nil, nil);
			}
		* =>
			panic(sys->sprint("unknown op %d\n", tagof(m)));
		}
	}
}

pparent(r: ref Repl): (ref Panel, ref Repl)
{
	fh := findfile(r.dirq);
	if (fh == nil)
		return (nil, nil);
	(pid, rid, nil) := qid2ids(fh.parentqid);
	return Panel.lookup(pid, rid);
}

pchilds(r: ref Repl) : array of (ref Panel, ref Repl)
{
	fh := findfile(r.dirq);
	if (fh == nil)
		return nil;
	childs := array[512] of big;
	nchilds := 0;
	for (cfh := fh.child; nchilds < 512 && cfh != nil; cfh = cfh.sibling)
		if (cfh.d.qid.qtype&QTDIR)
			childs[nchilds++] = cfh.d.qid.path;
	childs = childs[0:nchilds];
	if (nchilds == 512)
		panic("fix me: more than 512 childs for panel");
	cl := array[nchilds] of (ref Panel, ref Repl);
	for (i := 0; i < nchilds; i++){
		(pid, rid, nil) := qid2ids(childs[i]);
		cl[i] = Panel.lookup(pid, rid);
	}
	return cl;
}

pchanged(p: ref Panel, data: int, ctl: int)
{
	d := sys->nulldir;
	if (data){
		d.qid.vers = ++p.vers;
		d.length = big len p.data;
		d.mtime = now();
	}
	for (i := 0; i < len p.repl; i++){
		r := p.repl[i];
		if (r != nil){
			(pid, rid, nil) := qid2ids(r.dirq);
			if (data){
				dataf := mkqid(pid, rid, Qdata);
				fwstat(dataf, d);
			}
			if (ctl){
				d2 := sys->nulldir;
				d2.qid.vers = ++r.vers;
				d2.length = big len p.ctlstr(r);
				d2.mtime = now();
				ctlf := mkqid(pid, rid, Qctl);
				fwstat(ctlf, d2);
			}
			d2 := sys->nulldir;
			d2.qid.vers = ++r.dirvers;
			d2.mtime = now();
			fwstat(r.dirq, d2);
			# propagate changes to the update, up to /
			(pp, pr) := pparent(r);
			if (pr != nil && pr != r && pr.dirq != slash)
				pchanged(pp, 0, 0);
		}
	}
}

# order attribute: "order panel1name panel2name panel3name ..."
# This re-assigns replica positions to be unique, contiguous numbers,
# while keeping the order found, and reconstructs the order attribute.
neworder(dr: ref Repl)
{
	childs := pchilds(dr);
	s := "order ";
	for (i := 0; i < len childs; i++){
		m:= i;
		for (j := i+1; j < len childs; j++)
			if (childs[j].t1.pos < childs[i].t1.pos)
				m = j;
		t := childs[i];
		childs[i] = childs[m];
		childs[m] = t;
		childs[i].t1.pos = i;
		s += childs[i].t0.name + " ";
	}
	dr.attrs[Aorder] = s;
}

# Relocate replica r to be at pos ([0:n])
newreplpos(r: ref Repl, pos: int)
{
	# Renumber all the ones going after so that
	# we get the slot.
	(nil, dr) := pparent(r);
	childs := pchilds(dr);
	for (i := 0; i < len childs; i++)
		if (childs[i].t1.pos >= pos){
			childs[i].t1.pos++;
		}
	r.pos = pos;
	neworder(dr);
}		

chpos(nil: ref Panel, r: ref Repl, pos: int)
{
	if (r.pos == pos)	# nothing to do.
		return;
	newreplpos(r, pos);
	(dp, nil) := pparent(r);
	pchanged(dp, 0, 1);
	dp.vpost(nil, "update");
}

mkcol(p: ref Panel, r: ref Repl)
{
	if (!p.container)
		(p, r) = pparent(r);
	if (!p.container)
		panic("mkcol");
	name := sprint("col:user.%d", rand->rand(10000));
	np := pcreate(p, r, name);
	np.ctl(nil, "layout");
}

mktree()
{
	p := Panel.new("col:root");
	r := p.newrepl("/", Trepl);
	fcreate(r.dirq, newdir(".", DMDIR|8r775, r.dirq));
	slash = r.dirq;
	p = Panel.new("row:apps");
	r = p.newrepl("/appl", Tappl);
	fcreate(slash, newdir("appl", DMDIR|8r775, r.dirq));
	appl = r.dirq;
}

mkscreen(dp: ref Panel)
{
	menu := array[] of { "Ox", "New", "Exit" };
	# dp.ctl(nil, "notag");
	ps := pcreate(dp, nil, "row:stats");
	ps.ctl(nil, "layout");
		pc := pcreate(ps, nil, "row:cmds");
		pc.ctl(nil, "layout");
		for (i := 0; i < len menu; i++)
			pcreate(pc, nil, "button:" + menu[i]);

	pw := pcreate(dp, nil, "row:wins");
	pw.ctl(nil, "layout");
		c1 := pcreate(pw, nil, "col:1");
		c1.ctl(nil, "layout");
		c2 := pcreate(pw, nil, "col:2");
		c2.ctl(nil, "layout");
}

Dent: adt {
	name:	string;
	mode:	int;
	qtype:	int;
};

dirents: array of Dent;

# creates a replica of p within dr, and its file tree
pcreaterepl(dr: ref Repl, p: ref Panel, sizes: array of int): ref Repl
{
	if (dirents == nil)
		dirents = array[] of {
			Dent("data", 8r660, Qdata),
			Dent("ctl", 8r660, Qctl),
			Dent("image", 8r660, Qimage),
		};
	path := names->rooted(dr.path, p.name);
	r := p.newrepl(path, dr.tree);
	if (r == nil)
		panic("rcreate: newrepl");
	childs := pchilds(dr);
	r.pos = len childs;
	d := newdir(p.name, DMDIR|8r775, r.dirq);
	fcreate(dr.dirq, d);
	neworder(dr);
	for (i := 0; i < len dirents; i++){
		q := mkqid(p.id, r.id, dirents[i].qtype);
		dir := newdir(dirents[i].name, dirents[i].mode, q);
		if (sizes != nil)
			dir.length = big sizes[i];
		fcreate(r.dirq, dir);
	}
	return r;
}

# Creates the panel and its tree.
pcreate(dp: ref Panel, dr: ref Repl, name: string): ref Panel
{
	if (dr == nil)
		dr = dp.repl[0];
	d := dr.dirq;
	uname := name;
	if (d == slash)
		uname = "col:" + name;
	p := Panel.new(uname);
	if (p == nil)
		return nil;
	p.aid = dp.aid;		# inherit from parent
	p.pid = dp.pid;		# inherit from parent
	if (d == slash)
		p.name = name;
	for (i := 0; i < len dp.repl; i++)
		if ((dr = dp.repl[i]) != nil){
			r := pcreaterepl(dr, p, nil);
			if (d == slash){
				p.ctl(r, "layout");
				mkscreen(p);
			} else if (d != appl){
				(drp, nil) := pparent(r);
				pchanged(drp, 0, 1);
				drp.vpost(nil, "update");
			}
		}
	return p;
}

# removes a panel including all its replicas when r is the 0-th replica
# only the replica r otherwise.
premove(p: ref Panel, rr: ref Repl, depth: int)
{
	if (p.container){
		childs := pchilds(rr);
		for (i := 0; i < len childs; i++){
			(cp, cr) := childs[i];
			premove(cp, cr, depth+1);
		}
	}
	for (i := 0; i < len p.repl; i++)
		if ((r := p.repl[i]) != nil && (r == rr || rr.id == 0)){
			(pp, pr) := pparent(r);
			fremove(r.dirq);	# removes childs as well
			neworder(pr);
			pchanged(pp, 0, 1);
			pp.vpost(nil, "update");
		}
	if (rr.id == 0)
		p.close();
	else
		p.closerepl(rr);
}

# is f within d?
fwithin(d: big, f: big): int
{
	if (d == f)
		return 1;
	fh := findfile(d);
	if (fh == nil)
		return 0;
	for (cfh := fh.child; cfh != nil; cfh = cfh.sibling){
		if (cfh.d.qid.path == f)
			return 1;
		if (cfh.d.qid.qtype&QTDIR)
		if (fwithin(cfh.d.qid.path, f))
			return 1;
	}
	return 0;
}

movetarget(r: ref Repl, path: string, n: string): (ref Panel, ref Repl, string)
{
	dp: ref Panel;
	dr: ref Repl;

	(pp, pr) := pparent(r);
	if (pr.dirq == slash)
		return (nil, nil, "source is a screen tree");
	if (path == nil)
		(dp, dr) = (pp, pr);
	else {
		dq := fwalk(slash, path);
		if (dq == NOQID)
			return (nil, nil, "no such file: " + path);
		if (fwithin(r.dirq, dq))
			return (nil, nil, "read the GEB first");
		(dpid, drid, nil) := qid2ids(dq);
		(dp, dr) = Panel.lookup(dpid, drid);
		if (fwalk1(dr.dirq, n) != NOQID)
			return (nil, nil, Eexists);
	}
	if (dr.tree == Tappl || dr.dirq == slash)
		return (nil, nil, "target is not a screen tree");
	return (dp, dr, nil);
}

fixmovedrepl(p: ref Panel, r: ref Repl, spath, dpath: string)
{
	rel := names->relative(r.path, spath);
	r.path = rooted(dpath, rel);
	if (p.container){
		childs := pchilds(r);
		for (i := 0; i < len childs; i++){
			(cp, cr) := childs[i];
			fixmovedrepl(cp, cr, spath, dpath);
		}
	}
}

moveto(p: ref Panel, r: ref Repl, path: string, pos: int): string
{
	if (r.tree == Tappl)
		return "moveto: not from within /appl tree";
	(dp, dr, e) := movetarget(r, path, p.name);
	if (e != nil)
		return e;

	(pp, pr) := pparent(r);
	fdetach(r.dirq);
	neworder(pr);

	fattach(dr.dirq, r.dirq);
	childs := pchilds(dr);
	r.pos = len childs;
	neworder(dr);		# double-check
	newreplpos(r, pos);

	fixmovedrepl(p, r, pr.path, dr.path);

	pchanged(p, 0, 1);
	pchanged(dp, 0, 1);
	dp.vpost(nil, "update");
	pchanged(pp, 0, 1);
	pp.vpost(nil, "update");
	return nil;
}

_copyto(nil: ref Panel, dr: ref Repl, p: ref Panel, r: ref Repl): ref Repl
{
	sizes := array[3] of int;
	sizes[0] = len p.data;
	sizes[1] = len p.ctlstr(p.repl[0]);
	sizes[2] = 0;
	nr := pcreaterepl(dr, p, sizes);
	if (p.container){
		childs := pchilds(r);
		for (i := 0; i < len childs; i++){
			(cp, cr) := childs[i];
			_copyto(p, nr, cp, cr);
		}
		nr.attrs[Aorder] = r.attrs[Aorder];
	}
	return nr;
}

copyto(p: ref Panel, r: ref Repl, path: string, pos: int): string
{
	(dp, dr, e) := movetarget(r, path, p.name);
	if (e != nil)
		return e;
	nr := _copyto(dp, dr, p, r);
	newreplpos(nr, pos);
	pchanged(dp, 0, 1);
	pchanged(p, 0, 1);
	dp.vpost(nil, "update");
	return nil;
}

hashfn(q: big, n: int): int
{
	h := int (q % big n);
	if (h < 0)
		h += n;
	return h;
}

findfile(q: big): ref Fholder
{
	for (fh := fstab[hashfn(q, len fstab)]; fh != nil; fh = fh.hash)
		if (fh.d.qid.path == q)
			return fh;
	return nil;
}

fgetpath(q: big): string
{
	fh := findfile(q);
	if (fh == nil)
		return nil;
	if (fh.parentqid == fh.d.qid.path)
		return "/";
	s: string;
	for(;;) {
		if (s == nil)
			s = fh.d.name;
		else if (fh.parentqid == fh.d.qid.path)
			return "/" + s;
		else
			s = fh.d.name + "/" + s;
		fh = findfile(fh.parentqid);
		if (fh == nil)
			panic("fgetpath:parent not in table");
	}
	return nil;
}

fwalk(f: big, path: string): big
{
	els := elements(path);
	if (hd els != "/")
		panic("fwalk: relative path");
	for(els = tl els; els != nil && f != NOQID; els = tl els)
		f = fwalk1(f, hd els);
	return f;
}

fwalk1(q: big, name: string): big
{
	fh := findfile(q);
	if (fh == nil)
		return NOQID;
	if (name == "..")
		return fh.parentqid;
	for (fh = fh.child; fh != nil; fh = fh.sibling)
		if (fh.d.name == name)
			return fh.d.qid.path;
	return NOQID;
}


# detach f from parent. But keep on table. to move it around.
fdetach(f: big)
{
	fh := findfile(f);
	if (fh == nil)
		panic("fdetach: nil fh");
	parent := findfile(fh.parentqid);
	if (parent == nil)
		panic("fdetach: nil parent");
	_fdetach(fh, parent);
}

_fdetach(fh: ref Fholder, parent: ref Fholder)
{
	prev: ref Fholder;

	if (parent != nil) {
		prev = nil;
		for (sfh := parent.child; sfh != nil; sfh = sfh.sibling) {
			if (sfh == fh)
				break;
			prev = sfh;
		}
		if (sfh == nil)
			panic("fdetach: child not found in parent");
		if (prev == nil)
			parent.child = fh.sibling;
		else
			prev.sibling = fh.sibling;
	}
	fh.sibling = nil;
	fh.parentqid = NOQID;
}

fattach(d: big, f: big)
{
	parent := findfile(d);
	if (parent == nil)
		panic("fattach: no parent");
	fh := findfile(f);
	if (fh == nil)
		panic("fattach: no fh");
	fh.parentqid = d;
	# Attach at the end, so new panels show up last
	if (parent.child == nil)
		parent.child = fh;
	else {
		for (sf := parent.child; sf.sibling != nil; sf = sf.sibling)
			;
		sf.sibling = fh;
		fh.sibling = nil;
	}
}

fremove(q: big): string
{
	prev: ref Fholder;

	# remove from hash table
	slot := hashfn(q, len fstab);
	for (fh := fstab[slot]; fh != nil; fh = fh.hash) {
		if (fh.d.qid.path == q)
			break;
		prev = fh;
	}
	if (fh == nil)
		return Enotfound;
	if (prev == nil)
		fstab[slot] = fh.hash;
	else
		prev.hash = fh.hash;
	fh.hash = nil;

	# remove from parent's children
	parent := findfile(fh.parentqid);
	_fdetach(fh, parent);

	# now remove any descendents
	sibling: ref Fholder;
	for (sfh := fh.child; sfh != nil; sfh = sibling) {
		sibling = sfh.sibling;
		sfh.parentqid = sfh.d.qid.path;		# make sure it doesn't disrupt things.
		fremove(sfh.d.qid.path);
	}
	return nil;
}

fcreate(q: big, d: Sys->Dir): string
{
	if (findfile(d.qid.path) != nil)
		return Eexists;
	# allow creation of a root directory only if its parent is itself
	parent := findfile(q);
	if (parent == nil && d.qid.path != q)
		return Enotfound;
	fh: ref Fholder;
	if (parent == nil)
		fh = ref Fholder(q, d, nil, nil, nil);
	else {
		if (fwalk1(q, d.name) != NOQID)
			return Eexists;
		fh = ref Fholder(parent.d.qid.path, d, nil, nil, nil);
		# Attach at the end, so new panels show up last
		if (parent.child == nil)
			parent.child = fh;
		else {
			for (sf := parent.child; sf.sibling != nil; sf = sf.sibling)
				;
			sf.sibling = fh;
		}
	}
	slot := hashfn(d.qid.path, len fstab);
	fh.hash = fstab[slot];
	fstab[slot] = fh;
	return nil;
}

tabs : con "\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t";

dumptree(fh: ref Fholder, t: int): int
{
	n := 1;
	q := fh.d.qid.path;
	fprint(stderr, "%s%08bx\t%s\n", tabs[0:t], q, fgetpath(q));
	for (fh = fh.child; fh != nil; fh = fh.sibling)
		n += dumptree(fh, t+1);
	return n;
}

dumphash(): int
{
	n:= 0;
	for (i := 0; i < len fstab; i++)
		for (fh := fstab[i]; fh != nil; fh = fh.hash){
			n++;
			#q := fh.d.qid.path;
			# fprint(stderr, "%s%08bx\t%s\n", tabs[0:t], q, fgetpath(q));
		}
	return n;
}

dump()
{
	fh := findfile(slash);
	if (fh == nil)
		panic("file not in tree");
	n := dumptree(fh, 0);
	m := dumphash();
	fprint(stderr, "%d in tree %d in hash\n", n, m);
}

fwstat(q: big, d: Sys->Dir): string
{
	fh := findfile(q);
	if (fh == nil)
		return Enotfound;

	d = applydir(d, fh.d);

	# We don't allow renames
	if (d.name != fh.d.name)
		return "renames not allowed";
	fh.d = d;
	fh.d.qid.path = q;		# ensure the qid can't be changed
	return nil;
}

applydir(d: Sys->Dir, onto: Sys->Dir): Sys->Dir
{
	if (d.name != nil)
		onto.name = d.name;
	if (d.uid != nil)
		onto.uid = d.uid;
	if (d.gid != nil)
		onto.gid = d.gid;
	if (d.muid != nil)
		onto.muid = d.muid;
	if (d.qid.vers != ~0)
		onto.qid.vers = d.qid.vers;
	if (d.qid.qtype != ~0)
		onto.qid.qtype = d.qid.qtype;
	if (d.mode != ~0)
		onto.mode = d.mode;
	if (d.atime != ~0)
		onto.atime = d.atime;
	if (d.mtime != ~0)
		onto.mtime = d.mtime;
	if (d.length != ~big 0)
		onto.length = d.length;
	if (d.dtype != ~0)
		onto.dtype = d.dtype;
	if (d.dev != ~0)
		onto.dev = d.dev;
	return onto;
}

newdir(name: string, perm: int, qid: big): Dir
{
	d := sys->zerodir;
	d.name = name;
	d.uid = user;
	d.gid = user;
	d.qid.path = qid;
	if (perm & DMDIR)
		d.qid.qtype = QTDIR;
	else
		d.qid.qtype = QTFILE;
	d.mode = perm;
	return d;
}

Bell Labs OSI certified Powered by Plan 9

(Return to Plan 9 Home Page)

Copyright © 2021 Plan 9 Foundation. All Rights Reserved.
Comments to [email protected].