granicus.if.org Git - postgresql/blob - contrib/tsearch2/snowball/utilities.c

   1
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5
   6 #include "header.h"
   7
   8 #define unless(C) if(!(C))
   9
  10 #define CREATE_SIZE 1
  11
  12 extern symbol *
  13 create_s(void)
  14 {
  15         symbol     *p;
  16         void       *mem = malloc(HEAD + (CREATE_SIZE + 1) * sizeof(symbol));
  17
  18         if (mem == NULL)
  19                 return NULL;
  20         p = (symbol *) (HEAD + (char *) mem);
  21         CAPACITY(p) = CREATE_SIZE;
  22         SET_SIZE(p, CREATE_SIZE);
  23         return p;
  24 }
  25
  26 extern void
  27 lose_s(symbol * p)
  28 {
  29         if (p == NULL)
  30                 return;
  31         free((char *) p - HEAD);
  32 }
  33
  34 /*
  35    new_p = X_skip_utf8(p, c, lb, l, n); skips n characters forwards from p + c
  36    if n +ve, or n characters backwards from p +c - 1 if n -ve. new_p is the new
  37    position, or 0 on failure.
  38
  39    -- used to implement hop and next in the utf8 case.
  40 */
  41
  42 extern int
  43 skip_utf8(const symbol * p, int c, int lb, int l, int n)
  44 {
  45         int                     b;
  46
  47         if (n >= 0)
  48         {
  49                 for (; n > 0; n--)
  50                 {
  51                         if (c >= l)
  52                                 return -1;
  53                         b = p[c++];
  54                         if (b >= 0xC0)
  55                         {                                       /* 1100 0000 */
  56                                 while (c < l)
  57                                 {
  58                                         b = p[c];
  59                                         if (b >= 0xC0 || b < 0x80)
  60                                                 break;
  61                                         /* break unless b is 10------ */
  62                                         c++;
  63                                 }
  64                         }
  65                 }
  66         }
  67         else
  68         {
  69                 for (; n < 0; n++)
  70                 {
  71                         if (c <= lb)
  72                                 return -1;
  73                         b = p[--c];
  74                         if (b >= 0x80)
  75                         {                                       /* 1000 0000 */
  76                                 while (c > lb)
  77                                 {
  78                                         b = p[c];
  79                                         if (b >= 0xC0)
  80                                                 break;  /* 1100 0000 */
  81                                         c--;
  82                                 }
  83                         }
  84                 }
  85         }
  86         return c;
  87 }
  88
  89 /* Code for character groupings: utf8 cases */
  90
  91 static int
  92 get_utf8(const symbol * p, int c, int l, int *slot)
  93 {
  94         int                     b0,
  95                                 b1;
  96
  97         if (c >= l)
  98                 return 0;
  99         b0 = p[c++];
 100         if (b0 < 0xC0 || c == l)
 101         {                                                       /* 1100 0000 */
 102                 *slot = b0;
 103                 return 1;
 104         }
 105         b1 = p[c++];
 106         if (b0 < 0xE0 || c == l)
 107         {                                                       /* 1110 0000 */
 108                 *slot = (b0 & 0x1F) << 6 | (b1 & 0x3F);
 109                 return 2;
 110         }
 111         *slot = (b0 & 0xF) << 12 | (b1 & 0x3F) << 6 | (*p & 0x3F);
 112         return 3;
 113 }
 114
 115 static int
 116 get_b_utf8(const symbol * p, int c, int lb, int *slot)
 117 {
 118         int                     b0,
 119                                 b1;
 120
 121         if (c <= lb)
 122                 return 0;
 123         b0 = p[--c];
 124         if (b0 < 0x80 || c == lb)
 125         {                                                       /* 1000 0000 */
 126                 *slot = b0;
 127                 return 1;
 128         }
 129         b1 = p[--c];
 130         if (b1 >= 0xC0 || c == lb)
 131         {                                                       /* 1100 0000 */
 132                 *slot = (b1 & 0x1F) << 6 | (b0 & 0x3F);
 133                 return 2;
 134         }
 135         *slot = (*p & 0xF) << 12 | (b1 & 0x3F) << 6 | (b0 & 0x3F);
 136         return 3;
 137 }
 138
 139 extern int
 140 in_grouping_U(struct SN_env * z, unsigned char *s, int min, int max)
 141 {
 142         int                     ch;
 143         int                     w = get_utf8(z->p, z->c, z->l, &ch);
 144
 145         unless(w) return 0;
 146         if (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 147                 return 0;
 148         z->c += w;
 149         return 1;
 150 }
 151
 152 extern int
 153 in_grouping_b_U(struct SN_env * z, unsigned char *s, int min, int max)
 154 {
 155         int                     ch;
 156         int                     w = get_b_utf8(z->p, z->c, z->lb, &ch);
 157
 158         unless(w) return 0;
 159         if (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 160                 return 0;
 161         z->c -= w;
 162         return 1;
 163 }
 164
 165 extern int
 166 out_grouping_U(struct SN_env * z, unsigned char *s, int min, int max)
 167 {
 168         int                     ch;
 169         int                     w = get_utf8(z->p, z->c, z->l, &ch);
 170
 171         unless(w) return 0;
 172         unless(ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0) return 0;
 173         z->c += w;
 174         return 1;
 175 }
 176
 177 extern int
 178 out_grouping_b_U(struct SN_env * z, unsigned char *s, int min, int max)
 179 {
 180         int                     ch;
 181         int                     w = get_b_utf8(z->p, z->c, z->lb, &ch);
 182
 183         unless(w) return 0;
 184         unless(ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0) return 0;
 185         z->c -= w;
 186         return 1;
 187 }
 188
 189 /* Code for character groupings: non-utf8 cases */
 190
 191 extern int
 192 in_grouping(struct SN_env * z, unsigned char *s, int min, int max)
 193 {
 194         int                     ch;
 195
 196         if (z->c >= z->l)
 197                 return 0;
 198         ch = z->p[z->c];
 199         if (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 200                 return 0;
 201         z->c++;
 202         return 1;
 203 }
 204
 205 extern int
 206 in_grouping_b(struct SN_env * z, unsigned char *s, int min, int max)
 207 {
 208         int                     ch;
 209
 210         if (z->c <= z->lb)
 211                 return 0;
 212         ch = z->p[z->c - 1];
 213         if (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 214                 return 0;
 215         z->c--;
 216         return 1;
 217 }
 218
 219 extern int
 220 out_grouping(struct SN_env * z, unsigned char *s, int min, int max)
 221 {
 222         int                     ch;
 223
 224         if (z->c >= z->l)
 225                 return 0;
 226         ch = z->p[z->c];
 227         unless(ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0) return 0;
 228         z->c++;
 229         return 1;
 230 }
 231
 232 extern int
 233 out_grouping_b(struct SN_env * z, unsigned char *s, int min, int max)
 234 {
 235         int                     ch;
 236
 237         if (z->c <= z->lb)
 238                 return 0;
 239         ch = z->p[z->c - 1];
 240         unless(ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0) return 0;
 241         z->c--;
 242         return 1;
 243 }
 244
 245 extern int
 246 eq_s(struct SN_env * z, int s_size, symbol * s)
 247 {
 248         if (z->l - z->c < s_size || memcmp(z->p + z->c, s, s_size * sizeof(symbol)) != 0)
 249                 return 0;
 250         z->c += s_size;
 251         return 1;
 252 }
 253
 254 extern int
 255 eq_s_b(struct SN_env * z, int s_size, symbol * s)
 256 {
 257         if (z->c - z->lb < s_size || memcmp(z->p + z->c - s_size, s, s_size * sizeof(symbol)) != 0)
 258                 return 0;
 259         z->c -= s_size;
 260         return 1;
 261 }
 262
 263 extern int
 264 eq_v(struct SN_env * z, symbol * p)
 265 {
 266         return eq_s(z, SIZE(p), p);
 267 }
 268
 269 extern int
 270 eq_v_b(struct SN_env * z, symbol * p)
 271 {
 272         return eq_s_b(z, SIZE(p), p);
 273 }
 274
 275 extern int
 276 find_among(struct SN_env * z, struct among * v, int v_size)
 277 {
 278
 279         int                     i = 0;
 280         int                     j = v_size;
 281
 282         int                     c = z->c;
 283         int                     l = z->l;
 284         symbol     *q = z->p + c;
 285
 286         struct among *w;
 287
 288         int                     common_i = 0;
 289         int                     common_j = 0;
 290
 291         int                     first_key_inspected = 0;
 292
 293         while (1)
 294         {
 295                 int                     k = i + ((j - i) >> 1);
 296                 int                     diff = 0;
 297                 int                     common = common_i < common_j ? common_i : common_j; /* smaller */
 298
 299                 w = v + k;
 300                 {
 301                         int                     i;
 302
 303                         for (i = common; i < w->s_size; i++)
 304                         {
 305                                 if (c + common == l)
 306                                 {
 307                                         diff = -1;
 308                                         break;
 309                                 }
 310                                 diff = q[common] - w->s[i];
 311                                 if (diff != 0)
 312                                         break;
 313                                 common++;
 314                         }
 315                 }
 316                 if (diff < 0)
 317                 {
 318                         j = k;
 319                         common_j = common;
 320                 }
 321                 else
 322                 {
 323                         i = k;
 324                         common_i = common;
 325                 }
 326                 if (j - i <= 1)
 327                 {
 328                         if (i > 0)
 329                                 break;                  /* v->s has been inspected */
 330                         if (j == i)
 331                                 break;                  /* only one item in v */
 332
 333                         /*
 334                          * - but now we need to go round once more to get v->s inspected.
 335                          * This looks messy, but is actually the optimal approach.
 336                          */
 337
 338                         if (first_key_inspected)
 339                                 break;
 340                         first_key_inspected = 1;
 341                 }
 342         }
 343         while (1)
 344         {
 345                 w = v + i;
 346                 if (common_i >= w->s_size)
 347                 {
 348                         z->c = c + w->s_size;
 349                         if (w->function == 0)
 350                                 return w->result;
 351                         {
 352                                 int                     res = w->function(z);
 353
 354                                 z->c = c + w->s_size;
 355                                 if (res)
 356                                         return w->result;
 357                         }
 358                 }
 359                 i = w->substring_i;
 360                 if (i < 0)
 361                         return 0;
 362         }
 363 }
 364
 365 /* find_among_b is for backwards processing. Same comments apply */
 366
 367 extern int
 368 find_among_b(struct SN_env * z, struct among * v, int v_size)
 369 {
 370
 371         int                     i = 0;
 372         int                     j = v_size;
 373
 374         int                     c = z->c;
 375         int                     lb = z->lb;
 376         symbol     *q = z->p + c - 1;
 377
 378         struct among *w;
 379
 380         int                     common_i = 0;
 381         int                     common_j = 0;
 382
 383         int                     first_key_inspected = 0;
 384
 385         while (1)
 386         {
 387                 int                     k = i + ((j - i) >> 1);
 388                 int                     diff = 0;
 389                 int                     common = common_i < common_j ? common_i : common_j;
 390
 391                 w = v + k;
 392                 {
 393                         int                     i;
 394
 395                         for (i = w->s_size - 1 - common; i >= 0; i--)
 396                         {
 397                                 if (c - common == lb)
 398                                 {
 399                                         diff = -1;
 400                                         break;
 401                                 }
 402                                 diff = q[-common] - w->s[i];
 403                                 if (diff != 0)
 404                                         break;
 405                                 common++;
 406                         }
 407                 }
 408                 if (diff < 0)
 409                 {
 410                         j = k;
 411                         common_j = common;
 412                 }
 413                 else
 414                 {
 415                         i = k;
 416                         common_i = common;
 417                 }
 418                 if (j - i <= 1)
 419                 {
 420                         if (i > 0)
 421                                 break;
 422                         if (j == i)
 423                                 break;
 424                         if (first_key_inspected)
 425                                 break;
 426                         first_key_inspected = 1;
 427                 }
 428         }
 429         while (1)
 430         {
 431                 w = v + i;
 432                 if (common_i >= w->s_size)
 433                 {
 434                         z->c = c - w->s_size;
 435                         if (w->function == 0)
 436                                 return w->result;
 437                         {
 438                                 int                     res = w->function(z);
 439
 440                                 z->c = c - w->s_size;
 441                                 if (res)
 442                                         return w->result;
 443                         }
 444                 }
 445                 i = w->substring_i;
 446                 if (i < 0)
 447                         return 0;
 448         }
 449 }
 450
 451
 452 /* Increase the size of the buffer pointed to by p to at least n symbols.
 453  * If insufficient memory, returns NULL and frees the old buffer.
 454  */
 455 static symbol *
 456 increase_size(symbol * p, int n)
 457 {
 458         symbol     *q;
 459         int                     new_size = n + 20;
 460         void       *mem = realloc((char *) p - HEAD,
 461                                                           HEAD + (new_size + 1) * sizeof(symbol));
 462
 463         if (mem == NULL)
 464         {
 465                 lose_s(p);
 466                 return NULL;
 467         }
 468         q = (symbol *) (HEAD + (char *) mem);
 469         CAPACITY(q) = new_size;
 470         return q;
 471 }
 472
 473 /* to replace symbols between c_bra and c_ket in z->p by the
 474    s_size symbols at s.
 475    Returns 0 on success, -1 on error.
 476    Also, frees z->p (and sets it to NULL) on error.
 477 */
 478 extern int
 479 replace_s(struct SN_env * z, int c_bra, int c_ket, int s_size, const symbol * s, int *adjptr)
 480 {
 481         int                     adjustment;
 482         int                     len;
 483
 484         if (z->p == NULL)
 485         {
 486                 z->p = create_s();
 487                 if (z->p == NULL)
 488                         return -1;
 489         }
 490         adjustment = s_size - (c_ket - c_bra);
 491         len = SIZE(z->p);
 492         if (adjustment != 0)
 493         {
 494                 if (adjustment + len > CAPACITY(z->p))
 495                 {
 496                         z->p = increase_size(z->p, adjustment + len);
 497                         if (z->p == NULL)
 498                                 return -1;
 499                 }
 500                 memmove(z->p + c_ket + adjustment,
 501                                 z->p + c_ket,
 502                                 (len - c_ket) * sizeof(symbol));
 503                 SET_SIZE(z->p, adjustment + len);
 504                 z->l += adjustment;
 505                 if (z->c >= c_ket)
 506                         z->c += adjustment;
 507                 else if (z->c > c_bra)
 508                         z->c = c_bra;
 509         }
 510         unless(s_size == 0) memmove(z->p + c_bra, s, s_size * sizeof(symbol));
 511         if (adjptr != NULL)
 512                 *adjptr = adjustment;
 513         return 0;
 514 }
 515
 516 static int
 517 slice_check(struct SN_env * z)
 518 {
 519
 520         if (z->bra < 0 ||
 521                 z->bra > z->ket ||
 522                 z->ket > z->l ||
 523                 z->p == NULL ||
 524                 z->l > SIZE(z->p))              /* this line could be removed */
 525         {
 526 #if 0
 527                 fprintf(stderr, "faulty slice operation:\n");
 528                 debug(z, -1, 0);
 529 #endif
 530                 return -1;
 531         }
 532         return 0;
 533 }
 534
 535 extern int
 536 slice_from_s(struct SN_env * z, int s_size, symbol * s)
 537 {
 538         if (slice_check(z))
 539                 return -1;
 540         return replace_s(z, z->bra, z->ket, s_size, s, NULL);
 541 }
 542
 543 extern int
 544 slice_from_v(struct SN_env * z, symbol * p)
 545 {
 546         return slice_from_s(z, SIZE(p), p);
 547 }
 548
 549 extern int
 550 slice_del(struct SN_env * z)
 551 {
 552         return slice_from_s(z, 0, 0);
 553 }
 554
 555 extern int
 556 insert_s(struct SN_env * z, int bra, int ket, int s_size, symbol * s)
 557 {
 558         int                     adjustment;
 559
 560         if (replace_s(z, bra, ket, s_size, s, &adjustment))
 561                 return -1;
 562         if (bra <= z->bra)
 563                 z->bra += adjustment;
 564         if (bra <= z->ket)
 565                 z->ket += adjustment;
 566         return 0;
 567 }
 568
 569 extern int
 570 insert_v(struct SN_env * z, int bra, int ket, symbol * p)
 571 {
 572         int                     adjustment;
 573
 574         if (replace_s(z, bra, ket, SIZE(p), p, &adjustment))
 575                 return -1;
 576         if (bra <= z->bra)
 577                 z->bra += adjustment;
 578         if (bra <= z->ket)
 579                 z->ket += adjustment;
 580         return 0;
 581 }
 582
 583 extern symbol *
 584 slice_to(struct SN_env * z, symbol * p)
 585 {
 586         if (slice_check(z))
 587         {
 588                 lose_s(p);
 589                 return NULL;
 590         }
 591         {
 592                 int                     len = z->ket - z->bra;
 593
 594                 if (CAPACITY(p) < len)
 595                 {
 596                         p = increase_size(p, len);
 597                         if (p == NULL)
 598                                 return NULL;
 599                 }
 600                 memmove(p, z->p + z->bra, len * sizeof(symbol));
 601                 SET_SIZE(p, len);
 602         }
 603         return p;
 604 }
 605
 606 extern symbol *
 607 assign_to(struct SN_env * z, symbol * p)
 608 {
 609         int                     len = z->l;
 610
 611         if (CAPACITY(p) < len)
 612         {
 613                 p = increase_size(p, len);
 614                 if (p == NULL)
 615                         return NULL;
 616         }
 617         memmove(p, z->p, len * sizeof(symbol));
 618         SET_SIZE(p, len);
 619         return p;
 620 }
 621
 622 #if 0
 623 extern void
 624 debug(struct SN_env * z, int number, int line_count)
 625 {
 626         int                     i;
 627         int                     limit = SIZE(z->p);
 628
 629         /* if (number >= 0) printf("%3d (line %4d): '", number, line_count); */
 630         if (number >= 0)
 631                 printf("%3d (line %4d): [%d]'", number, line_count, limit);
 632         for (i = 0; i <= limit; i++)
 633         {
 634                 if (z->lb == i)
 635                         printf("{");
 636                 if (z->bra == i)
 637                         printf("[");
 638                 if (z->c == i)
 639                         printf("|");
 640                 if (z->ket == i)
 641                         printf("]");
 642                 if (z->l == i)
 643                         printf("}");
 644                 if (i < limit)
 645                 {
 646                         int                     ch = z->p[i];
 647
 648                         if (ch == 0)
 649                                 ch = '#';
 650                         printf("%c", ch);
 651                 }
 652         }
 653         printf("'\n");
 654 }
 655
 656 #endif