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, "") < 0){
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);
597 * reading from a pipe or a network device
598 * will give an error after a few eof reads
599 * however, we cannot tell the difference
600 * between a zero-length read and an interrupt
601 * on the processes writing to us,
602 * so we wait for the error
604 n = read9pmsg(fd, buf, messagesize);
610 rpc.data = (char*)buf + IOHDRSZ;
611 if(convM2S(buf, n, &rpc) == 0)
613 // fprint(2, "recv: %F\n", &rpc);
617 * flushes are way too hard.
618 * a reply to the original message seems to work
620 if(rpc.type == Tflush)
622 else if(rpc.type >= Tmax || !fcalls[rpc.type])
623 err = "bad fcall type";
625 err = (*fcalls[rpc.type])(fs, &rpc);
631 n = convS2M(&rpc, buf, messagesize);
632 // fprint(2, "send: %F\n", &rpc);
633 if(write(fd, buf, n) != n)
634 fatal("mount write");
639 mkfid(Fs *fs, uint fid)
645 for(f = fs->hash[h]; f; f = f->next){
650 f = emalloc(sizeof *f);
651 f->next = fs->hash[h];
653 f->next->last = &f->next;
654 f->last = &fs->hash[h];
665 getfid(Fs *fs, uint fid)
671 for(f = fs->hash[h]; f; f = f->next){
686 if(f->ref == 0 && f->attached == 0){
689 f->next->last = f->last;
691 searchfree(f->search);
697 fsversion(Fs *, Fcall *rpc)
700 return "version: message size too small";
701 if(rpc->msize > messagesize)
702 rpc->msize = messagesize;
703 messagesize = rpc->msize;
704 if(strncmp(rpc->version, "9P2000", 6) != 0)
705 return "unrecognized 9P version";
706 rpc->version = "9P2000";
711 fsauth(Fs *, Fcall *)
713 return "searchfs: authentication not required";
717 fsattach(Fs *fs, Fcall *rpc)
721 f = mkfid(fs, rpc->fid);
734 fswalk(Fs *fs, Fcall *rpc)
737 int nqid, nwname, type;
741 f = getfid(fs, rpc->fid);
745 if(rpc->fid != rpc->newfid){
746 nf = mkfid(fs, rpc->newfid);
758 nwname = rpc->nwname;
759 for(nqid=0; nqid<nwname; nqid++){
764 name = rpc->wname[nqid];
765 if(strcmp(name, "search") == 0){
768 }else if(strcmp(name, "stats") == 0){
771 }else if(strcmp(name, ".") == 0 || strcmp(name, "..") == 0){
778 rpc->wqid[nqid] = (Qid){path, 0, type};
782 if(nf != nil && nqid < nwname)
785 f->qid = rpc->wqid[nqid-1];
795 fsopen(Fs *fs, Fcall *rpc)
800 f = getfid(fs, rpc->fid);
807 mode = rpc->mode & OPERM;
809 || f->qid.path == Qroot && (mode == OWRITE || mode == ORDWR)){
818 rpc->iounit = messagesize-IOHDRSZ;
824 fscreate(Fs *, Fcall *)
830 fsread(Fs *fs, Fcall *rpc)
833 int n, off, count, len;
835 f = getfid(fs, rpc->fid);
845 if(f->qid.path == Qroot){
849 rpc->count = dostat(Qsearch, (uchar*)rpc->data, count);
851 if(off == 0 && rpc->count <= BIT16SZ)
852 return "directory read count too small";
855 if(f->qid.path == Qstats){
858 for(len = 0; len < count; len += n){
859 if(f->where == nil || f->search == nil)
862 f->where = searchsearch(f->search, f->where, edatabase, &f->n);
867 memmove(rpc->data+len, f->where, n);
879 fswrite(Fs *fs, Fcall *rpc)
883 f = getfid(fs, rpc->fid);
886 if(!f->open || f->qid.path != Qsearch){
892 searchfree(f->search);
893 f->search = searchparse(rpc->data, rpc->data + rpc->count);
894 if(f->search == nil){
905 fsclunk(Fs *fs, Fcall *rpc)
909 f = getfid(fs, rpc->fid);
918 fsremove(Fs *, Fcall *)
924 fsstat(Fs *fs, Fcall *rpc)
928 f = getfid(fs, rpc->fid);
931 rpc->stat = fs->statbuf;
932 rpc->nstat = dostat(f->qid.path, rpc->stat, sizeof fs->statbuf);
934 if(rpc->nstat <= BIT16SZ)
935 return "stat count too small";
940 fswstat(Fs *, Fcall *)
946 dostat(int path, uchar *buf, int nbuf)
970 d.uid = d.gid = d.muid = "none";
971 d.atime = d.mtime = time(nil);
972 return convD2M(&d, buf, nbuf);
976 urlunesc(char *s, char *e)
981 v = emalloc((e - s) + 1);
982 for(t = v; s < e; s++){
988 if(n >= '0' && n <= '9')
990 else if(n >= 'A' && n <= 'F')
992 else if(n >= 'a' && n <= 'f')
998 if(n >= '0' && n <= '9')
1000 else if(n >= 'A' && n <= 'F')
1002 else if(n >= 'a' && n <= 'f')
1018 if(c >= 'a' && c <= 'z')
1026 if(c >= 'A' && c <= 'Z')
1032 fatal(char *fmt, ...)
1037 write(2, "searchfs: ", 8);
1039 vseprint(buf, buf+1024, fmt, arg);
1041 write(2, buf, strlen(buf));
1053 fatal("out of memory");
1061 fprint(2, "usage: searchfs [-m mountpoint] [-s srvfile] database\n");