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