8 * this stuff is only meant to work for ascii databases
11 typedef struct Fid Fid;
13 typedef struct Quick Quick;
14 typedef struct Match Match;
15 typedef struct Search Search;
19 OPERM = 0x3, /* mask of all permission types in open mode */
31 * boyer-moore quick string matching
36 char *up; /* match string for upper case of pat */
37 int len; /* of pat (and up) -1; used for fast search */
38 uchar jump[256]; /* jump index table */
39 int miss; /* amount to jump if we falsely match the last char */
41 extern void quickmk(Quick*, char*, int);
42 extern void quickfree(Quick*);
43 extern char* quicksearch(Quick*, char*, char*);
46 * exact matching of a search string
51 char *pat; /* null-terminated search string */
52 char *up; /* upper case of pat */
53 int len; /* length of both pat and up */
54 int (*op)(Match*, char*, char*); /* method for this partiticular search */
59 Quick quick; /* quick match */
60 Match *match; /* exact matches */
61 int skip; /* number of matches to skip */
64 extern char* searchsearch(Search*, char*, char*, int*);
65 extern Search* searchparse(char*, char*);
66 extern void searchfree(Search*);
74 int ref; /* number of fcalls using the fid */
75 int attached; /* fid has beed attached or cloned and not clunked */
79 Search *search; /* search patterns */
80 char *where; /* current location in the database */
81 int n; /* number of bytes left in found item */
84 int dostat(int, uchar*, int);
86 void fatal(char*, ...);
87 Match* mkmatch(Match*, int(*)(Match*, char*, char*), char*);
88 Match* mkstrmatch(Match*, char*);
89 char* nextsearch(char*, char*, char**, char**);
90 int strlook(Match*, char*, char*);
91 char* strndup(char*, int);
94 char* urlunesc(char*, char*);
102 uchar statbuf[1024]; /* plenty big enough */
104 extern void fsrun(Fs*, int);
105 extern Fid* getfid(Fs*, uint);
106 extern Fid* mkfid(Fs*, uint);
107 extern void putfid(Fs*, Fid*);
108 extern char* fsversion(Fs*, Fcall*);
109 extern char* fsauth(Fs*, Fcall*);
110 extern char* fsattach(Fs*, Fcall*);
111 extern char* fswalk(Fs*, Fcall*);
112 extern char* fsopen(Fs*, Fcall*);
113 extern char* fscreate(Fs*, Fcall*);
114 extern char* fsread(Fs*, Fcall*);
115 extern char* fswrite(Fs*, Fcall*);
116 extern char* fsclunk(Fs*, Fcall*);
117 extern char* fsremove(Fs*, Fcall*);
118 extern char* fsstat(Fs*, Fcall*);
119 extern char* fswstat(Fs*, Fcall*);
121 char *(*fcalls[])(Fs*, Fcall*) =
123 [Tversion] fsversion,
137 char Eperm[] = "permission denied";
138 char Enotdir[] = "not a directory";
139 char Enotexist[] = "file does not exist";
140 char Eisopen[] = "file already open for I/O";
141 char Einuse[] = "fid is already in use";
142 char Enofid[] = "no such fid";
143 char Enotopen[] = "file is not open";
144 char Ebadsearch[] = "bad search string";
149 int messagesize = 8192+IOHDRSZ;
151 main(int argc, char **argv)
154 char buf[12], *mnt, *srv;
169 fmtinstall('F', fcallfmt);
174 fd = open(argv[0], OREAD);
175 if(fd < 0 || (d=dirfstat(fd)) == nil)
176 fatal("can't open %s: %r", argv[0]);
180 fatal("zero length database %s", argv[0]);
181 database = emalloc(n);
182 if(read(fd, database, n) != n)
183 fatal("can't read %s: %r", argv[0]);
185 edatabase = database + n;
188 fatal("pipe failed");
190 switch(rfork(RFPROC|RFMEM|RFNOTEG|RFNAMEG)){
195 fatal("fork failed");
201 fd = create(srv, OWRITE, 0666);
204 fd = create(srv, OWRITE, 0666);
207 fatal("create of %s failed", srv);
210 sprint(buf, "%d", p[1]);
211 if(write(fd, buf, strlen(buf)) < 0){
213 fatal("writing %s", srv);
219 if(mount(p[1], -1, mnt, MREPL, "") == -1){
221 fatal("mount failed");
230 * isolate the line in which the occured,
231 * and try all of the exact matches
234 searchsearch(Search *search, char *where, char *end, int *np)
240 if(search == nil || where == nil)
243 s = quicksearch(&search->quick, where, end);
246 e = memchr(s, '\n', end - s);
251 while(s > where && s[-1] != '\n')
253 for(m = search->match; m != nil; m = m->next){
254 if((*m->op)(m, s, e) == 0)
272 * parse a search string of the form
273 * tag=val&tag1=val1...
276 searchparse(char *search, char *esearch)
279 Match *m, *next, **last;
283 s = emalloc(sizeof *s);
287 * acording to the http spec,
288 * repeated search queries are ingored.
289 * the last search given is performed on the original object
291 while((p = memchr(s, '?', esearch - search)) != nil){
294 while(search < esearch){
295 search = nextsearch(search, esearch, &tag, &val);
300 if(strcmp(tag, "skip") == 0){
301 s->skip = strtoul(val, &p, 10);
304 }else if(strcmp(tag, "search") == 0){
305 s->match = mkstrmatch(s->match, val);
322 * order the matches by probability of occurance
323 * first cut is just by length
328 for(m = *last; m && m->next; m = *last){
329 if(m->next->len > m->len){
331 m->next = next->next;
341 * convert the best search into a fast lookup
345 quickmk(&s->quick, m->pat, 1);
353 searchfree(Search *s)
359 for(m = s->match; m; m = next){
365 quickfree(&s->quick);
370 nextsearch(char *search, char *esearch, char **tagp, char **valp)
376 for(tag = search; search < esearch && *search != '='; search++)
378 if(search == esearch)
380 tag = urlunesc(tag, search);
382 for(val = search; search < esearch && *search != '&'; search++)
384 val = urlunesc(val, search);
385 if(search != esearch)
393 mkstrmatch(Match *m, char *pat)
397 for(s = pat; *s; s++){
398 if(*s == ' ' || *s == '\t' || *s == '\n' || *s == '\r'){
400 m = mkmatch(m, strlook, pat);
405 return mkmatch(m, strlook, pat);
409 mkmatch(Match *next, int (*op)(Match*, char*, char*), char *pat)
418 m = emalloc(sizeof *m);
421 m->pat = strdup(pat);
423 for(p = m->up; *p; p++)
425 for(p = m->pat; *p; p++)
432 strlook(Match *m, char *str, char *e)
435 int c, pc, fc, fuc, n;
440 for(; str + n <= e; str++){
442 if(c != fc && c != fuc)
446 for(pat = m->pat + 1; pc = *pat; pat++){
448 if(c != pc && c != *up)
460 * boyer-moore style pattern matching
461 * implements an exact match for ascii
462 * however, if mulitbyte upper-case and lower-case
463 * characters differ in length or in more than one byte,
464 * it only implements an approximate match
467 quickmk(Quick *q, char *spat, int ignorecase)
471 int ep, ea, cp, ca, i, c, n;
474 * allocate the machine
483 pat = emalloc(2* n + 2);
498 pat[n] = up[n] = '\0';
501 * make the skipping table
509 for(i = 0; i <= n; i++){
510 j[(uchar)pat[i]] = n - i;
511 j[(uchar)up[i]] = n - i;
515 * find the minimum safe amount to skip
516 * if we match the last char but not the whole pat
520 for(i = n - 1; i >= 0; i--){
523 if(cp == ep || cp == ea || ca == ep || ca == ea)
538 quicksearch(Quick *q, char *s, char *e)
540 char *pat, *up, *m, *ee;
551 ee = e - (len * 4 + 4);
554 * look for a match on the last char
556 while(s < ee && (n = j[(uchar)*s])){
564 while(n = j[(uchar)*s]){
571 * does the string match?
574 for(n = 0; c = pat[n]; n++){
576 if(c != mc && mc != up[n])
587 fsrun(Fs *fs, int fd)
594 buf = emalloc(messagesize);
595 while((n = read9pmsg(fd, buf, messagesize)) != 0){
597 fatal("mount read: %r");
598 rpc.data = (char*)buf + IOHDRSZ;
599 if(convM2S(buf, n, &rpc) != n)
600 fatal("convM2S format error: %r");
603 * flushes are way too hard.
604 * a reply to the original message seems to work
606 if(rpc.type == Tflush)
608 else if(rpc.type >= Tmax || !fcalls[rpc.type])
609 err = "bad fcall type";
611 err = (*fcalls[rpc.type])(fs, &rpc);
617 n = convS2M(&rpc, buf, messagesize);
618 // fprint(2, "send: %F\n", &rpc);
619 if(write(fd, buf, n) != n)
620 fatal("mount write");
625 mkfid(Fs *fs, uint fid)
631 for(f = fs->hash[h]; f; f = f->next){
636 f = emalloc(sizeof *f);
637 f->next = fs->hash[h];
639 f->next->last = &f->next;
640 f->last = &fs->hash[h];
651 getfid(Fs *fs, uint fid)
657 for(f = fs->hash[h]; f; f = f->next){
672 if(f->ref == 0 && f->attached == 0){
675 f->next->last = f->last;
677 searchfree(f->search);
683 fsversion(Fs *, Fcall *rpc)
686 return "version: message size too small";
687 if(rpc->msize > messagesize)
688 rpc->msize = messagesize;
689 messagesize = rpc->msize;
690 if(strncmp(rpc->version, "9P", 2) != 0)
691 rpc->version = "unknown";
693 rpc->version = "9P2000";
698 fsauth(Fs *, Fcall *)
700 return "searchfs: authentication not required";
704 fsattach(Fs *fs, Fcall *rpc)
708 f = mkfid(fs, rpc->fid);
721 fswalk(Fs *fs, Fcall *rpc)
724 int nqid, nwname, type;
728 f = getfid(fs, rpc->fid);
732 if(rpc->fid != rpc->newfid){
733 nf = mkfid(fs, rpc->newfid);
745 nwname = rpc->nwname;
746 for(nqid=0; nqid<nwname; nqid++){
751 name = rpc->wname[nqid];
752 if(strcmp(name, "search") == 0){
755 }else if(strcmp(name, "stats") == 0){
758 }else if(strcmp(name, ".") == 0 || strcmp(name, "..") == 0){
765 rpc->wqid[nqid] = (Qid){path, 0, type};
769 if(nf != nil && nqid < nwname)
772 f->qid = rpc->wqid[nqid-1];
782 fsopen(Fs *fs, Fcall *rpc)
787 f = getfid(fs, rpc->fid);
794 mode = rpc->mode & OPERM;
796 || f->qid.path == Qroot && (mode == OWRITE || mode == ORDWR)){
805 rpc->iounit = messagesize-IOHDRSZ;
811 fscreate(Fs *, Fcall *)
817 fsread(Fs *fs, Fcall *rpc)
820 int n, off, count, len;
822 f = getfid(fs, rpc->fid);
832 if(f->qid.path == Qroot){
836 rpc->count = dostat(Qsearch, (uchar*)rpc->data, count);
838 if(off == 0 && rpc->count <= BIT16SZ)
839 return "directory read count too small";
842 if(f->qid.path == Qstats){
845 for(len = 0; len < count; len += n){
846 if(f->where == nil || f->search == nil)
849 f->where = searchsearch(f->search, f->where, edatabase, &f->n);
854 memmove(rpc->data+len, f->where, n);
866 fswrite(Fs *fs, Fcall *rpc)
870 f = getfid(fs, rpc->fid);
873 if(!f->open || f->qid.path != Qsearch){
879 searchfree(f->search);
880 f->search = searchparse(rpc->data, rpc->data + rpc->count);
881 if(f->search == nil){
892 fsclunk(Fs *fs, Fcall *rpc)
896 f = getfid(fs, rpc->fid);
905 fsremove(Fs *, Fcall *)
911 fsstat(Fs *fs, Fcall *rpc)
915 f = getfid(fs, rpc->fid);
918 rpc->stat = fs->statbuf;
919 rpc->nstat = dostat(f->qid.path, rpc->stat, sizeof fs->statbuf);
921 if(rpc->nstat <= BIT16SZ)
922 return "stat count too small";
927 fswstat(Fs *, Fcall *)
933 dostat(int path, uchar *buf, int nbuf)
957 d.uid = d.gid = d.muid = "none";
958 d.atime = d.mtime = time(nil);
959 return convD2M(&d, buf, nbuf);
963 urlunesc(char *s, char *e)
968 v = emalloc((e - s) + 1);
969 for(t = v; s < e; s++){
975 if(n >= '0' && n <= '9')
977 else if(n >= 'A' && n <= 'F')
979 else if(n >= 'a' && n <= 'f')
985 if(n >= '0' && n <= '9')
987 else if(n >= 'A' && n <= 'F')
989 else if(n >= 'a' && n <= 'f')
1005 if(c >= 'a' && c <= 'z')
1013 if(c >= 'A' && c <= 'Z')
1019 fatal(char *fmt, ...)
1024 write(2, "searchfs: ", 8);
1026 vseprint(buf, buf+1024, fmt, arg);
1028 write(2, buf, strlen(buf));
1040 fatal("out of memory");
1048 fprint(2, "usage: searchfs [-m mountpoint] [-s srvfile] database\n");