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