2 * Dolda Connect - Modular multiuser Direct Connect-style client
3 * Copyright (C) 2004 Fredrik Tolf (fredrik@dolda2000.com)
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.
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.
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
32 #include "sysevents.h"
44 struct srchlist *next, *prev;
61 wchar_t *begstr, *endstr, *onestr;
70 static void trycommit(void);
72 struct search *searches = NULL;
73 static struct srchlist *searchqueue = NULL;
74 static struct timer *committimer = NULL;
75 GCBCHAIN(newsrchcb, struct search *);
77 wchar_t *regexunquotesimple(wchar_t *re)
79 wchar_t *specials, *buf, *p;
81 specials = L"\\^$.*+?[{()|";
82 buf = smalloc((wcslen(re) + 1) * sizeof(wchar_t));
84 for(; *re != L'\0'; re++)
96 if(wcschr(specials, *re) != NULL)
108 static void freesln(struct wcslist *ln, struct wcslist **list)
111 ln->prev->next = ln->next;
113 ln->next->prev = ln->prev;
120 void freesl(struct wcslist **list)
123 freesln(*list, list);
126 static struct wcslist *newsl(struct wcslist **list, wchar_t *str)
130 ln = smalloc(sizeof(*ln));
131 memset(ln, 0, sizeof(*ln));
132 ln->str = swcsdup(str);
133 ln->len = wcslen(str);
142 static void slmerge1(struct wcslist **list, wchar_t *str)
145 struct wcslist *cur, *next;
148 for(cur = *list; cur != NULL; cur = next)
153 if(((len < cur->len) && wcsexists(cur->str, str)) || !wcscmp(str, cur->str))
155 } else if(len > cur->len) {
156 if(wcsexists(str, cur->str))
163 void slmergemax(struct wcslist **dest, struct wcslist *src)
165 for(; src != NULL; src = src->next)
166 slmerge1(dest, src->str);
169 static struct wcslist *makeminlist1(wchar_t *s1, wchar_t *s2)
173 struct wcslist *list;
176 for(p1 = s1; *p1 != L'\0'; p1++)
178 for(p2 = s2; *p2 != L'\0'; p2++)
180 for(i = 0; (p1[i] != L'\0') && (p2[i] != L'\0') && (towlower(p1[i]) == towlower(p2[i])); i++);
193 struct wcslist *slmergemin(struct wcslist *l1, struct wcslist *l2)
195 struct wcslist *cur1, *cur2, *list, *rlist;
198 for(cur1 = l1; cur1 != NULL; cur1 = cur1->next)
200 for(cur2 = l2; cur2 != NULL; cur2 = cur2->next)
202 rlist = makeminlist1(cur1->str, cur2->str);
203 slmergemax(&list, rlist);
210 static struct bound readbound(wchar_t *p, wchar_t **endret)
233 ret.min = wcstol(p, &p, 10);
240 ret.max = wcstol(p, &p, 10);
246 /* Cannot happen in a validated regex... */
247 flog(LOG_WARNING, "BUG? \"Impossible\" case encountered in search.c:readbound() (No `}' after `{'-type bound!");
262 #define fnc(p) do {if((p) != NULL) free(p); (p) = NULL; p ## size = 0; p ## data = 0;} while(0)
264 static struct reinfo analyzere(wchar_t *re, wchar_t **endret, wchar_t endc)
266 int i, commit, parsealt;
267 struct reinfo ret, sinf;
270 size_t cssize, csdata, nssize, nsdata, len1, len2, maxlen, minlen;
272 struct wcslist *list;
274 memset(&ret, 0, sizeof(ret));
275 commit = parsealt = 0;
278 cssize = csdata = nssize = nsdata = 0;
279 while((*re != endc) && !parsealt)
290 b = readbound(re, &re);
296 sinf = analyzere(re, &re, L')');
298 b = readbound(re, &re);
299 if(sinf.onestr != NULL)
301 for(i = 0; i < b.min; i++)
303 bufcat(cs, sinf.onestr, wcslen(sinf.onestr));
304 bufcat(ns, sinf.onestr, wcslen(sinf.onestr));
306 if((b.max == -1) || (b.max > b.min))
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));
318 if(sinf.begstr != NULL)
320 if(sinf.endstr != NULL)
322 if(sinf.onestr != NULL)
325 slmergemax(&ret.strs, sinf.strs);
331 /* Must exist in a validated RE... */
332 while(*(re++) != L']');
342 /* A validated RE cannot end in a backslash, so fall
346 b = readbound(re, &re);
347 for(i = 0; i < b.min; i++)
349 if((b.max == -1) || (b.max > b.min))
360 ret.begstr = swcsdup(cs);
364 slmerge1(&ret.strs, cs);
380 ret.onestr = swcsdup(cs);
382 ret.endstr = swcsdup(cs);
383 slmerge1(&ret.strs, cs);
388 sinf = analyzere(re, &re, endc);
389 list = slmergemin(ret.strs, sinf.strs);
393 if(sinf.begstr != NULL)
395 if(ret.begstr != NULL)
397 for(i = 0; (sinf.begstr[i] != L'\0') && (ret.begstr != L'\0') && (ret.begstr[i] == sinf.begstr[i]); i++);
402 ret.begstr[i] = L'\0';
407 if(ret.begstr != NULL)
413 if(sinf.endstr != NULL)
415 if(ret.endstr != NULL)
417 len1 = wcslen(ret.endstr);
418 len2 = wcslen(sinf.endstr);
427 for(i = 1; (i <= minlen) && (ret.endstr[len1 - i] == sinf.endstr[len2 - i]); i++);
431 } else if(i <= maxlen) {
432 wmemmove(ret.endstr, ret.endstr + (len1 - i) + 1, i);
437 if(ret.endstr != NULL)
443 if(sinf.onestr != NULL)
445 if(ret.onestr != NULL)
447 /* XXX: Comparing beginning and end of the onestrs and
448 * create begstr and endstr if there isn't an exact
450 if(wcscmp(ret.onestr, sinf.onestr))
458 if(ret.onestr != NULL)
472 struct wcslist *regexfindstrings(wchar_t *re)
476 i = analyzere(re, NULL, L'\0');
486 static struct sexpr *newsexpr(void)
490 sexpr = smalloc(sizeof(*sexpr));
491 memset(sexpr, 0, sizeof(*sexpr));
496 void getsexpr(struct sexpr *sexpr)
501 void putsexpr(struct sexpr *sexpr)
503 if(--sexpr->refcount != 0)
509 if((sexpr->op == SOP_NAMERE) || (sexpr->op == SOP_LINKRE))
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);
516 if((sexpr->op == SOP_NAMESS) || (sexpr->op == SOP_LINKSS))
518 if(sexpr->d.s != NULL)
521 if(sexpr->op == SOP_HASHIS)
523 if(sexpr->d.hash != NULL)
524 freehash(sexpr->d.hash);
529 static struct tok *newtok(void)
533 tok = smalloc(sizeof(*tok));
534 memset(tok, 0, sizeof(*tok));
539 static void freetok(struct tok *tok)
541 if((tok->type == TOK_STR) && (tok->d.str != NULL))
543 if((tok->type == TOK_SE) && (tok->d.se != NULL))
548 static void pushtok(struct tok *tok, struct tok **st)
554 static struct tok *poptok(struct tok **st)
563 int calccost(struct sexpr *sexpr)
565 sexpr->tcost = sexpr->cost;
567 sexpr->tcost += calccost(sexpr->l);
569 sexpr->tcost += calccost(sexpr->r);
570 return(sexpr->tcost);
573 struct sexpr *parsesexpr(int argc, wchar_t **argv)
576 struct tok *st, *tok, *tok2;
583 for(i = 0; i < argc; i++)
585 pushtok(tok = newtok(), &st);
587 tok->d.str = swcsdup(argv[i]);
592 if((st->type == TOK_STR) && !wcscmp(st->d.str, L"("))
594 freetok(poptok(&st));
595 pushtok(tok = newtok(), &st);
598 } else if((st->type == TOK_STR) && !wcscmp(st->d.str, L")")) {
599 freetok(poptok(&st));
600 pushtok(tok = newtok(), &st);
603 } else if((st->type == TOK_STR) && (!wcsncmp(st->d.str, L"N~", 2) || !wcsncmp(st->d.str, L"L~", 2))) {
605 pushtok(tok = newtok(), &st);
608 if((wbuf = regexunquotesimple(tok2->d.str + 2)) != NULL)
610 if(tok2->d.str[0] == L'N')
611 sexpr->op = SOP_NAMESS;
613 sexpr->op = SOP_LINKSS;
617 if(tok2->d.str[0] == L'N')
618 sexpr->op = SOP_NAMERE;
620 sexpr->op = SOP_LINKRE;
622 if((buf = icwcstombs(tok2->d.str + 2, "UTF-8")) == NULL)
628 if(regcomp(&sexpr->d.re.cre, buf, REG_EXTENDED | REG_ICASE | REG_NOSUB))
636 sexpr->d.re.inited = 1;
637 sexpr->d.re.sre = swcsdup(tok2->d.str + 2);
639 getsexpr(tok->d.se = sexpr);
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))) {
645 pushtok(tok = newtok(), &st);
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;
653 sexpr->op = SOP_SIZEGT;
654 sexpr->d.n = wcstol(tok2->d.str + 2, NULL, 0);
656 getsexpr(tok->d.se = sexpr);
660 } else if((st->type == TOK_STR) && !wcsncmp(st->d.str, L"H=", 2)) {
662 pushtok(tok = newtok(), &st);
665 sexpr->op = SOP_HASHIS;
666 if((sexpr->d.hash = parsehash(tok2->d.str + 2)) == NULL)
673 getsexpr(tok->d.se = sexpr);
677 } else if((std >= 3) && (st->type == TOK_CP) && (st->next->type == TOK_SE) && (st->next->next->type == TOK_OP)) {
678 freetok(poptok(&st));
680 freetok(poptok(&st));
684 } else if((std >= 2) && (st->type == TOK_SE) && (st->next->type == TOK_STR) && !wcscmp(st->next->d.str, L"!")) {
688 getsexpr(sexpr->l = st->d.se);
689 freetok(poptok(&st));
690 freetok(poptok(&st));
691 pushtok(tok = newtok(), &st);
693 getsexpr(tok->d.se = sexpr);
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)) {
699 if(!wcscmp(st->next->d.str, L"&"))
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);
711 getsexpr(tok->d.se = sexpr);
718 if((st == NULL) || (st->next != NULL) || (st->type != TOK_SE))
720 getsexpr(sexpr = st->d.se);
727 freetok(poptok(&st));
731 void optsexpr(struct sexpr *sexpr)
735 if((sexpr->l != NULL) && (sexpr->r != NULL))
737 if(sexpr->l->tcost > sexpr->r->tcost)
750 struct wcslist *findsexprstrs(struct sexpr *sexpr)
752 struct wcslist *list, *l1, *l2;
758 list = findsexprstrs(sexpr->l);
759 l1 = findsexprstrs(sexpr->r);
760 slmergemax(&list, l1);
764 l1 = findsexprstrs(sexpr->l);
765 l2 = findsexprstrs(sexpr->r);
766 list = slmergemin(l1, l2);
772 list = regexfindstrings(sexpr->d.re.sre);
776 slmerge1(&list, sexpr->d.s);
784 static void unlinksqueue(struct srchlist *ln)
787 ln->prev->next = ln->next;
789 ln->next->prev = ln->prev;
790 if(ln == searchqueue)
791 searchqueue = ln->next;
795 static void ctexpire(int cancelled, void *data)
802 static void estimatequeue(void)
804 struct srchlist *cur;
805 struct srchfnnlist *ln;
808 if(searchqueue == NULL)
810 start = now = time(NULL);
811 for(ln = searchqueue->srch->fnl; ln != NULL; ln = ln->next)
813 if((ln->fn->lastsrch != 0) && (ln->fn->lastsrch + ln->fn->srchwait > start))
814 start = ln->fn->lastsrch + ln->fn->srchwait;
816 if(start != searchqueue->srch->eta)
818 searchqueue->srch->eta = start;
819 CBCHAINDOCB(searchqueue->srch, search_eta, searchqueue->srch);
821 for(cur = searchqueue->next; cur != NULL; cur = cur->next)
824 for(ln = cur->srch->fnl; ln != NULL; ln = ln->next)
826 if(now + ln->fn->srchwait > start)
827 start = now + ln->fn->srchwait;
829 if(start != cur->srch->eta)
831 cur->srch->eta = start;
832 CBCHAINDOCB(cur->srch, search_eta, cur->srch);
835 if((committimer == NULL) || ((time_t)committimer->at != searchqueue->srch->eta))
837 if(committimer != NULL)
838 canceltimer(committimer);
839 committimer = timercallback(searchqueue->srch->eta, ctexpire, NULL);
843 struct search *findsearch(int id)
847 for(srch = searches; srch != NULL; srch = srch->next)
855 struct search *newsearch(wchar_t *owner, struct sexpr *sexpr)
860 srch = smalloc(sizeof(*srch));
861 memset(srch, 0, sizeof(*srch));
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;
873 searches->prev = srch;
878 static void srchexpire(int cancelled, struct search *srch)
880 srch->freetimer = NULL;
885 static void trycommit(void)
887 struct srchfnnlist *ln;
891 if(searchqueue == NULL)
893 srch = searchqueue->srch;
895 for(ln = srch->fnl; ln != NULL; ln = ln->next)
897 if(now < ln->fn->lastsrch + ln->fn->srchwait)
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);
913 void freesearch(struct search *srch)
915 struct srchfnnlist *ln;
916 struct srchlist *sln;
918 if(srch->prev != NULL)
919 srch->prev->next = srch->next;
920 if(srch->next != NULL)
921 srch->next->prev = srch->prev;
923 searches = srch->next;
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)
936 if(sln->srch == srch)
942 while(srch->fnl != NULL)
945 srch->fnl = ln->next;
946 CBCHAINDOCB(ln, searchfnl_destroy, ln);
947 CBCHAINFREE(ln, searchfnl_destroy);
951 if(srch->sexpr != NULL)
952 putsexpr(srch->sexpr);
953 if(srch->owner != NULL)
958 void searchaddfn(struct search *srch, struct fnetnode *fn)
960 struct srchfnnlist *ln;
962 for(ln = srch->fnl; ln != NULL; ln = ln->next)
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;
975 static void linksearch(struct search *srch, struct srchlist *prev)
977 struct srchlist *new;
979 new = smalloc(sizeof(*new));
984 new->next = searchqueue;
985 if(searchqueue != NULL)
986 searchqueue->prev = new;
990 if((new->next = prev->next) != NULL)
991 new->next->prev = new;
994 GCBCHAINDOCB(newsrchcb, srch);
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
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.
1015 void queuesearch(struct search *srch)
1017 struct srchlist *cur, *lastmine, *prev;
1020 for(prev = NULL, cur = searchqueue; cur != NULL; prev = cur, cur = cur->next)
1022 if(cur->srch->prio >= srch->prio)
1027 linksearch(srch, prev);
1031 for(; cur != NULL; prev = cur, cur = cur->next)
1033 if(!wcscmp(cur->srch->owner, srch->owner))
1034 lastmine = cur->next;
1035 if(cur->srch->prio > srch->prio)
1038 if((lastmine == NULL) || (lastmine->srch->prio > srch->prio))
1040 linksearch(srch, prev);
1043 nexto = lastmine->srch->owner;
1044 for(cur = lastmine->next; cur != NULL; prev = cur, cur = cur->next)
1046 if(!wcscmp(cur->srch->owner, nexto))
1048 if(cur->srch->prio > srch->prio)
1053 linksearch(srch, prev);
1056 linksearch(srch, prev);
1059 static int srisvalid(struct srchres *sr, struct sexpr *sexpr)
1072 if(!srisvalid(sr, sexpr->l))
1074 return(srisvalid(sr, sexpr->r));
1076 if(srisvalid(sr, sexpr->l))
1078 return(srisvalid(sr, sexpr->r));
1080 return(!srisvalid(sr, sexpr->l));
1082 if((buf = icwcstombs(sr->filename, "UTF-8")) == NULL)
1084 ret = regexec(&sexpr->d.re.cre, buf, 0, NULL, 0);
1089 if(sr->fnet->filebasename != NULL)
1090 p = sr->fnet->filebasename(p);
1091 if((buf = icwcstombs(p, "UTF-8")) == NULL)
1093 ret = regexec(&sexpr->d.re.cre, buf, 0, NULL, 0);
1097 return(wcsexists(sr->filename, sexpr->d.s));
1100 if(sr->fnet->filebasename != NULL)
1101 p = sr->fnet->filebasename(p);
1102 return(wcsexists(p, sexpr->d.s));
1104 return(sr->size < sexpr->d.n);
1106 return(sr->size == sexpr->d.n);
1108 return(sr->size > sexpr->d.n);
1110 if(sr->hash == NULL)
1112 return(hashcmp(sr->hash, sexpr->d.hash));
1117 struct srchres *newsrchres(struct fnet *fnet, wchar_t *filename, wchar_t *peerid)
1121 sr = smalloc(sizeof(*sr));
1122 memset(sr, 0, sizeof(*sr));
1126 sr->filename = swcsdup(filename);
1127 sr->peerid = swcsdup(peerid);
1131 void freesrchres(struct srchres *sr)
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)
1139 if(sr->srch->results == sr)
1140 sr->srch->results = sr->next;
1143 if(sr->hash != NULL)
1145 if(sr->filename != NULL)
1147 if(sr->peerid != NULL)
1149 if(sr->peernick != NULL)
1152 putfnetnode(sr->fn);
1156 struct srchres *dupsrchres(struct srchres *sr)
1158 struct srchres *new;
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);
1172 getfnetnode(new->fn = sr->fn);
1173 if(sr->hash != NULL)
1174 new->hash = duphash(sr->hash);
1178 static void linksr(struct search *srch, struct srchres *sr)
1181 sr->next = srch->results;
1182 if(srch->results != NULL)
1183 srch->results->prev = sr;
1186 sr->time = ntime() - srch->committime;
1190 void submitsrchres(struct srchres *sr)
1192 struct search *srch;
1193 struct srchfnnlist *ln;
1194 struct srchres *dsr;
1196 for(srch = searches; srch != NULL; srch = srch->next)
1198 if(srch->state == SRCH_RUN)
1200 if(!srisvalid(sr, srch->sexpr))
1202 for(ln = srch->fnl; ln != NULL; ln = ln->next)
1204 if(((sr->fn != NULL) && (ln->fn == sr->fn)) || ((sr->fn == NULL) && (sr->fnet == ln->fn->fnet)))
1209 dsr = dupsrchres(sr);
1211 CBCHAINDOCB(srch, search_result, srch, dsr);