datrie/darray.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  * darray.c - Double-array trie structure
  23  * Created: 2006-08-13
  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 "trie-private.h"
  35 #include "darray.h"
  36 #include "fileutils.h"
  37
  38 /*----------------------------------*
  39  *    INTERNAL TYPES DECLARATIONS   *
  40  *----------------------------------*/
  41
  42 struct _Symbols {
  43     short       num_symbols;
  44     TrieChar    symbols[TRIE_CHAR_MAX + 1];
  45 };
  46
  47 static Symbols *    symbols_new ();
  48 static void         symbols_add (Symbols *syms, TrieChar c);
  49 #define symbols_add_fast(s,c)   ((s)->symbols[(s)->num_symbols++] = c)
  50
  51 /*-----------------------------------*
  52  *    PRIVATE METHODS DECLARATIONS   *
  53  *-----------------------------------*/
  54
  55 #define da_get_free_list(d)      (1)
  56
  57 static Bool         da_check_free_cell (DArray         *d,
  58                                         TrieIndex       s);
  59
  60 static Bool         da_has_children    (const DArray   *d,
  61                                         TrieIndex       s);
  62
  63 static TrieIndex    da_find_free_base  (DArray         *d,
  64                                         const Symbols  *symbols);
  65
  66 static Bool         da_fit_symbols     (DArray         *d,
  67                                         TrieIndex       base,
  68                                         const Symbols  *symbols);
  69
  70 static void         da_relocate_base   (DArray         *d,
  71                                         TrieIndex       s,
  72                                         TrieIndex       new_base);
  73
  74 static Bool         da_extend_pool     (DArray         *d,
  75                                         TrieIndex       to_index);
  76
  77 static void         da_alloc_cell      (DArray         *d,
  78                                         TrieIndex       cell);
  79
  80 static void         da_free_cell       (DArray         *d,
  81                                         TrieIndex       cell);
  82
  83 /* ==================== BEGIN IMPLEMENTATION PART ====================  */
  84
  85 /*------------------------------------*
  86  *   INTERNAL TYPES IMPLEMENTATIONS   *
  87  *------------------------------------*/
  88
  89 static Symbols *
  90 symbols_new ()
  91 {
  92     Symbols *syms;
  93
  94     syms = (Symbols *) malloc (sizeof (Symbols));
  95
  96     if (UNLIKELY (!syms))
  97         return NULL;
  98
  99     syms->num_symbols = 0;
 100
 101     return syms;
 102 }
 103
 104 void
 105 symbols_free (Symbols *syms)
 106 {
 107     free (syms);
 108 }
 109
 110 static void
 111 symbols_add (Symbols *syms, TrieChar c)
 112 {
 113     short lower, upper;
 114
 115     lower = 0;
 116     upper = syms->num_symbols;
 117     while (lower < upper) {
 118         short middle;
 119
 120         middle = (lower + upper)/2;
 121         if (c > syms->symbols[middle])
 122             lower = middle + 1;
 123         else if (c < syms->symbols[middle])
 124             upper = middle;
 125         else
 126             return;
 127     }
 128     if (lower < syms->num_symbols) {
 129         memmove (syms->symbols + lower + 1, syms->symbols + lower,
 130                  syms->num_symbols - lower);
 131     }
 132     syms->symbols[lower] = c;
 133     syms->num_symbols++;
 134 }
 135
 136 int
 137 symbols_num (const Symbols *syms)
 138 {
 139     return syms->num_symbols;
 140 }
 141
 142 TrieChar
 143 symbols_get (const Symbols *syms, int index)
 144 {
 145     return syms->symbols[index];
 146 }
 147
 148
 149 /*------------------------------*
 150  *    PRIVATE DATA DEFINITONS   *
 151  *------------------------------*/
 152
 153 typedef struct {
 154     TrieIndex   base;
 155     TrieIndex   check;
 156 } DACell;
 157
 158 struct _DArray {
 159     TrieIndex   num_cells;
 160     DACell     *cells;
 161 };
 162
 163 /*-----------------------------*
 164  *    METHODS IMPLEMENTAIONS   *
 165  *-----------------------------*/
 166
 167 #define DA_SIGNATURE 0xDAFCDAFC
 168
 169 /* DA Header:
 170  * - Cell 0: SIGNATURE, number of cells
 171  * - Cell 1: free circular-list pointers
 172  * - Cell 2: root node
 173  * - Cell 3: DA pool begin
 174  */
 175 #define DA_POOL_BEGIN 3
 176
 177 /**
 178  * @brief Create a new double-array object
 179  *
 180  * Create a new empty doubla-array object.
 181  */
 182 DArray *
 183 da_new ()
 184 {
 185     DArray     *d;
 186
 187     d = (DArray *) malloc (sizeof (DArray));
 188     if (UNLIKELY (!d))
 189         return NULL;
 190
 191     d->num_cells = DA_POOL_BEGIN;
 192     d->cells     = (DACell *) malloc (d->num_cells * sizeof (DACell));
 193     if (UNLIKELY (!d->cells))
 194         goto exit_da_created;
 195     d->cells[0].base = DA_SIGNATURE;
 196     d->cells[0].check = d->num_cells;
 197     d->cells[1].base = -1;
 198     d->cells[1].check = -1;
 199     d->cells[2].base = DA_POOL_BEGIN;
 200     d->cells[2].check = 0;
 201
 202     return d;
 203
 204 exit_da_created:
 205     free (d);
 206     return NULL;
 207 }
 208
 209 /**
 210  * @brief Read double-array data from file
 211  *
 212  * @param file : the file to read
 213  *
 214  * @return a pointer to the openned double-array, NULL on failure
 215  *
 216  * Read double-array data from the opened file, starting from the current
 217  * file pointer until the end of double array data block. On return, the
 218  * file pointer is left at the position after the read block.
 219  */
 220 DArray *
 221 da_fread (FILE *file)
 222 {
 223     long        save_pos;
 224     DArray     *d = NULL;
 225     TrieIndex   n;
 226
 227     /* check signature */
 228     save_pos = ftell (file);
 229     if (!file_read_int32 (file, &n) || DA_SIGNATURE != (uint32) n)
 230         goto exit_file_read;
 231
 232     d = (DArray *) malloc (sizeof (DArray));
 233     if (UNLIKELY (!d))
 234         goto exit_file_read;
 235
 236     /* read number of cells */
 237     if (!file_read_int32 (file, &d->num_cells))
 238         goto exit_da_created;
 239     if (d->num_cells > SIZE_MAX / sizeof (DACell))
 240         goto exit_da_created;
 241     d->cells = (DACell *) malloc (d->num_cells * sizeof (DACell));
 242     if (UNLIKELY (!d->cells))
 243         goto exit_da_created;
 244     d->cells[0].base = DA_SIGNATURE;
 245     d->cells[0].check= d->num_cells;
 246     for (n = 1; n < d->num_cells; n++) {
 247         if (!file_read_int32 (file, &d->cells[n].base) ||
 248             !file_read_int32 (file, &d->cells[n].check))
 249         {
 250             goto exit_da_cells_created;
 251         }
 252     }
 253
 254     return d;
 255
 256 exit_da_cells_created:
 257     free (d->cells);
 258 exit_da_created:
 259     free (d);
 260 exit_file_read:
 261     fseek (file, save_pos, SEEK_SET);
 262     return NULL;
 263 }
 264
 265 /**
 266  * @brief Free double-array data
 267  *
 268  * @param d : the double-array data
 269  *
 270  * Free the given double-array data.
 271  */
 272 void
 273 da_free (DArray *d)
 274 {
 275     free (d->cells);
 276     free (d);
 277 }
 278
 279 /**
 280  * @brief Write double-array data
 281  *
 282  * @param d     : the double-array data
 283  * @param file  : the file to write to
 284  *
 285  * @return 0 on success, non-zero on failure
 286  *
 287  * Write double-array data to the given @a file, starting from the current
 288  * file pointer. On return, the file pointer is left after the double-array
 289  * data block.
 290  */
 291 int
 292 da_fwrite (const DArray *d, FILE *file)
 293 {
 294     TrieIndex   i;
 295
 296     for (i = 0; i < d->num_cells; i++) {
 297         if (!file_write_int32 (file, d->cells[i].base) ||
 298             !file_write_int32 (file, d->cells[i].check))
 299         {
 300             return -1;
 301         }
 302     }
 303
 304     return 0;
 305 }
 306
 307
 308 /**
 309  * @brief Get root state
 310  *
 311  * @param d     : the double-array data
 312  *
 313  * @return root state of the @a index set, or TRIE_INDEX_ERROR on failure
 314  *
 315  * Get root state for stepwise walking.
 316  */
 317 TrieIndex
 318 da_get_root (const DArray *d)
 319 {
 320     /* can be calculated value for multi-index trie */
 321     return 2;
 322 }
 323
 324
 325 /**
 326  * @brief Get BASE cell
 327  *
 328  * @param d : the double-array data
 329  * @param s : the double-array state to get data
 330  *
 331  * @return the BASE cell value for the given state
 332  *
 333  * Get BASE cell value for the given state.
 334  */
 335 TrieIndex
 336 da_get_base (const DArray *d, TrieIndex s)
 337 {
 338     return LIKELY (s < d->num_cells) ? d->cells[s].base : TRIE_INDEX_ERROR;
 339 }
 340
 341 /**
 342  * @brief Get CHECK cell
 343  *
 344  * @param d : the double-array data
 345  * @param s : the double-array state to get data
 346  *
 347  * @return the CHECK cell value for the given state
 348  *
 349  * Get CHECK cell value for the given state.
 350  */
 351 TrieIndex
 352 da_get_check (const DArray *d, TrieIndex s)
 353 {
 354     return LIKELY (s < d->num_cells) ? d->cells[s].check : TRIE_INDEX_ERROR;
 355 }
 356
 357
 358 /**
 359  * @brief Set BASE cell
 360  *
 361  * @param d   : the double-array data
 362  * @param s   : the double-array state to get data
 363  * @param val : the value to set
 364  *
 365  * Set BASE cell for the given state to the given value.
 366  */
 367 void
 368 da_set_base (DArray *d, TrieIndex s, TrieIndex val)
 369 {
 370     if (LIKELY (s < d->num_cells)) {
 371         d->cells[s].base = val;
 372     }
 373 }
 374
 375 /**
 376  * @brief Set CHECK cell
 377  *
 378  * @param d   : the double-array data
 379  * @param s   : the double-array state to get data
 380  * @param val : the value to set
 381  *
 382  * Set CHECK cell for the given state to the given value.
 383  */
 384 void
 385 da_set_check (DArray *d, TrieIndex s, TrieIndex val)
 386 {
 387     if (LIKELY (s < d->num_cells)) {
 388         d->cells[s].check = val;
 389     }
 390 }
 391
 392 /**
 393  * @brief Walk in double-array structure
 394  *
 395  * @param d : the double-array structure
 396  * @param s : current state
 397  * @param c : the input character
 398  *
 399  * @return boolean indicating success
 400  *
 401  * Walk the double-array trie from state @a *s, using input character @a c.
 402  * If there exists an edge from @a *s with arc labeled @a c, this function
 403  * returns TRUE and @a *s is updated to the new state. Otherwise, it returns
 404  * FALSE and @a *s is left unchanged.
 405  */
 406 Bool
 407 da_walk (const DArray *d, TrieIndex *s, TrieChar c)
 408 {
 409     TrieIndex   next;
 410
 411     next = da_get_base (d, *s) + c;
 412     if (da_get_check (d, next) == *s) {
 413         *s = next;
 414         return TRUE;
 415     }
 416     return FALSE;
 417 }
 418
 419 /**
 420  * @brief Insert a branch from trie node
 421  *
 422  * @param d : the double-array structure
 423  * @param s : the state to add branch to
 424  * @param c : the character for the branch label
 425  *
 426  * @return the index of the new node
 427  *
 428  * Insert a new arc labelled with character @a c from the trie node
 429  * represented by index @a s in double-array structure @a d.
 430  * Note that it assumes that no such arc exists before inserting.
 431  */
 432 TrieIndex
 433 da_insert_branch (DArray *d, TrieIndex s, TrieChar c)
 434 {
 435     TrieIndex   base, next;
 436
 437     base = da_get_base (d, s);
 438
 439     if (base > 0) {
 440         next = base + c;
 441
 442         /* if already there, do not actually insert */
 443         if (da_get_check (d, next) == s)
 444             return next;
 445
 446         /* if (base + c) > TRIE_INDEX_MAX which means 'next' is overflow,
 447          * or cell [next] is not free, relocate to a free slot
 448          */
 449         if (base > TRIE_INDEX_MAX - c || !da_check_free_cell (d, next)) {
 450             Symbols    *symbols;
 451             TrieIndex   new_base;
 452
 453             /* relocate BASE[s] */
 454             symbols = da_output_symbols (d, s);
 455             symbols_add (symbols, c);
 456             new_base = da_find_free_base (d, symbols);
 457             symbols_free (symbols);
 458
 459             if (UNLIKELY (TRIE_INDEX_ERROR == new_base))
 460                 return TRIE_INDEX_ERROR;
 461
 462             da_relocate_base (d, s, new_base);
 463             next = new_base + c;
 464         }
 465     } else {
 466         Symbols    *symbols;
 467         TrieIndex   new_base;
 468
 469         symbols = symbols_new ();
 470         symbols_add (symbols, c);
 471         new_base = da_find_free_base (d, symbols);
 472         symbols_free (symbols);
 473
 474         if (UNLIKELY (TRIE_INDEX_ERROR == new_base))
 475             return TRIE_INDEX_ERROR;
 476
 477         da_set_base (d, s, new_base);
 478         next = new_base + c;
 479     }
 480     da_alloc_cell (d, next);
 481     da_set_check (d, next, s);
 482
 483     return next;
 484 }
 485
 486 static Bool
 487 da_check_free_cell (DArray         *d,
 488                     TrieIndex       s)
 489 {
 490     return da_extend_pool (d, s) && da_get_check (d, s) < 0;
 491 }
 492
 493 static Bool
 494 da_has_children    (const DArray   *d,
 495                     TrieIndex       s)
 496 {
 497     TrieIndex   base;
 498     TrieIndex   c, max_c;
 499
 500     base = da_get_base (d, s);
 501     if (TRIE_INDEX_ERROR == base || base < 0)
 502         return FALSE;
 503
 504     max_c = MIN_VAL (TRIE_CHAR_MAX, d->num_cells - base);
 505     for (c = 0; c <= max_c; c++) {
 506         if (da_get_check (d, base + c) == s)
 507             return TRUE;
 508     }
 509
 510     return FALSE;
 511 }
 512
 513 Symbols *
 514 da_output_symbols  (const DArray   *d,
 515                     TrieIndex       s)
 516 {
 517     Symbols    *syms;
 518     TrieIndex   base;
 519     TrieIndex   c, max_c;
 520
 521     syms = symbols_new ();
 522
 523     base = da_get_base (d, s);
 524     max_c = MIN_VAL (TRIE_CHAR_MAX, d->num_cells - base);
 525     for (c = 0; c <= max_c; c++) {
 526         if (da_get_check (d, base + c) == s)
 527             symbols_add_fast (syms, (TrieChar) c);
 528     }
 529
 530     return syms;
 531 }
 532
 533 static TrieIndex
 534 da_find_free_base  (DArray         *d,
 535                     const Symbols  *symbols)
 536 {
 537     TrieChar        first_sym;
 538     TrieIndex       s;
 539
 540     /* find first free cell that is beyond the first symbol */
 541     first_sym = symbols_get (symbols, 0);
 542     s = -da_get_check (d, da_get_free_list (d));
 543     while (s != da_get_free_list (d)
 544            && s < (TrieIndex) first_sym + DA_POOL_BEGIN)
 545     {
 546         s = -da_get_check (d, s);
 547     }
 548     if (s == da_get_free_list (d)) {
 549         for (s = first_sym + DA_POOL_BEGIN; ; ++s) {
 550             if (!da_extend_pool (d, s))
 551                 return TRIE_INDEX_ERROR;
 552             if (da_get_check (d, s) < 0)
 553                 break;
 554         }
 555     }
 556
 557     /* search for next free cell that fits the symbols set */
 558     while (!da_fit_symbols (d, s - first_sym, symbols)) {
 559         /* extend pool before getting exhausted */
 560         if (-da_get_check (d, s) == da_get_free_list (d)) {
 561             if (UNLIKELY (!da_extend_pool (d, d->num_cells)))
 562                 return TRIE_INDEX_ERROR;
 563         }
 564
 565         s = -da_get_check (d, s);
 566     }
 567
 568     return s - first_sym;
 569 }
 570
 571 static Bool
 572 da_fit_symbols     (DArray         *d,
 573                     TrieIndex       base,
 574                     const Symbols  *symbols)
 575 {
 576     int         i;
 577
 578     for (i = 0; i < symbols_num (symbols); i++) {
 579         TrieChar    sym = symbols_get (symbols, i);
 580
 581         /* if (base + sym) > TRIE_INDEX_MAX which means it's overflow,
 582          * or cell [base + sym] is not free, the symbol is not fit.
 583          */
 584         if (base > TRIE_INDEX_MAX - sym || !da_check_free_cell (d, base + sym))
 585             return FALSE;
 586     }
 587     return TRUE;
 588 }
 589
 590 static void
 591 da_relocate_base   (DArray         *d,
 592                     TrieIndex       s,
 593                     TrieIndex       new_base)
 594 {
 595     TrieIndex   old_base;
 596     Symbols    *symbols;
 597     int         i;
 598
 599     old_base = da_get_base (d, s);
 600     symbols = da_output_symbols (d, s);
 601
 602     for (i = 0; i < symbols_num (symbols); i++) {
 603         TrieIndex   old_next, new_next, old_next_base;
 604
 605         old_next = old_base + symbols_get (symbols, i);
 606         new_next = new_base + symbols_get (symbols, i);
 607         old_next_base = da_get_base (d, old_next);
 608
 609         /* allocate new next node and copy BASE value */
 610         da_alloc_cell (d, new_next);
 611         da_set_check (d, new_next, s);
 612         da_set_base (d, new_next, old_next_base);
 613
 614         /* old_next node is now moved to new_next
 615          * so, all cells belonging to old_next
 616          * must be given to new_next
 617          */
 618         /* preventing the case of TAIL pointer */
 619         if (old_next_base > 0) {
 620             TrieIndex   c, max_c;
 621
 622             max_c = MIN_VAL (TRIE_CHAR_MAX, d->num_cells - old_next_base);
 623             for  (c = 0; c <= max_c; c++) {
 624                 if (da_get_check (d, old_next_base + c) == old_next)
 625                     da_set_check (d, old_next_base + c, new_next);
 626             }
 627         }
 628
 629         /* free old_next node */
 630         da_free_cell (d, old_next);
 631     }
 632
 633     symbols_free (symbols);
 634
 635     /* finally, make BASE[s] point to new_base */
 636     da_set_base (d, s, new_base);
 637 }
 638
 639 static Bool
 640 da_extend_pool     (DArray         *d,
 641                     TrieIndex       to_index)
 642 {
 643     void       *new_block;
 644     TrieIndex   new_begin;
 645     TrieIndex   i;
 646     TrieIndex   free_tail;
 647
 648     if (UNLIKELY (to_index <= 0 || TRIE_INDEX_MAX <= to_index))
 649         return FALSE;
 650
 651     if (to_index < d->num_cells)
 652         return TRUE;
 653
 654     new_block = realloc (d->cells, (to_index + 1) * sizeof (DACell));
 655     if (UNLIKELY (!new_block))
 656         return FALSE;
 657
 658     d->cells = (DACell *) new_block;
 659     new_begin = d->num_cells;
 660     d->num_cells = to_index + 1;
 661
 662     /* initialize new free list */
 663     for (i = new_begin; i < to_index; i++) {
 664         da_set_check (d, i, -(i + 1));
 665         da_set_base (d, i + 1, -i);
 666     }
 667
 668     /* merge the new circular list to the old */
 669     free_tail = -da_get_base (d, da_get_free_list (d));
 670     da_set_check (d, free_tail, -new_begin);
 671     da_set_base (d, new_begin, -free_tail);
 672     da_set_check (d, to_index, -da_get_free_list (d));
 673     da_set_base (d, da_get_free_list (d), -to_index);
 674
 675     /* update header cell */
 676     d->cells[0].check = d->num_cells;
 677
 678     return TRUE;
 679 }
 680
 681 /**
 682  * @brief Prune the single branch
 683  *
 684  * @param d : the double-array structure
 685  * @param s : the dangling state to prune off
 686  *
 687  * Prune off a non-separate path up from the final state @a s.
 688  * If @a s still has some children states, it does nothing. Otherwise,
 689  * it deletes the node and all its parents which become non-separate.
 690  */
 691 void
 692 da_prune (DArray *d, TrieIndex s)
 693 {
 694     da_prune_upto (d, da_get_root (d), s);
 695 }
 696
 697 /**
 698  * @brief Prune the single branch up to given parent
 699  *
 700  * @param d : the double-array structure
 701  * @param p : the parent up to which to be pruned
 702  * @param s : the dangling state to prune off
 703  *
 704  * Prune off a non-separate path up from the final state @a s to the
 705  * given parent @a p. The prunning stop when either the parent @a p
 706  * is met, or a first non-separate node is found.
 707  */
 708 void
 709 da_prune_upto (DArray *d, TrieIndex p, TrieIndex s)
 710 {
 711     while (p != s && !da_has_children (d, s)) {
 712         TrieIndex   parent;
 713
 714         parent = da_get_check (d, s);
 715         da_free_cell (d, s);
 716         s = parent;
 717     }
 718 }
 719
 720 static void
 721 da_alloc_cell      (DArray         *d,
 722                     TrieIndex       cell)
 723 {
 724     TrieIndex   prev, next;
 725
 726     prev = -da_get_base (d, cell);
 727     next = -da_get_check (d, cell);
 728
 729     /* remove the cell from free list */
 730     da_set_check (d, prev, -next);
 731     da_set_base (d, next, -prev);
 732 }
 733
 734 static void
 735 da_free_cell       (DArray         *d,
 736                     TrieIndex       cell)
 737 {
 738     TrieIndex   i, prev;
 739
 740     /* find insertion point */
 741     i = -da_get_check (d, da_get_free_list (d));
 742     while (i != da_get_free_list (d) && i < cell)
 743         i = -da_get_check (d, i);
 744
 745     prev = -da_get_base (d, i);
 746
 747     /* insert cell before i */
 748     da_set_check (d, cell, -i);
 749     da_set_base (d, cell, -prev);
 750     da_set_check (d, prev, -cell);
 751     da_set_base (d, i, -cell);
 752 }
 753
 754 /**
 755  * @brief Find first separate node in a sub-trie
 756  *
 757  * @param d       : the double-array structure
 758  * @param root    : the sub-trie root to search from
 759  * @param keybuff : the TrieString buffer for incrementally calcuating key
 760  *
 761  * @return index to the first separate node; TRIE_INDEX_ERROR on any failure
 762  *
 763  * Find the first separate node under a sub-trie rooted at @a root.
 764  *
 765  * On return, @a keybuff is appended with the key characters which walk from
 766  * @a root to the separate node. This is for incrementally calculating the
 767  * transition key, which is more efficient than later totally reconstructing
 768  * key from the given separate node.
 769  *
 770  * Available since: 0.2.6
 771  */
 772 TrieIndex
 773 da_first_separate (DArray *d, TrieIndex root, TrieString *keybuff)
 774 {
 775     TrieIndex base;
 776     TrieIndex c, max_c;
 777
 778     while ((base = da_get_base (d, root)) >= 0) {
 779         max_c = MIN_VAL (TRIE_CHAR_MAX, d->num_cells - base);
 780         for (c = 0; c <= max_c; c++) {
 781             if (da_get_check (d, base + c) == root)
 782                 break;
 783         }
 784
 785         if (c > max_c)
 786             return TRIE_INDEX_ERROR;
 787
 788         trie_string_append_char (keybuff, c);
 789         root = base + c;
 790     }
 791
 792     return root;
 793 }
 794
 795 /**
 796  * @brief Find next separate node in a sub-trie
 797  *
 798  * @param d     : the double-array structure
 799  * @param root  : the sub-trie root to search from
 800  * @param sep   : the current separate node
 801  * @param keybuff : the TrieString buffer for incrementally calcuating key
 802  *
 803  * @return index to the next separate node; TRIE_INDEX_ERROR if no more
 804  *         separate node is found
 805  *
 806  * Find the next separate node under a sub-trie rooted at @a root starting
 807  * from the current separate node @a sep.
 808  *
 809  * On return, @a keybuff is incrementally updated from the key which walks
 810  * to previous separate node to the one which walks to the new separate node.
 811  * So, it is assumed to be initialized by at least one da_first_separate()
 812  * call before. This incremental key calculation is more efficient than later
 813  * totally reconstructing key from the given separate node.
 814  *
 815  * Available since: 0.2.6
 816  */
 817 TrieIndex
 818 da_next_separate (DArray *d, TrieIndex root, TrieIndex sep, TrieString *keybuff)
 819 {
 820     TrieIndex parent;
 821     TrieIndex base;
 822     TrieIndex c, max_c;
 823
 824     while (sep != root) {
 825         parent = da_get_check (d, sep);
 826         base = da_get_base (d, parent);
 827         c = sep - base;
 828
 829         trie_string_cut_last (keybuff);
 830
 831         /* find next sibling of sep */
 832         max_c = MIN_VAL (TRIE_CHAR_MAX, d->num_cells - base);
 833         while (++c <= max_c) {
 834             if (da_get_check (d, base + c) == parent) {
 835                 trie_string_append_char (keybuff, c);
 836                 return da_first_separate (d, base + c, keybuff);
 837             }
 838         }
 839
 840         sep = parent;
 841     }
 842
 843     return TRIE_INDEX_ERROR;
 844 }
 845
 846 /*
 847 vi:ts=4:ai:expandtab
 848 */