datrie/alpha-map.c

   1 /* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * libdatrie - Double-Array Trie Library
   4  * Copyright (C) 2006  Theppitak Karoonboonyanan <theppitak@gmail.com>
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  */
  20
  21 /*
  22  * alpha-map.c - map between character codes and trie alphabet
  23  * Created: 2006-08-19
  24  * Author:  Theppitak Karoonboonyanan <theppitak@gmail.com>
  25  */
  26
  27 #include <ctype.h>
  28 #include <string.h>
  29 #include <stdlib.h>
  30 #include <stdio.h>
  31 #include <assert.h>
  32
  33 #include "alpha-map.h"
  34 #include "alpha-map-private.h"
  35 #include "trie-private.h"
  36 #include "fileutils.h"
  37
  38 /**
  39  * @brief Alphabet string length
  40  *
  41  * @param str   : the array of null-terminated AlphaChar string to measure
  42  *
  43  * @return the total characters in @a str.
  44  */
  45 int
  46 alpha_char_strlen (const AlphaChar *str)
  47 {
  48     const AlphaChar *p;
  49
  50     for (p = str; *p; p++)
  51         ;
  52     return p - str;
  53 }
  54
  55 /**
  56  * @brief Compare alphabet strings
  57  *
  58  * @param str1, str2  : the arrays of null-terminated AlphaChar strings
  59  *                      to compare
  60  *
  61  * @return negative if @a str1 < @a str2;
  62  *         0 if @a str1 == @a str2;
  63  *         positive if @a str1 > @a str2
  64  *
  65  * Available since: 0.2.7
  66  */
  67 int
  68 alpha_char_strcmp (const AlphaChar *str1, const AlphaChar *str2)
  69 {
  70     while (*str1 && *str1 == *str2) {
  71         str1++; str2++;
  72     }
  73     if (*str1 < *str2)
  74         return -1;
  75     if (*str1 > *str2)
  76         return 1;
  77     return 0;
  78 }
  79
  80 /*------------------------------*
  81  *    PRIVATE DATA DEFINITONS   *
  82  *------------------------------*/
  83
  84 typedef struct _AlphaRange {
  85     struct _AlphaRange *next;
  86
  87     AlphaChar           begin;
  88     AlphaChar           end;
  89 } AlphaRange;
  90
  91 struct _AlphaMap {
  92     AlphaRange     *first_range;
  93
  94     /* work area */
  95     /* alpha-to-trie map */
  96     AlphaChar  alpha_begin;
  97     AlphaChar  alpha_end;
  98     int        alpha_map_sz;
  99     TrieIndex *alpha_to_trie_map;
 100
 101     /* trie-to-alpha map */
 102     int        trie_map_sz;
 103     AlphaChar *trie_to_alpha_map;
 104 };
 105
 106 /*-----------------------------------*
 107  *    PRIVATE METHODS DECLARATIONS   *
 108  *-----------------------------------*/
 109 static int  alpha_map_get_total_ranges (const AlphaMap *alpha_map);
 110 static int  alpha_map_add_range_only (AlphaMap *alpha_map,
 111                                       AlphaChar begin, AlphaChar end);
 112 static int  alpha_map_recalc_work_area (AlphaMap *alpha_map);
 113
 114 /*-----------------------------*
 115  *    METHODS IMPLEMENTAIONS   *
 116  *-----------------------------*/
 117
 118 #define ALPHAMAP_SIGNATURE  0xD9FCD9FC
 119
 120 /* AlphaMap Header:
 121  * - INT32: signature
 122  * - INT32: total ranges
 123  *
 124  * Ranges:
 125  * - INT32: range begin
 126  * - INT32: range end
 127  */
 128
 129 /**
 130  * @brief Create new alphabet map
 131  *
 132  * @return a pointer to the newly created alphabet map, NULL on failure
 133  *
 134  * Create a new empty alphabet map. The map contents can then be added with
 135  * alpha_map_add_range().
 136  *
 137  *  The created object must be freed with alpha_map_free().
 138  */
 139 AlphaMap *
 140 alpha_map_new ()
 141 {
 142     AlphaMap   *alpha_map;
 143
 144     alpha_map = (AlphaMap *) malloc (sizeof (AlphaMap));
 145     if (UNLIKELY (!alpha_map))
 146         return NULL;
 147
 148     alpha_map->first_range = NULL;
 149
 150     /* work area */
 151     alpha_map->alpha_begin = 0;
 152     alpha_map->alpha_end = 0;
 153     alpha_map->alpha_map_sz = 0;
 154     alpha_map->alpha_to_trie_map = NULL;
 155
 156     alpha_map->trie_map_sz = 0;
 157     alpha_map->trie_to_alpha_map = NULL;
 158
 159     return alpha_map;
 160 }
 161
 162 /**
 163  * @brief Create a clone of alphabet map
 164  *
 165  * @param a_map : the source alphabet map to clone
 166  *
 167  * @return a pointer to the alphabet map clone, NULL on failure
 168  *
 169  *  The created object must be freed with alpha_map_free().
 170  */
 171 AlphaMap *
 172 alpha_map_clone (const AlphaMap *a_map)
 173 {
 174     AlphaMap   *alpha_map;
 175     AlphaRange *range;
 176
 177     alpha_map = alpha_map_new ();
 178     if (UNLIKELY (!alpha_map))
 179         return NULL;
 180
 181     for (range = a_map->first_range; range; range = range->next) {
 182         if (alpha_map_add_range_only (alpha_map, range->begin, range->end) != 0)
 183             goto exit_map_created;
 184     }
 185
 186     if (alpha_map_recalc_work_area (alpha_map) != 0)
 187         goto exit_map_created;
 188
 189     return alpha_map;
 190
 191 exit_map_created:
 192     alpha_map_free (alpha_map);
 193     return NULL;
 194 }
 195
 196 /**
 197  * @brief Free an alphabet map object
 198  *
 199  * @param alpha_map : the alphabet map object to free
 200  *
 201  * Destruct the @a alpha_map and free its allocated memory.
 202  */
 203 void
 204 alpha_map_free (AlphaMap *alpha_map)
 205 {
 206     AlphaRange *p, *q;
 207
 208     p = alpha_map->first_range;
 209     while (p) {
 210         q = p->next;
 211         free (p);
 212         p = q;
 213     }
 214
 215     /* work area */
 216     if (alpha_map->alpha_to_trie_map)
 217         free (alpha_map->alpha_to_trie_map);
 218     if (alpha_map->trie_to_alpha_map)
 219         free (alpha_map->trie_to_alpha_map);
 220
 221     free (alpha_map);
 222 }
 223
 224 AlphaMap *
 225 alpha_map_fread_bin (FILE *file)
 226 {
 227     long        save_pos;
 228     uint32      sig;
 229     int32       total, i;
 230     AlphaMap   *alpha_map;
 231
 232     /* check signature */
 233     save_pos = ftell (file);
 234     if (!file_read_int32 (file, (int32 *) &sig) || ALPHAMAP_SIGNATURE != sig)
 235         goto exit_file_read;
 236
 237     alpha_map = alpha_map_new ();
 238     if (UNLIKELY (!alpha_map))
 239         goto exit_file_read;
 240
 241     /* read number of ranges */
 242     if (!file_read_int32 (file, &total))
 243         goto exit_map_created;
 244
 245     /* read character ranges */
 246     for (i = 0; i < total; i++) {
 247         int32   b, e;
 248
 249         if (!file_read_int32 (file, &b) || !file_read_int32 (file, &e))
 250             goto exit_map_created;
 251         alpha_map_add_range_only (alpha_map, b, e);
 252     }
 253
 254     /* work area */
 255     if (UNLIKELY (alpha_map_recalc_work_area (alpha_map) != 0))
 256         goto exit_map_created;
 257
 258     return alpha_map;
 259
 260 exit_map_created:
 261     alpha_map_free (alpha_map);
 262 exit_file_read:
 263     fseek (file, save_pos, SEEK_SET);
 264     return NULL;
 265 }
 266
 267 static int
 268 alpha_map_get_total_ranges (const AlphaMap *alpha_map)
 269 {
 270     int         n;
 271     AlphaRange *range;
 272
 273     for (n = 0, range = alpha_map->first_range; range; range = range->next) {
 274         ++n;
 275     }
 276
 277     return n;
 278 }
 279
 280 int
 281 alpha_map_fwrite_bin (const AlphaMap *alpha_map, FILE *file)
 282 {
 283     AlphaRange *range;
 284
 285     if (!file_write_int32 (file, ALPHAMAP_SIGNATURE) ||
 286         !file_write_int32 (file, alpha_map_get_total_ranges (alpha_map)))
 287     {
 288         return -1;
 289     }
 290
 291     for (range = alpha_map->first_range; range; range = range->next) {
 292         if (!file_write_int32 (file, range->begin) ||
 293             !file_write_int32 (file, range->end))
 294         {
 295             return -1;
 296         }
 297     }
 298
 299     return 0;
 300 }
 301
 302 static int
 303 alpha_map_add_range_only (AlphaMap *alpha_map, AlphaChar begin, AlphaChar end)
 304 {
 305     AlphaRange *q, *r, *begin_node, *end_node;
 306
 307     if (begin > end)
 308         return -1;
 309
 310     begin_node = end_node = 0;
 311
 312     /* Skip first ranges till 'begin' is covered */
 313     for (q = 0, r = alpha_map->first_range;
 314          r && r->begin <= begin;
 315          q = r, r = r->next)
 316     {
 317         if (begin <= r->end) {
 318             /* 'r' covers 'begin' -> take 'r' as beginning point */
 319             begin_node = r;
 320             break;
 321         }
 322         if (r->end + 1 == begin) {
 323             /* 'begin' is next to 'r'-end
 324              * -> extend 'r'-end to cover 'begin'
 325              */
 326             r->end = begin;
 327             begin_node = r;
 328             break;
 329         }
 330     }
 331     if (!begin_node && r && r->begin <= end + 1) {
 332         /* ['begin', 'end'] overlaps into 'r'-begin
 333          * or 'r' is next to 'end' if r->begin == end + 1
 334          * -> extend 'r'-begin to include the range
 335          */
 336         r->begin = begin;
 337         begin_node = r;
 338     }
 339     /* Run upto the first range that exceeds 'end' */
 340     while (r && r->begin <= end + 1) {
 341         if (end <= r->end) {
 342             /* 'r' covers 'end' -> take 'r' as ending point */
 343             end_node = r;
 344         } else if (r != begin_node) {
 345             /* ['begin', 'end'] covers the whole 'r' -> remove 'r' */
 346             if (q) {
 347                 q->next = r->next;
 348                 free (r);
 349                 r = q->next;
 350             } else {
 351                 alpha_map->first_range = r->next;
 352                 free (r);
 353                 r = alpha_map->first_range;
 354             }
 355             continue;
 356         }
 357         q = r;
 358         r = r->next;
 359     }
 360     if (!end_node && q && begin <= q->end) {
 361         /* ['begin', 'end'] overlaps 'q' at the end
 362          * -> extend 'q'-end to include the range
 363          */
 364         q->end = end;
 365         end_node = q;
 366     }
 367
 368     if (begin_node && end_node) {
 369         if (begin_node != end_node) {
 370             /* Merge begin_node and end_node ranges together */
 371             assert (begin_node->next == end_node);
 372             begin_node->end = end_node->end;
 373             begin_node->next = end_node->next;
 374             free (end_node);
 375         }
 376     } else if (!begin_node && !end_node) {
 377         /* ['begin', 'end'] overlaps with none of the ranges
 378          * -> insert a new range
 379          */
 380         AlphaRange *range = (AlphaRange *) malloc (sizeof (AlphaRange));
 381
 382         if (UNLIKELY (!range))
 383             return -1;
 384
 385         range->begin = begin;
 386         range->end   = end;
 387
 388         /* insert it between 'q' and 'r' */
 389         if (q) {
 390             q->next = range;
 391         } else {
 392             alpha_map->first_range = range;
 393         }
 394         range->next = r;
 395     }
 396
 397     return 0;
 398 }
 399
 400 static int
 401 alpha_map_recalc_work_area (AlphaMap *alpha_map)
 402 {
 403     AlphaRange *range;
 404
 405     /* free old existing map */
 406     if (alpha_map->alpha_to_trie_map) {
 407         free (alpha_map->alpha_to_trie_map);
 408         alpha_map->alpha_to_trie_map = NULL;
 409     }
 410     if (alpha_map->trie_to_alpha_map) {
 411         free (alpha_map->trie_to_alpha_map);
 412         alpha_map->trie_to_alpha_map = NULL;
 413     }
 414
 415     range = alpha_map->first_range;
 416     if (range) {
 417         const AlphaChar alpha_begin = range->begin;
 418         int       n_cells, i;
 419         AlphaChar a;
 420         TrieIndex trie_last = 0;
 421         TrieChar  tc;
 422
 423         /* reconstruct alpha-to-trie map */
 424         alpha_map->alpha_begin = alpha_begin;
 425         while (range->next) {
 426             range = range->next;
 427         }
 428         alpha_map->alpha_end = range->end;
 429         alpha_map->alpha_map_sz = n_cells = range->end - alpha_begin + 1;
 430         alpha_map->alpha_to_trie_map
 431             = (TrieIndex *) malloc (n_cells * sizeof (TrieIndex));
 432         if (UNLIKELY (!alpha_map->alpha_to_trie_map))
 433             goto error_alpha_map_not_created;
 434         for (i = 0; i < n_cells; i++) {
 435             alpha_map->alpha_to_trie_map[i] = TRIE_INDEX_MAX;
 436         }
 437         for (range = alpha_map->first_range; range; range = range->next) {
 438             for (a = range->begin; a <= range->end; a++) {
 439                 alpha_map->alpha_to_trie_map[a - alpha_begin] = ++trie_last;
 440             }
 441         }
 442
 443         /* reconstruct trie-to-alpha map */
 444         alpha_map->trie_map_sz = n_cells = trie_last + 1;
 445         alpha_map->trie_to_alpha_map
 446             = (AlphaChar *) malloc (n_cells * sizeof (AlphaChar));
 447         if (UNLIKELY (!alpha_map->trie_to_alpha_map))
 448             goto error_alpha_map_created;
 449         alpha_map->trie_to_alpha_map[0] = 0;
 450         tc = 1;
 451         for (range = alpha_map->first_range; range; range = range->next) {
 452             for (a = range->begin; a <= range->end; a++) {
 453                 alpha_map->trie_to_alpha_map[tc++] = a;
 454             }
 455         }
 456     }
 457
 458     return 0;
 459
 460 error_alpha_map_created:
 461     free (alpha_map->alpha_to_trie_map);
 462     alpha_map->alpha_to_trie_map = NULL;
 463 error_alpha_map_not_created:
 464     return -1;
 465 }
 466
 467 /**
 468  * @brief Add a range to alphabet map
 469  *
 470  * @param alpha_map : the alphabet map object
 471  * @param begin     : the first character of the range
 472  * @param end       : the last character of the range
 473  *
 474  * @return 0 on success, non-zero on failure
 475  *
 476  * Add a range of character codes from @a begin to @a end to the
 477  * alphabet set.
 478  */
 479 int
 480 alpha_map_add_range (AlphaMap *alpha_map, AlphaChar begin, AlphaChar end)
 481 {
 482     int res = alpha_map_add_range_only (alpha_map, begin, end);
 483     if (res != 0)
 484         return res;
 485     return alpha_map_recalc_work_area (alpha_map);
 486 }
 487
 488 TrieIndex
 489 alpha_map_char_to_trie (const AlphaMap *alpha_map, AlphaChar ac)
 490 {
 491     TrieIndex   alpha_begin;
 492
 493     if (UNLIKELY (0 == ac))
 494         return 0;
 495
 496     if (UNLIKELY (!alpha_map->alpha_to_trie_map))
 497         return TRIE_INDEX_MAX;
 498
 499     alpha_begin = alpha_map->alpha_begin;
 500     if (alpha_begin <= ac && ac <= alpha_map->alpha_end)
 501     {
 502         return alpha_map->alpha_to_trie_map[ac - alpha_begin];
 503     }
 504
 505     return TRIE_INDEX_MAX;
 506 }
 507
 508 AlphaChar
 509 alpha_map_trie_to_char (const AlphaMap *alpha_map, TrieChar tc)
 510 {
 511     if (tc < alpha_map->trie_map_sz)
 512         return alpha_map->trie_to_alpha_map[tc];
 513
 514     return ALPHA_CHAR_ERROR;
 515 }
 516
 517 TrieChar *
 518 alpha_map_char_to_trie_str (const AlphaMap *alpha_map, const AlphaChar *str)
 519 {
 520     TrieChar   *trie_str, *p;
 521
 522     trie_str = (TrieChar *) malloc (alpha_char_strlen (str) + 1);
 523     if (UNLIKELY (!trie_str))
 524         return NULL;
 525
 526     for (p = trie_str; *str; p++, str++) {
 527         TrieIndex tc = alpha_map_char_to_trie (alpha_map, *str);
 528         if (TRIE_INDEX_MAX == tc)
 529             goto error_str_allocated;
 530         *p = (TrieChar) tc;
 531     }
 532     *p = 0;
 533
 534     return trie_str;
 535
 536 error_str_allocated:
 537     free (trie_str);
 538     return NULL;
 539 }
 540
 541 AlphaChar *
 542 alpha_map_trie_to_char_str (const AlphaMap *alpha_map, const TrieChar *str)
 543 {
 544     AlphaChar  *alpha_str, *p;
 545
 546     alpha_str = (AlphaChar *) malloc ((strlen ((const char *)str) + 1)
 547                                       * sizeof (AlphaChar));
 548     if (UNLIKELY (!alpha_str))
 549         return NULL;
 550
 551     for (p = alpha_str; *str; p++, str++) {
 552         *p = (AlphaChar) alpha_map_trie_to_char (alpha_map, *str);
 553     }
 554     *p = 0;
 555
 556     return alpha_str;
 557 }
 558
 559 /*
 560 vi:ts=4:ai:expandtab
 561 */