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