Add hash attribute to SRs.
[doldaconnect.git] / daemon / search.c
... / ...
CommitLineData
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
43struct srchlist
44{
45 struct srchlist *next, *prev;
46 struct search *srch;
47};
48
49struct tok
50{
51 struct tok *next;
52 int type;
53 union
54 {
55 wchar_t *str;
56 struct sexpr *se;
57 } d;
58};
59
60struct reinfo
61{
62 wchar_t *begstr, *endstr, *onestr;
63 struct wcslist *strs;
64};
65
66struct bound
67{
68 int min, max;
69};
70
71static void trycommit(void);
72
73struct search *searches = NULL;
74static struct srchlist *searchqueue = NULL;
75static struct timer *committimer = NULL;
76GCBCHAIN(newsrchcb, struct search *);
77
78wchar_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
109static 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
121void freesl(struct wcslist **list)
122{
123 while(*list != NULL)
124 freesln(*list, list);
125}
126
127static 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
143static 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
164void slmergemax(struct wcslist **dest, struct wcslist *src)
165{
166 for(; src != NULL; src = src->next)
167 slmerge1(dest, src->str);
168}
169
170static 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
194struct 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
211static 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
265static 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
469struct 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
483static 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
493void getsexpr(struct sexpr *sexpr)
494{
495 sexpr->refcount++;
496}
497
498void 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
521static 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
531static 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
540static void pushtok(struct tok *tok, struct tok **st)
541{
542 tok->next = *st;
543 *st = tok;
544}
545
546static struct tok *poptok(struct tok **st)
547{
548 struct tok *tok;
549
550 tok = *st;
551 *st = (*st)->next;
552 return(tok);
553}
554
555int 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
565struct 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
706void 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
725struct 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
761static 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
772static void ctexpire(int cancelled, void *data)
773{
774 committimer = NULL;
775 if(!cancelled)
776 trycommit();
777}
778
779static 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
820struct 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
832struct 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
855static void srchexpire(int cancelled, struct search *srch)
856{
857 srch->freetimer = NULL;
858 if(!cancelled)
859 freesearch(srch);
860}
861
862static 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
890void 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
935void 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
952static 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 */
992void 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
1036static 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
1090struct 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
1104void 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
1129struct 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
1151static 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
1163void 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}