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 (void)
  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 static size_t
 274 tc_strlen (const TrieChar *str)
 275 {
 276     size_t len = 0;
 277     while (*str++) {
 278         ++len;
 279     }
 280     return len;
 281 }
 282
 283 static TrieChar *
 284 tc_strdup (const TrieChar *str)
 285 {
 286     TrieChar *dup
 287         = (TrieChar *) malloc (sizeof (TrieChar) * (tc_strlen (str) + 1));
 288     TrieChar *p = dup;
 289
 290     while (*str) {
 291         *p++ = *str++;
 292     }
 293     *p = (TrieChar) 0;
 294
 295     return dup;
 296 }
 297
 298 /**
 299  * @brief Set suffix of existing entry
 300  *
 301  * @param t      : the tail data
 302  * @param index  : the index of the suffix
 303  * @param suffix : the new suffix
 304  *
 305  * Set suffix of existing entry of given @a index in tail.
 306  */
 307 Bool
 308 tail_set_suffix (Tail *t, TrieIndex index, const TrieChar *suffix)
 309 {
 310     index -= TAIL_START_BLOCKNO;
 311     if (LIKELY (index < t->num_tails)) {
 312         /* suffix and t->tails[index].suffix may overlap;
 313          * so, dup it before it's overwritten
 314          */
 315         TrieChar *tmp = NULL;
 316         if (suffix) {
 317             tmp = tc_strdup (suffix);
 318             if (UNLIKELY (!tmp))
 319                 return FALSE;
 320         }
 321         if (t->tails[index].suffix)
 322             free (t->tails[index].suffix);
 323         t->tails[index].suffix = tmp;
 324
 325         return TRUE;
 326     }
 327     return FALSE;
 328 }
 329
 330 /**
 331  * @brief Add a new suffix
 332  *
 333  * @param t      : the tail data
 334  * @param suffix : the new suffix
 335  *
 336  * @return the index of the newly added suffix,
 337  *         or TRIE_INDEX_ERROR on failure.
 338  *
 339  * Add a new suffix entry to tail.
 340  */
 341 TrieIndex
 342 tail_add_suffix (Tail *t, const TrieChar *suffix)
 343 {
 344     TrieIndex   new_block;
 345
 346     new_block = tail_alloc_block (t);
 347     if (UNLIKELY (TRIE_INDEX_ERROR == new_block))
 348         return TRIE_INDEX_ERROR;
 349
 350     tail_set_suffix (t, new_block, suffix);
 351
 352     return new_block;
 353 }
 354
 355 static TrieIndex
 356 tail_alloc_block (Tail *t)
 357 {
 358     TrieIndex   block;
 359
 360     if (0 != t->first_free) {
 361         block = t->first_free;
 362         t->first_free = t->tails[block].next_free;
 363     } else {
 364         void *new_block;
 365
 366         block = t->num_tails;
 367
 368         new_block = realloc (t->tails, (t->num_tails + 1) * sizeof (TailBlock));
 369         if (UNLIKELY (!new_block))
 370             return TRIE_INDEX_ERROR;
 371
 372         t->tails = (TailBlock *) new_block;
 373         ++t->num_tails;
 374     }
 375     t->tails[block].next_free = -1;
 376     t->tails[block].data = TRIE_DATA_ERROR;
 377     t->tails[block].suffix = NULL;
 378
 379     return block + TAIL_START_BLOCKNO;
 380 }
 381
 382 static void
 383 tail_free_block (Tail *t, TrieIndex block)
 384 {
 385     TrieIndex   i, j;
 386
 387     block -= TAIL_START_BLOCKNO;
 388
 389     if (block >= t->num_tails)
 390         return;
 391
 392     t->tails[block].data = TRIE_DATA_ERROR;
 393     if (NULL != t->tails[block].suffix) {
 394         free (t->tails[block].suffix);
 395         t->tails[block].suffix = NULL;
 396     }
 397
 398     /* find insertion point */
 399     j = 0;
 400     for (i = t->first_free; i != 0 && i < block; i = t->tails[i].next_free)
 401         j = i;
 402
 403     /* insert free block between j and i */
 404     t->tails[block].next_free = i;
 405     if (0 != j)
 406         t->tails[j].next_free = block;
 407     else
 408         t->first_free = block;
 409 }
 410
 411 /**
 412  * @brief Get data associated to suffix entry
 413  *
 414  * @param t      : the tail data
 415  * @param index  : the index of the suffix
 416  *
 417  * @return the data associated to the suffix entry
 418  *
 419  * Get data associated to suffix entry @a index in tail data.
 420  */
 421 TrieData
 422 tail_get_data (const Tail *t, TrieIndex index)
 423 {
 424     index -= TAIL_START_BLOCKNO;
 425     return LIKELY (index < t->num_tails)
 426              ? t->tails[index].data : TRIE_DATA_ERROR;
 427 }
 428
 429 /**
 430  * @brief Set data associated to suffix entry
 431  *
 432  * @param t      : the tail data
 433  * @param index  : the index of the suffix
 434  * @param data   : the data to set
 435  *
 436  * @return boolean indicating success
 437  *
 438  * Set data associated to suffix entry @a index in tail data.
 439  */
 440 Bool
 441 tail_set_data (Tail *t, TrieIndex index, TrieData data)
 442 {
 443     index -= TAIL_START_BLOCKNO;
 444     if (LIKELY (index < t->num_tails)) {
 445         t->tails[index].data = data;
 446         return TRUE;
 447     }
 448     return FALSE;
 449 }
 450
 451 /**
 452  * @brief Delete suffix entry
 453  *
 454  * @param t      : the tail data
 455  * @param index  : the index of the suffix to delete
 456  *
 457  * Delete suffix entry from the tail data.
 458  */
 459 void
 460 tail_delete (Tail *t, TrieIndex index)
 461 {
 462     tail_free_block (t, index);
 463 }
 464
 465 /**
 466  * @brief Walk in tail with a string
 467  *
 468  * @param t          : the tail data
 469  * @param s          : the tail data index
 470  * @param suffix_idx : pointer to current character index in suffix
 471  * @param str        : the string to use in walking
 472  * @param len        : total characters in @a str to walk
 473  *
 474  * @return total number of characters successfully walked
 475  *
 476  * Walk in the tail data @a t at entry @a s, from given character position
 477  * @a *suffix_idx, using @a len characters of given string @a str. On return,
 478  * @a *suffix_idx is updated to the position after the last successful walk,
 479  * and the function returns the total number of character succesfully walked.
 480  */
 481 int
 482 tail_walk_str  (const Tail      *t,
 483                 TrieIndex        s,
 484                 short           *suffix_idx,
 485                 const TrieChar  *str,
 486                 int              len)
 487 {
 488     const TrieChar *suffix;
 489     int             i;
 490     short           j;
 491
 492     suffix = tail_get_suffix (t, s);
 493     if (UNLIKELY (!suffix))
 494         return FALSE;
 495
 496     i = 0; j = *suffix_idx;
 497     while (i < len) {
 498         if (str[i] != suffix[j])
 499             break;
 500         ++i;
 501         /* stop and stay at null-terminator */
 502         if (0 == suffix[j])
 503             break;
 504         ++j;
 505     }
 506     *suffix_idx = j;
 507     return i;
 508 }
 509
 510 /**
 511  * @brief Walk in tail with a character
 512  *
 513  * @param t          : the tail data
 514  * @param s          : the tail data index
 515  * @param suffix_idx : pointer to current character index in suffix
 516  * @param c          : the character to use in walking
 517  *
 518  * @return boolean indicating success
 519  *
 520  * Walk in the tail data @a t at entry @a s, from given character position
 521  * @a *suffix_idx, using given character @a c. If the walk is successful,
 522  * it returns TRUE, and @a *suffix_idx is updated to the next character.
 523  * Otherwise, it returns FALSE, and @a *suffix_idx is left unchanged.
 524  */
 525 Bool
 526 tail_walk_char (const Tail      *t,
 527                 TrieIndex        s,
 528                 short           *suffix_idx,
 529                 TrieChar         c)
 530 {
 531     const TrieChar *suffix;
 532     TrieChar        suffix_char;
 533
 534     suffix = tail_get_suffix (t, s);
 535     if (UNLIKELY (!suffix))
 536         return FALSE;
 537
 538     suffix_char = suffix[*suffix_idx];
 539     if (suffix_char == c) {
 540         if (0 != suffix_char)
 541             ++*suffix_idx;
 542         return TRUE;
 543     }
 544     return FALSE;
 545 }
 546
 547 /*
 548 vi:ts=4:ai:expandtab
 549 */