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