datrie/tail.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  * tail.c - trie tail for keeping suffixes
  23  * Created: 2006-08-15
  24  * Author:  Theppitak Karoonboonyanan <theppitak@gmail.com>
  25  */
  26
  27 #include <string.h>
  28 #include <stdlib.h>
  29 #ifndef _MSC_VER /* for SIZE_MAX */
  30 # include <stdint.h>
  31 #endif
  32 #include <stdio.h>
  33
  34 #include "tail.h"
  35 #include "trie-private.h"
  36 #include "fileutils.h"
  37
  38 /*----------------------------------*
  39  *    INTERNAL TYPES DECLARATIONS   *
  40  *----------------------------------*/
  41
  42 /*-----------------------------------*
  43  *    PRIVATE METHODS DECLARATIONS   *
  44  *-----------------------------------*/
  45
  46 static TrieIndex    tail_alloc_block (Tail *t);
  47 static void         tail_free_block (Tail *t, TrieIndex block);
  48
  49 /* ==================== BEGIN IMPLEMENTATION PART ====================  */
  50
  51 /*------------------------------------*
  52  *   INTERNAL TYPES IMPLEMENTATIONS   *
  53  *------------------------------------*/
  54
  55 /*------------------------------*
  56  *    PRIVATE DATA DEFINITONS   *
  57  *------------------------------*/
  58
  59 typedef struct {
  60     TrieIndex   next_free;
  61     TrieData    data;
  62     TrieChar   *suffix;
  63 } TailBlock;
  64
  65 struct _Tail {
  66     TrieIndex   num_tails;
  67     TailBlock  *tails;
  68     TrieIndex   first_free;
  69 };
  70
  71 /*-----------------------------*
  72  *    METHODS IMPLEMENTAIONS   *
  73  *-----------------------------*/
  74
  75 #define TAIL_SIGNATURE      0xDFFCDFFC
  76 #define TAIL_START_BLOCKNO  1
  77
  78 /* Tail Header:
  79  * INT32: signature
  80  * INT32: pointer to first free slot
  81  * INT32: number of tail blocks
  82  *
  83  * Tail Blocks:
  84  * INT32: pointer to next free block (-1 for allocated blocks)
  85  * INT32: data for the key
  86  * INT16: length
  87  * BYTES[length]: suffix string (no terminating '\0')
  88  */
  89
  90 /**
  91  * @brief Create a new tail object
  92  *
  93  * Create a new empty tail object.
  94  */
  95 Tail *
  96 tail_new ()
  97 {
  98     Tail       *t;
  99
 100     t = (Tail *) malloc (sizeof (Tail));
 101     if (UNLIKELY (!t))
 102         return NULL;
 103
 104     t->first_free = 0;
 105     t->num_tails  = 0;
 106     t->tails      = NULL;
 107
 108     return t;
 109 }
 110
 111 /**
 112  * @brief Read tail data from file
 113  *
 114  * @param file : the file to read
 115  *
 116  * @return a pointer to the openned tail data, NULL on failure
 117  *
 118  * Read tail data from the opened file, starting from the current
 119  * file pointer until the end of tail data block. On return, the
 120  * file pointer is left at the position after the read block.
 121  */
 122 Tail *
 123 tail_fread (FILE *file)
 124 {
 125     long        save_pos;
 126     Tail       *t;
 127     TrieIndex   i;
 128     uint32      sig;
 129
 130     /* check signature */
 131     save_pos = ftell (file);
 132     if (!file_read_int32 (file, (int32 *) &sig) || TAIL_SIGNATURE != sig)
 133         goto exit_file_read;
 134
 135     t = (Tail *) malloc (sizeof (Tail));
 136     if (UNLIKELY (!t))
 137         goto exit_file_read;
 138
 139     if (!file_read_int32 (file, &t->first_free) ||
 140         !file_read_int32 (file, &t->num_tails))
 141     {
 142         goto exit_tail_created;
 143     }
 144     if (t->num_tails > SIZE_MAX / sizeof (TailBlock))
 145         goto exit_tail_created;
 146     t->tails = (TailBlock *) malloc (t->num_tails * sizeof (TailBlock));
 147     if (UNLIKELY (!t->tails))
 148         goto exit_tail_created;
 149     for (i = 0; i < t->num_tails; i++) {
 150         int16   length;
 151
 152         if (!file_read_int32 (file, &t->tails[i].next_free) ||
 153             !file_read_int32 (file, &t->tails[i].data) ||
 154             !file_read_int16 (file, &length))
 155         {
 156             goto exit_in_loop;
 157         }
 158
 159         t->tails[i].suffix = (TrieChar *) malloc (length + 1);
 160         if (UNLIKELY (!t->tails[i].suffix))
 161             goto exit_in_loop;
 162         if (length > 0) {
 163             if (!file_read_chars (file, (char *)t->tails[i].suffix, length)) {
 164                 free (t->tails[i].suffix);
 165                 goto exit_in_loop;
 166             }
 167         }
 168         t->tails[i].suffix[length] = '\0';
 169     }
 170
 171     return t;
 172
 173 exit_in_loop:
 174     while (i > 0) {
 175         free (t->tails[--i].suffix);
 176     }
 177     free (t->tails);
 178 exit_tail_created:
 179     free (t);
 180 exit_file_read:
 181     fseek (file, save_pos, SEEK_SET);
 182     return NULL;
 183 }
 184
 185 /**
 186  * @brief Free tail data
 187  *
 188  * @param t : the tail data
 189  *
 190  * @return 0 on success, non-zero on failure
 191  *
 192  * Free the given tail data.
 193  */
 194 void
 195 tail_free (Tail *t)
 196 {
 197     TrieIndex   i;
 198
 199     if (t->tails) {
 200         for (i = 0; i < t->num_tails; i++)
 201             if (t->tails[i].suffix)
 202                 free (t->tails[i].suffix);
 203         free (t->tails);
 204     }
 205     free (t);
 206 }
 207
 208 /**
 209  * @brief Write tail data
 210  *
 211  * @param t     : the tail data
 212  * @param file  : the file to write to
 213  *
 214  * @return 0 on success, non-zero on failure
 215  *
 216  * Write tail data to the given @a file, starting from the current file
 217  * pointer. On return, the file pointer is left after the tail data block.
 218  */
 219 int
 220 tail_fwrite (const Tail *t, FILE *file)
 221 {
 222     TrieIndex   i;
 223
 224     if (!file_write_int32 (file, TAIL_SIGNATURE) ||
 225         !file_write_int32 (file, t->first_free)  ||
 226         !file_write_int32 (file, t->num_tails))
 227     {
 228         return -1;
 229     }
 230     for (i = 0; i < t->num_tails; i++) {
 231         int16   length;
 232
 233         if (!file_write_int32 (file, t->tails[i].next_free) ||
 234             !file_write_int32 (file, t->tails[i].data))
 235         {
 236             return -1;
 237         }
 238
 239         length = t->tails[i].suffix ? strlen ((const char *)t->tails[i].suffix)
 240                                     : 0;
 241         if (!file_write_int16 (file, length))
 242             return -1;
 243         if (length > 0 &&
 244             !file_write_chars (file, (char *)t->tails[i].suffix, length))
 245         {
 246             return -1;
 247         }
 248     }
 249
 250     return 0;
 251 }
 252
 253
 254 /**
 255  * @brief Get suffix
 256  *
 257  * @param t     : the tail data
 258  * @param index : the index of the suffix
 259  *
 260  * @return pointer to the indexed suffix string.
 261  *
 262  * Get suffix from tail with given @a index. The returned string is a pointer
 263  * to internal storage, which should be accessed read-only by the caller.
 264  * No need to free() it.
 265  */
 266 const TrieChar *
 267 tail_get_suffix (const Tail *t, TrieIndex index)
 268 {
 269     index -= TAIL_START_BLOCKNO;
 270     return LIKELY (index < t->num_tails) ? t->tails[index].suffix : NULL;
 271 }
 272
 273 /**
 274  * @brief Set suffix of existing entry
 275  *
 276  * @param t      : the tail data
 277  * @param index  : the index of the suffix
 278  * @param suffix : the new suffix
 279  *
 280  * Set suffix of existing entry of given @a index in tail.
 281  */
 282 Bool
 283 tail_set_suffix (Tail *t, TrieIndex index, const TrieChar *suffix)
 284 {
 285     index -= TAIL_START_BLOCKNO;
 286     if (LIKELY (index < t->num_tails)) {
 287         /* suffix and t->tails[index].suffix may overlap;
 288          * so, dup it before it's overwritten
 289          */
 290         TrieChar *tmp = NULL;
 291         if (suffix) {
 292             tmp = (TrieChar *) strdup ((const char *)suffix);
 293             if (UNLIKELY (!tmp))
 294                 return FALSE;
 295         }
 296         if (t->tails[index].suffix)
 297             free (t->tails[index].suffix);
 298         t->tails[index].suffix = tmp;
 299
 300         return TRUE;
 301     }
 302     return FALSE;
 303 }
 304
 305 /**
 306  * @brief Add a new suffix
 307  *
 308  * @param t      : the tail data
 309  * @param suffix : the new suffix
 310  *
 311  * @return the index of the newly added suffix,
 312  *         or TRIE_INDEX_ERROR on failure.
 313  *
 314  * Add a new suffix entry to tail.
 315  */
 316 TrieIndex
 317 tail_add_suffix (Tail *t, const TrieChar *suffix)
 318 {
 319     TrieIndex   new_block;
 320
 321     new_block = tail_alloc_block (t);
 322     if (UNLIKELY (TRIE_INDEX_ERROR == new_block))
 323         return TRIE_INDEX_ERROR;
 324
 325     tail_set_suffix (t, new_block, suffix);
 326
 327     return new_block;
 328 }
 329
 330 static TrieIndex
 331 tail_alloc_block (Tail *t)
 332 {
 333     TrieIndex   block;
 334
 335     if (0 != t->first_free) {
 336         block = t->first_free;
 337         t->first_free = t->tails[block].next_free;
 338     } else {
 339         void *new_block;
 340
 341         block = t->num_tails;
 342
 343         new_block = realloc (t->tails, (t->num_tails + 1) * sizeof (TailBlock));
 344         if (UNLIKELY (!new_block))
 345             return TRIE_INDEX_ERROR;
 346
 347         t->tails = (TailBlock *) new_block;
 348         ++t->num_tails;
 349     }
 350     t->tails[block].next_free = -1;
 351     t->tails[block].data = TRIE_DATA_ERROR;
 352     t->tails[block].suffix = NULL;
 353
 354     return block + TAIL_START_BLOCKNO;
 355 }
 356
 357 static void
 358 tail_free_block (Tail *t, TrieIndex block)
 359 {
 360     TrieIndex   i, j;
 361
 362     block -= TAIL_START_BLOCKNO;
 363
 364     if (block >= t->num_tails)
 365         return;
 366
 367     t->tails[block].data = TRIE_DATA_ERROR;
 368     if (NULL != t->tails[block].suffix) {
 369         free (t->tails[block].suffix);
 370         t->tails[block].suffix = NULL;
 371     }
 372
 373     /* find insertion point */
 374     j = 0;
 375     for (i = t->first_free; i != 0 && i < block; i = t->tails[i].next_free)
 376         j = i;
 377
 378     /* insert free block between j and i */
 379     t->tails[block].next_free = i;
 380     if (0 != j)
 381         t->tails[j].next_free = block;
 382     else
 383         t->first_free = block;
 384 }
 385
 386 /**
 387  * @brief Get data associated to suffix entry
 388  *
 389  * @param t      : the tail data
 390  * @param index  : the index of the suffix
 391  *
 392  * @return the data associated to the suffix entry
 393  *
 394  * Get data associated to suffix entry @a index in tail data.
 395  */
 396 TrieData
 397 tail_get_data (const Tail *t, TrieIndex index)
 398 {
 399     index -= TAIL_START_BLOCKNO;
 400     return LIKELY (index < t->num_tails)
 401              ? t->tails[index].data : TRIE_DATA_ERROR;
 402 }
 403
 404 /**
 405  * @brief Set data associated to suffix entry
 406  *
 407  * @param t      : the tail data
 408  * @param index  : the index of the suffix
 409  * @param data   : the data to set
 410  *
 411  * @return boolean indicating success
 412  *
 413  * Set data associated to suffix entry @a index in tail data.
 414  */
 415 Bool
 416 tail_set_data (Tail *t, TrieIndex index, TrieData data)
 417 {
 418     index -= TAIL_START_BLOCKNO;
 419     if (LIKELY (index < t->num_tails)) {
 420         t->tails[index].data = data;
 421         return TRUE;
 422     }
 423     return FALSE;
 424 }
 425
 426 /**
 427  * @brief Delete suffix entry
 428  *
 429  * @param t      : the tail data
 430  * @param index  : the index of the suffix to delete
 431  *
 432  * Delete suffix entry from the tail data.
 433  */
 434 void
 435 tail_delete (Tail *t, TrieIndex index)
 436 {
 437     tail_free_block (t, index);
 438 }
 439
 440 /**
 441  * @brief Walk in tail with a string
 442  *
 443  * @param t          : the tail data
 444  * @param s          : the tail data index
 445  * @param suffix_idx : pointer to current character index in suffix
 446  * @param str        : the string to use in walking
 447  * @param len        : total characters in @a str to walk
 448  *
 449  * @return total number of characters successfully walked
 450  *
 451  * Walk in the tail data @a t at entry @a s, from given character position
 452  * @a *suffix_idx, using @a len characters of given string @a str. On return,
 453  * @a *suffix_idx is updated to the position after the last successful walk,
 454  * and the function returns the total number of character succesfully walked.
 455  */
 456 int
 457 tail_walk_str  (const Tail      *t,
 458                 TrieIndex        s,
 459                 short           *suffix_idx,
 460                 const TrieChar  *str,
 461                 int              len)
 462 {
 463     const TrieChar *suffix;
 464     int             i;
 465     short           j;
 466
 467     suffix = tail_get_suffix (t, s);
 468     if (UNLIKELY (!suffix))
 469         return FALSE;
 470
 471     i = 0; j = *suffix_idx;
 472     while (i < len) {
 473         if (str[i] != suffix[j])
 474             break;
 475         ++i;
 476         /* stop and stay at null-terminator */
 477         if (0 == suffix[j])
 478             break;
 479         ++j;
 480     }
 481     *suffix_idx = j;
 482     return i;
 483 }
 484
 485 /**
 486  * @brief Walk in tail with a character
 487  *
 488  * @param t          : the tail data
 489  * @param s          : the tail data index
 490  * @param suffix_idx : pointer to current character index in suffix
 491  * @param c          : the character to use in walking
 492  *
 493  * @return boolean indicating success
 494  *
 495  * Walk in the tail data @a t at entry @a s, from given character position
 496  * @a *suffix_idx, using given character @a c. If the walk is successful,
 497  * it returns TRUE, and @a *suffix_idx is updated to the next character.
 498  * Otherwise, it returns FALSE, and @a *suffix_idx is left unchanged.
 499  */
 500 Bool
 501 tail_walk_char (const Tail      *t,
 502                 TrieIndex        s,
 503                 short           *suffix_idx,
 504                 TrieChar         c)
 505 {
 506     const TrieChar *suffix;
 507     TrieChar        suffix_char;
 508
 509     suffix = tail_get_suffix (t, s);
 510     if (UNLIKELY (!suffix))
 511         return FALSE;
 512
 513     suffix_char = suffix[*suffix_idx];
 514     if (suffix_char == c) {
 515         if (0 != suffix_char)
 516             ++*suffix_idx;
 517         return TRUE;
 518     }
 519     return FALSE;
 520 }
 521
 522 /*
 523 vi:ts=4:ai:expandtab
 524 */