A couple of bugs fix in dolcon.
[doldaconnect.git] / daemon / search.c
CommitLineData
d3372da9 1/*
2 * Dolda Connect - Modular multiuser Direct Connect-style client
302a2600 3 * Copyright (C) 2004 Fredrik Tolf <fredrik@dolda2000.com>
d3372da9 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>
d3372da9 20#include <wchar.h>
21#include <wctype.h>
22#include <errno.h>
23#include <regex.h>
24#include <string.h>
25#include <time.h>
26
27#ifdef HAVE_CONFIG_H
28#include <config.h>
29#endif
30#include "utils.h"
31#include "log.h"
32#include "sysevents.h"
33#include "filenet.h"
7dd2a79b 34#include "client.h"
d3372da9 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
42struct srchlist
43{
44 struct srchlist *next, *prev;
45 struct search *srch;
46};
47
48struct tok
49{
50 struct tok *next;
51 int type;
52 union
53 {
54 wchar_t *str;
55 struct sexpr *se;
56 } d;
57};
58
59struct reinfo
60{
61 wchar_t *begstr, *endstr, *onestr;
62 struct wcslist *strs;
63};
64
65struct bound
66{
67 int min, max;
68};
69
70static void trycommit(void);
71
72struct search *searches = NULL;
73static struct srchlist *searchqueue = NULL;
74static struct timer *committimer = NULL;
75GCBCHAIN(newsrchcb, struct search *);
76
77wchar_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
108static 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
120void freesl(struct wcslist **list)
121{
122 while(*list != NULL)
123 freesln(*list, list);
124}
125
126static 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
142static 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
163void slmergemax(struct wcslist **dest, struct wcslist *src)
164{
165 for(; src != NULL; src = src->next)
166 slmerge1(dest, src->str);
167}
168
169static 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
193struct 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
210static 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
264static 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++);
c74516fb 398 if(i == 0) {
d3372da9 399 free(ret.begstr);
c74516fb 400 ret.begstr = NULL;
401 } else {
d3372da9 402 ret.begstr[i] = L'\0';
c74516fb 403 }
d3372da9 404 }
405 free(sinf.begstr);
406 } else {
407 if(ret.begstr != NULL)
408 {
409 free(ret.begstr);
410 ret.begstr = NULL;
411 }
412 }
413 if(sinf.endstr != NULL)
414 {
415 if(ret.endstr != NULL)
416 {
417 len1 = wcslen(ret.endstr);
418 len2 = wcslen(sinf.endstr);
419 if(len1 < len2)
420 {
421 minlen = len1;
422 maxlen = len2;
423 } else {
424 minlen = len2;
425 maxlen = len1;
426 }
427 for(i = 1; (i <= minlen) && (ret.endstr[len1 - i] == sinf.endstr[len2 - i]); i++);
c74516fb 428 if(i == 1) {
d3372da9 429 free(ret.endstr);
c74516fb 430 ret.endstr = NULL;
431 } else if(i <= maxlen) {
d3372da9 432 wmemmove(ret.endstr, ret.endstr + (len1 - i) + 1, i);
c74516fb 433 }
d3372da9 434 }
435 free(sinf.endstr);
436 } else {
437 if(ret.endstr != NULL)
438 {
439 free(ret.endstr);
440 ret.endstr = NULL;
441 }
442 }
443 if(sinf.onestr != NULL)
444 {
445 if(ret.onestr != NULL)
446 {
447 /* XXX: Comparing beginning and end of the onestrs and
448 * create begstr and endstr if there isn't an exact
449 * match.*/
450 if(wcscmp(ret.onestr, sinf.onestr))
451 {
452 free(ret.onestr);
453 ret.onestr = NULL;
454 }
455 }
456 free(sinf.onestr);
457 } else {
458 if(ret.onestr != NULL)
459 {
460 free(ret.onestr);
461 ret.onestr = NULL;
462 }
463 }
464 }
465 if(endret != NULL)
466 *endret = re;
467 return(ret);
468}
469
470#undef fnc
471
472struct wcslist *regexfindstrings(wchar_t *re)
473{
474 struct reinfo i;
475
476 i = analyzere(re, NULL, L'\0');
477 if(i.begstr != NULL)
478 free(i.begstr);
479 if(i.endstr != NULL)
480 free(i.endstr);
481 if(i.onestr != NULL)
482 free(i.onestr);
483 return(i.strs);
484}
485
486static struct sexpr *newsexpr(void)
487{
488 struct sexpr *sexpr;
489
490 sexpr = smalloc(sizeof(*sexpr));
491 memset(sexpr, 0, sizeof(*sexpr));
492 sexpr->refcount = 1;
493 return(sexpr);
494}
495
496void getsexpr(struct sexpr *sexpr)
497{
498 sexpr->refcount++;
499}
500
501void putsexpr(struct sexpr *sexpr)
502{
503 if(--sexpr->refcount != 0)
504 return;
505 if(sexpr->l != NULL)
506 putsexpr(sexpr->l);
507 if(sexpr->r != NULL)
508 putsexpr(sexpr->r);
509 if((sexpr->op == SOP_NAMERE) || (sexpr->op == SOP_LINKRE))
510 {
511 if(sexpr->d.re.sre != NULL)
512 free(sexpr->d.re.sre);
513 if(sexpr->d.re.inited)
514 regfree(&sexpr->d.re.cre);
515 }
516 if((sexpr->op == SOP_NAMESS) || (sexpr->op == SOP_LINKSS))
517 {
518 if(sexpr->d.s != NULL)
519 free(sexpr->d.s);
520 }
9d8cf743 521 if(sexpr->op == SOP_HASHIS)
522 {
523 if(sexpr->d.hash != NULL)
524 freehash(sexpr->d.hash);
525 }
d3372da9 526 free(sexpr);
527}
528
529static struct tok *newtok(void)
530{
531 struct tok *tok;
532
533 tok = smalloc(sizeof(*tok));
534 memset(tok, 0, sizeof(*tok));
535 tok->next = NULL;
536 return(tok);
537}
538
539static void freetok(struct tok *tok)
540{
541 if((tok->type == TOK_STR) && (tok->d.str != NULL))
542 free(tok->d.str);
543 if((tok->type == TOK_SE) && (tok->d.se != NULL))
544 putsexpr(tok->d.se);
545 free(tok);
546}
547
548static void pushtok(struct tok *tok, struct tok **st)
549{
550 tok->next = *st;
551 *st = tok;
552}
553
554static struct tok *poptok(struct tok **st)
555{
556 struct tok *tok;
557
558 tok = *st;
559 *st = (*st)->next;
560 return(tok);
561}
562
563int calccost(struct sexpr *sexpr)
564{
565 sexpr->tcost = sexpr->cost;
566 if(sexpr->l != NULL)
567 sexpr->tcost += calccost(sexpr->l);
568 if(sexpr->r != NULL)
569 sexpr->tcost += calccost(sexpr->r);
570 return(sexpr->tcost);
571}
572
573struct sexpr *parsesexpr(int argc, wchar_t **argv)
574{
575 int i, done, std;
576 struct tok *st, *tok, *tok2;
577 struct sexpr *sexpr;
578 char *buf;
579 wchar_t *wbuf;
580
581 std = 0;
582 st = NULL;
583 for(i = 0; i < argc; i++)
584 {
585 pushtok(tok = newtok(), &st);
586 tok->type = TOK_STR;
587 tok->d.str = swcsdup(argv[i]);
588 std++;
589 do
590 {
591 done = 1;
592 if((st->type == TOK_STR) && !wcscmp(st->d.str, L"("))
593 {
594 freetok(poptok(&st));
595 pushtok(tok = newtok(), &st);
596 tok->type = TOK_OP;
597 done = 0;
598 } else if((st->type == TOK_STR) && !wcscmp(st->d.str, L")")) {
599 freetok(poptok(&st));
600 pushtok(tok = newtok(), &st);
601 tok->type = TOK_CP;
602 done = 0;
603 } else if((st->type == TOK_STR) && (!wcsncmp(st->d.str, L"N~", 2) || !wcsncmp(st->d.str, L"L~", 2))) {
604 tok2 = poptok(&st);
605 pushtok(tok = newtok(), &st);
606 tok->type = TOK_SE;
607 sexpr = newsexpr();
608 if((wbuf = regexunquotesimple(tok2->d.str + 2)) != NULL)
609 {
610 if(tok2->d.str[0] == L'N')
611 sexpr->op = SOP_NAMESS;
612 else
613 sexpr->op = SOP_LINKSS;
614 sexpr->d.s = wbuf;
615 sexpr->cost = 5;
616 } else {
617 if(tok2->d.str[0] == L'N')
618 sexpr->op = SOP_NAMERE;
619 else
620 sexpr->op = SOP_LINKRE;
621 sexpr->cost = 20;
622 if((buf = icwcstombs(tok2->d.str + 2, "UTF-8")) == NULL)
623 {
624 freetok(tok2);
625 putsexpr(sexpr);
626 goto out_err;
627 }
628 if(regcomp(&sexpr->d.re.cre, buf, REG_EXTENDED | REG_ICASE | REG_NOSUB))
629 {
630 freetok(tok2);
631 free(buf);
632 putsexpr(sexpr);
633 goto out_err;
634 }
635 free(buf);
636 sexpr->d.re.inited = 1;
637 sexpr->d.re.sre = swcsdup(tok2->d.str + 2);
638 }
639 getsexpr(tok->d.se = sexpr);
640 freetok(tok2);
641 putsexpr(sexpr);
642 done = 0;
643 } 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))) {
644 tok2 = poptok(&st);
645 pushtok(tok = newtok(), &st);
646 tok->type = TOK_SE;
647 sexpr = newsexpr();
648 if(tok2->d.str[1] == L'<')
649 sexpr->op = SOP_SIZELT;
650 else if(tok2->d.str[1] == L'=')
651 sexpr->op = SOP_SIZEEQ;
652 else
653 sexpr->op = SOP_SIZEGT;
654 sexpr->d.n = wcstol(tok2->d.str + 2, NULL, 0);
655 sexpr->cost = 0;
656 getsexpr(tok->d.se = sexpr);
657 freetok(tok2);
658 putsexpr(sexpr);
659 done = 0;
9d8cf743 660 } else if((st->type == TOK_STR) && !wcsncmp(st->d.str, L"H=", 2)) {
661 tok2 = poptok(&st);
662 pushtok(tok = newtok(), &st);
663 tok->type = TOK_SE;
664 sexpr = newsexpr();
665 sexpr->op = SOP_HASHIS;
666 if((sexpr->d.hash = parsehash(tok2->d.str + 2)) == NULL)
667 {
668 freetok(tok2);
669 putsexpr(sexpr);
670 goto out_err;
671 }
672 sexpr->cost = 2;
673 getsexpr(tok->d.se = sexpr);
674 freetok(tok2);
675 putsexpr(sexpr);
676 done = 0;
d3372da9 677 } else if((std >= 3) && (st->type == TOK_CP) && (st->next->type == TOK_SE) && (st->next->next->type == TOK_OP)) {
678 freetok(poptok(&st));
679 tok = poptok(&st);
680 freetok(poptok(&st));
681 pushtok(tok, &st);
682 std -= 2;
683 done = 0;
684 } else if((std >= 2) && (st->type == TOK_SE) && (st->next->type == TOK_STR) && !wcscmp(st->next->d.str, L"!")) {
685 sexpr = newsexpr();
686 sexpr->op = SOP_NOT;
687 sexpr->cost = 0;
688 getsexpr(sexpr->l = st->d.se);
689 freetok(poptok(&st));
690 freetok(poptok(&st));
691 pushtok(tok = newtok(), &st);
692 tok->type = TOK_SE;
693 getsexpr(tok->d.se = sexpr);
694 putsexpr(sexpr);
695 std -= 1;
696 done = 0;
697 } 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)) {
698 sexpr = newsexpr();
699 if(!wcscmp(st->next->d.str, L"&"))
700 sexpr->op = SOP_AND;
701 else
702 sexpr->op = SOP_OR;
703 sexpr->cost = 0;
704 getsexpr(sexpr->l = st->next->next->d.se);
705 getsexpr(sexpr->r = st->d.se);
706 freetok(poptok(&st));
707 freetok(poptok(&st));
708 freetok(poptok(&st));
709 pushtok(tok = newtok(), &st);
710 tok->type = TOK_SE;
711 getsexpr(tok->d.se = sexpr);
712 putsexpr(sexpr);
713 std -= 2;
714 done = 0;
715 }
716 } while(!done);
717 }
718 if((st == NULL) || (st->next != NULL) || (st->type != TOK_SE))
719 goto out_err;
720 getsexpr(sexpr = st->d.se);
721 freetok(st);
722 calccost(sexpr);
723 return(sexpr);
724
725 out_err:
726 while(st != NULL)
727 freetok(poptok(&st));
728 return(NULL);
729}
730
731void optsexpr(struct sexpr *sexpr)
732{
733 struct sexpr *buf;
734
735 if((sexpr->l != NULL) && (sexpr->r != NULL))
736 {
737 if(sexpr->l->tcost > sexpr->r->tcost)
738 {
739 buf = sexpr->r;
740 sexpr->r = sexpr->l;
741 sexpr->l = buf;
742 }
743 }
744 if(sexpr->l != NULL)
745 optsexpr(sexpr->l);
746 if(sexpr->r != NULL)
747 optsexpr(sexpr->r);
748}
749
750struct wcslist *findsexprstrs(struct sexpr *sexpr)
751{
752 struct wcslist *list, *l1, *l2;
753
754 list = NULL;
755 switch(sexpr->op)
756 {
757 case SOP_AND:
758 list = findsexprstrs(sexpr->l);
759 l1 = findsexprstrs(sexpr->r);
760 slmergemax(&list, l1);
761 freesl(&l1);
762 break;
763 case SOP_OR:
764 l1 = findsexprstrs(sexpr->l);
765 l2 = findsexprstrs(sexpr->r);
766 list = slmergemin(l1, l2);
767 freesl(&l1);
768 freesl(&l2);
769 break;
d3372da9 770 case SOP_NAMERE:
771 case SOP_LINKRE:
772 list = regexfindstrings(sexpr->d.re.sre);
773 break;
774 case SOP_NAMESS:
775 case SOP_LINKSS:
776 slmerge1(&list, sexpr->d.s);
777 break;
778 default:
779 break;
780 }
781 return(list);
782}
783
784static void unlinksqueue(struct srchlist *ln)
785{
786 if(ln->prev != NULL)
787 ln->prev->next = ln->next;
788 if(ln->next != NULL)
789 ln->next->prev = ln->prev;
790 if(ln == searchqueue)
791 searchqueue = ln->next;
792 free(ln);
793}
794
795static void ctexpire(int cancelled, void *data)
796{
797 committimer = NULL;
798 if(!cancelled)
799 trycommit();
800}
801
802static void estimatequeue(void)
803{
804 struct srchlist *cur;
805 struct srchfnnlist *ln;
806 time_t now, start;
807
808 if(searchqueue == NULL)
809 return;
810 start = now = time(NULL);
811 for(ln = searchqueue->srch->fnl; ln != NULL; ln = ln->next)
812 {
813 if((ln->fn->lastsrch != 0) && (ln->fn->lastsrch + ln->fn->srchwait > start))
814 start = ln->fn->lastsrch + ln->fn->srchwait;
815 }
816 if(start != searchqueue->srch->eta)
817 {
818 searchqueue->srch->eta = start;
819 CBCHAINDOCB(searchqueue->srch, search_eta, searchqueue->srch);
820 }
821 for(cur = searchqueue->next; cur != NULL; cur = cur->next)
822 {
823 now = start;
824 for(ln = cur->srch->fnl; ln != NULL; ln = ln->next)
825 {
826 if(now + ln->fn->srchwait > start)
827 start = now + ln->fn->srchwait;
828 }
829 if(start != cur->srch->eta)
830 {
831 cur->srch->eta = start;
832 CBCHAINDOCB(cur->srch, search_eta, cur->srch);
833 }
834 }
835 if((committimer == NULL) || ((time_t)committimer->at != searchqueue->srch->eta))
836 {
837 if(committimer != NULL)
838 canceltimer(committimer);
839 committimer = timercallback(searchqueue->srch->eta, ctexpire, NULL);
840 }
841}
842
843struct search *findsearch(int id)
844{
845 struct search *srch;
846
847 for(srch = searches; srch != NULL; srch = srch->next)
848 {
849 if(srch->id == id)
850 break;
851 }
852 return(srch);
853}
854
855struct search *newsearch(wchar_t *owner, struct sexpr *sexpr)
856{
857 struct search *srch;
858 static int id = 0;
859
860 srch = smalloc(sizeof(*srch));
861 memset(srch, 0, sizeof(*srch));
862 srch->id = id++;
863 srch->owner = swcsdup(owner);
864 if((srch->sexpr = sexpr) != NULL)
865 getsexpr(srch->sexpr);
866 CBCHAININIT(srch, search_eta);
867 CBCHAININIT(srch, search_commit);
868 CBCHAININIT(srch, search_result);
869 CBCHAININIT(srch, search_destroy);
870 srch->next = searches;
871 srch->prev = NULL;
872 if(searches != NULL)
873 searches->prev = srch;
874 searches = srch;
875 return(srch);
876}
877
878static void srchexpire(int cancelled, struct search *srch)
879{
880 srch->freetimer = NULL;
881 if(!cancelled)
882 freesearch(srch);
883}
884
885static void trycommit(void)
886{
887 struct srchfnnlist *ln;
888 struct search *srch;
889 time_t now;
890
891 if(searchqueue == NULL)
892 return;
893 srch = searchqueue->srch;
894 now = time(NULL);
895 for(ln = srch->fnl; ln != NULL; ln = ln->next)
896 {
897 if(now < ln->fn->lastsrch + ln->fn->srchwait)
898 break;
899 }
900 if(ln != NULL)
901 return;
902 unlinksqueue(searchqueue);
903 srch->state = SRCH_RUN;
904 srch->eta = time(NULL);
905 srch->committime = ntime();
906 srch->freetimer = timercallback(ntime() + 300, (void (*)(int, void *))srchexpire, srch);
907 CBCHAINDOCB(srch, search_commit, srch);
908 for(ln = srch->fnl; ln != NULL; ln = ln->next)
909 fnetsearch(ln->fn, srch, ln);
910 estimatequeue();
911}
912
913void freesearch(struct search *srch)
914{
915 struct srchfnnlist *ln;
916 struct srchlist *sln;
917
918 if(srch->prev != NULL)
919 srch->prev->next = srch->next;
920 if(srch->next != NULL)
921 srch->next->prev = srch->prev;
922 if(srch == searches)
923 searches = srch->next;
924 estimatequeue();
925 if(srch->freetimer != NULL)
926 canceltimer(srch->freetimer);
927 CBCHAINDOCB(srch, search_destroy, srch);
928 CBCHAINFREE(srch, search_eta);
929 CBCHAINFREE(srch, search_commit);
930 CBCHAINFREE(srch, search_result);
931 CBCHAINFREE(srch, search_destroy);
932 while(srch->results != NULL)
933 freesrchres(srch->results);
934 for(sln = searchqueue; sln != NULL; sln = sln->next)
935 {
936 if(sln->srch == srch)
937 {
938 unlinksqueue(sln);
939 break;
940 }
941 }
942 while(srch->fnl != NULL)
943 {
944 ln = srch->fnl;
945 srch->fnl = ln->next;
946 CBCHAINDOCB(ln, searchfnl_destroy, ln);
947 CBCHAINFREE(ln, searchfnl_destroy);
948 putfnetnode(ln->fn);
949 free(ln);
950 }
951 if(srch->sexpr != NULL)
952 putsexpr(srch->sexpr);
953 if(srch->owner != NULL)
954 free(srch->owner);
955 free(srch);
956}
957
958void searchaddfn(struct search *srch, struct fnetnode *fn)
959{
960 struct srchfnnlist *ln;
961
962 for(ln = srch->fnl; ln != NULL; ln = ln->next)
963 {
964 if(ln->fn == fn)
965 return;
966 }
967 ln = smalloc(sizeof(*ln));
968 memset(ln, 0, sizeof(*ln));
969 getfnetnode(ln->fn = fn);
970 CBCHAININIT(ln, searchfnl_destroy);
971 ln->next = srch->fnl;
972 srch->fnl = ln;
973}
974
975static void linksearch(struct search *srch, struct srchlist *prev)
976{
977 struct srchlist *new;
978
979 new = smalloc(sizeof(*new));
980 new->srch = srch;
981 if(prev == NULL)
982 {
983 new->prev = NULL;
984 new->next = searchqueue;
985 if(searchqueue != NULL)
986 searchqueue->prev = new;
987 searchqueue = new;
988 } else {
989 new->prev = prev;
990 if((new->next = prev->next) != NULL)
991 new->next->prev = new;
992 prev->next = new;
993 }
994 GCBCHAINDOCB(newsrchcb, srch);
995 estimatequeue();
996}
997
998/*
999 * queuesearch is also the "scheduler" function - it finds a suitable
1000 * place in the queue for the new search. I'll make a weak attempt at
1001 * describing the algorithm:
1002 * First, we find the first search that doesn't have a lower priority
1003 * than this one. If there is no such, we just link this one onto the
1004 * end of the queue.
1005 * Then, if we have a search of this priority in the queue with the
1006 * same owner as the new search, we set lastmine to the search after
1007 * that one, otherwise, lastmine is the first search of this
1008 * priority. If lastmine is discovered either to not exist (that is,
1009 * our last search is at the end of the queue), or to be of lower
1010 * priority (higher number), we link it in at the appropriate end.
1011 * Then, we find the next search of the same priority and owner as
1012 * lastmine, and link this search in before it. That should yield a
1013 * 'round-robin-like' scheduling within priority boundaries. I think.
1014 */
1015void queuesearch(struct search *srch)
1016{
1017 struct srchlist *cur, *lastmine, *prev;
1018 wchar_t *nexto;
1019
1020 for(prev = NULL, cur = searchqueue; cur != NULL; prev = cur, cur = cur->next)
1021 {
1022 if(cur->srch->prio >= srch->prio)
1023 break;
1024 }
1025 if(cur == NULL)
1026 {
1027 linksearch(srch, prev);
1028 return;
1029 }
1030 lastmine = cur;
1031 for(; cur != NULL; prev = cur, cur = cur->next)
1032 {
1033 if(!wcscmp(cur->srch->owner, srch->owner))
1034 lastmine = cur->next;
1035 if(cur->srch->prio > srch->prio)
1036 break;
1037 }
1038 if((lastmine == NULL) || (lastmine->srch->prio > srch->prio))
1039 {
1040 linksearch(srch, prev);
1041 return;
1042 }
1043 nexto = lastmine->srch->owner;
1044 for(cur = lastmine->next; cur != NULL; prev = cur, cur = cur->next)
1045 {
1046 if(!wcscmp(cur->srch->owner, nexto))
1047 break;
1048 if(cur->srch->prio > srch->prio)
1049 break;
1050 }
1051 if(cur == NULL)
1052 {
1053 linksearch(srch, prev);
1054 return;
1055 }
1056 linksearch(srch, prev);
1057}
1058
1059static int srisvalid(struct srchres *sr, struct sexpr *sexpr)
1060{
1061 int ret;
1062 char *buf;
1063 wchar_t *p;
1064
1065 switch(sexpr->op)
1066 {
1067 case SOP_FALSE:
1068 return(0);
1069 case SOP_TRUE:
1070 return(1);
1071 case SOP_AND:
1072 if(!srisvalid(sr, sexpr->l))
1073 return(0);
1074 return(srisvalid(sr, sexpr->r));
1075 case SOP_OR:
1076 if(srisvalid(sr, sexpr->l))
1077 return(1);
1078 return(srisvalid(sr, sexpr->r));
1079 case SOP_NOT:
1080 return(!srisvalid(sr, sexpr->l));
1081 case SOP_NAMERE:
1082 if((buf = icwcstombs(sr->filename, "UTF-8")) == NULL)
1083 return(0);
1084 ret = regexec(&sexpr->d.re.cre, buf, 0, NULL, 0);
1085 free(buf);
1086 return(!ret);
1087 case SOP_LINKRE:
1088 p = sr->filename;
1089 if(sr->fnet->filebasename != NULL)
1090 p = sr->fnet->filebasename(p);
1091 if((buf = icwcstombs(p, "UTF-8")) == NULL)
1092 return(0);
1093 ret = regexec(&sexpr->d.re.cre, buf, 0, NULL, 0);
1094 free(buf);
1095 return(!ret);
1096 case SOP_NAMESS:
1097 return(wcsexists(sr->filename, sexpr->d.s));
1098 case SOP_LINKSS:
1099 p = sr->filename;
1100 if(sr->fnet->filebasename != NULL)
1101 p = sr->fnet->filebasename(p);
1102 return(wcsexists(p, sexpr->d.s));
1103 case SOP_SIZELT:
1104 return(sr->size < sexpr->d.n);
1105 case SOP_SIZEEQ:
1106 return(sr->size == sexpr->d.n);
1107 case SOP_SIZEGT:
1108 return(sr->size > sexpr->d.n);
9d8cf743 1109 case SOP_HASHIS:
1110 if(sr->hash == NULL)
1111 return(0);
1112 return(hashcmp(sr->hash, sexpr->d.hash));
d3372da9 1113 }
1114 return(0);
1115}
1116
1117struct srchres *newsrchres(struct fnet *fnet, wchar_t *filename, wchar_t *peerid)
1118{
1119 struct srchres *sr;
1120
1121 sr = smalloc(sizeof(*sr));
1122 memset(sr, 0, sizeof(*sr));
1123 sr->size = -1;
1124 sr->slots = -1;
1125 sr->fnet = fnet;
1126 sr->filename = swcsdup(filename);
1127 sr->peerid = swcsdup(peerid);
1128 return(sr);
1129}
1130
1131void freesrchres(struct srchres *sr)
1132{
1133 if(sr->next != NULL)
1134 sr->next->prev = sr->prev;
1135 if(sr->prev != NULL)
1136 sr->prev->next = sr->next;
1137 if(sr->srch != NULL)
1138 {
1139 if(sr->srch->results == sr)
1140 sr->srch->results = sr->next;
1141 sr->srch->numres--;
1142 }
7dd2a79b 1143 if(sr->hash != NULL)
1144 freehash(sr->hash);
d3372da9 1145 if(sr->filename != NULL)
1146 free(sr->filename);
1147 if(sr->peerid != NULL)
1148 free(sr->peerid);
1149 if(sr->peernick != NULL)
1150 free(sr->peernick);
1151 if(sr->fn != NULL)
1152 putfnetnode(sr->fn);
1153 free(sr);
1154}
1155
1156struct srchres *dupsrchres(struct srchres *sr)
1157{
1158 struct srchres *new;
1159
1160 new = smalloc(sizeof(*new));
1161 memset(new, 0, sizeof(*new));
1162 new->size = sr->size;
1163 new->slots = sr->slots;
1164 new->fnet = sr->fnet;
1165 if(sr->peerid != NULL)
1166 new->peerid = swcsdup(sr->peerid);
1167 if(sr->peernick != NULL)
1168 new->peernick = swcsdup(sr->peernick);
1169 if(sr->filename != NULL)
1170 new->filename = swcsdup(sr->filename);
1171 if(sr->fn != NULL)
1172 getfnetnode(new->fn = sr->fn);
7dd2a79b 1173 if(sr->hash != NULL)
1174 new->hash = duphash(sr->hash);
d3372da9 1175 return(new);
1176}
1177
1178static void linksr(struct search *srch, struct srchres *sr)
1179{
1180 sr->prev = NULL;
1181 sr->next = srch->results;
1182 if(srch->results != NULL)
1183 srch->results->prev = sr;
1184 srch->results = sr;
1185 sr->srch = srch;
1186 sr->time = ntime() - srch->committime;
1187 srch->numres++;
1188}
1189
1190void submitsrchres(struct srchres *sr)
1191{
1192 struct search *srch;
1193 struct srchfnnlist *ln;
1194 struct srchres *dsr;
1195
1196 for(srch = searches; srch != NULL; srch = srch->next)
1197 {
1198 if(srch->state == SRCH_RUN)
1199 {
1200 if(!srisvalid(sr, srch->sexpr))
1201 continue;
1202 for(ln = srch->fnl; ln != NULL; ln = ln->next)
1203 {
1204 if(((sr->fn != NULL) && (ln->fn == sr->fn)) || ((sr->fn == NULL) && (sr->fnet == ln->fn->fnet)))
1205 break;
1206 }
1207 if(ln != NULL)
1208 {
1209 dsr = dupsrchres(sr);
1210 linksr(srch, dsr);
1211 CBCHAINDOCB(srch, search_result, srch, dsr);
1212 }
1213 }
1214 }
1215}