src/backend/snowball/libstemmer/utilities.c

   1 #include "header.h"
   2
   3 #define unless(C) if(!(C))
   4
   5 #define CREATE_SIZE 1
   6
   7 extern symbol * create_s(void) {
   8     symbol * p;
   9     void * mem = malloc(HEAD + (CREATE_SIZE + 1) * sizeof(symbol));
  10     if (mem == NULL) return NULL;
  11     p = (symbol *) (HEAD + (char *) mem);
  12     CAPACITY(p) = CREATE_SIZE;
  13     SET_SIZE(p, CREATE_SIZE);
  14     return p;
  15 }
  16
  17 extern void lose_s(symbol * p) {
  18     if (p == NULL) return;
  19     free((char *) p - HEAD);
  20 }
  21
  22 /*
  23    new_p = skip_utf8(p, c, lb, l, n); skips n characters forwards from p + c
  24    if n +ve, or n characters backwards from p + c - 1 if n -ve. new_p is the new
  25    position, or 0 on failure.
  26
  27    -- used to implement hop and next in the utf8 case.
  28 */
  29
  30 extern int skip_utf8(const symbol * p, int c, int lb, int l, int n) {
  31     int b;
  32     if (n >= 0) {
  33         for (; n > 0; n--) {
  34             if (c >= l) return -1;
  35             b = p[c++];
  36             if (b >= 0xC0) {   /* 1100 0000 */
  37                 while (c < l) {
  38                     b = p[c];
  39                     if (b >= 0xC0 || b < 0x80) break;
  40                     /* break unless b is 10------ */
  41                     c++;
  42                 }
  43             }
  44         }
  45     } else {
  46         for (; n < 0; n++) {
  47             if (c <= lb) return -1;
  48             b = p[--c];
  49             if (b >= 0x80) {   /* 1000 0000 */
  50                 while (c > lb) {
  51                     b = p[c];
  52                     if (b >= 0xC0) break; /* 1100 0000 */
  53                     c--;
  54                 }
  55             }
  56         }
  57     }
  58     return c;
  59 }
  60
  61 /* Code for character groupings: utf8 cases */
  62
  63 static int get_utf8(const symbol * p, int c, int l, int * slot) {
  64     int b0, b1;
  65     if (c >= l) return 0;
  66     b0 = p[c++];
  67     if (b0 < 0xC0 || c == l) {   /* 1100 0000 */
  68         * slot = b0; return 1;
  69     }
  70     b1 = p[c++];
  71     if (b0 < 0xE0 || c == l) {   /* 1110 0000 */
  72         * slot = (b0 & 0x1F) << 6 | (b1 & 0x3F); return 2;
  73     }
  74     * slot = (b0 & 0xF) << 12 | (b1 & 0x3F) << 6 | (p[c] & 0x3F); return 3;
  75 }
  76
  77 static int get_b_utf8(const symbol * p, int c, int lb, int * slot) {
  78     int b0, b1;
  79     if (c <= lb) return 0;
  80     b0 = p[--c];
  81     if (b0 < 0x80 || c == lb) {   /* 1000 0000 */
  82         * slot = b0; return 1;
  83     }
  84     b1 = p[--c];
  85     if (b1 >= 0xC0 || c == lb) {   /* 1100 0000 */
  86         * slot = (b1 & 0x1F) << 6 | (b0 & 0x3F); return 2;
  87     }
  88     * slot = (p[c] & 0xF) << 12 | (b1 & 0x3F) << 6 | (b0 & 0x3F); return 3;
  89 }
  90
  91 extern int in_grouping_U(struct SN_env * z, const unsigned char * s, int min, int max, int repeat) {
  92     do {
  93         int ch;
  94         int w = get_utf8(z->p, z->c, z->l, & ch);
  95         unless (w) return -1;
  96         if (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
  97             return w;
  98         z->c += w;
  99     } while (repeat);
 100     return 0;
 101 }
 102
 103 extern int in_grouping_b_U(struct SN_env * z, const unsigned char * s, int min, int max, int repeat) {
 104     do {
 105         int ch;
 106         int w = get_b_utf8(z->p, z->c, z->lb, & ch);
 107         unless (w) return -1;
 108         if (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 109             return w;
 110         z->c -= w;
 111     } while (repeat);
 112     return 0;
 113 }
 114
 115 extern int out_grouping_U(struct SN_env * z, const unsigned char * s, int min, int max, int repeat) {
 116     do {
 117         int ch;
 118         int w = get_utf8(z->p, z->c, z->l, & ch);
 119         unless (w) return -1;
 120         unless (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 121             return w;
 122         z->c += w;
 123     } while (repeat);
 124     return 0;
 125 }
 126
 127 extern int out_grouping_b_U(struct SN_env * z, const unsigned char * s, int min, int max, int repeat) {
 128     do {
 129         int ch;
 130         int w = get_b_utf8(z->p, z->c, z->lb, & ch);
 131         unless (w) return -1;
 132         unless (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 133             return w;
 134         z->c -= w;
 135     } while (repeat);
 136     return 0;
 137 }
 138
 139 /* Code for character groupings: non-utf8 cases */
 140
 141 extern int in_grouping(struct SN_env * z, const unsigned char * s, int min, int max, int repeat) {
 142     do {
 143         int ch;
 144         if (z->c >= z->l) return -1;
 145         ch = z->p[z->c];
 146         if (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 147             return 1;
 148         z->c++;
 149     } while (repeat);
 150     return 0;
 151 }
 152
 153 extern int in_grouping_b(struct SN_env * z, const unsigned char * s, int min, int max, int repeat) {
 154     do {
 155         int ch;
 156         if (z->c <= z->lb) return -1;
 157         ch = z->p[z->c - 1];
 158         if (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 159             return 1;
 160         z->c--;
 161     } while (repeat);
 162     return 0;
 163 }
 164
 165 extern int out_grouping(struct SN_env * z, const unsigned char * s, int min, int max, int repeat) {
 166     do {
 167         int ch;
 168         if (z->c >= z->l) return -1;
 169         ch = z->p[z->c];
 170         unless (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 171             return 1;
 172         z->c++;
 173     } while (repeat);
 174     return 0;
 175 }
 176
 177 extern int out_grouping_b(struct SN_env * z, const unsigned char * s, int min, int max, int repeat) {
 178     do {
 179         int ch;
 180         if (z->c <= z->lb) return -1;
 181         ch = z->p[z->c - 1];
 182         unless (ch > max || (ch -= min) < 0 || (s[ch >> 3] & (0X1 << (ch & 0X7))) == 0)
 183             return 1;
 184         z->c--;
 185     } while (repeat);
 186     return 0;
 187 }
 188
 189 extern int eq_s(struct SN_env * z, int s_size, const symbol * s) {
 190     if (z->l - z->c < s_size || memcmp(z->p + z->c, s, s_size * sizeof(symbol)) != 0) return 0;
 191     z->c += s_size; return 1;
 192 }
 193
 194 extern int eq_s_b(struct SN_env * z, int s_size, const symbol * s) {
 195     if (z->c - z->lb < s_size || memcmp(z->p + z->c - s_size, s, s_size * sizeof(symbol)) != 0) return 0;
 196     z->c -= s_size; return 1;
 197 }
 198
 199 extern int eq_v(struct SN_env * z, const symbol * p) {
 200     return eq_s(z, SIZE(p), p);
 201 }
 202
 203 extern int eq_v_b(struct SN_env * z, const symbol * p) {
 204     return eq_s_b(z, SIZE(p), p);
 205 }
 206
 207 extern int find_among(struct SN_env * z, const struct among * v, int v_size) {
 208
 209     int i = 0;
 210     int j = v_size;
 211
 212     int c = z->c; int l = z->l;
 213     symbol * q = z->p + c;
 214
 215     const struct among * w;
 216
 217     int common_i = 0;
 218     int common_j = 0;
 219
 220     int first_key_inspected = 0;
 221
 222     while(1) {
 223         int k = i + ((j - i) >> 1);
 224         int diff = 0;
 225         int common = common_i < common_j ? common_i : common_j; /* smaller */
 226         w = v + k;
 227         {
 228             int i2; for (i2 = common; i2 < w->s_size; i2++) {
 229                 if (c + common == l) { diff = -1; break; }
 230                 diff = q[common] - w->s[i2];
 231                 if (diff != 0) break;
 232                 common++;
 233             }
 234         }
 235         if (diff < 0) { j = k; common_j = common; }
 236                  else { i = k; common_i = common; }
 237         if (j - i <= 1) {
 238             if (i > 0) break; /* v->s has been inspected */
 239             if (j == i) break; /* only one item in v */
 240
 241             /* - but now we need to go round once more to get
 242                v->s inspected. This looks messy, but is actually
 243                the optimal approach.  */
 244
 245             if (first_key_inspected) break;
 246             first_key_inspected = 1;
 247         }
 248     }
 249     while(1) {
 250         w = v + i;
 251         if (common_i >= w->s_size) {
 252             z->c = c + w->s_size;
 253             if (w->function == 0) return w->result;
 254             {
 255                 int res = w->function(z);
 256                 z->c = c + w->s_size;
 257                 if (res) return w->result;
 258             }
 259         }
 260         i = w->substring_i;
 261         if (i < 0) return 0;
 262     }
 263 }
 264
 265 /* find_among_b is for backwards processing. Same comments apply */
 266
 267 extern int find_among_b(struct SN_env * z, const struct among * v, int v_size) {
 268
 269     int i = 0;
 270     int j = v_size;
 271
 272     int c = z->c; int lb = z->lb;
 273     symbol * q = z->p + c - 1;
 274
 275     const struct among * w;
 276
 277     int common_i = 0;
 278     int common_j = 0;
 279
 280     int first_key_inspected = 0;
 281
 282     while(1) {
 283         int k = i + ((j - i) >> 1);
 284         int diff = 0;
 285         int common = common_i < common_j ? common_i : common_j;
 286         w = v + k;
 287         {
 288             int i2; for (i2 = w->s_size - 1 - common; i2 >= 0; i2--) {
 289                 if (c - common == lb) { diff = -1; break; }
 290                 diff = q[- common] - w->s[i2];
 291                 if (diff != 0) break;
 292                 common++;
 293             }
 294         }
 295         if (diff < 0) { j = k; common_j = common; }
 296                  else { i = k; common_i = common; }
 297         if (j - i <= 1) {
 298             if (i > 0) break;
 299             if (j == i) break;
 300             if (first_key_inspected) break;
 301             first_key_inspected = 1;
 302         }
 303     }
 304     while(1) {
 305         w = v + i;
 306         if (common_i >= w->s_size) {
 307             z->c = c - w->s_size;
 308             if (w->function == 0) return w->result;
 309             {
 310                 int res = w->function(z);
 311                 z->c = c - w->s_size;
 312                 if (res) return w->result;
 313             }
 314         }
 315         i = w->substring_i;
 316         if (i < 0) return 0;
 317     }
 318 }
 319
 320
 321 /* Increase the size of the buffer pointed to by p to at least n symbols.
 322  * If insufficient memory, returns NULL and frees the old buffer.
 323  */
 324 static symbol * increase_size(symbol * p, int n) {
 325     symbol * q;
 326     int new_size = n + 20;
 327     void * mem = realloc((char *) p - HEAD,
 328                          HEAD + (new_size + 1) * sizeof(symbol));
 329     if (mem == NULL) {
 330         lose_s(p);
 331         return NULL;
 332     }
 333     q = (symbol *) (HEAD + (char *)mem);
 334     CAPACITY(q) = new_size;
 335     return q;
 336 }
 337
 338 /* to replace symbols between c_bra and c_ket in z->p by the
 339    s_size symbols at s.
 340    Returns 0 on success, -1 on error.
 341    Also, frees z->p (and sets it to NULL) on error.
 342 */
 343 extern int replace_s(struct SN_env * z, int c_bra, int c_ket, int s_size, const symbol * s, int * adjptr)
 344 {
 345     int adjustment;
 346     int len;
 347     if (z->p == NULL) {
 348         z->p = create_s();
 349         if (z->p == NULL) return -1;
 350     }
 351     adjustment = s_size - (c_ket - c_bra);
 352     len = SIZE(z->p);
 353     if (adjustment != 0) {
 354         if (adjustment + len > CAPACITY(z->p)) {
 355             z->p = increase_size(z->p, adjustment + len);
 356             if (z->p == NULL) return -1;
 357         }
 358         memmove(z->p + c_ket + adjustment,
 359                 z->p + c_ket,
 360                 (len - c_ket) * sizeof(symbol));
 361         SET_SIZE(z->p, adjustment + len);
 362         z->l += adjustment;
 363         if (z->c >= c_ket)
 364             z->c += adjustment;
 365         else
 366             if (z->c > c_bra)
 367                 z->c = c_bra;
 368     }
 369     unless (s_size == 0) memmove(z->p + c_bra, s, s_size * sizeof(symbol));
 370     if (adjptr != NULL)
 371         *adjptr = adjustment;
 372     return 0;
 373 }
 374
 375 static int slice_check(struct SN_env * z) {
 376
 377     if (z->bra < 0 ||
 378         z->bra > z->ket ||
 379         z->ket > z->l ||
 380         z->p == NULL ||
 381         z->l > SIZE(z->p)) /* this line could be removed */
 382     {
 383 #if 0
 384         fprintf(stderr, "faulty slice operation:\n");
 385         debug(z, -1, 0);
 386 #endif
 387         return -1;
 388     }
 389     return 0;
 390 }
 391
 392 extern int slice_from_s(struct SN_env * z, int s_size, const symbol * s) {
 393     if (slice_check(z)) return -1;
 394     return replace_s(z, z->bra, z->ket, s_size, s, NULL);
 395 }
 396
 397 extern int slice_from_v(struct SN_env * z, const symbol * p) {
 398     return slice_from_s(z, SIZE(p), p);
 399 }
 400
 401 extern int slice_del(struct SN_env * z) {
 402     return slice_from_s(z, 0, 0);
 403 }
 404
 405 extern int insert_s(struct SN_env * z, int bra, int ket, int s_size, const symbol * s) {
 406     int adjustment;
 407     if (replace_s(z, bra, ket, s_size, s, &adjustment))
 408         return -1;
 409     if (bra <= z->bra) z->bra += adjustment;
 410     if (bra <= z->ket) z->ket += adjustment;
 411     return 0;
 412 }
 413
 414 extern int insert_v(struct SN_env * z, int bra, int ket, const symbol * p) {
 415     int adjustment;
 416     if (replace_s(z, bra, ket, SIZE(p), p, &adjustment))
 417         return -1;
 418     if (bra <= z->bra) z->bra += adjustment;
 419     if (bra <= z->ket) z->ket += adjustment;
 420     return 0;
 421 }
 422
 423 extern symbol * slice_to(struct SN_env * z, symbol * p) {
 424     if (slice_check(z)) {
 425         lose_s(p);
 426         return NULL;
 427     }
 428     {
 429         int len = z->ket - z->bra;
 430         if (CAPACITY(p) < len) {
 431             p = increase_size(p, len);
 432             if (p == NULL)
 433                 return NULL;
 434         }
 435         memmove(p, z->p + z->bra, len * sizeof(symbol));
 436         SET_SIZE(p, len);
 437     }
 438     return p;
 439 }
 440
 441 extern symbol * assign_to(struct SN_env * z, symbol * p) {
 442     int len = z->l;
 443     if (CAPACITY(p) < len) {
 444         p = increase_size(p, len);
 445         if (p == NULL)
 446             return NULL;
 447     }
 448     memmove(p, z->p, len * sizeof(symbol));
 449     SET_SIZE(p, len);
 450     return p;
 451 }
 452
 453 #if 0
 454 extern void debug(struct SN_env * z, int number, int line_count) {
 455     int i;
 456     int limit = SIZE(z->p);
 457     /*if (number >= 0) printf("%3d (line %4d): '", number, line_count);*/
 458     if (number >= 0) printf("%3d (line %4d): [%d]'", number, line_count,limit);
 459     for (i = 0; i <= limit; i++) {
 460         if (z->lb == i) printf("{");
 461         if (z->bra == i) printf("[");
 462         if (z->c == i) printf("|");
 463         if (z->ket == i) printf("]");
 464         if (z->l == i) printf("}");
 465         if (i < limit)
 466         {   int ch = z->p[i];
 467             if (ch == 0) ch = '#';
 468             printf("%c", ch);
 469         }
 470     }
 471     printf("'\n");
 472 }
 473 #endif