Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!gatech!hao!ames!ucbcad!ucbvax!unisoft!lll-lcc!well!ewhac
From: ewhac@well.UUCP (Leo 'Bols Ewhac' Schwab)
Newsgroups: comp.sys.amiga
Subject: Re: Faster directories under AmigaDOS -> binary incl.
Message-ID: <3040@well.UUCP>
Date: Tue, 12-May-87 01:05:58 EDT
Article-I.D.: well.3040
Posted: Tue May 12 01:05:58 1987
Date-Received: Thu, 14-May-87 06:36:28 EDT
References: <8705110932.AA29181@cogsci.berkeley.edu>
Reply-To: ewhac@well.UUCP (Leo 'Bols Ewhac' Schwab)
Organization: Whole Earth 'Lectronic Link, Sausalito, CA
Lines: 376
Summary: My own version.

[ Removal of this line by any means is punishable by Federal law. ]

	Shit.

	It seems like every time I come up with something resembling a useful
utility, someone else beats me to it, and comes out with something almost
the same.

	This was the case a looong time ago with a program I called LITE
(Leo's Incredible Terminal Emulator).  Then David Wecker came out with his
VT100 emulator, and suddenly there didn't seem to be any point in it any
more (no slight upon you, Dave; it's an excellent program).

	Now it's happened again.  I *WAS* going to write a program for
publication in Amazing Computing that did faster directories.  Then I found
out that Dave Haynie has been working on almost the exact same program for
the exact same magazine.  No problem, thinks I, I'll just clean it up a bit
and throw it at the Net, or RoboCity News, or something.

	Now I log in to find this gentleman has already posted a program to
help speed up directories.  It's enough to make a guy beat his head against
the keyboard.  In fact, I think I will.

	nhbg mjmn ,kjh ,kmjnh nhbgvf bgvf]trnhbgvf mnjhbg .l,kmj .,m!!!!

	Sigh.

	Oh well, you may as well have the program to see what I did.  It
uses the AmigaDOG ACTION_GET_BLOCK packet to get raw disk blocks off the
disk and do things to them.  Preliminary studies indicate that directories
are only 25% faster on average.  Speed increases ranged from 50% to -5%
(yup, sorting things actually makes it run slower).  The test beds I used
were Fish Disk 13 (all that BASIC crud), and the three-disk Portal program
from Activision.  'dir' on Portal disk #2 takes about 2:35.  My program
takes about 1:29 (as I recall).

	Known limitations:  Running the program on the boot disk crashes the
machine (if you type 'cd' and get "DF0:" as a response, you are on the boot
device).  If you 'cd' into a directory, remove the disk in question, then
run the program, it fails gracefully, but gives an unhelpful error code.  It
doesn't work on the RAM: driver.

	Dave Haynie and I have been conducting an E-mail discussion on our
respective programs, and based on his description, his deserves publication
more than mine does, and he has been working longer on it.  So Dave,
consider this official notification:  Clean up your program and send it off
to Amazing.

	I'm not trying to be negative about this.....  All right, maybe I
am.  But I mean, gee whiz.  This is frustrating.....

	Oh well, hope you find the program useful.  External hacking to
improve it is encouraged.

	By the way, the program is called 'eless.'

_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 ________		 ___			Leo L. Schwab
	   \		/___--__		The Guy in The Cape
  ___  ___ /\		    ---##\		ihnp4!ptsfa!well!ewhac
      /   X  \_____    |  __ _---))			..or..
     /   /_\--    -----+==____\ // \  _		well ---\
___ (   o---+------------------O/   \/ \	dual ----> !unicom!ewhac
     \     /		    ___ \_  (`o )	hplabs -/       ("AE-wack")
 ____ \___/			     \_/
	      Recumbent Bikes:			"Work FOR?  I don't work FOR
	    The _O_n_l_y Way To Fly!		anybody!  I'm just having fun."

_-_-_-_-_-_ All right, fine.  Don't cut here.  See if I care... _-_-_-_-_-_-_
/* :ts=8 bk=0
 * 
 * eless.c:	An attempt at a reasonable-speed 'ls' program by fiddling
 *		with the DOS.
 *
 *		Compiles under Manx 3.20 and patched 3.40.
 *		cc eless.c
 *		ln eless.c -lc -o eless
 *
 * Leo L. Schwab		8704.26		(415)-456-6565
 */

#include <exec/types.h>
#include <exec/memory.h>
#include <libraries/dosextens.h>

#define	BLOCKSIZE	128
#define	STARTTAB	6
#define ENDTAB		(BLOCKSIZE-51)
#define	TABSIZ		(BLOCKSIZE-56)
#define	FILENAME	(BLOCKSIZE-20)
#define	HASHCHAIN	(BLOCKSIZE-4)
#define	SECONDARY	(BLOCKSIZE-1)
#define	ST_DIR		2
#define	ST_FILE		-3

/*
 * Note:  I usually declare Amiga functions this way to disable the compiler's
 * type checking.  This allows me to assign values to variables without
 * explicitly casting them to the appropriate type.  In reality, these
 * functions return things entirely different from the way I've declared
 * them.  For example, CreatePort() should really be declared as:
 *
 * struct MsgPort *CreatePort();
 *
 * Caveat Programmer.
 */
extern void	*AllocMem(), *CreatePort(), *RemTail(), *FindTask();
extern long	Lock(), Examine();

long		dopacket();
int		longcmp(), namecmp();


struct StandardPacket	*packet;
struct FileInfoBlock	*fib;
struct FileLock		*lock;
struct InfoData		*id;
struct MsgPort		*dosreply;
BPTR			lok;
long			*buf, hashtab[TABSIZ];


main (ac, av)
char **av;
{
	int flag;

	openstuff ();

	if (ac < 2)		/*  No arguments; do current directory  */
		printdir (((struct Process *) FindTask (0L)) -> pr_CurrentDir);

	else {			/*  Arguments; treat as directories  */
		flag = (ac > 2);
		while (++av, --ac) {
			if (!(lok = Lock (*av, ACCESS_READ))) {
				printf ("%s: Not found.\n", *av);
				if (ac > 1)
					putchar ('\n');
				continue;
			}

			if (!Examine (lok, fib))
				die ("Examine failed.");
			if (fib -> fib_DirEntryType < 0) {
				printf ("%s: Not a directory.\n", *av);
				if (ac > 1)
					putchar ('\n');
				continue;
			}

			if (flag)
				printf ("%s:\n", *av);
			printdir (lok);
			if (ac > 1)
				putchar ('\n');
			UnLock (lok);  lok = NULL;
		}
	}

	closestuff ();
}


/*
 * This function prints the directory in a nice, pretty columnar format.
 */
printdir (dirlock)
BPTR dirlock;
{
	struct List		namelist;
	register struct Node	*name, **namearray;
	long			args[2];
	register int		i, n;
	int			len = 0, ncols, nlines, nfiles = 0;
	char			fmt1[16], fmt2[16];
	char			*fn = (char *) (&buf[FILENAME]) + 1;

	lock = (struct FileLock *) (dirlock << 2);
	args[0] = lock -> fl_Key;	/*  Block number  */
	args[1] = (long) buf >> 2;	/*  BPTR to buffer  */

	/*  Attempt to get raw directory block.  */
	if (!dopacket (lock -> fl_Task, ACTION_GET_BLOCK, args, 2)) {
		if (packet -> sp_Pkt.dp_Res2 == ERROR_ACTION_NOT_KNOWN)
			printf ("Not a block device.\n");
		else
			printf ("Error %ld while getting dirblock.\n",
				packet -> sp_Pkt.dp_Res2);
		return;
	}

	/*  Copy DOS's hash table into our array.  */
	for (i=0; i<TABSIZ; i++)
		hashtab[i] = buf[i+STARTTAB];

	NewList (&namelist);
	while (1) {
		/*  Sort hash table.  */
		qsort (hashtab, TABSIZ, sizeof (long), longcmp);
		if (!hashtab[0])	/*  Empty hash table  */
			break;

		/*
		 * Retrieve disk blocks according to sorted hash table and
		 * collect filenames.
		 */
		for (i=0; hashtab[i] && i<TABSIZ; i++) {
			args[0] = hashtab[i];
			dopacket (lock -> fl_Task, ACTION_GET_BLOCK, args, 2);

			if (!(name = AllocMem (sizeof (*name) + *(fn-1) + 1L,
					       MEMF_CLEAR))) {
				puts ("Node memory allocation failure.");
				goto bombout;
			}

			name -> ln_Name = (char *) name + sizeof (*name);
			name -> ln_Type = (buf[SECONDARY] == ST_DIR);
			fn[*(fn-1)] = '\0';	/*  Force null-termination  */
			strcpy (name -> ln_Name, fn);
			AddTail (&namelist, name);
			nfiles++;	/*  Number of files found  */

			hashtab[i] = buf[HASHCHAIN];
		}
	}
	if (!nfiles)	/*  No files  */
		return;

	/*  Create array that qsort can deal with.  */
	if (!(namearray = AllocMem
			   ((long) nfiles * sizeof (char *), MEMF_CLEAR))) {
		puts ("Name array allocation failure.");
		goto bombout;
	}

	/*  Load up the array.  */
	for (name = namelist.lh_Head, i=0;
	     name -> ln_Succ;
	     name = name -> ln_Succ, i++)
	     	namearray[i] = name;

	/*  Alphabetize filenames.  */
	qsort (namearray, nfiles, sizeof (struct Node *), namecmp);

	/*  Find longest string so we can format intelligently.  */
	for (i=0; i<nfiles; i++)
		if ((n = strlen (namearray[i] -> ln_Name)) > len)
			len = n;
	len += 2;	/*  Inter-name spacing  */

	/*  Print them suckers out  */
	ncols = 77 / len;		/*  Assume CON: is 77 columns  */
	nlines = nfiles/ncols + (nfiles%ncols != 0);
	sprintf (fmt1, "%%-%ds", len);		/*  Normal format string  */
	sprintf (fmt2, "\033[33m%%-%ds\033[m", len);	/* For directories */
	for (i=0; i<nlines; i++) {
		for (n=i; n<nfiles; n+=nlines)
			printf (namearray[n] -> ln_Type ? fmt2 : fmt1,
				namearray[n] -> ln_Name);
		putchar ('\n');
	}

	/*  Phew!  Now free all the stuff we allocated.  */
bombout:
	freenamelist (&namelist);
	if (namearray)
		FreeMem (namearray, (long) nfiles * sizeof (struct Node *));
}

freenamelist (list)
struct List *list;
{
	register struct Node *now;

	while (now = RemTail (list))
		FreeMem (now, sizeof (*now) + strlen (now -> ln_Name) + 1L);
}


/*
 * This function assumes the existence of a properly initialized
 * standardpacket structure called "packet" and a reply port called
 * "dosreply".  A more general function would not do this.
 *
 * This function is synchronous i.e. it doesn't return until the specified
 * action has been performed.
 */
long
dopacket (proc, action, args, nargs)
struct MsgPort *proc;
long action;
register long *args;
register int nargs;
{
	register long *argp = &packet -> sp_Pkt.dp_Arg1;

	for (; nargs>0; nargs--)
		*argp++ = *args++;

	/*
	 * AmigaDOS scribbles over the reply port, so we have to initialize
	 * it every time we send a packet.
	 */
	packet -> sp_Pkt.dp_Port = dosreply;
	packet -> sp_Pkt.dp_Type = action;

	PutMsg (proc, packet);
	WaitPort (dosreply);
	GetMsg (dosreply);

	return (packet -> sp_Pkt.dp_Res1);
}


/*
 * These functions are called by qsort().  The sense of camparisons is
 * reversed in longcmp to get a reverse sort (largest elements first).
 */
longcmp (foo, bar)
long *foo, *bar;
{
	/*
	 * We have to do it this way because qsort() expects an int to be
	 * returned.  Subtracting longs directly might overflow a 16-bit int.
	 */
	return ((*foo < *bar) - (*foo > *bar));
}

namecmp (foo, bar)
struct Node **foo, **bar;
{
	return (strcmp ((*foo) -> ln_Name, (*bar) -> ln_Name));
}


/*
 * Resource allocation/deallocation routines.
 */
openstuff ()
{
	if (!(packet = AllocMem ((long) sizeof (*packet), MEMF_CLEAR)))
		die ("Can't allocate packet space.");

	if (!(dosreply = CreatePort (NULL, NULL)))
		die ("Dos reply port create failed.");
	packet -> sp_Msg.mn_Node.ln_Name	= (char *) &packet -> sp_Pkt;
	packet -> sp_Pkt.dp_Link		= &packet -> sp_Msg;

	if (!(fib = AllocMem ((long) sizeof (*fib), MEMF_CLEAR)))
		die ("Can't allocate FileInfoBlock.");

	/*
	 * Note:  This allocation may not work with DMA hard disks.
	 */
	if (!(buf = AllocMem (BLOCKSIZE * 4L, MEMF_CHIP | MEMF_PUBLIC)))
		die ("Couldn't allocate sector buffer.");
}

closestuff ()
{
	if (lok)		UnLock (lok);
	if (buf)		FreeMem (buf, BLOCKSIZE * 4L);
	if (fib)		FreeMem (fib, (long) sizeof (*fib));
	if (dosreply)		DeletePort (dosreply);
	if (packet)		FreeMem (packet, (long) sizeof (*packet));
}

die (str)
char *str;
{
	puts (str);
	closestuff ();
	exit (1);
}