daemon/search.c

   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 <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"
  34 #include "client.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
  42 struct srchlist
  43 {
  44     struct srchlist *next, *prev;
  45     struct search *srch;
  46 };
  47
  48 struct tok
  49 {
  50     struct tok *next;
  51     int type;
  52     union
  53     {
  54         wchar_t *str;
  55         struct sexpr *se;
  56     } d;
  57 };
  58
  59 struct reinfo
  60 {
  61     wchar_t *begstr, *endstr, *onestr;
  62     struct wcslist *strs;
  63 };
  64
  65 struct bound
  66 {
  67     int min, max;
  68 };
  69
  70 static void trycommit(void);
  71
  72 struct search *searches = NULL;
  73 static struct srchlist *searchqueue = NULL;
  74 static struct timer *committimer = NULL;
  75 GCBCHAIN(newsrchcb, struct search *);
  76
  77 wchar_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
 108 static 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
 120 void freesl(struct wcslist **list)
 121 {
 122     while(*list != NULL)
 123         freesln(*list, list);
 124 }
 125
 126 static 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
 142 static int wcsexists(wchar_t *h, wchar_t *n)
 143 {
 144     size_t hl = wcslen(h), nl = wcslen(n);
 145     wchar_t lh[hl + 1], ln[nl + 1];
 146     int i;
 147
 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);
 153 }
 154
 155 static void slmerge1(struct wcslist **list, wchar_t *str)
 156 {
 157     size_t len;
 158     struct wcslist *cur, *next;
 159
 160     len = wcslen(str);
 161     for(cur = *list; cur != NULL; cur = next)
 162     {
 163         next = cur->next;
 164         if(len <= cur->len)
 165         {
 166             if(((len < cur->len) && wcsexists(cur->str, str)) || !wcscmp(str, cur->str))
 167                 return;
 168         } else if(len > cur->len) {
 169             if(wcsexists(str, cur->str))
 170                 freesln(cur, list);
 171         }
 172     }
 173     newsl(list, str);
 174 }
 175
 176 void slmergemax(struct wcslist **dest, struct wcslist *src)
 177 {
 178     for(; src != NULL; src = src->next)
 179         slmerge1(dest, src->str);
 180 }
 181
 182 static struct wcslist *makeminlist1(wchar_t *s1, wchar_t *s2)
 183 {
 184     int i;
 185     wchar_t *p1, *p2, c;
 186     struct wcslist *list;
 187
 188     list = NULL;
 189     for(p1 = s1; *p1 != L'\0'; p1++)
 190     {
 191         for(p2 = s2; *p2 != L'\0'; p2++)
 192         {
 193             for(i = 0; (p1[i] != L'\0') && (p2[i] != L'\0') && (towlower(p1[i]) == towlower(p2[i])); i++);
 194             if(i > 0)
 195             {
 196                 c = p2[i];
 197                 p2[i] = L'\0';
 198                 slmerge1(&list, p2);
 199                 p2[i] = c;
 200             }
 201         }
 202     }
 203     return(list);
 204 }
 205
 206 struct wcslist *slmergemin(struct wcslist *l1, struct wcslist *l2)
 207 {
 208     struct wcslist *cur1, *cur2, *list, *rlist;
 209
 210     list = NULL;
 211     for(cur1 = l1; cur1 != NULL; cur1 = cur1->next)
 212     {
 213         for(cur2 = l2; cur2 != NULL; cur2 = cur2->next)
 214         {
 215             rlist = makeminlist1(cur1->str, cur2->str);
 216             slmergemax(&list, rlist);
 217             freesl(&rlist);
 218         }
 219     }
 220     return(list);
 221 }
 222
 223 static struct bound readbound(wchar_t *p, wchar_t **endret)
 224 {
 225     struct bound ret;
 226
 227     switch(*p)
 228     {
 229     case L'?':
 230         ret.min = 0;
 231         ret.max = 1;
 232         p++;
 233         break;
 234     case L'*':
 235         ret.min = 0;
 236         ret.max = -1;
 237         p++;
 238         break;
 239     case L'+':
 240         ret.min = 1;
 241         ret.max = -1;
 242         p++;
 243         break;
 244     case L'{':
 245         p++;
 246         ret.min = wcstol(p, &p, 10);
 247         if(*p == L',')
 248         {
 249             p++;
 250             if(*p == L'}')
 251                 ret.max = -1;
 252             else
 253                 ret.max = wcstol(p, &p, 10);
 254         } else {
 255             ret.max = ret.min;
 256         }
 257         if(*p != L'}')
 258         {
 259             /* Cannot happen in a validated regex... */
 260             flog(LOG_WARNING, "BUG? \"Impossible\" case encountered in search.c:readbound() (No `}' after `{'-type bound!");
 261         } else {
 262             p++;
 263         }
 264         break;
 265     default:
 266         ret.min = 1;
 267         ret.max = 1;
 268         break;
 269     }
 270     if(endret != NULL)
 271         *endret = p;
 272     return(ret);
 273 }
 274
 275 #define fnc(p) do {if((p) != NULL) free(p); (p) = NULL; p ## size = 0; p ## data = 0;} while(0)
 276
 277 static struct reinfo analyzere(wchar_t *re, wchar_t **endret, wchar_t endc)
 278 {
 279     int i, commit, parsealt;
 280     struct reinfo ret, sinf;
 281     struct bound b;
 282     wchar_t *cs, *ns;
 283     size_t cssize, csdata, nssize, nsdata, len1, len2, maxlen, minlen;
 284     wchar_t beg, c;
 285     struct wcslist *list;
 286
 287     memset(&ret, 0, sizeof(ret));
 288     commit = parsealt = 0;
 289     beg = 1;
 290     cs = ns = NULL;
 291     cssize = csdata = nssize = nsdata = 0;
 292     while((*re != endc) && !parsealt)
 293     {
 294         switch(*re)
 295         {
 296         case L'$':
 297         case L'^':
 298             re++;
 299             commit = 1;
 300             break;
 301         case L'.':
 302             re++;
 303             b = readbound(re, &re);
 304             if(b.max != 0)
 305                 commit = 1;
 306             break;
 307         case L'(':
 308             re++;
 309             sinf = analyzere(re, &re, L')');
 310             re++;
 311             b = readbound(re, &re);
 312             if(sinf.onestr != NULL)
 313             {
 314                 for(i = 0; i < b.min; i++)
 315                 {
 316                     bufcat(cs, sinf.onestr, wcslen(sinf.onestr));
 317                     bufcat(ns, sinf.onestr, wcslen(sinf.onestr));
 318                 }
 319                 if((b.max == -1) || (b.max > b.min))
 320                     commit = 1;
 321             } else {
 322                 commit = 1;
 323                 if(b.min > 0)
 324                 {
 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));
 329                 }
 330             }
 331             if(sinf.begstr != NULL)
 332                 free(sinf.begstr);
 333             if(sinf.endstr != NULL)
 334                 free(sinf.endstr);
 335             if(sinf.onestr != NULL)
 336                 free(sinf.onestr);
 337             if(b.min > 0)
 338                 slmergemax(&ret.strs, sinf.strs);
 339             freesl(&sinf.strs);
 340             break;
 341         case L'[':
 342             c = L'\0';
 343             re += 2;
 344             /* Must exist in a validated RE... */
 345             while(*(re++) != L']');
 346             readbound(re, &re);
 347             commit = 1;
 348             break;
 349         case L'|':
 350             re++;
 351             parsealt = 1;
 352             break;
 353         case L'\\':
 354             re++;
 355             /* A validated RE cannot end in a backslash, so fall
 356              * through */
 357         default:
 358             c = *(re++);
 359             b = readbound(re, &re);
 360             for(i = 0; i < b.min; i++)
 361                 addtobuf(cs, c);
 362             if((b.max == -1) || (b.max > b.min))
 363                 commit = 1;
 364             break;
 365         }
 366         if(commit)
 367         {
 368             if(cs != NULL)
 369                 addtobuf(cs, L'\0');
 370             if(beg)
 371             {
 372                 if(cs != NULL)
 373                     ret.begstr = swcsdup(cs);
 374                 beg = 0;
 375             }
 376             if(cs != NULL)
 377                 slmerge1(&ret.strs, cs);
 378             fnc(cs);
 379             commit = 0;
 380             if(ns != NULL)
 381             {
 382                 cs = swcsdup(ns);
 383                 cssize = nssize;
 384                 csdata = nsdata;
 385                 fnc(ns);
 386             }
 387         }
 388     }
 389     if(cs != NULL)
 390     {
 391         addtobuf(cs, L'\0');
 392         if(beg)
 393             ret.onestr = swcsdup(cs);
 394         else
 395             ret.endstr = swcsdup(cs);
 396         slmerge1(&ret.strs, cs);
 397         fnc(cs);
 398     }
 399     if(parsealt)
 400     {
 401         sinf = analyzere(re, &re, endc);
 402         list = slmergemin(ret.strs, sinf.strs);
 403         freesl(&ret.strs);
 404         freesl(&sinf.strs);
 405         ret.strs = list;
 406         if(sinf.begstr != NULL)
 407         {
 408             if(ret.begstr != NULL)
 409             {
 410                 for(i = 0; (sinf.begstr[i] != L'\0') && (ret.begstr != L'\0') && (ret.begstr[i] == sinf.begstr[i]); i++);
 411                 if(i == 0) {
 412                     free(ret.begstr);
 413                     ret.begstr = NULL;
 414                 } else {
 415                     ret.begstr[i] = L'\0';
 416                 }
 417             }
 418             free(sinf.begstr);
 419         } else {
 420             if(ret.begstr != NULL)
 421             {
 422                 free(ret.begstr);
 423                 ret.begstr = NULL;
 424             }
 425         }
 426         if(sinf.endstr != NULL)
 427         {
 428             if(ret.endstr != NULL)
 429             {
 430                 len1 = wcslen(ret.endstr);
 431                 len2 = wcslen(sinf.endstr);
 432                 if(len1 < len2)
 433                 {
 434                     minlen = len1;
 435                     maxlen = len2;
 436                 } else {
 437                     minlen = len2;
 438                     maxlen = len1;
 439                 }
 440                 for(i = 1; (i <= minlen) && (ret.endstr[len1 - i] == sinf.endstr[len2 - i]); i++);
 441                 if(i == 1) {
 442                     free(ret.endstr);
 443                     ret.endstr = NULL;
 444                 } else if(i <= maxlen) {
 445                     wmemmove(ret.endstr, ret.endstr + (len1 - i) + 1, i);
 446                 }
 447             }
 448             free(sinf.endstr);
 449         } else {
 450             if(ret.endstr != NULL)
 451             {
 452                 free(ret.endstr);
 453                 ret.endstr = NULL;
 454             }
 455         }
 456         if(sinf.onestr != NULL)
 457         {
 458             if(ret.onestr != NULL)
 459             {
 460                 /* XXX: Comparing beginning and end of the onestrs and
 461                  * create begstr and endstr if there isn't an exact
 462                  * match.*/
 463                 if(wcscmp(ret.onestr, sinf.onestr))
 464                 {
 465                     free(ret.onestr);
 466                     ret.onestr = NULL;
 467                 }
 468             }
 469             free(sinf.onestr);
 470         } else {
 471             if(ret.onestr != NULL)
 472             {
 473                 free(ret.onestr);
 474                 ret.onestr = NULL;
 475             }
 476         }
 477     }
 478     if(endret != NULL)
 479         *endret = re;
 480     return(ret);
 481 }
 482
 483 #undef fnc
 484
 485 struct wcslist *regexfindstrings(wchar_t *re)
 486 {
 487     struct reinfo i;
 488
 489     i = analyzere(re, NULL, L'\0');
 490     if(i.begstr != NULL)
 491         free(i.begstr);
 492     if(i.endstr != NULL)
 493         free(i.endstr);
 494     if(i.onestr != NULL)
 495         free(i.onestr);
 496     return(i.strs);
 497 }
 498
 499 static struct sexpr *newsexpr(void)
 500 {
 501     struct sexpr *sexpr;
 502
 503     sexpr = smalloc(sizeof(*sexpr));
 504     memset(sexpr, 0, sizeof(*sexpr));
 505     sexpr->refcount = 1;
 506     return(sexpr);
 507 }
 508
 509 void getsexpr(struct sexpr *sexpr)
 510 {
 511     sexpr->refcount++;
 512 }
 513
 514 void putsexpr(struct sexpr *sexpr)
 515 {
 516     if(--sexpr->refcount != 0)
 517         return;
 518     if(sexpr->l != NULL)
 519         putsexpr(sexpr->l);
 520     if(sexpr->r != NULL)
 521         putsexpr(sexpr->r);
 522     if((sexpr->op == SOP_NAMERE) || (sexpr->op == SOP_LINKRE))
 523     {
 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);
 528     }
 529     if((sexpr->op == SOP_NAMESS) || (sexpr->op == SOP_LINKSS))
 530     {
 531         if(sexpr->d.s != NULL)
 532             free(sexpr->d.s);
 533     }
 534     if(sexpr->op == SOP_HASHIS)
 535     {
 536         if(sexpr->d.hash != NULL)
 537             freehash(sexpr->d.hash);
 538     }
 539     free(sexpr);
 540 }
 541
 542 static struct tok *newtok(void)
 543 {
 544     struct tok *tok;
 545
 546     tok = smalloc(sizeof(*tok));
 547     memset(tok, 0, sizeof(*tok));
 548     tok->next = NULL;
 549     return(tok);
 550 }
 551
 552 static void freetok(struct tok *tok)
 553 {
 554     if((tok->type == TOK_STR) && (tok->d.str != NULL))
 555         free(tok->d.str);
 556     if((tok->type == TOK_SE) && (tok->d.se != NULL))
 557         putsexpr(tok->d.se);
 558     free(tok);
 559 }
 560
 561 static void pushtok(struct tok *tok, struct tok **st)
 562 {
 563     tok->next = *st;
 564     *st = tok;
 565 }
 566
 567 static struct tok *poptok(struct tok **st)
 568 {
 569     struct tok *tok;
 570
 571     tok = *st;
 572     *st = (*st)->next;
 573     return(tok);
 574 }
 575
 576 int calccost(struct sexpr *sexpr)
 577 {
 578     sexpr->tcost = sexpr->cost;
 579     if(sexpr->l != NULL)
 580         sexpr->tcost += calccost(sexpr->l);
 581     if(sexpr->r != NULL)
 582         sexpr->tcost += calccost(sexpr->r);
 583     return(sexpr->tcost);
 584 }
 585
 586 struct sexpr *parsesexpr(int argc, wchar_t **argv)
 587 {
 588     int i, done, std;
 589     struct tok *st, *tok, *tok2;
 590     struct sexpr *sexpr;
 591     char *buf;
 592     wchar_t *wbuf;
 593
 594     std = 0;
 595     st = NULL;
 596     for(i = 0; i < argc; i++)
 597     {
 598         pushtok(tok = newtok(), &st);
 599         tok->type = TOK_STR;
 600         tok->d.str = swcsdup(argv[i]);
 601         std++;
 602         do
 603         {
 604             done = 1;
 605             if((st->type == TOK_STR) && !wcscmp(st->d.str, L"("))
 606             {
 607                 freetok(poptok(&st));
 608                 pushtok(tok = newtok(), &st);
 609                 tok->type = TOK_OP;
 610                 done = 0;
 611             } else if((st->type == TOK_STR) && !wcscmp(st->d.str, L")")) {
 612                 freetok(poptok(&st));
 613                 pushtok(tok = newtok(), &st);
 614                 tok->type = TOK_CP;
 615                 done = 0;
 616             } else if((st->type == TOK_STR) && (!wcsncmp(st->d.str, L"N~", 2) || !wcsncmp(st->d.str, L"L~", 2))) {
 617                 tok2 = poptok(&st);
 618                 pushtok(tok = newtok(), &st);
 619                 tok->type = TOK_SE;
 620                 sexpr = newsexpr();
 621                 if((wbuf = regexunquotesimple(tok2->d.str + 2)) != NULL)
 622                 {
 623                     if(tok2->d.str[0] == L'N')
 624                         sexpr->op = SOP_NAMESS;
 625                     else
 626                         sexpr->op = SOP_LINKSS;
 627                     sexpr->d.s = wbuf;
 628                     sexpr->cost = 5;
 629                 } else {
 630                     if(tok2->d.str[0] == L'N')
 631                         sexpr->op = SOP_NAMERE;
 632                     else
 633                         sexpr->op = SOP_LINKRE;
 634                     sexpr->cost = 20;
 635                     if((buf = icwcstombs(tok2->d.str + 2, "UTF-8")) == NULL)
 636                     {
 637                         freetok(tok2);
 638                         putsexpr(sexpr);
 639                         goto out_err;
 640                     }
 641                     if(regcomp(&sexpr->d.re.cre, buf, REG_EXTENDED | REG_ICASE | REG_NOSUB))
 642                     {
 643                         freetok(tok2);
 644                         free(buf);
 645                         putsexpr(sexpr);
 646                         goto out_err;
 647                     }
 648                     free(buf);
 649                     sexpr->d.re.inited = 1;
 650                     sexpr->d.re.sre = swcsdup(tok2->d.str + 2);
 651                 }
 652                 getsexpr(tok->d.se = sexpr);
 653                 freetok(tok2);
 654                 putsexpr(sexpr);
 655                 done = 0;
 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))) {
 657                 tok2 = poptok(&st);
 658                 pushtok(tok = newtok(), &st);
 659                 tok->type = TOK_SE;
 660                 sexpr = newsexpr();
 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;
 665                 else
 666                     sexpr->op = SOP_SIZEGT;
 667                 sexpr->d.sz = wcstoll(tok2->d.str + 2, NULL, 0);
 668                 sexpr->cost = 0;
 669                 getsexpr(tok->d.se = sexpr);
 670                 freetok(tok2);
 671                 putsexpr(sexpr);
 672                 done = 0;
 673             } else if((st->type == TOK_STR) && !wcsncmp(st->d.str, L"H=", 2)) {
 674                 tok2 = poptok(&st);
 675                 pushtok(tok = newtok(), &st);
 676                 tok->type = TOK_SE;
 677                 sexpr = newsexpr();
 678                 sexpr->op = SOP_HASHIS;
 679                 if((sexpr->d.hash = parsehash(tok2->d.str + 2)) == NULL)
 680                 {
 681                     freetok(tok2);
 682                     putsexpr(sexpr);
 683                     goto out_err;
 684                 }
 685                 sexpr->cost = 2;
 686                 getsexpr(tok->d.se = sexpr);
 687                 freetok(tok2);
 688                 putsexpr(sexpr);
 689                 done = 0;
 690             } else if((std >= 3) && (st->type == TOK_CP) && (st->next->type == TOK_SE) && (st->next->next->type == TOK_OP)) {
 691                 freetok(poptok(&st));
 692                 tok = poptok(&st);
 693                 freetok(poptok(&st));
 694                 pushtok(tok, &st);
 695                 std -= 2;
 696                 done = 0;
 697             } else if((std >= 2) && (st->type == TOK_SE) && (st->next->type == TOK_STR) && !wcscmp(st->next->d.str, L"!")) {
 698                 sexpr = newsexpr();
 699                 sexpr->op = SOP_NOT;
 700                 sexpr->cost = 0;
 701                 getsexpr(sexpr->l = st->d.se);
 702                 freetok(poptok(&st));
 703                 freetok(poptok(&st));
 704                 pushtok(tok = newtok(), &st);
 705                 tok->type = TOK_SE;
 706                 getsexpr(tok->d.se = sexpr);
 707                 putsexpr(sexpr);
 708                 std -= 1;
 709                 done = 0;
 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)) {
 711                 sexpr = newsexpr();
 712                 if(!wcscmp(st->next->d.str, L"&"))
 713                     sexpr->op = SOP_AND;
 714                 else
 715                     sexpr->op = SOP_OR;
 716                 sexpr->cost = 0;
 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);
 723                 tok->type = TOK_SE;
 724                 getsexpr(tok->d.se = sexpr);
 725                 putsexpr(sexpr);
 726                 std -= 2;
 727                 done = 0;
 728             }
 729         } while(!done);
 730     }
 731     if((st == NULL) || (st->next != NULL) || (st->type != TOK_SE))
 732         goto out_err;
 733     getsexpr(sexpr = st->d.se);
 734     freetok(st);
 735     calccost(sexpr);
 736     return(sexpr);
 737
 738  out_err:
 739     while(st != NULL)
 740         freetok(poptok(&st));
 741     return(NULL);
 742 }
 743
 744 void optsexpr(struct sexpr *sexpr)
 745 {
 746     struct sexpr *buf;
 747
 748     if((sexpr->l != NULL) && (sexpr->r != NULL))
 749     {
 750         if(sexpr->l->tcost > sexpr->r->tcost)
 751         {
 752             buf = sexpr->r;
 753             sexpr->r = sexpr->l;
 754             sexpr->l = buf;
 755         }
 756     }
 757     if(sexpr->l != NULL)
 758         optsexpr(sexpr->l);
 759     if(sexpr->r != NULL)
 760         optsexpr(sexpr->r);
 761 }
 762
 763 struct wcslist *findsexprstrs(struct sexpr *sexpr)
 764 {
 765     struct wcslist *list, *l1, *l2;
 766
 767     list = NULL;
 768     switch(sexpr->op)
 769     {
 770     case SOP_AND:
 771         list = findsexprstrs(sexpr->l);
 772         l1 = findsexprstrs(sexpr->r);
 773         slmergemax(&list, l1);
 774         freesl(&l1);
 775         break;
 776     case SOP_OR:
 777         l1 = findsexprstrs(sexpr->l);
 778         l2 = findsexprstrs(sexpr->r);
 779         list = slmergemin(l1, l2);
 780         freesl(&l1);
 781         freesl(&l2);
 782         break;
 783     case SOP_NAMERE:
 784     case SOP_LINKRE:
 785         list = regexfindstrings(sexpr->d.re.sre);
 786         break;
 787     case SOP_NAMESS:
 788     case SOP_LINKSS:
 789         slmerge1(&list, sexpr->d.s);
 790         break;
 791     default:
 792         break;
 793     }
 794     return(list);
 795 }
 796
 797 static void unlinksqueue(struct srchlist *ln)
 798 {
 799     if(ln->prev != NULL)
 800         ln->prev->next = ln->next;
 801     if(ln->next != NULL)
 802         ln->next->prev = ln->prev;
 803     if(ln == searchqueue)
 804         searchqueue = ln->next;
 805     free(ln);
 806 }
 807
 808 static void ctexpire(int cancelled, void *data)
 809 {
 810     committimer = NULL;
 811     if(!cancelled)
 812         trycommit();
 813 }
 814
 815 static void estimatequeue(void)
 816 {
 817     struct srchlist *cur;
 818     struct srchfnnlist *ln;
 819     time_t now, start;
 820
 821     if(searchqueue == NULL)
 822         return;
 823     start = now = time(NULL);
 824     for(ln = searchqueue->srch->fnl; ln != NULL; ln = ln->next)
 825     {
 826         if((ln->fn->lastsrch != 0) && (ln->fn->lastsrch + ln->fn->srchwait > start))
 827             start = ln->fn->lastsrch + ln->fn->srchwait;
 828     }
 829     if(start != searchqueue->srch->eta)
 830     {
 831         searchqueue->srch->eta = start;
 832         CBCHAINDOCB(searchqueue->srch, search_eta, searchqueue->srch);
 833     }
 834     for(cur = searchqueue->next; cur != NULL; cur = cur->next)
 835     {
 836         now = start;
 837         for(ln = cur->srch->fnl; ln != NULL; ln = ln->next)
 838         {
 839             if(now + ln->fn->srchwait > start)
 840                 start = now + ln->fn->srchwait;
 841         }
 842         if(start != cur->srch->eta)
 843         {
 844             cur->srch->eta = start;
 845             CBCHAINDOCB(cur->srch, search_eta, cur->srch);
 846         }
 847     }
 848     if((committimer == NULL) || ((time_t)committimer->at != searchqueue->srch->eta))
 849     {
 850         if(committimer != NULL)
 851             canceltimer(committimer);
 852         committimer = timercallback(searchqueue->srch->eta, ctexpire, NULL);
 853     }
 854 }
 855
 856 struct search *findsearch(int id)
 857 {
 858     struct search *srch;
 859
 860     for(srch = searches; srch != NULL; srch = srch->next)
 861     {
 862         if(srch->id == id)
 863             break;
 864     }
 865     return(srch);
 866 }
 867
 868 struct search *newsearch(wchar_t *owner, struct sexpr *sexpr)
 869 {
 870     struct search *srch;
 871     static int id = 0;
 872
 873     srch = smalloc(sizeof(*srch));
 874     memset(srch, 0, sizeof(*srch));
 875     srch->id = id++;
 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;
 884     srch->prev = NULL;
 885     if(searches != NULL)
 886         searches->prev = srch;
 887     searches = srch;
 888     return(srch);
 889 }
 890
 891 static void srchexpire(int cancelled, struct search *srch)
 892 {
 893     srch->freetimer = NULL;
 894     if(!cancelled)
 895         freesearch(srch);
 896 }
 897
 898 static void trycommit(void)
 899 {
 900     struct srchfnnlist *ln;
 901     struct search *srch;
 902     time_t now;
 903
 904     if(searchqueue == NULL)
 905         return;
 906     srch = searchqueue->srch;
 907     now = time(NULL);
 908     for(ln = srch->fnl; ln != NULL; ln = ln->next)
 909     {
 910         if(now < ln->fn->lastsrch + ln->fn->srchwait)
 911             break;
 912     }
 913     if(ln != NULL)
 914         return;
 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);
 923     estimatequeue();
 924 }
 925
 926 void freesearch(struct search *srch)
 927 {
 928     struct srchfnnlist *ln;
 929     struct srchlist *sln;
 930
 931     if(srch->prev != NULL)
 932         srch->prev->next = srch->next;
 933     if(srch->next != NULL)
 934         srch->next->prev = srch->prev;
 935     if(srch == searches)
 936         searches = srch->next;
 937     estimatequeue();
 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)
 948     {
 949         if(sln->srch == srch)
 950         {
 951             unlinksqueue(sln);
 952             break;
 953         }
 954     }
 955     while(srch->fnl != NULL)
 956     {
 957         ln = srch->fnl;
 958         srch->fnl = ln->next;
 959         CBCHAINDOCB(ln, searchfnl_destroy, ln);
 960         CBCHAINFREE(ln, searchfnl_destroy);
 961         putfnetnode(ln->fn);
 962         free(ln);
 963     }
 964     if(srch->sexpr != NULL)
 965         putsexpr(srch->sexpr);
 966     if(srch->owner != NULL)
 967         free(srch->owner);
 968     free(srch);
 969 }
 970
 971 void searchaddfn(struct search *srch, struct fnetnode *fn)
 972 {
 973     struct srchfnnlist *ln;
 974
 975     for(ln = srch->fnl; ln != NULL; ln = ln->next)
 976     {
 977         if(ln->fn == fn)
 978             return;
 979     }
 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;
 985     srch->fnl = ln;
 986 }
 987
 988 static void linksearch(struct search *srch, struct srchlist *prev)
 989 {
 990     struct srchlist *new;
 991
 992     new = smalloc(sizeof(*new));
 993     new->srch = srch;
 994     if(prev == NULL)
 995     {
 996         new->prev = NULL;
 997         new->next = searchqueue;
 998         if(searchqueue != NULL)
 999             searchqueue->prev = new;
1000         searchqueue = new;
1001     } else {
1002         new->prev = prev;
1003         if((new->next = prev->next) != NULL)
1004             new->next->prev = new;
1005         prev->next = new;
1006     }
1007     GCBCHAINDOCB(newsrchcb, srch);
1008     estimatequeue();
1009 }
1010
1011 /*
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
1017  * end of the queue.
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.
1027  */
1028 void queuesearch(struct search *srch)
1029 {
1030     struct srchlist *cur, *lastmine, *prev;
1031     wchar_t *nexto;
1032
1033     for(prev = NULL, cur = searchqueue; cur != NULL; prev = cur, cur = cur->next)
1034     {
1035         if(cur->srch->prio >= srch->prio)
1036             break;
1037     }
1038     if(cur == NULL)
1039     {
1040         linksearch(srch, prev);
1041         return;
1042     }
1043     lastmine = cur;
1044     for(; cur != NULL; prev = cur, cur = cur->next)
1045     {
1046         if(!wcscmp(cur->srch->owner, srch->owner))
1047             lastmine = cur->next;
1048         if(cur->srch->prio > srch->prio)
1049             break;
1050     }
1051     if((lastmine == NULL) || (lastmine->srch->prio > srch->prio))
1052     {
1053         linksearch(srch, prev);
1054         return;
1055     }
1056     nexto = lastmine->srch->owner;
1057     for(cur = lastmine->next; cur != NULL; prev = cur, cur = cur->next)
1058     {
1059         if(!wcscmp(cur->srch->owner, nexto))
1060             break;
1061         if(cur->srch->prio > srch->prio)
1062             break;
1063     }
1064     if(cur == NULL)
1065     {
1066         linksearch(srch, prev);
1067         return;
1068     }
1069     linksearch(srch, prev);
1070 }
1071
1072 static int srisvalid(struct srchres *sr, struct sexpr *sexpr)
1073 {
1074     int ret;
1075     char *buf;
1076     wchar_t *p;
1077
1078     switch(sexpr->op)
1079     {
1080     case SOP_FALSE:
1081         return(0);
1082     case SOP_TRUE:
1083         return(1);
1084     case SOP_AND:
1085         if(!srisvalid(sr, sexpr->l))
1086             return(0);
1087         return(srisvalid(sr, sexpr->r));
1088     case SOP_OR:
1089         if(srisvalid(sr, sexpr->l))
1090             return(1);
1091         return(srisvalid(sr, sexpr->r));
1092     case SOP_NOT:
1093         return(!srisvalid(sr, sexpr->l));
1094     case SOP_NAMERE:
1095         if((buf = icwcstombs(sr->filename, "UTF-8")) == NULL)
1096             return(0);
1097         ret = regexec(&sexpr->d.re.cre, buf, 0, NULL, 0);
1098         free(buf);
1099         return(!ret);
1100     case SOP_LINKRE:
1101         p = fnfilebasename(sr->filename);
1102         if((buf = icwcstombs(p, "UTF-8")) == NULL)
1103             return(0);
1104         ret = regexec(&sexpr->d.re.cre, buf, 0, NULL, 0);
1105         free(buf);
1106         return(!ret);
1107     case SOP_NAMESS:
1108         return(wcsexists(sr->filename, sexpr->d.s));
1109     case SOP_LINKSS:
1110         p = fnfilebasename(sr->filename);
1111         return(wcsexists(p, sexpr->d.s));
1112     case SOP_SIZELT:
1113         return(sr->size < sexpr->d.sz);
1114     case SOP_SIZEEQ:
1115         return(sr->size == sexpr->d.sz);
1116     case SOP_SIZEGT:
1117         return(sr->size > sexpr->d.sz);
1118     case SOP_HASHIS:
1119         if(sr->hash == NULL)
1120             return(0);
1121         return(hashcmp(sr->hash, sexpr->d.hash));
1122     }
1123     return(0);
1124 }
1125
1126 struct srchres *newsrchres(struct fnet *fnet, wchar_t *filename, wchar_t *peerid)
1127 {
1128     struct srchres *sr;
1129
1130     sr = smalloc(sizeof(*sr));
1131     memset(sr, 0, sizeof(*sr));
1132     sr->size = -1;
1133     sr->slots = -1;
1134     sr->fnet = fnet;
1135     sr->filename = swcsdup(filename);
1136     sr->peerid = swcsdup(peerid);
1137     return(sr);
1138 }
1139
1140 void freesrchres(struct srchres *sr)
1141 {
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)
1147     {
1148         if(sr->srch->results == sr)
1149             sr->srch->results = sr->next;
1150         sr->srch->numres--;
1151     }
1152     if(sr->hash != NULL)
1153         freehash(sr->hash);
1154     if(sr->filename != NULL)
1155         free(sr->filename);
1156     if(sr->peerid != NULL)
1157         free(sr->peerid);
1158     if(sr->peernick != NULL)
1159         free(sr->peernick);
1160     if(sr->fn != NULL)
1161         putfnetnode(sr->fn);
1162     free(sr);
1163 }
1164
1165 struct srchres *dupsrchres(struct srchres *sr)
1166 {
1167     struct srchres *new;
1168
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);
1180     if(sr->fn != NULL)
1181         getfnetnode(new->fn = sr->fn);
1182     if(sr->hash != NULL)
1183         new->hash = duphash(sr->hash);
1184     return(new);
1185 }
1186
1187 static void linksr(struct search *srch, struct srchres *sr)
1188 {
1189     sr->prev = NULL;
1190     sr->next = srch->results;
1191     if(srch->results != NULL)
1192         srch->results->prev = sr;
1193     srch->results = sr;
1194     sr->srch = srch;
1195     sr->time = ntime() - srch->committime;
1196     srch->numres++;
1197 }
1198
1199 void submitsrchres(struct srchres *sr)
1200 {
1201     struct search *srch;
1202     struct srchfnnlist *ln;
1203     struct srchres *dsr;
1204
1205     for(srch = searches; srch != NULL; srch = srch->next)
1206     {
1207         if(srch->state == SRCH_RUN)
1208         {
1209             if(!srisvalid(sr, srch->sexpr))
1210                 continue;
1211             for(ln = srch->fnl; ln != NULL; ln = ln->next)
1212             {
1213                 if(((sr->fn != NULL) && (ln->fn == sr->fn)) || ((sr->fn == NULL) && (sr->fnet == ln->fn->fnet)))
1214                     break;
1215             }
1216             if(ln != NULL)
1217             {
1218                 dsr = dupsrchres(sr);
1219                 linksr(srch, dsr);
1220                 CBCHAINDOCB(srch, search_result, srch, dsr);
1221             }
1222         }
1223     }
1224 }