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 int wcsexists(wchar_t *h, wchar_t *n)
144 size_t hl = wcslen(h), nl = wcslen(n);
145 wchar_t lh[hl + 1], ln[nl + 1];
148 for(i = 0; i <= hl; i++)
149 lh[i] = towlower(h[i]);
150 for(i = 0; i <= nl; i++)
151 ln[i] = towlower(n[i]);
152 return(wcsstr(lh, ln) != NULL);
155 static void slmerge1(struct wcslist **list, wchar_t *str)
158 struct wcslist *cur, *next;
161 for(cur = *list; cur != NULL; cur = next)
166 if(((len < cur->len) && wcsexists(cur->str, str)) || !wcscmp(str, cur->str))
168 } else if(len > cur->len) {
169 if(wcsexists(str, cur->str))
176 void slmergemax(struct wcslist **dest, struct wcslist *src)
178 for(; src != NULL; src = src->next)
179 slmerge1(dest, src->str);
182 static struct wcslist *makeminlist1(wchar_t *s1, wchar_t *s2)
186 struct wcslist *list;
189 for(p1 = s1; *p1 != L'\0'; p1++)
191 for(p2 = s2; *p2 != L'\0'; p2++)
193 for(i = 0; (p1[i] != L'\0') && (p2[i] != L'\0') && (towlower(p1[i]) == towlower(p2[i])); i++);
206 struct wcslist *slmergemin(struct wcslist *l1, struct wcslist *l2)
208 struct wcslist *cur1, *cur2, *list, *rlist;
211 for(cur1 = l1; cur1 != NULL; cur1 = cur1->next)
213 for(cur2 = l2; cur2 != NULL; cur2 = cur2->next)
215 rlist = makeminlist1(cur1->str, cur2->str);
216 slmergemax(&list, rlist);
223 static struct bound readbound(wchar_t *p, wchar_t **endret)
246 ret.min = wcstol(p, &p, 10);
253 ret.max = wcstol(p, &p, 10);
259 /* Cannot happen in a validated regex... */
260 flog(LOG_WARNING, "BUG? \"Impossible\" case encountered in search.c:readbound() (No `}' after `{'-type bound!");
275 #define fnc(p) do {if((p) != NULL) free(p); (p) = NULL; p ## size = 0; p ## data = 0;} while(0)
277 static struct reinfo analyzere(wchar_t *re, wchar_t **endret, wchar_t endc)
279 int i, commit, parsealt;
280 struct reinfo ret, sinf;
283 size_t cssize, csdata, nssize, nsdata, len1, len2, maxlen, minlen;
285 struct wcslist *list;
287 memset(&ret, 0, sizeof(ret));
288 commit = parsealt = 0;
291 cssize = csdata = nssize = nsdata = 0;
292 while((*re != endc) && !parsealt)
303 b = readbound(re, &re);
309 sinf = analyzere(re, &re, L')');
311 b = readbound(re, &re);
312 if(sinf.onestr != NULL)
314 for(i = 0; i < b.min; i++)
316 bufcat(cs, sinf.onestr, wcslen(sinf.onestr));
317 bufcat(ns, sinf.onestr, wcslen(sinf.onestr));
319 if((b.max == -1) || (b.max > b.min))
325 if(sinf.begstr != NULL)
326 bufcat(cs, sinf.begstr, wcslen(sinf.begstr));
327 if(sinf.endstr != NULL)
328 bufcat(ns, sinf.endstr, wcslen(sinf.endstr));
331 if(sinf.begstr != NULL)
333 if(sinf.endstr != NULL)
335 if(sinf.onestr != NULL)
338 slmergemax(&ret.strs, sinf.strs);
344 /* Must exist in a validated RE... */
345 while(*(re++) != L']');
355 /* A validated RE cannot end in a backslash, so fall
359 b = readbound(re, &re);
360 for(i = 0; i < b.min; i++)
362 if((b.max == -1) || (b.max > b.min))
373 ret.begstr = swcsdup(cs);
377 slmerge1(&ret.strs, cs);
393 ret.onestr = swcsdup(cs);
395 ret.endstr = swcsdup(cs);
396 slmerge1(&ret.strs, cs);
401 sinf = analyzere(re, &re, endc);
402 list = slmergemin(ret.strs, sinf.strs);
406 if(sinf.begstr != NULL)
408 if(ret.begstr != NULL)
410 for(i = 0; (sinf.begstr[i] != L'\0') && (ret.begstr != L'\0') && (ret.begstr[i] == sinf.begstr[i]); i++);
415 ret.begstr[i] = L'\0';
420 if(ret.begstr != NULL)
426 if(sinf.endstr != NULL)
428 if(ret.endstr != NULL)
430 len1 = wcslen(ret.endstr);
431 len2 = wcslen(sinf.endstr);
440 for(i = 1; (i <= minlen) && (ret.endstr[len1 - i] == sinf.endstr[len2 - i]); i++);
444 } else if(i <= maxlen) {
445 wmemmove(ret.endstr, ret.endstr + (len1 - i) + 1, i);
450 if(ret.endstr != NULL)
456 if(sinf.onestr != NULL)
458 if(ret.onestr != NULL)
460 /* XXX: Comparing beginning and end of the onestrs and
461 * create begstr and endstr if there isn't an exact
463 if(wcscmp(ret.onestr, sinf.onestr))
471 if(ret.onestr != NULL)
485 struct wcslist *regexfindstrings(wchar_t *re)
489 i = analyzere(re, NULL, L'\0');
499 static struct sexpr *newsexpr(void)
503 sexpr = smalloc(sizeof(*sexpr));
504 memset(sexpr, 0, sizeof(*sexpr));
509 void getsexpr(struct sexpr *sexpr)
514 void putsexpr(struct sexpr *sexpr)
516 if(--sexpr->refcount != 0)
522 if((sexpr->op == SOP_NAMERE) || (sexpr->op == SOP_LINKRE))
524 if(sexpr->d.re.sre != NULL)
525 free(sexpr->d.re.sre);
526 if(sexpr->d.re.inited)
527 regfree(&sexpr->d.re.cre);
529 if((sexpr->op == SOP_NAMESS) || (sexpr->op == SOP_LINKSS))
531 if(sexpr->d.s != NULL)
534 if(sexpr->op == SOP_HASHIS)
536 if(sexpr->d.hash != NULL)
537 freehash(sexpr->d.hash);
542 static struct tok *newtok(void)
546 tok = smalloc(sizeof(*tok));
547 memset(tok, 0, sizeof(*tok));
552 static void freetok(struct tok *tok)
554 if((tok->type == TOK_STR) && (tok->d.str != NULL))
556 if((tok->type == TOK_SE) && (tok->d.se != NULL))
561 static void pushtok(struct tok *tok, struct tok **st)
567 static struct tok *poptok(struct tok **st)
576 int calccost(struct sexpr *sexpr)
578 sexpr->tcost = sexpr->cost;
580 sexpr->tcost += calccost(sexpr->l);
582 sexpr->tcost += calccost(sexpr->r);
583 return(sexpr->tcost);
586 struct sexpr *parsesexpr(int argc, wchar_t **argv)
589 struct tok *st, *tok, *tok2;
596 for(i = 0; i < argc; i++)
598 pushtok(tok = newtok(), &st);
600 tok->d.str = swcsdup(argv[i]);
605 if((st->type == TOK_STR) && !wcscmp(st->d.str, L"("))
607 freetok(poptok(&st));
608 pushtok(tok = newtok(), &st);
611 } else if((st->type == TOK_STR) && !wcscmp(st->d.str, L")")) {
612 freetok(poptok(&st));
613 pushtok(tok = newtok(), &st);
616 } else if((st->type == TOK_STR) && (!wcsncmp(st->d.str, L"N~", 2) || !wcsncmp(st->d.str, L"L~", 2))) {
618 pushtok(tok = newtok(), &st);
621 if((wbuf = regexunquotesimple(tok2->d.str + 2)) != NULL)
623 if(tok2->d.str[0] == L'N')
624 sexpr->op = SOP_NAMESS;
626 sexpr->op = SOP_LINKSS;
630 if(tok2->d.str[0] == L'N')
631 sexpr->op = SOP_NAMERE;
633 sexpr->op = SOP_LINKRE;
635 if((buf = icwcstombs(tok2->d.str + 2, "UTF-8")) == NULL)
641 if(regcomp(&sexpr->d.re.cre, buf, REG_EXTENDED | REG_ICASE | REG_NOSUB))
649 sexpr->d.re.inited = 1;
650 sexpr->d.re.sre = swcsdup(tok2->d.str + 2);
652 getsexpr(tok->d.se = sexpr);
656 } 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))) {
658 pushtok(tok = newtok(), &st);
661 if(tok2->d.str[1] == L'<')
662 sexpr->op = SOP_SIZELT;
663 else if(tok2->d.str[1] == L'=')
664 sexpr->op = SOP_SIZEEQ;
666 sexpr->op = SOP_SIZEGT;
667 sexpr->d.n = wcstol(tok2->d.str + 2, NULL, 0);
669 getsexpr(tok->d.se = sexpr);
673 } else if((st->type == TOK_STR) && !wcsncmp(st->d.str, L"H=", 2)) {
675 pushtok(tok = newtok(), &st);
678 sexpr->op = SOP_HASHIS;
679 if((sexpr->d.hash = parsehash(tok2->d.str + 2)) == NULL)
686 getsexpr(tok->d.se = sexpr);
690 } else if((std >= 3) && (st->type == TOK_CP) && (st->next->type == TOK_SE) && (st->next->next->type == TOK_OP)) {
691 freetok(poptok(&st));
693 freetok(poptok(&st));
697 } else if((std >= 2) && (st->type == TOK_SE) && (st->next->type == TOK_STR) && !wcscmp(st->next->d.str, L"!")) {
701 getsexpr(sexpr->l = st->d.se);
702 freetok(poptok(&st));
703 freetok(poptok(&st));
704 pushtok(tok = newtok(), &st);
706 getsexpr(tok->d.se = sexpr);
710 } 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)) {
712 if(!wcscmp(st->next->d.str, L"&"))
717 getsexpr(sexpr->l = st->next->next->d.se);
718 getsexpr(sexpr->r = st->d.se);
719 freetok(poptok(&st));
720 freetok(poptok(&st));
721 freetok(poptok(&st));
722 pushtok(tok = newtok(), &st);
724 getsexpr(tok->d.se = sexpr);
731 if((st == NULL) || (st->next != NULL) || (st->type != TOK_SE))
733 getsexpr(sexpr = st->d.se);
740 freetok(poptok(&st));
744 void optsexpr(struct sexpr *sexpr)
748 if((sexpr->l != NULL) && (sexpr->r != NULL))
750 if(sexpr->l->tcost > sexpr->r->tcost)
763 struct wcslist *findsexprstrs(struct sexpr *sexpr)
765 struct wcslist *list, *l1, *l2;
771 list = findsexprstrs(sexpr->l);
772 l1 = findsexprstrs(sexpr->r);
773 slmergemax(&list, l1);
777 l1 = findsexprstrs(sexpr->l);
778 l2 = findsexprstrs(sexpr->r);
779 list = slmergemin(l1, l2);
785 list = regexfindstrings(sexpr->d.re.sre);
789 slmerge1(&list, sexpr->d.s);
797 static void unlinksqueue(struct srchlist *ln)
800 ln->prev->next = ln->next;
802 ln->next->prev = ln->prev;
803 if(ln == searchqueue)
804 searchqueue = ln->next;
808 static void ctexpire(int cancelled, void *data)
815 static void estimatequeue(void)
817 struct srchlist *cur;
818 struct srchfnnlist *ln;
821 if(searchqueue == NULL)
823 start = now = time(NULL);
824 for(ln = searchqueue->srch->fnl; ln != NULL; ln = ln->next)
826 if((ln->fn->lastsrch != 0) && (ln->fn->lastsrch + ln->fn->srchwait > start))
827 start = ln->fn->lastsrch + ln->fn->srchwait;
829 if(start != searchqueue->srch->eta)
831 searchqueue->srch->eta = start;
832 CBCHAINDOCB(searchqueue->srch, search_eta, searchqueue->srch);
834 for(cur = searchqueue->next; cur != NULL; cur = cur->next)
837 for(ln = cur->srch->fnl; ln != NULL; ln = ln->next)
839 if(now + ln->fn->srchwait > start)
840 start = now + ln->fn->srchwait;
842 if(start != cur->srch->eta)
844 cur->srch->eta = start;
845 CBCHAINDOCB(cur->srch, search_eta, cur->srch);
848 if((committimer == NULL) || ((time_t)committimer->at != searchqueue->srch->eta))
850 if(committimer != NULL)
851 canceltimer(committimer);
852 committimer = timercallback(searchqueue->srch->eta, ctexpire, NULL);
856 struct search *findsearch(int id)
860 for(srch = searches; srch != NULL; srch = srch->next)
868 struct search *newsearch(wchar_t *owner, struct sexpr *sexpr)
873 srch = smalloc(sizeof(*srch));
874 memset(srch, 0, sizeof(*srch));
876 srch->owner = swcsdup(owner);
877 if((srch->sexpr = sexpr) != NULL)
878 getsexpr(srch->sexpr);
879 CBCHAININIT(srch, search_eta);
880 CBCHAININIT(srch, search_commit);
881 CBCHAININIT(srch, search_result);
882 CBCHAININIT(srch, search_destroy);
883 srch->next = searches;
886 searches->prev = srch;
891 static void srchexpire(int cancelled, struct search *srch)
893 srch->freetimer = NULL;
898 static void trycommit(void)
900 struct srchfnnlist *ln;
904 if(searchqueue == NULL)
906 srch = searchqueue->srch;
908 for(ln = srch->fnl; ln != NULL; ln = ln->next)
910 if(now < ln->fn->lastsrch + ln->fn->srchwait)
915 unlinksqueue(searchqueue);
916 srch->state = SRCH_RUN;
917 srch->eta = time(NULL);
918 srch->committime = ntime();
919 srch->freetimer = timercallback(ntime() + 300, (void (*)(int, void *))srchexpire, srch);
920 CBCHAINDOCB(srch, search_commit, srch);
921 for(ln = srch->fnl; ln != NULL; ln = ln->next)
922 fnetsearch(ln->fn, srch, ln);
926 void freesearch(struct search *srch)
928 struct srchfnnlist *ln;
929 struct srchlist *sln;
931 if(srch->prev != NULL)
932 srch->prev->next = srch->next;
933 if(srch->next != NULL)
934 srch->next->prev = srch->prev;
936 searches = srch->next;
938 if(srch->freetimer != NULL)
939 canceltimer(srch->freetimer);
940 CBCHAINDOCB(srch, search_destroy, srch);
941 CBCHAINFREE(srch, search_eta);
942 CBCHAINFREE(srch, search_commit);
943 CBCHAINFREE(srch, search_result);
944 CBCHAINFREE(srch, search_destroy);
945 while(srch->results != NULL)
946 freesrchres(srch->results);
947 for(sln = searchqueue; sln != NULL; sln = sln->next)
949 if(sln->srch == srch)
955 while(srch->fnl != NULL)
958 srch->fnl = ln->next;
959 CBCHAINDOCB(ln, searchfnl_destroy, ln);
960 CBCHAINFREE(ln, searchfnl_destroy);
964 if(srch->sexpr != NULL)
965 putsexpr(srch->sexpr);
966 if(srch->owner != NULL)
971 void searchaddfn(struct search *srch, struct fnetnode *fn)
973 struct srchfnnlist *ln;
975 for(ln = srch->fnl; ln != NULL; ln = ln->next)
980 ln = smalloc(sizeof(*ln));
981 memset(ln, 0, sizeof(*ln));
982 getfnetnode(ln->fn = fn);
983 CBCHAININIT(ln, searchfnl_destroy);
984 ln->next = srch->fnl;
988 static void linksearch(struct search *srch, struct srchlist *prev)
990 struct srchlist *new;
992 new = smalloc(sizeof(*new));
997 new->next = searchqueue;
998 if(searchqueue != NULL)
999 searchqueue->prev = new;
1003 if((new->next = prev->next) != NULL)
1004 new->next->prev = new;
1007 GCBCHAINDOCB(newsrchcb, srch);
1012 * queuesearch is also the "scheduler" function - it finds a suitable
1013 * place in the queue for the new search. I'll make a weak attempt at
1014 * describing the algorithm:
1015 * First, we find the first search that doesn't have a lower priority
1016 * than this one. If there is no such, we just link this one onto the
1018 * Then, if we have a search of this priority in the queue with the
1019 * same owner as the new search, we set lastmine to the search after
1020 * that one, otherwise, lastmine is the first search of this
1021 * priority. If lastmine is discovered either to not exist (that is,
1022 * our last search is at the end of the queue), or to be of lower
1023 * priority (higher number), we link it in at the appropriate end.
1024 * Then, we find the next search of the same priority and owner as
1025 * lastmine, and link this search in before it. That should yield a
1026 * 'round-robin-like' scheduling within priority boundaries. I think.
1028 void queuesearch(struct search *srch)
1030 struct srchlist *cur, *lastmine, *prev;
1033 for(prev = NULL, cur = searchqueue; cur != NULL; prev = cur, cur = cur->next)
1035 if(cur->srch->prio >= srch->prio)
1040 linksearch(srch, prev);
1044 for(; cur != NULL; prev = cur, cur = cur->next)
1046 if(!wcscmp(cur->srch->owner, srch->owner))
1047 lastmine = cur->next;
1048 if(cur->srch->prio > srch->prio)
1051 if((lastmine == NULL) || (lastmine->srch->prio > srch->prio))
1053 linksearch(srch, prev);
1056 nexto = lastmine->srch->owner;
1057 for(cur = lastmine->next; cur != NULL; prev = cur, cur = cur->next)
1059 if(!wcscmp(cur->srch->owner, nexto))
1061 if(cur->srch->prio > srch->prio)
1066 linksearch(srch, prev);
1069 linksearch(srch, prev);
1072 static int srisvalid(struct srchres *sr, struct sexpr *sexpr)
1085 if(!srisvalid(sr, sexpr->l))
1087 return(srisvalid(sr, sexpr->r));
1089 if(srisvalid(sr, sexpr->l))
1091 return(srisvalid(sr, sexpr->r));
1093 return(!srisvalid(sr, sexpr->l));
1095 if((buf = icwcstombs(sr->filename, "UTF-8")) == NULL)
1097 ret = regexec(&sexpr->d.re.cre, buf, 0, NULL, 0);
1101 p = fnfilebasename(sr->filename);
1102 if((buf = icwcstombs(p, "UTF-8")) == NULL)
1104 ret = regexec(&sexpr->d.re.cre, buf, 0, NULL, 0);
1108 return(wcsexists(sr->filename, sexpr->d.s));
1110 p = fnfilebasename(sr->filename);
1111 return(wcsexists(p, sexpr->d.s));
1113 return(sr->size < sexpr->d.n);
1115 return(sr->size == sexpr->d.n);
1117 return(sr->size > sexpr->d.n);
1119 if(sr->hash == NULL)
1121 return(hashcmp(sr->hash, sexpr->d.hash));
1126 struct srchres *newsrchres(struct fnet *fnet, wchar_t *filename, wchar_t *peerid)
1130 sr = smalloc(sizeof(*sr));
1131 memset(sr, 0, sizeof(*sr));
1135 sr->filename = swcsdup(filename);
1136 sr->peerid = swcsdup(peerid);
1140 void freesrchres(struct srchres *sr)
1142 if(sr->next != NULL)
1143 sr->next->prev = sr->prev;
1144 if(sr->prev != NULL)
1145 sr->prev->next = sr->next;
1146 if(sr->srch != NULL)
1148 if(sr->srch->results == sr)
1149 sr->srch->results = sr->next;
1152 if(sr->hash != NULL)
1154 if(sr->filename != NULL)
1156 if(sr->peerid != NULL)
1158 if(sr->peernick != NULL)
1161 putfnetnode(sr->fn);
1165 struct srchres *dupsrchres(struct srchres *sr)
1167 struct srchres *new;
1169 new = smalloc(sizeof(*new));
1170 memset(new, 0, sizeof(*new));
1171 new->size = sr->size;
1172 new->slots = sr->slots;
1173 new->fnet = sr->fnet;
1174 if(sr->peerid != NULL)
1175 new->peerid = swcsdup(sr->peerid);
1176 if(sr->peernick != NULL)
1177 new->peernick = swcsdup(sr->peernick);
1178 if(sr->filename != NULL)
1179 new->filename = swcsdup(sr->filename);
1181 getfnetnode(new->fn = sr->fn);
1182 if(sr->hash != NULL)
1183 new->hash = duphash(sr->hash);
1187 static void linksr(struct search *srch, struct srchres *sr)
1190 sr->next = srch->results;
1191 if(srch->results != NULL)
1192 srch->results->prev = sr;
1195 sr->time = ntime() - srch->committime;
1199 void submitsrchres(struct srchres *sr)
1201 struct search *srch;
1202 struct srchfnnlist *ln;
1203 struct srchres *dsr;
1205 for(srch = searches; srch != NULL; srch = srch->next)
1207 if(srch->state == SRCH_RUN)
1209 if(!srisvalid(sr, srch->sexpr))
1211 for(ln = srch->fnl; ln != NULL; ln = ln->next)
1213 if(((sr->fn != NULL) && (ln->fn == sr->fn)) || ((sr->fn == NULL) && (sr->fnet == ln->fn->fnet)))
1218 dsr = dupsrchres(sr);
1220 CBCHAINDOCB(srch, search_result, srch, dsr);