searchfs.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

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

/*
 * caveat:
 * this stuff is only meant to work for ascii databases
 */

typedef struct Fid Fid;
typedef struct Fs Fs;
typedef struct Quick Quick;
typedef struct Match Match;
typedef struct Search Search;

enum
{
	OPERM	= 0x3,		/* mask of all permission types in open mode */
	Nfidhash	= 32,

	/*
	 * qids
	 */
	Qroot	= 1,
	Qsearch	= 2,
	Qstats	= 3,
};

/*
 * boyer-moore quick string matching
 */
struct Quick
{
	char	*pat;
	char	*up;		/* match string for upper case of pat */
	int	len;		/* of pat (and up) -1; used for fast search */
	uchar 	jump[256];	/* jump index table */
	int	miss;		/* amount to jump if we falsely match the last char */
};
extern void	quickmk(Quick*, char*, int);
extern void	quickfree(Quick*);
extern char*	quicksearch(Quick*, char*, char*);

/*
 * exact matching of a search string
 */
struct Match
{
	Match	*next;
	char	*pat;				/* null-terminated search string */
	char	*up;				/* upper case of pat */
	int	len;				/* length of both pat and up */
	int	(*op)(Match*, char*, char*);		/* method for this partiticular search */
};

struct Search
{
	Quick		quick;		/* quick match */
	Match		*match;		/* exact matches */
	int		skip;		/* number of matches to skip */
};

extern char*	searchsearch(Search*, char*, char*, int*);
extern Search*	searchparse(char*, char*);
extern void	searchfree(Search*);

struct Fid
{
	Lock;
	Fid	*next;
	Fid	**last;
	uint	fid;
	int	ref;		/* number of fcalls using the fid */
	int	attached;		/* fid has beed attached or cloned and not clunked */

	int	open;
	Qid	qid;
	Search	*search;		/* search patterns */
	char	*where;		/* current location in the database */
	int	n;		/* number of bytes left in found item */
};

int			dostat(int, uchar*, int);
void*			emalloc(uint);
void			fatal(char*, ...);
Match*			mkmatch(Match*, int(*)(Match*, char*, char*), char*);
Match*			mkstrmatch(Match*, char*);
char*		nextsearch(char*, char*, char**, char**);
int			strlook(Match*, char*, char*);
char*			strndup(char*, int);
int			tolower(int);
int			toupper(int);
char*			urlunesc(char*, char*);
void			usage(void);

struct Fs
{
	Lock;			/* for fids */

	Fid	*hash[Nfidhash];
	uchar	statbuf[1024];	/* plenty big enough */
};
extern	void	fsrun(Fs*, int);
extern	Fid*	getfid(Fs*, uint);
extern	Fid*	mkfid(Fs*, uint);
extern	void	putfid(Fs*, Fid*);
extern	char*	fsversion(Fs*, Fcall*);
extern	char*	fsauth(Fs*, Fcall*);
extern	char*	fsattach(Fs*, Fcall*);
extern	char*	fswalk(Fs*, Fcall*);
extern	char*	fsopen(Fs*, Fcall*);
extern	char*	fscreate(Fs*, Fcall*);
extern	char*	fsread(Fs*, Fcall*);
extern	char*	fswrite(Fs*, Fcall*);
extern	char*	fsclunk(Fs*, Fcall*);
extern	char*	fsremove(Fs*, Fcall*);
extern	char*	fsstat(Fs*, Fcall*);
extern	char*	fswstat(Fs*, Fcall*);

char	*(*fcalls[])(Fs*, Fcall*) =
{
	[Tversion]		fsversion,
	[Tattach]	fsattach,
	[Tauth]	fsauth,
	[Twalk]		fswalk,
	[Topen]		fsopen,
	[Tcreate]	fscreate,
	[Tread]		fsread,
	[Twrite]	fswrite,
	[Tclunk]	fsclunk,
	[Tremove]	fsremove,
	[Tstat]		fsstat,
	[Twstat]	fswstat
};

char	Eperm[] =	"permission denied";
char	Enotdir[] =	"not a directory";
char	Enotexist[] =	"file does not exist";
char	Eisopen[] = 	"file already open for I/O";
char	Einuse[] =	"fid is already in use";
char	Enofid[] = 	"no such fid";
char	Enotopen[] =	"file is not open";
char	Ebadsearch[] =	"bad search string";

Fs	fs;
char	*database;
char	*edatabase;
int	messagesize = 8192+IOHDRSZ;
void
main(int argc, char **argv)
{
	Dir *d;
	char buf[12], *mnt, *srv;
	int fd, p[2], n;

	mnt = "/tmp";
	srv = nil;
	ARGBEGIN{
		case 's':
			srv = ARGF();
			mnt = nil;
			break;
		case 'm':
			mnt = ARGF();
			break;
	}ARGEND

	fmtinstall('F', fcallfmt);

	if(argc != 1)
		usage();
	d = nil;
	fd = open(argv[0], OREAD);
	if(fd < 0 || (d=dirfstat(fd)) == nil)
		fatal("can't open %s: %r", argv[0]);
	n = d->length;
	free(d);
	if(n == 0)
		fatal("zero length database %s", argv[0]);
	database = emalloc(n);
	if(read(fd, database, n) != n)
		fatal("can't read %s: %r", argv[0]);
	close(fd);
	edatabase = database + n;

	if(pipe(p) < 0)
		fatal("pipe failed");

	switch(rfork(RFPROC|RFMEM|RFNOTEG|RFNAMEG)){
	case 0:
		fsrun(&fs, p[0]);
		exits(nil);
	case -1:	
		fatal("fork failed");
	}

	if(mnt == nil){
		if(srv == nil)
			usage();
		fd = create(srv, OWRITE, 0666);
		if(fd < 0){
			remove(srv);
			fd = create(srv, OWRITE, 0666);
			if(fd < 0){
				close(p[1]);
				fatal("create of %s failed", srv);
			}
		}
		sprint(buf, "%d", p[1]);
		if(write(fd, buf, strlen(buf)) < 0){
			close(p[1]);
			fatal("writing %s", srv);
		}
		close(p[1]);
		exits(nil);
	}

	if(mount(p[1], -1, mnt, MREPL, "") < 0){
		close(p[1]);
		fatal("mount failed");
	}
	close(p[1]);
	exits(nil);
}

/*
 * execute the search
 * do a quick match,
 * isolate the line in which the occured,
 * and try all of the exact matches
 */
char*
searchsearch(Search *search, char *where, char *end, int *np)
{
	Match *m;
	char *s, *e;

	*np = 0;
	if(search == nil || where == nil)
		return nil;
	for(;;){
		s = quicksearch(&search->quick, where, end);
		if(s == nil)
			return nil;
		e = memchr(s, '\n', end - s);
		if(e == nil)
			e = end;
		else
			e++;
		while(s > where && s[-1] != '\n')
			s--;
		for(m = search->match; m != nil; m = m->next){
			if((*m->op)(m, s, e) == 0)
				break;
		}

		if(m == nil){
			if(search->skip > 0)
				search->skip--;
			else{
				*np = e - s;
				return s;
			}
		}

		where = e;
	}
}

/*
 * parse a search string of the form
 * tag=val&tag1=val1...
 */
Search*
searchparse(char *search, char *esearch)
{
	Search *s;
	Match *m, *next, **last;
	char *tag, *val, *p;
	int ok;

	s = emalloc(sizeof *s);
	s->match = nil;

	/*
	 * acording to the http spec,
	 * repeated search queries are ingored.
	 * the last search given is performed on the original object
	 */
	while((p = memchr(s, '?', esearch - search)) != nil){
		search = p + 1;
	}
	while(search < esearch){
		search = nextsearch(search, esearch, &tag, &val);
		if(tag == nil)
			continue;

		ok = 0;
		if(strcmp(tag, "skip") == 0){
			s->skip = strtoul(val, &p, 10);
			if(*p == 0)
				ok = 1;
		}else if(strcmp(tag, "search") == 0){
			s->match = mkstrmatch(s->match, val);
			ok = 1;
		}
		free(tag);
		free(val);
		if(!ok){
			searchfree(s);
			return nil;
		}
	}

	if(s->match == nil){
		free(s);
		return nil;
	}

	/*
	 * order the matches by probability of occurance
	 * first cut is just by length
	 */
	for(ok = 0; !ok; ){
		ok = 1;
		last = &s->match;
		for(m = *last; m && m->next; m = *last){
			if(m->next->len > m->len){
				next = m->next;
				m->next = next->next;
				next->next = m;
				*last = next;
				ok = 0;
			}
			last = &m->next;
		}
	}

	/*
	 * convert the best search into a fast lookup
	 */
	m = s->match;
	s->match = m->next;
	quickmk(&s->quick, m->pat, 1);
	free(m->pat);
	free(m->up);
	free(m);
	return s;
}

void
searchfree(Search *s)
{
	Match *m, *next;

	if(s == nil)
		return;
	for(m = s->match; m; m = next){
		next = m->next;
		free(m->pat);
		free(m->up);
		free(m);
	}
	quickfree(&s->quick);
	free(s);
}

char*
nextsearch(char *search, char *esearch, char **tagp, char **valp)
{
	char *tag, *val;

	*tagp = nil;
	*valp = nil;
	for(tag = search; search < esearch && *search != '='; search++)
		;
	if(search == esearch)
		return search;
	tag = urlunesc(tag, search);
	search++;
	for(val = search; search < esearch && *search != '&'; search++)
		;
	val = urlunesc(val, search);
	if(search != esearch)
		search++;
	*tagp = tag;
	*valp = val;
	return search;
}

Match*
mkstrmatch(Match *m, char *pat)
{
	char *s;

	for(s = pat; *s; s++){
		if(*s == ' ' || *s == '\t' || *s == '\n' || *s == '\r'){
			*s = 0;
			m = mkmatch(m, strlook, pat);
			pat = s + 1;
		}else
			*s = tolower(*s);
	}
	return mkmatch(m, strlook, pat);
}

Match*
mkmatch(Match *next, int (*op)(Match*, char*, char*), char *pat)
{
	Match *m;
	char *p;
	int n;

	n = strlen(pat);
	if(n == 0)
		return next;
	m = emalloc(sizeof *m);
	m->op = op;
	m->len = n;
	m->pat = strdup(pat);
	m->up = strdup(pat);
	for(p = m->up; *p; p++)
		*p = toupper(*p);
	for(p = m->pat; *p; p++)
		*p = tolower(*p);
	m->next = next;
	return m;
}

int
strlook(Match *m, char *str, char *e)
{
	char *pat, *up, *s;
	int c, pc, fc, fuc, n;

	n = m->len;
	fc = m->pat[0];
	fuc = m->up[0];
	for(; str + n <= e; str++){
		c = *str;
		if(c != fc && c != fuc)
			continue;
		s = str + 1;
		up = m->up + 1;
		for(pat = m->pat + 1; pc = *pat; pat++){
			c = *s;
			if(c != pc && c != *up)
				break;
			up++;
			s++;
		}
		if(pc == 0)
			return 1;
	}
	return 0;
}

/*
 * boyer-moore style pattern matching
 * implements an exact match for ascii
 * however, if mulitbyte upper-case and lower-case
 * characters differ in length or in more than one byte,
 * it only implements an approximate match
 */
void
quickmk(Quick *q, char *spat, int ignorecase)
{
	char *pat, *up;
	uchar *j;	
	int ep, ea, cp, ca, i, c, n;

	/*
	 * allocate the machine
	 */
	n = strlen(spat);
	if(n == 0){
		q->pat = nil;
		q->up = nil;
		q->len = -1;
		return;
	}
	pat = emalloc(2* n + 2);
	q->pat = pat;
	up = pat;
	if(ignorecase)
		up = pat + n + 1;
	q->up = up;
	while(c = *spat++){
		if(ignorecase){
			*up++ = toupper(c);
			c = tolower(c);
		}
		*pat++ = c;
	}
	pat = q->pat;
	up = q->up;
	pat[n] = up[n] = '\0';

	/*
	 * make the skipping table
	 */
	if(n > 255)
		n = 255;
	j = q->jump;
	memset(j, n, 256);
	n--;
	q->len = n;
	for(i = 0; i <= n; i++){
		j[(uchar)pat[i]] = n - i;
		j[(uchar)up[i]] = n - i;
	}
	
	/*
	 * find the minimum safe amount to skip
	 * if we match the last char but not the whole pat
	 */
	ep = pat[n];
	ea = up[n];
	for(i = n - 1; i >= 0; i--){
		cp = pat[i];
		ca = up[i];
		if(cp == ep || cp == ea || ca == ep || ca == ea)
			break;
	}
	q->miss = n - i;
}

void
quickfree(Quick *q)
{
	if(q->pat != nil)