Set correct MIME type.
[doldaconnect.git] / daemon / search.c
1 /*
2  *  Dolda Connect - Modular multiuser Direct Connect-style client
3  *  Copyright (C) 2004 Fredrik Tolf (fredrik@dolda2000.com)
4  *  
5  *  This program is free software; you can redistribute it and/or modify
6  *  it under the terms of the GNU General Public License as published by
7  *  the Free Software Foundation; either version 2 of the License, or
8  *  (at your option) any later version.
9  *  
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  *  GNU General Public License for more details.
14  *  
15  *  You should have received a copy of the GNU General Public License
16  *  along with this program; if not, write to the Free Software
17  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18 */
19 #include <stdlib.h>
20 #include <malloc.h>
21 #include <wchar.h>
22 #include <wctype.h>
23 #include <errno.h>
24 #include <regex.h>
25 #include <string.h>
26 #include <time.h>
27
28 #ifdef HAVE_CONFIG_H
29 #include <config.h>
30 #endif
31 #include "utils.h"
32 #include "log.h"
33 #include "sysevents.h"
34 #include "filenet.h"
35 #include "search.h"
36
37 #define TOK_STR 0
38 #define TOK_SE 1
39 #define TOK_OP 2
40 #define TOK_CP 3
41
42 struct srchlist
43 {
44     struct srchlist *next, *prev;
45     struct search *srch;
46 };
47
48 struct tok
49 {
50     struct tok *next;
51     int type;
52     union
53     {
54         wchar_t *str;
55         struct sexpr *se;
56     } d;
57 };
58
59 struct reinfo
60 {
61     wchar_t *begstr, *endstr, *onestr;
62     struct wcslist *strs;
63 };
64
65 struct bound
66 {
67     int min, max;
68 };
69
70 static void trycommit(void);
71
72 struct search *searches = NULL;
73 static struct srchlist *searchqueue = NULL;
74 static struct timer *committimer = NULL;
75 GCBCHAIN(newsrchcb, struct search *);
76
77 wchar_t *regexunquotesimple(wchar_t *re)
78 {
79     wchar_t *specials, *buf, *p;
80     
81     specials = L"\\^$.*+?[{()|";
82     buf = smalloc((wcslen(re) + 1) * sizeof(wchar_t));
83     p = buf;
84     for(; *re != L'\0'; re++)
85     {
86         if(*re == L'\\')
87         {
88             re++;
89             if(!*re)
90             {
91                 *p = L'\0';
92                 return(buf);
93             }
94             *(p++) = *re;
95         } else {
96             if(wcschr(specials, *re) != NULL)
97             {
98                 free(buf);
99                 return(NULL);
100             }
101             *(p++) = *re;
102         }
103     }
104     *p = L'\0';
105     return(buf);
106 }
107
108 static void freesln(struct wcslist *ln, struct wcslist **list)
109 {
110     if(ln->prev != NULL)
111         ln->prev->next = ln->next;
112     if(ln->next != NULL)
113         ln->next->prev = ln->prev;
114     if(ln == *list)
115         *list = ln->next;
116     free(ln->str);
117     free(ln);
118 }
119
120 void freesl(struct wcslist **list)
121 {
122     while(*list != NULL)
123         freesln(*list, list);
124 }
125
126 static struct wcslist *newsl(struct wcslist **list, wchar_t *str)
127 {
128     struct wcslist *ln;
129     
130     ln = smalloc(sizeof(*ln));
131     memset(ln, 0, sizeof(*ln));
132     ln->str = swcsdup(str);
133     ln->len = wcslen(str);
134     ln->next = *list;
135     ln->prev = NULL;
136     if(*list != NULL)
137         (*list)->prev = ln;
138     *list = ln;
139     return(ln);
140 }
141
142 static void slmerge1(struct wcslist **list, wchar_t *str)
143 {
144     size_t len;
145     struct wcslist *cur, *next;
146     
147     len = wcslen(str);
148     for(cur = *list; cur != NULL; cur = next)
149     {
150         next = cur->next;
151         if(len <= cur->len)
152         {
153             if(((len < cur->len) && wcsexists(cur->str, str)) || !wcscmp(str, cur->str))
154                 return;
155         } else if(len > cur->len) {
156             if(wcsexists(str, cur->str))
157                 freesln(cur, list);
158         }
159     }
160     newsl(list, str);
161 }
162
163 void slmergemax(struct wcslist **dest, struct wcslist *src)
164 {
165     for(; src != NULL; src = src->next)
166         slmerge1(dest, src->str);
167 }
168
169 static struct wcslist *makeminlist1(wchar_t *s1, wchar_t *s2)
170 {
171     int i;
172     wchar_t *p1, *p2, c;
173     struct wcslist *list;
174     
175     list = NULL;
176     for(p1 = s1; *p1 != L'\0'; p1++)
177     {
178         for(p2 = s2; *p2 != L'\0'; p2++)
179         {
180             for(i = 0; (p1[i] != L'\0') && (p2[i] != L'\0') && (towlower(p1[i]) == towlower(p2[i])); i++);
181             if(i > 0)
182             {
183                 c = p2[i];
184                 p2[i] = L'\0';
185                 slmerge1(&list, p2);
186                 p2[i] = c;
187             }
188         }
189     }
190     return(list);
191 }
192
193 struct wcslist *slmergemin(struct wcslist *l1, struct wcslist *l2)
194 {
195     struct wcslist *cur1, *cur2, *list, *rlist;
196     
197     list = NULL;
198     for(cur1 = l1; cur1 != NULL; cur1 = cur1->next)
199     {
200         for(cur2 = l2; cur2 != NULL; cur2 = cur2->next)
201         {
202             rlist = makeminlist1(cur1->str, cur2->str);
203             slmergemax(&list, rlist);
204             freesl(&rlist);
205         }
206     }
207     return(list);
208 }
209
210 static struct bound readbound(wchar_t *p, wchar_t **endret)
211 {
212     struct bound ret;
213     
214     switch(*p)
215     {
216     case L'?':
217         ret.min = 0;
218         ret.max = 1;
219         p++;
220         break;
221     case L'*':
222         ret.min = 0;
223         ret.max = -1;
224         p++;
225         break;
226     case L'+':
227         ret.min = 1;
228         ret.max = -1;
229         p++;
230         break;
231     case L'{':
232         p++;
233         ret.min = wcstol(p, &p, 10);
234         if(*p == L',')
235         {
236             p++;
237             if(*p == L'}')
238                 ret.max = -1;
239             else
240                 ret.max = wcstol(p, &p, 10);
241         } else {
242             ret.max = ret.min;
243         }
244         if(*p != L'}')
245         {
246             /* Cannot happen in a validated regex... */
247             flog(LOG_WARNING, "BUG? \"Impossible\" case encountered in search.c:readbound() (No `}' after `{'-type bound!");
248         } else {
249             p++;
250         }
251         break;
252     default:
253         ret.min = 1;
254         ret.max = 1;
255         break;
256     }
257     if(endret != NULL)
258         *endret = p;
259     return(ret);
260 }
261
262 #define fnc(p) do {if((p) != NULL) free(p); (p) = NULL; p ## size = 0; p ## data = 0;} while(0)
263
264 static struct reinfo analyzere(wchar_t *re, wchar_t **endret, wchar_t endc)
265 {
266     int i, commit, parsealt;
267     struct reinfo ret, sinf;
268     struct bound b;
269     wchar_t *cs, *ns;
270     size_t cssize, csdata, nssize, nsdata, len1, len2, maxlen, minlen;
271     wchar_t beg, c;
272     struct wcslist *list;
273     
274     memset(&ret, 0, sizeof(ret));
275     commit = parsealt = 0;
276     beg = 1;
277     cs = ns = NULL;
278     cssize = csdata = nssize = nsdata = 0;
279     while((*re != endc) && !parsealt)
280     {
281         switch(*re)
282         {
283         case L'$':
284         case L'^':
285             re++;
286             commit = 1;
287             break;
288         case L'.':
289             re++;
290             b = readbound(re, &re);
291             if(b.max != 0)
292                 commit = 1;
293             break;
294         case L'(':
295             re++;
296             sinf = analyzere(re, &re, L')');
297             re++;
298             b = readbound(re, &re);
299             if(sinf.onestr != NULL)
300             {
301                 for(i = 0; i < b.min; i++)
302                 {
303                     bufcat(cs, sinf.onestr, wcslen(sinf.onestr));
304                     bufcat(ns, sinf.onestr, wcslen(sinf.onestr));
305                 }
306                 if((b.max == -1) || (b.max > b.min))
307                     commit = 1;
308             } else {
309                 commit = 1;
310                 if(b.min > 0)
311                 {
312                     if(sinf.begstr != NULL)
313                         bufcat(cs, sinf.begstr, wcslen(sinf.begstr));
314                     if(sinf.endstr != NULL)
315                         bufcat(ns, sinf.endstr, wcslen(sinf.endstr));
316                 }
317             }
318             if(sinf.begstr != NULL)
319                 free(sinf.begstr);
320             if(sinf.endstr != NULL)
321                 free(sinf.endstr);
322             if(sinf.onestr != NULL)
323                 free(sinf.onestr);
324             if(b.min > 0)
325                 slmergemax(&ret.strs, sinf.strs);
326             freesl(&sinf.strs);
327             break;
328         case L'[':
329             c = L'\0';
330             re += 2;
331             /* Must exist in a validated RE... */
332             while(*(re++) != L']');
333             readbound(re, &re);
334             commit = 1;
335             break;
336         case L'|':
337             re++;
338             parsealt = 1;
339             break;
340         case L'\\':
341             re++;
342             /* A validated RE cannot end in a backslash, so fall
343              * through */
344         default:
345             c = *(re++);
346             b = readbound(re, &re);
347             for(i = 0; i < b.min; i++)
348                 addtobuf(cs, c);
349             if((b.max == -1) || (b.max > b.min))
350                 commit = 1;
351             break;
352         }
353         if(commit)
354         {
355             if(cs != NULL)
356                 addtobuf(cs, L'\0');
357             if(beg)
358             {
359                 if(cs != NULL)
360                     ret.begstr = swcsdup(cs);
361                 beg = 0;
362             }
363             if(cs != NULL)
364                 slmerge1(&ret.strs, cs);
365             fnc(cs);
366             commit = 0;
367             if(ns != NULL)
368             {
369                 cs = swcsdup(ns);
370                 cssize = nssize;
371                 csdata = nsdata;
372                 fnc(ns);
373             }
374         }
375     }
376     if(cs != NULL)
377     {
378         addtobuf(cs, L'\0');
379         if(beg)
380             ret.onestr = swcsdup(cs);
381         else
382             ret.endstr = swcsdup(cs);
383         slmerge1(&ret.strs, cs);
384         fnc(cs);
385     }
386     if(parsealt)
387     {
388         sinf = analyzere(re, &re, endc);
389         list = slmergemin(ret.strs, sinf.strs);
390         freesl(&ret.strs);
391         freesl(&sinf.strs);
392         ret.strs = list;
393         if(sinf.begstr != NULL)
394         {
395             if(ret.begstr != NULL)
396             {
397                 for(i = 0; (sinf.begstr[i] != L'\0') && (ret.begstr != L'\0') && (ret.begstr[i] == sinf.begstr[i]); i++);
398                 if(i == 0)
399                     free(ret.begstr);
400                 else
401                     ret.begstr[i] = L'\0';
402             }
403             free(sinf.begstr);
404         } else {
405             if(ret.begstr != NULL)
406             {
407                 free(ret.begstr);
408                 ret.begstr = NULL;
409             }
410         }
411         if(sinf.endstr != NULL)
412         {
413             if(ret.endstr != NULL)
414             {
415                 len1 = wcslen(ret.endstr);
416                 len2 = wcslen(sinf.endstr);
417                 if(len1 < len2)
418                 {
419                     minlen = len1;
420                     maxlen = len2;
421                 } else {
422                     minlen = len2;
423                     maxlen = len1;
424                 }
425                 for(i = 1; (i <= minlen) && (ret.endstr[len1 - i] == sinf.endstr[len2 - i]); i++);
426                 if(i == 1)
427                     free(ret.endstr);
428                 else if(i <= maxlen)
429                     wmemmove(ret.endstr, ret.endstr + (len1 - i) + 1, i);
430             }
431             free(sinf.endstr);
432         } else {
433             if(ret.endstr != NULL)
434             {
435                 free(ret.endstr);
436                 ret.endstr = NULL;
437             }
438         }
439         if(sinf.onestr != NULL)
440         {
441             if(ret.onestr != NULL)
442             {
443                 /* XXX: Comparing beginning and end of the onestrs and
444                  * create begstr and endstr if there isn't an exact
445                  * match.*/
446                 if(wcscmp(ret.onestr, sinf.onestr))
447                 {
448                     free(ret.onestr);
449                     ret.onestr = NULL;
450                 }
451             }
452             free(sinf.onestr);
453         } else {
454             if(ret.onestr != NULL)
455             {
456                 free(ret.onestr);
457                 ret.onestr = NULL;
458             }
459         }
460     }
461     if(endret != NULL)
462         *endret = re;
463     return(ret);
464 }
465
466 #undef fnc
467
468 struct wcslist *regexfindstrings(wchar_t *re)
469 {
470     struct reinfo i;
471     
472     i = analyzere(re, NULL, L'\0');
473     if(i.begstr != NULL)
474         free(i.begstr);
475     if(i.endstr != NULL)
476         free(i.endstr);
477     if(i.onestr != NULL)
478         free(i.onestr);
479     return(i.strs);
480 }
481
482 static struct sexpr *newsexpr(void)
483 {
484     struct sexpr *sexpr;
485     
486     sexpr = smalloc(sizeof(*sexpr));
487     memset(sexpr, 0, sizeof(*sexpr));
488     sexpr->refcount = 1;
489     return(sexpr);
490 }
491
492 void getsexpr(struct sexpr *sexpr)
493 {
494     sexpr->refcount++;
495 }
496
497 void putsexpr(struct sexpr *sexpr)
498 {
499     if(--sexpr->refcount != 0)
500         return;
501     if(sexpr->l != NULL)
502         putsexpr(sexpr->l);
503     if(sexpr->r != NULL)
504         putsexpr(sexpr->r);
505     if((sexpr->op == SOP_NAMERE) || (sexpr->op == SOP_LINKRE))
506     {
507         if(sexpr->d.re.sre != NULL)
508             free(sexpr->d.re.sre);
509         if(sexpr->d.re.inited)
510             regfree(&sexpr->d.re.cre);
511     }
512     if((sexpr->op == SOP_NAMESS) || (sexpr->op == SOP_LINKSS))
513     {
514         if(sexpr->d.s != NULL)
515             free(sexpr->d.s);
516     }
517     free(sexpr);
518 }
519
520 static struct tok *newtok(void)
521 {
522     struct tok *tok;
523     
524     tok = smalloc(sizeof(*tok));
525     memset(tok, 0, sizeof(*tok));
526     tok->next = NULL;
527     return(tok);
528 }
529
530 static void freetok(struct tok *tok)
531 {
532     if((tok->type == TOK_STR) && (tok->d.str != NULL))
533         free(tok->d.str);
534     if((tok->type == TOK_SE) && (tok->d.se != NULL))
535         putsexpr(tok->d.se);
536     free(tok);
537 }
538
539 static void pushtok(struct tok *tok, struct tok **st)
540 {
541     tok->next = *st;
542     *st = tok;
543 }
544
545 static struct tok *poptok(struct tok **st)
546 {
547     struct tok *tok;
548     
549     tok = *st;
550     *st = (*st)->next;
551     return(tok);
552 }
553
554 int calccost(struct sexpr *sexpr)
555 {
556     sexpr->tcost = sexpr->cost;
557     if(sexpr->l != NULL)
558         sexpr->tcost += calccost(sexpr->l);
559     if(sexpr->r != NULL)
560         sexpr->tcost += calccost(sexpr->r);
561     return(sexpr->tcost);
562 }
563
564 struct sexpr *parsesexpr(int argc, wchar_t **argv)
565 {
566     int i, done, std;
567     struct tok *st, *tok, *tok2;
568     struct sexpr *sexpr;
569     char *buf;
570     wchar_t *wbuf;
571     
572     std = 0;
573     st = NULL;
574     for(i = 0; i < argc; i++)
575     {
576         pushtok(tok = newtok(), &st);
577         tok->type = TOK_STR;
578         tok->d.str = swcsdup(argv[i]);
579         std++;
580         do
581         {
582             done = 1;
583             if((st->type == TOK_STR) && !wcscmp(st->d.str, L"("))
584             {
585                 freetok(poptok(&st));
586                 pushtok(tok = newtok(), &st);
587                 tok->type = TOK_OP;
588                 done = 0;
589             } else if((st->type == TOK_STR) && !wcscmp(st->d.str, L")")) {
590                 freetok(poptok(&st));
591                 pushtok(tok = newtok(), &st);
592                 tok->type = TOK_CP;
593                 done = 0;
594             } else if((st->type == TOK_STR) && (!wcsncmp(st->d.str, L"N~", 2) || !wcsncmp(st->d.str, L"L~", 2))) {
595                 tok2 = poptok(&st);
596                 pushtok(tok = newtok(), &st);
597                 tok->type = TOK_SE;
598                 sexpr = newsexpr();
599                 if((wbuf = regexunquotesimple(tok2->d.str + 2)) != NULL)
600                 {
601                     if(tok2->d.str[0] == L'N')
602                         sexpr->op = SOP_NAMESS;
603                     else
604                         sexpr->op = SOP_LINKSS;
605                     sexpr->d.s = wbuf;
606                     sexpr->cost = 5;
607                 } else {
608                     if(tok2->d.str[0] == L'N')
609                         sexpr->op = SOP_NAMERE;
610                     else
611                         sexpr->op = SOP_LINKRE;
612                     sexpr->cost = 20;
613                     if((buf = icwcstombs(tok2->d.str + 2, "UTF-8")) == NULL)
614                     {
615                         freetok(tok2);
616                         putsexpr(sexpr);
617                         goto out_err;
618                     }
619                     if(regcomp(&sexpr->d.re.cre, buf, REG_EXTENDED | REG_ICASE | REG_NOSUB))
620                     {
621                         freetok(tok2);
622                         free(buf);
623                         putsexpr(sexpr);
624                         goto out_err;
625                     }
626                     free(buf);
627                     sexpr->d.re.inited = 1;
628                     sexpr->d.re.sre = swcsdup(tok2->d.str + 2);
629                 }
630                 getsexpr(tok->d.se = sexpr);
631                 freetok(tok2);
632                 putsexpr(sexpr);
633                 done = 0;
634             } else if((st->type == TOK_STR) && (!wcsncmp(st->d.str, L"S<", 2) || !wcsncmp(st->d.str, L"S=", 2) || !wcsncmp(st->d.str, L"S>", 2))) {
635                 tok2 = poptok(&st);
636                 pushtok(tok = newtok(), &st);
637                 tok->type = TOK_SE;
638                 sexpr = newsexpr();
639                 if(tok2->d.str[1] == L'<')
640                     sexpr->op = SOP_SIZELT;
641                 else if(tok2->d.str[1] == L'=')
642                     sexpr->op = SOP_SIZEEQ;
643                 else
644                     sexpr->op = SOP_SIZEGT;
645                 sexpr->d.n = wcstol(tok2->d.str + 2, NULL, 0);
646                 sexpr->cost = 0;
647                 getsexpr(tok->d.se = sexpr);
648                 freetok(tok2);
649                 putsexpr(sexpr);
650                 done = 0;
651             } else if((std >= 3) && (st->type == TOK_CP) && (st->next->type == TOK_SE) && (st->next->next->type == TOK_OP)) {
652                 freetok(poptok(&st));
653                 tok = poptok(&st);
654                 freetok(poptok(&st));
655                 pushtok(tok, &st);
656                 std -= 2;
657                 done = 0;
658             } else if((std >= 2) && (st->type == TOK_SE) && (st->next->type == TOK_STR) && !wcscmp(st->next->d.str, L"!")) {
659                 sexpr = newsexpr();
660                 sexpr->op = SOP_NOT;
661                 sexpr->cost = 0;
662                 getsexpr(sexpr->l = st->d.se);
663                 freetok(poptok(&st));
664                 freetok(poptok(&st));
665                 pushtok(tok = newtok(), &st);
666                 tok->type = TOK_SE;
667                 getsexpr(tok->d.se = sexpr);
668                 putsexpr(sexpr);
669                 std -= 1;
670                 done = 0;
671             } else if((std >= 3) && (st->type == TOK_SE) && (st->next->type == TOK_STR) && (!wcscmp(st->next->d.str, L"&") || !wcscmp(st->next->d.str, L"|")) && (st->next->next->type == TOK_SE)) {
672                 sexpr = newsexpr();
673                 if(!wcscmp(st->next->d.str, L"&"))
674                     sexpr->op = SOP_AND;
675                 else
676                     sexpr->op = SOP_OR;
677                 sexpr->cost = 0;
678                 getsexpr(sexpr->l = st->next->next->d.se);
679                 getsexpr(sexpr->r = st->d.se);
680                 freetok(poptok(&st));
681                 freetok(poptok(&st));
682                 freetok(poptok(&st));
683                 pushtok(tok = newtok(), &st);
684                 tok->type = TOK_SE;
685                 getsexpr(tok->d.se = sexpr);
686                 putsexpr(sexpr);
687                 std -= 2;
688                 done = 0;
689             }
690         } while(!done);
691     }
692     if((st == NULL) || (st->next != NULL) || (st->type != TOK_SE))
693         goto out_err;
694     getsexpr(sexpr = st->d.se);
695     freetok(st);
696     calccost(sexpr);
697     return(sexpr);
698
699  out_err:
700     while(st != NULL)
701         freetok(poptok(&st));
702     return(NULL);
703 }
704
705 void optsexpr(struct sexpr *sexpr)
706 {
707     struct sexpr *buf;
708     
709     if((sexpr->l != NULL) && (sexpr->r != NULL))
710     {
711         if(sexpr->l->tcost > sexpr->r->tcost)
712         {
713             buf = sexpr->r;
714             sexpr->r = sexpr->l;
715             sexpr->l = buf;
716         }
717     }
718     if(sexpr->l != NULL)
719         optsexpr(sexpr->l);
720     if(sexpr->r != NULL)
721         optsexpr(sexpr->r);
722 }
723
724 struct wcslist *findsexprstrs(struct sexpr *sexpr)
725 {
726     struct wcslist *list, *l1, *l2;
727     
728     list = NULL;
729     switch(sexpr->op)
730     {
731     case SOP_AND:
732         list = findsexprstrs(sexpr->l);
733         l1 = findsexprstrs(sexpr->r);
734         slmergemax(&list, l1);
735         freesl(&l1);
736         break;
737     case SOP_OR:
738         l1 = findsexprstrs(sexpr->l);
739         l2 = findsexprstrs(sexpr->r);
740         list = slmergemin(l1, l2);
741         freesl(&l1);
742         freesl(&l2);
743         break;
744     case SOP_NOT:
745         break;
746     case SOP_NAMERE:
747     case SOP_LINKRE:
748         list = regexfindstrings(sexpr->d.re.sre);
749         break;
750     case SOP_NAMESS:
751     case SOP_LINKSS:
752         slmerge1(&list, sexpr->d.s);
753         break;
754     default:
755         break;
756     }
757     return(list);
758 }
759
760 static void unlinksqueue(struct srchlist *ln)
761 {
762     if(ln->prev != NULL)
763         ln->prev->next = ln->next;
764     if(ln->next != NULL)
765         ln->next->prev = ln->prev;
766     if(ln == searchqueue)
767         searchqueue = ln->next;
768     free(ln);
769 }
770
771 static void ctexpire(int cancelled, void *data)
772 {
773     committimer = NULL;
774     if(!cancelled)
775         trycommit();
776 }
777
778 static void estimatequeue(void)
779 {
780     struct srchlist *cur;
781     struct srchfnnlist *ln;
782     time_t now, start;
783     
784     if(searchqueue == NULL)
785         return;
786     start = now = time(NULL);
787     for(ln = searchqueue->srch->fnl; ln != NULL; ln = ln->next)
788     {
789         if((ln->fn->lastsrch != 0) && (ln->fn->lastsrch + ln->fn->srchwait > start))
790             start = ln->fn->lastsrch + ln->fn->srchwait;
791     }
792     if(start != searchqueue->srch->eta)
793     {
794         searchqueue->srch->eta = start;
795         CBCHAINDOCB(searchqueue->srch, search_eta, searchqueue->srch);
796     }
797     for(cur = searchqueue->next; cur != NULL; cur = cur->next)
798     {
799         now = start;
800         for(ln = cur->srch->fnl; ln != NULL; ln = ln->next)
801         {
802             if(now + ln->fn->srchwait > start)
803                 start = now + ln->fn->srchwait;
804         }
805         if(start != cur->srch->eta)
806         {
807             cur->srch->eta = start;
808             CBCHAINDOCB(cur->srch, search_eta, cur->srch);
809         }
810     }
811     if((committimer == NULL) || ((time_t)committimer->at != searchqueue->srch->eta))
812     {
813         if(committimer != NULL)
814             canceltimer(committimer);
815         committimer = timercallback(searchqueue->srch->eta, ctexpire, NULL);
816     }
817 }
818
819 struct search *findsearch(int id)
820 {
821     struct search *srch;
822     
823     for(srch = searches; srch != NULL; srch = srch->next)
824     {
825         if(srch->id == id)
826             break;
827     }
828     return(srch);
829 }
830
831 struct search *newsearch(wchar_t *owner, struct sexpr *sexpr)
832 {
833     struct search *srch;
834     static int id = 0;
835     
836     srch = smalloc(sizeof(*srch));
837     memset(srch, 0, sizeof(*srch));
838     srch->id = id++;
839     srch->owner = swcsdup(owner);
840     if((srch->sexpr = sexpr) != NULL)
841         getsexpr(srch->sexpr);
842     CBCHAININIT(srch, search_eta);
843     CBCHAININIT(srch, search_commit);
844     CBCHAININIT(srch, search_result);
845     CBCHAININIT(srch, search_destroy);
846     srch->next = searches;
847     srch->prev = NULL;
848     if(searches != NULL)
849         searches->prev = srch;
850     searches = srch;
851     return(srch);
852 }
853
854 static void srchexpire(int cancelled, struct search *srch)
855 {
856     srch->freetimer = NULL;
857     if(!cancelled)
858         freesearch(srch);
859 }
860
861 static void trycommit(void)
862 {
863     struct srchfnnlist *ln;
864     struct search *srch;
865     time_t now;
866     
867     if(searchqueue == NULL)
868         return;
869     srch = searchqueue->srch;
870     now = time(NULL);
871     for(ln = srch->fnl; ln != NULL; ln = ln->next)
872     {
873         if(now < ln->fn->lastsrch + ln->fn->srchwait)
874             break;
875     }
876     if(ln != NULL)
877         return;
878     unlinksqueue(searchqueue);
879     srch->state = SRCH_RUN;
880     srch->eta = time(NULL);
881     srch->committime = ntime();
882     srch->freetimer = timercallback(ntime() + 300, (void (*)(int, void *))srchexpire, srch);
883     CBCHAINDOCB(srch, search_commit, srch);
884     for(ln = srch->fnl; ln != NULL; ln = ln->next)
885         fnetsearch(ln->fn, srch, ln);
886     estimatequeue();
887 }
888
889 void freesearch(struct search *srch)
890 {
891     struct srchfnnlist *ln;
892     struct srchlist *sln;
893     
894     if(srch->prev != NULL)
895         srch->prev->next = srch->next;
896     if(srch->next != NULL)
897         srch->next->prev = srch->prev;
898     if(srch == searches)
899         searches = srch->next;
900     estimatequeue();
901     if(srch->freetimer != NULL)
902         canceltimer(srch->freetimer);
903     CBCHAINDOCB(srch, search_destroy, srch);
904     CBCHAINFREE(srch, search_eta);
905     CBCHAINFREE(srch, search_commit);
906     CBCHAINFREE(srch, search_result);
907     CBCHAINFREE(srch, search_destroy);
908     while(srch->results != NULL)
909         freesrchres(srch->results);
910     for(sln = searchqueue; sln != NULL; sln = sln->next)
911     {
912         if(sln->srch == srch)
913         {
914             unlinksqueue(sln);
915             break;
916         }
917     }
918     while(srch->fnl != NULL)
919     {
920         ln = srch->fnl;
921         srch->fnl = ln->next;
922         CBCHAINDOCB(ln, searchfnl_destroy, ln);
923         CBCHAINFREE(ln, searchfnl_destroy);
924         putfnetnode(ln->fn);
925         free(ln);
926     }
927     if(srch->sexpr != NULL)
928         putsexpr(srch->sexpr);
929     if(srch->owner != NULL)
930         free(srch->owner);
931     free(srch);
932 }
933
934 void searchaddfn(struct search *srch, struct fnetnode *fn)
935 {
936     struct srchfnnlist *ln;
937     
938     for(ln = srch->fnl; ln != NULL; ln = ln->next)
939     {
940         if(ln->fn == fn)
941             return;
942     }
943     ln = smalloc(sizeof(*ln));
944     memset(ln, 0, sizeof(*ln));
945     getfnetnode(ln->fn = fn);
946     CBCHAININIT(ln, searchfnl_destroy);
947     ln->next = srch->fnl;
948     srch->fnl = ln;
949 }
950
951 static void linksearch(struct search *srch, struct srchlist *prev)
952 {
953     struct srchlist *new;
954     
955     new = smalloc(sizeof(*new));
956     new->srch = srch;
957     if(prev == NULL)
958     {
959         new->prev = NULL;
960         new->next = searchqueue;
961         if(searchqueue != NULL)
962             searchqueue->prev = new;
963         searchqueue = new;
964     } else {
965         new->prev = prev;
966         if((new->next = prev->next) != NULL)
967             new->next->prev = new;
968         prev->next = new;
969     }
970     GCBCHAINDOCB(newsrchcb, srch);
971     estimatequeue();
972 }
973
974 /* 
975  * queuesearch is also the "scheduler" function - it finds a suitable
976  * place in the queue for the new search. I'll make a weak attempt at
977  * describing the algorithm:
978  * First, we find the first search that doesn't have a lower priority
979  * than this one. If there is no such, we just link this one onto the
980  * end of the queue.
981  * Then, if we have a search of this priority in the queue with the
982  * same owner as the new search, we set lastmine to the search after
983  * that one, otherwise, lastmine is the first search of this
984  * priority. If lastmine is discovered either to not exist (that is,
985  * our last search is at the end of the queue), or to be of lower
986  * priority (higher number), we link it in at the appropriate end.
987  * Then, we find the next search of the same priority and owner as
988  * lastmine, and link this search in before it. That should yield a
989  * 'round-robin-like' scheduling within priority boundaries. I think.
990  */
991 void queuesearch(struct search *srch)
992 {
993     struct srchlist *cur, *lastmine, *prev;
994     wchar_t *nexto;
995     
996     for(prev = NULL, cur = searchqueue; cur != NULL; prev = cur, cur = cur->next)
997     {
998         if(cur->srch->prio >= srch->prio)
999             break;
1000     }
1001     if(cur == NULL)
1002     {
1003         linksearch(srch, prev);
1004         return;
1005     }
1006     lastmine = cur;
1007     for(; cur != NULL; prev = cur, cur = cur->next)
1008     {
1009         if(!wcscmp(cur->srch->owner, srch->owner))
1010             lastmine = cur->next;
1011         if(cur->srch->prio > srch->prio)
1012             break;
1013     }
1014     if((lastmine == NULL) || (lastmine->srch->prio > srch->prio))
1015     {
1016         linksearch(srch, prev);
1017         return;
1018     }
1019     nexto = lastmine->srch->owner;
1020     for(cur = lastmine->next; cur != NULL; prev = cur, cur = cur->next)
1021     {
1022         if(!wcscmp(cur->srch->owner, nexto))
1023             break;
1024         if(cur->srch->prio > srch->prio)
1025             break;
1026     }
1027     if(cur == NULL)
1028     {
1029         linksearch(srch, prev);
1030         return;
1031     }
1032     linksearch(srch, prev);
1033 }
1034
1035 static int srisvalid(struct srchres *sr, struct sexpr *sexpr)
1036 {
1037     int ret;
1038     char *buf;
1039     wchar_t *p;
1040     
1041     switch(sexpr->op)
1042     {
1043     case SOP_FALSE:
1044         return(0);
1045     case SOP_TRUE:
1046         return(1);
1047     case SOP_AND:
1048         if(!srisvalid(sr, sexpr->l))
1049             return(0);
1050         return(srisvalid(sr, sexpr->r));
1051     case SOP_OR:
1052         if(srisvalid(sr, sexpr->l))
1053             return(1);
1054         return(srisvalid(sr, sexpr->r));
1055     case SOP_NOT:
1056         return(!srisvalid(sr, sexpr->l));
1057     case SOP_NAMERE:
1058         if((buf = icwcstombs(sr->filename, "UTF-8")) == NULL)
1059             return(0);
1060         ret = regexec(&sexpr->d.re.cre, buf, 0, NULL, 0);
1061         free(buf);
1062         return(!ret);
1063     case SOP_LINKRE:
1064         p = sr->filename;
1065         if(sr->fnet->filebasename != NULL)
1066             p = sr->fnet->filebasename(p);
1067         if((buf = icwcstombs(p, "UTF-8")) == NULL)
1068             return(0);
1069         ret = regexec(&sexpr->d.re.cre, buf, 0, NULL, 0);
1070         free(buf);
1071         return(!ret);
1072     case SOP_NAMESS:
1073         return(wcsexists(sr->filename, sexpr->d.s));
1074     case SOP_LINKSS:
1075         p = sr->filename;
1076         if(sr->fnet->filebasename != NULL)
1077             p = sr->fnet->filebasename(p);
1078         return(wcsexists(p, sexpr->d.s));
1079     case SOP_SIZELT:
1080         return(sr->size < sexpr->d.n);
1081     case SOP_SIZEEQ:
1082         return(sr->size == sexpr->d.n);
1083     case SOP_SIZEGT:
1084         return(sr->size > sexpr->d.n);
1085     }
1086     return(0);
1087 }
1088
1089 struct srchres *newsrchres(struct fnet *fnet, wchar_t *filename, wchar_t *peerid)
1090 {
1091     struct srchres *sr;
1092     
1093     sr = smalloc(sizeof(*sr));
1094     memset(sr, 0, sizeof(*sr));
1095     sr->size = -1;
1096     sr->slots = -1;
1097     sr->fnet = fnet;
1098     sr->filename = swcsdup(filename);
1099     sr->peerid = swcsdup(peerid);
1100     return(sr);
1101 }
1102
1103 void freesrchres(struct srchres *sr)
1104 {
1105     if(sr->next != NULL)
1106         sr->next->prev = sr->prev;
1107     if(sr->prev != NULL)
1108         sr->prev->next = sr->next;
1109     if(sr->srch != NULL)
1110     {
1111         if(sr->srch->results == sr)
1112             sr->srch->results = sr->next;
1113         sr->srch->numres--;
1114     }
1115     if(sr->filename != NULL)
1116         free(sr->filename);
1117     if(sr->peerid != NULL)
1118         free(sr->peerid);
1119     if(sr->peernick != NULL)
1120         free(sr->peernick);
1121     if(sr->fn != NULL)
1122         putfnetnode(sr->fn);
1123     free(sr);
1124 }
1125
1126 struct srchres *dupsrchres(struct srchres *sr)
1127 {
1128     struct srchres *new;
1129     
1130     new = smalloc(sizeof(*new));
1131     memset(new, 0, sizeof(*new));
1132     new->size = sr->size;
1133     new->slots = sr->slots;
1134     new->fnet = sr->fnet;
1135     if(sr->peerid != NULL)
1136         new->peerid = swcsdup(sr->peerid);
1137     if(sr->peernick != NULL)
1138         new->peernick = swcsdup(sr->peernick);
1139     if(sr->filename != NULL)
1140         new->filename = swcsdup(sr->filename);
1141     if(sr->fn != NULL)
1142         getfnetnode(new->fn = sr->fn);
1143     return(new);
1144 }
1145
1146 static void linksr(struct search *srch, struct srchres *sr)
1147 {
1148     sr->prev = NULL;
1149     sr->next = srch->results;
1150     if(srch->results != NULL)
1151         srch->results->prev = sr;
1152     srch->results = sr;
1153     sr->srch = srch;
1154     sr->time = ntime() - srch->committime;
1155     srch->numres++;
1156 }
1157
1158 void submitsrchres(struct srchres *sr)
1159 {
1160     struct search *srch;
1161     struct srchfnnlist *ln;
1162     struct srchres *dsr;
1163     
1164     for(srch = searches; srch != NULL; srch = srch->next)
1165     {
1166         if(srch->state == SRCH_RUN)
1167         {
1168             if(!srisvalid(sr, srch->sexpr))
1169                 continue;
1170             for(ln = srch->fnl; ln != NULL; ln = ln->next)
1171             {
1172                 if(((sr->fn != NULL) && (ln->fn == sr->fn)) || ((sr->fn == NULL) && (sr->fnet == ln->fn->fnet)))
1173                     break;
1174             }
1175             if(ln != NULL)
1176             {
1177                 dsr = dupsrchres(sr);
1178                 linksr(srch, dsr);
1179                 CBCHAINDOCB(srch, search_result, srch, dsr);
1180             }
1181         }
1182     }
1183 }