1 files changed, 123 insertions, 0 deletions
diff --git a/appl/lib/readdir.b b/appl/lib/readdir.b
new file mode 100644
index 00000000..8b8ad276
--- /dev/null
+++ b/appl/lib/readdir.b
@@ -0,0 +1,123 @@
+implement Readdir;
+
+include "sys.m";
+	sys: Sys;
+	Dir: import sys;
+include "readdir.m";
+
+init(path: string, sortkey: int): (array of ref Dir, int)
+{
+	sys = load Sys Sys->PATH;
+	fd := sys->open(path, sys->OREAD);
+	if(fd == nil)
+		return (nil, -1);
+	return readall(fd, sortkey);
+}
+
+readall(fd: ref Sys->FD, sortkey: int): (array of ref Dir, int)
+{
+	sys = load Sys Sys->PATH;
+	dl: list of array of Dir;
+	n := 0;
+	for(;;){
+		(nr, b) := sys->dirread(fd);
+		if(nr <= 0){
+			# any error makes the whole directory unreadable
+			if(nr < 0)
+				return (nil, -1);
+			break;
+		}
+		dl = b :: dl;
+		n += nr;
+	}
+	rl := dl;
+	for(dl = nil; rl != nil; rl = tl rl)
+		dl = hd rl :: dl;
+	a := makerefs(dl, n, sortkey & COMPACT);
+	sortkey &= ~COMPACT;
+	if((sortkey & ~DESCENDING) == NONE)
+		return (a, len a);
+	return sortdir(a, sortkey);
+}
+
+makerefs(dl: list of array of Dir, n: int, compact: int): array of ref Dir
+{
+	a := array[n] of ref Dir;
+	ht: array of list of string;
+	if(compact)
+		ht = array[41] of list of string;
+	j := 0;
+	for(; dl != nil; dl = tl dl){
+		d := hd dl;
+		for(i := 0; i < len d; i++)
+			if(ht == nil || hashadd(ht, d[i].name))
+				a[j++] = ref d[i];
+	}
+	if(j != n)
+		a = a[0:j];
+	return a;
+}
+
+sortdir(a: array of ref Dir, key: int): (array of ref Dir, int)
+{
+	mergesort(a, array[len a] of ref Dir, key);
+	return (a, len a);
+}
+	
+# mergesort because it's stable.
+mergesort(a, b: array of ref Dir, key: int)
+{
+	r := len a;
+	if (r > 1) {
+		m := (r-1)/2 + 1;
+		mergesort(a[0:m], b[0:m], key);
+		mergesort(a[m:], b[m:], key);
+		b[0:] = a;
+		for ((i, j, k) := (0, m, 0); i < m && j < r; k++) {
+			if (greater(b[i], b[j], key))
+				a[k] = b[j++];
+			else
+				a[k] = b[i++];
+		}
+		if (i < m)
+			a[k:] = b[i:m];
+		else if (j < r)
+			a[k:] = b[j:r];
+	}
+}
+
+greater(x, y: ref Dir, sortkey: int): int
+{
+	case (sortkey) {
+	NAME => return(x.name > y.name);
+	ATIME => return(x.atime < y.atime);
+	MTIME => return(x.mtime < y.mtime);
+	SIZE => return(x.length > y.length);
+	NAME|DESCENDING => return(x.name < y.name);
+	ATIME|DESCENDING => return(x.atime > y.atime);
+	MTIME|DESCENDING => return(x.mtime > y.mtime);
+	SIZE|DESCENDING => return(x.length < y.length);
+	}
+	return 0;
+}
+
+# from tcl_strhash.b
+hashfn(key: string, n : int): int
+{
+	h := 0;
+	for(i := 0; i < len key; i++){
+		h = 10*h + key[i];
+		h = h%n;
+	}
+	return h%n;
+}
+
+hashadd(ht: array of list of string, nm: string): int
+{
+	idx := hashfn(nm, len ht);
+	for (ent := ht[idx]; ent != nil; ent = tl ent)
+		if (hd ent == nm)
+			return 0;
+	ht[idx] = nm :: ht[idx];
+	return 1;
+}