Debian Codegraph @

datrie/darray.c

raw
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 <[email protected]>
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 <[email protected]>
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 (void);
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 (void)
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 (void)
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 size_t
309 da_get_serialized_size (const DArray *d)
310 {
311 if (d->num_cells > 0)
312 return 4 * d->num_cells * 2; /* 'base' and 'check' */
313 else
314 return 0;
315 }
316
317
318 void
319 da_serialize (const DArray *d, uint8 **ptr)
320 {
321 TrieIndex i;
322
323 for (i = 0; i < d->num_cells; i++) {
324 serialize_int32_be_incr (ptr, d->cells[i].base);
325 serialize_int32_be_incr (ptr, d->cells[i].check);
326 }
327 }
328
329
330 /**
331 * @brief Get root state
332 *
333 * @param d : the double-array data
334 *
335 * @return root state of the @a index set, or TRIE_INDEX_ERROR on failure
336 *
337 * Get root state for stepwise walking.
338 */
339 TrieIndex
340 da_get_root (const DArray *d)
341 {
342 /* can be calculated value for multi-index trie */
343 return 2;
344 }
345
346
347 /**
348 * @brief Get BASE cell
349 *
350 * @param d : the double-array data
351 * @param s : the double-array state to get data
352 *
353 * @return the BASE cell value for the given state
354 *
355 * Get BASE cell value for the given state.
356 */
357 TrieIndex
358 da_get_base (const DArray *d, TrieIndex s)
359 {
360 return LIKELY (s < d->num_cells) ? d->cells[s].base : TRIE_INDEX_ERROR;
361 }
362
363 /**
364 * @brief Get CHECK cell
365 *
366 * @param d : the double-array data
367 * @param s : the double-array state to get data
368 *
369 * @return the CHECK cell value for the given state
370 *
371 * Get CHECK cell value for the given state.
372 */
373 TrieIndex
374 da_get_check (const DArray *d, TrieIndex s)
375 {
376 return LIKELY (s < d->num_cells) ? d->cells[s].check : TRIE_INDEX_ERROR;
377 }
378
379
380 /**
381 * @brief Set BASE cell
382 *
383 * @param d : the double-array data
384 * @param s : the double-array state to get data
385 * @param val : the value to set
386 *
387 * Set BASE cell for the given state to the given value.
388 */
389 void
390 da_set_base (DArray *d, TrieIndex s, TrieIndex val)
391 {
392 if (LIKELY (s < d->num_cells)) {
393 d->cells[s].base = val;
394 }
395 }
396
397 /**
398 * @brief Set CHECK cell
399 *
400 * @param d : the double-array data
401 * @param s : the double-array state to get data
402 * @param val : the value to set
403 *
404 * Set CHECK cell for the given state to the given value.
405 */
406 void
407 da_set_check (DArray *d, TrieIndex s, TrieIndex val)
408 {
409 if (LIKELY (s < d->num_cells)) {
410 d->cells[s].check = val;
411 }
412 }
413
414 /**
415 * @brief Walk in double-array structure
416 *
417 * @param d : the double-array structure
418 * @param s : current state
419 * @param c : the input character
420 *
421 * @return boolean indicating success
422 *
423 * Walk the double-array trie from state @a *s, using input character @a c.
424 * If there exists an edge from @a *s with arc labeled @a c, this function
425 * returns TRUE and @a *s is updated to the new state. Otherwise, it returns
426 * FALSE and @a *s is left unchanged.
427 */
428 Bool
429 da_walk (const DArray *d, TrieIndex *s, TrieChar c)
430 {
431 TrieIndex next;
432
433 next = da_get_base (d, *s) + c;
434 if (da_get_check (d, next) == *s) {
435 *s = next;
436 return TRUE;
437 }
438 return FALSE;
439 }
440
441 /**
442 * @brief Insert a branch from trie node
443 *
444 * @param d : the double-array structure
445 * @param s : the state to add branch to
446 * @param c : the character for the branch label
447 *
448 * @return the index of the new node
449 *
450 * Insert a new arc labelled with character @a c from the trie node
451 * represented by index @a s in double-array structure @a d.
452 * Note that it assumes that no such arc exists before inserting.
453 */
454 TrieIndex
455 da_insert_branch (DArray *d, TrieIndex s, TrieChar c)
456 {
457 TrieIndex base, next;
458
459 base = da_get_base (d, s);
460
461 if (base > 0) {
462 next = base + c;
463
464 /* if already there, do not actually insert */
465 if (da_get_check (d, next) == s)
466 return next;
467
468 /* if (base + c) > TRIE_INDEX_MAX which means 'next' is overflow,
469 * or cell [next] is not free, relocate to a free slot
470 */
471 if (base > TRIE_INDEX_MAX - c || !da_check_free_cell (d, next)) {
472 Symbols *symbols;
473 TrieIndex new_base;
474
475 /* relocate BASE[s] */
476 symbols = da_output_symbols (d, s);
477 symbols_add (symbols, c);
478 new_base = da_find_free_base (d, symbols);
479 symbols_free (symbols);
480
481 if (UNLIKELY (TRIE_INDEX_ERROR == new_base))
482 return TRIE_INDEX_ERROR;
483
484 da_relocate_base (d, s, new_base);
485 next = new_base + c;
486 }
487 } else {
488 Symbols *symbols;
489 TrieIndex new_base;
490
491 symbols = symbols_new ();
492 symbols_add (symbols, c);
493 new_base = da_find_free_base (d, symbols);
494 symbols_free (symbols);
495
496 if (UNLIKELY (TRIE_INDEX_ERROR == new_base))
497 return TRIE_INDEX_ERROR;
498
499 da_set_base (d, s, new_base);
500 next = new_base + c;
501 }
502 da_alloc_cell (d, next);
503 da_set_check (d, next, s);
504
505 return next;
506 }
507
508 static Bool
509 da_check_free_cell (DArray *d,
510 TrieIndex s)
511 {
512 return da_extend_pool (d, s) && da_get_check (d, s) < 0;
513 }
514
515 static Bool
516 da_has_children (const DArray *d,
517 TrieIndex s)
518 {
519 TrieIndex base;
520 TrieIndex c, max_c;
521
522 base = da_get_base (d, s);
523 if (TRIE_INDEX_ERROR == base || base < 0)
524 return FALSE;
525
526 max_c = MIN_VAL (TRIE_CHAR_MAX, d->num_cells - base);
527 for (c = 0; c <= max_c; c++) {
528 if (da_get_check (d, base + c) == s)
529 return TRUE;
530 }
531
532 return FALSE;
533 }
534
535 Symbols *
536 da_output_symbols (const DArray *d,
537 TrieIndex s)
538 {
539 Symbols *syms;
540 TrieIndex base;
541 TrieIndex c, max_c;
542
543 syms = symbols_new ();
544
545 base = da_get_base (d, s);
546 max_c = MIN_VAL (TRIE_CHAR_MAX, d->num_cells - base);
547 for (c = 0; c <= max_c; c++) {
548 if (da_get_check (d, base + c) == s)
549 symbols_add_fast (syms, (TrieChar) c);
550 }
551
552 return syms;
553 }
554
555 static TrieIndex
556 da_find_free_base (DArray *d,
557 const Symbols *symbols)
558 {
559 TrieChar first_sym;
560 TrieIndex s;
561
562 /* find first free cell that is beyond the first symbol */
563 first_sym = symbols_get (symbols, 0);
564 s = -da_get_check (d, da_get_free_list (d));
565 while (s != da_get_free_list (d)
566 && s < (TrieIndex) first_sym + DA_POOL_BEGIN)
567 {
568 s = -da_get_check (d, s);
569 }
570 if (s == da_get_free_list (d)) {
571 for (s = first_sym + DA_POOL_BEGIN; ; ++s) {
572 if (!da_extend_pool (d, s))
573 return TRIE_INDEX_ERROR;
574 if (da_get_check (d, s) < 0)
575 break;
576 }
577 }
578
579 /* search for next free cell that fits the symbols set */
580 while (!da_fit_symbols (d, s - first_sym, symbols)) {
581 /* extend pool before getting exhausted */
582 if (-da_get_check (d, s) == da_get_free_list (d)) {
583 if (UNLIKELY (!da_extend_pool (d, d->num_cells)))
584 return TRIE_INDEX_ERROR;
585 }
586
587 s = -da_get_check (d, s);
588 }
589
590 return s - first_sym;
591 }
592
593 static Bool
594 da_fit_symbols (DArray *d,
595 TrieIndex base,
596 const Symbols *symbols)
597 {
598 int i;
599
600 for (i = 0; i < symbols_num (symbols); i++) {
601 TrieChar sym = symbols_get (symbols, i);
602
603 /* if (base + sym) > TRIE_INDEX_MAX which means it's overflow,
604 * or cell [base + sym] is not free, the symbol is not fit.
605 */
606 if (base > TRIE_INDEX_MAX - sym || !da_check_free_cell (d, base + sym))
607 return FALSE;
608 }
609 return TRUE;
610 }
611
612 static void
613 da_relocate_base (DArray *d,
614 TrieIndex s,
615 TrieIndex new_base)
616 {
617 TrieIndex old_base;
618 Symbols *symbols;
619 int i;
620
621 old_base = da_get_base (d, s);
622 symbols = da_output_symbols (d, s);
623
624 for (i = 0; i < symbols_num (symbols); i++) {
625 TrieIndex old_next, new_next, old_next_base;
626
627 old_next = old_base + symbols_get (symbols, i);
628 new_next = new_base + symbols_get (symbols, i);
629 old_next_base = da_get_base (d, old_next);
630
631 /* allocate new next node and copy BASE value */
632 da_alloc_cell (d, new_next);
633 da_set_check (d, new_next, s);
634 da_set_base (d, new_next, old_next_base);
635
636 /* old_next node is now moved to new_next
637 * so, all cells belonging to old_next
638 * must be given to new_next
639 */
640 /* preventing the case of TAIL pointer */
641 if (old_next_base > 0) {
642 TrieIndex c, max_c;
643
644 max_c = MIN_VAL (TRIE_CHAR_MAX, d->num_cells - old_next_base);
645 for (c = 0; c <= max_c; c++) {
646 if (da_get_check (d, old_next_base + c) == old_next)
647 da_set_check (d, old_next_base + c, new_next);
648 }
649 }
650
651 /* free old_next node */
652 da_free_cell (d, old_next);
653 }
654
655 symbols_free (symbols);
656
657 /* finally, make BASE[s] point to new_base */
658 da_set_base (d, s, new_base);
659 }
660
661 static Bool
662 da_extend_pool (DArray *d,
663 TrieIndex to_index)
664 {
665 void *new_block;
666 TrieIndex new_begin;
667 TrieIndex i;
668 TrieIndex free_tail;
669
670 if (UNLIKELY (to_index <= 0 || TRIE_INDEX_MAX <= to_index))
671 return FALSE;
672
673 if (to_index < d->num_cells)
674 return TRUE;
675
676 new_block = realloc (d->cells, (to_index + 1) * sizeof (DACell));
677 if (UNLIKELY (!new_block))
678 return FALSE;
679
680 d->cells = (DACell *) new_block;
681 new_begin = d->num_cells;
682 d->num_cells = to_index + 1;
683
684 /* initialize new free list */
685 for (i = new_begin; i < to_index; i++) {
686 da_set_check (d, i, -(i + 1));
687 da_set_base (d, i + 1, -i);
688 }
689
690 /* merge the new circular list to the old */
691 free_tail = -da_get_base (d, da_get_free_list (d));
692 da_set_check (d, free_tail, -new_begin);
693 da_set_base (d, new_begin, -free_tail);
694 da_set_check (d, to_index, -da_get_free_list (d));
695 da_set_base (d, da_get_free_list (d), -to_index);
696
697 /* update header cell */
698 d->cells[0].check = d->num_cells;
699
700 return TRUE;
701 }
702
703 /**
704 * @brief Prune the single branch
705 *
706 * @param d : the double-array structure
707 * @param s : the dangling state to prune off
708 *
709 * Prune off a non-separate path up from the final state @a s.
710 * If @a s still has some children states, it does nothing. Otherwise,
711 * it deletes the node and all its parents which become non-separate.
712 */
713 void
714 da_prune (DArray *d, TrieIndex s)
715 {
716 da_prune_upto (d, da_get_root (d), s);
717 }
718
719 /**
720 * @brief Prune the single branch up to given parent
721 *
722 * @param d : the double-array structure
723 * @param p : the parent up to which to be pruned
724 * @param s : the dangling state to prune off
725 *
726 * Prune off a non-separate path up from the final state @a s to the
727 * given parent @a p. The prunning stop when either the parent @a p
728 * is met, or a first non-separate node is found.
729 */
730 void
731 da_prune_upto (DArray *d, TrieIndex p, TrieIndex s)
732 {
733 while (p != s && !da_has_children (d, s)) {
734 TrieIndex parent;
735
736 parent = da_get_check (d, s);
737 da_free_cell (d, s);
738 s = parent;
739 }
740 }
741
742 static void
743 da_alloc_cell (DArray *d,
744 TrieIndex cell)
745 {
746 TrieIndex prev, next;
747
748 prev = -da_get_base (d, cell);
749 next = -da_get_check (d, cell);
750
751 /* remove the cell from free list */
752 da_set_check (d, prev, -next);
753 da_set_base (d, next, -prev);
754 }
755
756 static void
757 da_free_cell (DArray *d,
758 TrieIndex cell)
759 {
760 TrieIndex i, prev;
761
762 /* find insertion point */
763 i = -da_get_check (d, da_get_free_list (d));
764 while (i != da_get_free_list (d) && i < cell)
765 i = -da_get_check (d, i);
766
767 prev = -da_get_base (d, i);
768
769 /* insert cell before i */
770 da_set_check (d, cell, -i);
771 da_set_base (d, cell, -prev);
772 da_set_check (d, prev, -cell);
773 da_set_base (d, i, -cell);
774 }
775
776 /**
777 * @brief Find first separate node in a sub-trie
778 *
779 * @param d : the double-array structure
780 * @param root : the sub-trie root to search from
781 * @param keybuff : the TrieString buffer for incrementally calcuating key
782 *
783 * @return index to the first separate node; TRIE_INDEX_ERROR on any failure
784 *
785 * Find the first separate node under a sub-trie rooted at @a root.
786 *
787 * On return, @a keybuff is appended with the key characters which walk from
788 * @a root to the separate node. This is for incrementally calculating the
789 * transition key, which is more efficient than later totally reconstructing
790 * key from the given separate node.
791 *
792 * Available since: 0.2.6
793 */
794 TrieIndex
795 da_first_separate (DArray *d, TrieIndex root, TrieString *keybuff)
796 {
797 TrieIndex base;
798 TrieIndex c, max_c;
799
800 while ((base = da_get_base (d, root)) >= 0) {
801 max_c = MIN_VAL (TRIE_CHAR_MAX, d->num_cells - base);
802 for (c = 0; c <= max_c; c++) {
803 if (da_get_check (d, base + c) == root)
804 break;
805 }
806
807 if (c > max_c)
808 return TRIE_INDEX_ERROR;
809
810 trie_string_append_char (keybuff, c);
811 root = base + c;
812 }
813
814 return root;
815 }
816
817 /**
818 * @brief Find next separate node in a sub-trie
819 *
820 * @param d : the double-array structure
821 * @param root : the sub-trie root to search from
822 * @param sep : the current separate node
823 * @param keybuff : the TrieString buffer for incrementally calcuating key
824 *
825 * @return index to the next separate node; TRIE_INDEX_ERROR if no more
826 * separate node is found
827 *
828 * Find the next separate node under a sub-trie rooted at @a root starting
829 * from the current separate node @a sep.
830 *
831 * On return, @a keybuff is incrementally updated from the key which walks
832 * to previous separate node to the one which walks to the new separate node.
833 * So, it is assumed to be initialized by at least one da_first_separate()
834 * call before. This incremental key calculation is more efficient than later
835 * totally reconstructing key from the given separate node.
836 *
837 * Available since: 0.2.6
838 */
839 TrieIndex
840 da_next_separate (DArray *d, TrieIndex root, TrieIndex sep, TrieString *keybuff)
841 {
842 TrieIndex parent;
843 TrieIndex base;
844 TrieIndex c, max_c;
845
846 while (sep != root) {
847 parent = da_get_check (d, sep);
848 base = da_get_base (d, parent);
849 c = sep - base;
850
851 trie_string_cut_last (keybuff);
852
853 /* find next sibling of sep */
854 max_c = MIN_VAL (TRIE_CHAR_MAX, d->num_cells - base);
855 while (++c <= max_c) {
856 if (da_get_check (d, base + c) == parent) {
857 trie_string_append_char (keybuff, c);
858 return da_first_separate (d, base + c, keybuff);
859 }
860 }
861
862 sep = parent;
863 }
864
865 return TRIE_INDEX_ERROR;
866 }
867
868 /*
869 vi:ts=4:ai:expandtab
870 */