2 Copyright (C) 1989-1998, 2000, 2002 Free Software Foundation, Inc.
3 Written by Douglas C. Schmidt <schmidt@ics.uci.edu>
4 and Bruno Haible <bruno@clisp.org>.
6 This file is part of GNU GPERF.
8 GNU GPERF is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU GPERF is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; see the file COPYING.
20 If not, write to the Free Software Foundation, Inc.,
21 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
27 #include <stdlib.h> /* declares exit(), rand(), srand() */
28 #include <string.h> /* declares memset(), memcmp() */
29 #include <time.h> /* declares time() */
30 #include <math.h> /* declares exp() */
31 #include <limits.h> /* defines INT_MIN, INT_MAX, UINT_MAX */
33 #include "hash-table.h"
36 /* ============================== Portability ============================== */
38 /* Assume ISO C++ 'for' scoping rule. */
39 /* This code is used to work around scoping issues with visual studio 6 from
40 * 1998. Comment it out here to queisce numerous -Wdangling-else warnings
42 #define for if (0) ; else for */
44 /* Dynamically allocated array with dynamic extent:
47 DYNAMIC_ARRAY (my_array, int, n);
49 FREE_DYNAMIC_ARRAY (my_array);
51 Attention: depending on your implementation my_array is either the array
52 itself or a pointer to the array! Always use my_array only as expression!
54 #if HAVE_DYNAMIC_ARRAY
55 #define DYNAMIC_ARRAY(var,eltype,size) eltype var[size]
56 #define FREE_DYNAMIC_ARRAY(var)
58 #define DYNAMIC_ARRAY(var,eltype,size) eltype *var = new eltype[size]
59 #define FREE_DYNAMIC_ARRAY(var) delete[] var
62 /* ================================ Theory ================================= */
64 /* The general form of the hash function is
66 hash (keyword) = sum (asso_values[keyword[i] + alpha_inc[i]] : i in Pos)
69 where Pos is a set of byte positions,
70 each alpha_inc[i] is a nonnegative integer,
71 each asso_values[c] is a nonnegative integer,
72 len (keyword) is the keyword's length if !option[NOLENGTH], or 0 otherwise.
74 Theorem 1: If all keywords are different, there is a set Pos such that
75 all tuples (keyword[i] : i in Pos) are different.
77 Theorem 2: If all tuples (keyword[i] : i in Pos) are different, there
78 are nonnegative integers alpha_inc[i] such that all multisets
79 {keyword[i] + alpha_inc[i] : i in Pos} are different.
81 Define selchars[keyword] := {keyword[i] + alpha_inc[i] : i in Pos}.
83 Theorem 3: If all multisets selchars[keyword] are different, there are
84 nonnegative integers asso_values[c] such that all hash values
85 sum (asso_values[c] : c in selchars[keyword]) are different.
87 Based on these three facts, we find the hash function in three steps:
89 Step 1 (Finding good byte positions):
90 Find a set Pos, as small as possible, such that all tuples
91 (keyword[i] : i in Pos) are different.
93 Step 2 (Finding good alpha increments):
94 Find nonnegative integers alpha_inc[i], as many of them as possible being
95 zero, and the others being as small as possible, such that all multisets
96 {keyword[i] + alpha_inc[i] : i in Pos} are different.
98 Step 3 (Finding good asso_values):
99 Find asso_values[c] such that all hash (keyword) are different.
101 In other words, each step finds a projection that is injective on the
103 proj1 : String --> Map (Pos --> N)
104 proj2 : Map (Pos --> N) --> Map (Pos --> N) / S(Pos)
105 proj3 : Map (Pos --> N) / S(Pos) --> N
107 N denotes the set of nonnegative integers,
108 Map (A --> B) := Hom_Set (A, B) is the set of maps from A to B, and
109 S(Pos) is the symmetric group over Pos.
111 This was the theory for option[NOLENGTH]; if !option[NOLENGTH], slight
113 proj1 : String --> Map (Pos --> N) x N
114 proj2 : Map (Pos --> N) x N --> Map (Pos --> N) / S(Pos) x N
115 proj3 : Map (Pos --> N) / S(Pos) x N --> N
117 For a case-insensitive hash function, the general form is
120 sum (asso_values[alpha_unify[keyword[i] + alpha_inc[i]]] : i in Pos)
123 where alpha_unify[c] is chosen so that an upper/lower case change in
124 keyword[i] doesn't change alpha_unify[keyword[i] + alpha_inc[i]].
127 /* ==================== Initialization and Preparation ===================== */
129 Search::Search (KeywordExt_List *list)
137 /* Compute the total number of keywords. */
139 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
142 /* Compute the minimum and maximum keyword length. */
143 _max_key_len = INT_MIN;
144 _min_key_len = INT_MAX;
145 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
147 KeywordExt *keyword = temp->first();
149 if (_max_key_len < keyword->_allchars_length)
150 _max_key_len = keyword->_allchars_length;
151 if (_min_key_len > keyword->_allchars_length)
152 _min_key_len = keyword->_allchars_length;
155 /* Exit program if an empty string is used as keyword, since the comparison
156 expressions don't work correctly for looking up an empty string. */
157 if (_min_key_len == 0)
159 fprintf (stderr, "Empty input keyword is not allowed.\n"
160 "To recognize an empty input keyword, your code should check for\n"
161 "len == 0 before calling the gperf generated lookup function.\n");
165 /* Exit program if the characters in the keywords are not in the required
167 if (option[SEVENBIT])
168 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
170 KeywordExt *keyword = temp->first();
172 const char *k = keyword->_allchars;
173 for (int i = keyword->_allchars_length; i > 0; k++, i--)
174 if (!(static_cast<unsigned char>(*k) < 128))
176 fprintf (stderr, "Option --seven-bit has been specified,\n"
177 "but keyword \"%.*s\" contains non-ASCII characters.\n"
178 "Try removing option --seven-bit.\n",
179 keyword->_allchars_length, keyword->_allchars);
185 /* ====================== Finding good byte positions ====================== */
187 /* Computes the upper bound on the indices passed to asso_values[],
188 assuming no alpha_increments. */
190 Search::compute_alpha_size () const
192 return (option[SEVENBIT] ? 128 : 256);
195 /* Computes the unification rules between different asso_values[c],
196 assuming no alpha_increments. */
198 Search::compute_alpha_unify () const
200 if (option[UPPERLOWER])
202 /* Uppercase to lowercase mapping. */
203 unsigned int alpha_size = compute_alpha_size();
204 unsigned int *alpha_unify = new unsigned int[alpha_size];
205 for (unsigned int c = 0; c < alpha_size; c++)
207 for (unsigned int c = 'A'; c <= 'Z'; c++)
208 alpha_unify[c] = c + ('a'-'A');
212 /* Identity mapping. */
216 /* Initializes each keyword's _selchars array. */
218 Search::init_selchars_tuple (const Positions& positions, const unsigned int *alpha_unify) const
220 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
221 temp->first()->init_selchars_tuple(positions, alpha_unify);
224 /* Deletes each keyword's _selchars array. */
226 Search::delete_selchars () const
228 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
229 temp->first()->delete_selchars();
232 /* Count the duplicate keywords that occur with a given set of positions.
233 In other words, it returns the difference
235 where K is the multiset of given keywords. */
237 Search::count_duplicates_tuple (const Positions& positions, const unsigned int *alpha_unify) const
239 /* Run through the keyword list and count the duplicates incrementally.
240 The result does not depend on the order of the keyword list, thanks to
241 the formula above. */
242 init_selchars_tuple (positions, alpha_unify);
244 unsigned int count = 0;
246 Hash_Table representatives (_total_keys, option[NOLENGTH]);
247 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
249 KeywordExt *keyword = temp->first();
250 if (representatives.insert (keyword))
260 /* Find good key positions. */
263 Search::find_positions ()
265 /* If the user gave the key positions, we use them. */
266 if (option[POSITIONS])
268 _key_positions = option.get_key_positions();
272 /* Compute preliminary alpha_unify table. */
273 unsigned int *alpha_unify = compute_alpha_unify ();
275 /* 1. Find positions that must occur in order to distinguish duplicates. */
280 for (KeywordExt_List *l1 = _head; l1 && l1->rest(); l1 = l1->rest())
282 KeywordExt *keyword1 = l1->first();
283 for (KeywordExt_List *l2 = l1->rest(); l2; l2 = l2->rest())
285 KeywordExt *keyword2 = l2->first();
287 /* If keyword1 and keyword2 have the same length and differ
288 in just one position, and it is not the last character,
289 this position is mandatory. */
290 if (keyword1->_allchars_length == keyword2->_allchars_length)
292 int n = keyword1->_allchars_length;
294 for (i = 0; i < n - 1; i++)
296 unsigned char c1 = keyword1->_allchars[i];
297 unsigned char c2 = keyword2->_allchars[i];
298 if (option[UPPERLOWER])
300 if (c1 >= 'A' && c1 <= 'Z')
302 if (c2 >= 'A' && c2 <= 'Z')
311 for (j = i + 1; j < n; j++)
313 unsigned char c1 = keyword1->_allchars[j];
314 unsigned char c2 = keyword2->_allchars[j];
315 if (option[UPPERLOWER])
317 if (c1 >= 'A' && c1 <= 'Z')
319 if (c2 >= 'A' && c2 <= 'Z')
327 /* Position i is mandatory. */
328 if (!mandatory.contains (i))
337 /* 2. Add positions, as long as this decreases the duplicates count. */
338 int imax = (_max_key_len - 1 < Positions::MAX_KEY_POS - 1
339 ? _max_key_len - 1 : Positions::MAX_KEY_POS - 1);
340 Positions current = mandatory;
341 unsigned int current_duplicates_count =
342 count_duplicates_tuple (current, alpha_unify);
346 unsigned int best_duplicates_count = UINT_MAX;
348 for (int i = imax; i >= -1; i--)
349 if (!current.contains (i))
351 Positions tryal = current;
353 unsigned int try_duplicates_count =
354 count_duplicates_tuple (tryal, alpha_unify);
356 /* We prefer 'try' to 'best' if it produces less duplicates,
357 or if it produces the same number of duplicates but with
358 a more efficient hash function. */
359 if (try_duplicates_count < best_duplicates_count
360 || (try_duplicates_count == best_duplicates_count && i >= 0))
363 best_duplicates_count = try_duplicates_count;
367 /* Stop adding positions when it gives no improvement. */
368 if (best_duplicates_count >= current_duplicates_count)
372 current_duplicates_count = best_duplicates_count;
375 /* 3. Remove positions, as long as this doesn't increase the duplicates
380 unsigned int best_duplicates_count = UINT_MAX;
382 for (int i = imax; i >= -1; i--)
383 if (current.contains (i) && !mandatory.contains (i))
385 Positions tryal = current;
387 unsigned int try_duplicates_count =
388 count_duplicates_tuple (tryal, alpha_unify);
390 /* We prefer 'try' to 'best' if it produces less duplicates,
391 or if it produces the same number of duplicates but with
392 a more efficient hash function. */
393 if (try_duplicates_count < best_duplicates_count
394 || (try_duplicates_count == best_duplicates_count && i == -1))
397 best_duplicates_count = try_duplicates_count;
401 /* Stop removing positions when it gives no improvement. */
402 if (best_duplicates_count > current_duplicates_count)
406 current_duplicates_count = best_duplicates_count;
409 /* 4. Replace two positions by one, as long as this doesn't increase the
414 unsigned int best_duplicates_count = UINT_MAX;
416 for (int i1 = imax; i1 >= -1; i1--)
417 if (current.contains (i1) && !mandatory.contains (i1))
418 for (int i2 = imax; i2 >= -1; i2--)
419 if (current.contains (i2) && !mandatory.contains (i2) && i2 != i1)
420 for (int i3 = imax; i3 >= 0; i3--)
421 if (!current.contains (i3))
423 Positions tryal = current;
427 unsigned int try_duplicates_count =
428 count_duplicates_tuple (tryal, alpha_unify);
430 /* We prefer 'try' to 'best' if it produces less duplicates,
431 or if it produces the same number of duplicates but with
432 a more efficient hash function. */
433 if (try_duplicates_count < best_duplicates_count
434 || (try_duplicates_count == best_duplicates_count
435 && (i1 == -1 || i2 == -1 || i3 >= 0)))
438 best_duplicates_count = try_duplicates_count;
442 /* Stop removing positions when it gives no improvement. */
443 if (best_duplicates_count > current_duplicates_count)
447 current_duplicates_count = best_duplicates_count;
450 /* That's it. Hope it's good enough. */
451 _key_positions = current;
455 /* Print the result. */
456 fprintf (stderr, "\nComputed positions: ");
457 PositionReverseIterator iter = _key_positions.reviterator();
458 bool seen_lastchar = false;
460 for (int i; (i = iter.next ()) != PositionReverseIterator::EOS; )
463 fprintf (stderr, ", ");
464 if (i == Positions::LASTCHAR)
465 seen_lastchar = true;
468 fprintf (stderr, "%d", i + 1);
475 fprintf (stderr, ", ");
476 fprintf (stderr, "$");
478 fprintf (stderr, "\n");
481 /* Free preliminary alpha_unify table. */
482 delete[] alpha_unify;
485 /* Count the duplicate keywords that occur with the found set of positions.
486 In other words, it returns the difference
488 where K is the multiset of given keywords. */
490 Search::count_duplicates_tuple () const
492 unsigned int *alpha_unify = compute_alpha_unify ();
493 unsigned int count = count_duplicates_tuple (_key_positions, alpha_unify);
494 delete[] alpha_unify;
498 /* ===================== Finding good alpha increments ===================== */
500 /* Computes the upper bound on the indices passed to asso_values[]. */
502 Search::compute_alpha_size (const unsigned int *alpha_inc) const
504 unsigned int max_alpha_inc = 0;
505 for (int i = 0; i < _max_key_len; i++)
506 if (max_alpha_inc < alpha_inc[i])
507 max_alpha_inc = alpha_inc[i];
508 return (option[SEVENBIT] ? 128 : 256) + max_alpha_inc;
511 /* Computes the unification rules between different asso_values[c]. */
513 Search::compute_alpha_unify (const Positions& positions, const unsigned int *alpha_inc) const
515 if (option[UPPERLOWER])
517 /* Without alpha increments, we would simply unify
518 'A' -> 'a', ..., 'Z' -> 'z'.
519 But when a keyword contains at position i a character c,
520 we have the constraint
521 asso_values[tolower(c) + alpha_inc[i]] ==
522 asso_values[toupper(c) + alpha_inc[i]].
523 This introduces a unification
524 toupper(c) + alpha_inc[i] -> tolower(c) + alpha_inc[i].
525 Note that this unification can extend outside the range of
526 ASCII letters! But still every unified character pair is at
527 a distance of 'a'-'A' = 32, or (after chained unification)
528 at a multiple of 32. So in the end the alpha_unify vector has
529 the form c -> c + 32 * f(c) where f(c) is a nonnegative
531 unsigned int alpha_size = compute_alpha_size (alpha_inc);
533 unsigned int *alpha_unify = new unsigned int[alpha_size];
534 for (unsigned int c = 0; c < alpha_size; c++)
537 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
539 KeywordExt *keyword = temp->first();
541 /* Iterate through the selected character positions. */
542 PositionIterator iter = positions.iterator(keyword->_allchars_length);
544 for (int i; (i = iter.next ()) != PositionIterator::EOS; )
547 if (i == Positions::LASTCHAR)
548 c = static_cast<unsigned char>(keyword->_allchars[keyword->_allchars_length - 1]);
549 else if (i < keyword->_allchars_length)
550 c = static_cast<unsigned char>(keyword->_allchars[i]);
553 if (c >= 'A' && c <= 'Z')
555 if (c >= 'a' && c <= 'z')
557 if (i != Positions::LASTCHAR)
559 /* Unify c with c - ('a'-'A'). */
560 unsigned int d = alpha_unify[c];
561 unsigned int b = c - ('a'-'A');
562 for (int a = b; a >= 0 && alpha_unify[a] == b; a -= ('a'-'A'))
570 /* Identity mapping. */
574 /* Initializes each keyword's _selchars array. */
576 Search::init_selchars_multiset (const Positions& positions, const unsigned int *alpha_unify, const unsigned int *alpha_inc) const
578 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
579 temp->first()->init_selchars_multiset(positions, alpha_unify, alpha_inc);
582 /* Count the duplicate keywords that occur with the given set of positions
583 and a given alpha_inc[] array.
584 In other words, it returns the difference
585 # K - # proj2 (proj1 (K))
586 where K is the multiset of given keywords. */
588 Search::count_duplicates_multiset (const unsigned int *alpha_inc) const
590 /* Run through the keyword list and count the duplicates incrementally.
591 The result does not depend on the order of the keyword list, thanks to
592 the formula above. */
593 unsigned int *alpha_unify = compute_alpha_unify (_key_positions, alpha_inc);
594 init_selchars_multiset (_key_positions, alpha_unify, alpha_inc);
596 unsigned int count = 0;
598 Hash_Table representatives (_total_keys, option[NOLENGTH]);
599 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
601 KeywordExt *keyword = temp->first();
602 if (representatives.insert (keyword))
608 delete[] alpha_unify;
613 /* Find good _alpha_inc[]. */
616 Search::find_alpha_inc ()
618 /* The goal is to choose _alpha_inc[] such that it doesn't introduce
619 artificial duplicates.
620 In other words, the goal is # proj2 (proj1 (K)) = # proj1 (K). */
621 unsigned int duplicates_goal = count_duplicates_tuple ();
623 /* Start with zero increments. This is sufficient in most cases. */
624 unsigned int *current = new unsigned int [_max_key_len];
625 for (int i = 0; i < _max_key_len; i++)
627 unsigned int current_duplicates_count = count_duplicates_multiset (current);
629 if (current_duplicates_count > duplicates_goal)
631 /* Look which _alpha_inc[i] we are free to increment. */
632 unsigned int nindices;
635 PositionIterator iter = _key_positions.iterator(_max_key_len);
638 int key_pos = iter.next ();
639 if (key_pos == PositionIterator::EOS)
641 if (key_pos != Positions::LASTCHAR)
646 DYNAMIC_ARRAY (indices, unsigned int, nindices);
649 PositionIterator iter = _key_positions.iterator(_max_key_len);
652 int key_pos = iter.next ();
653 if (key_pos == PositionIterator::EOS)
655 if (key_pos != Positions::LASTCHAR)
656 indices[j++] = key_pos;
658 if (!(j == nindices))
662 /* Perform several rounds of searching for a good alpha increment.
663 Each round reduces the number of artificial collisions by adding
664 an increment in a single key position. */
665 DYNAMIC_ARRAY (best, unsigned int, _max_key_len);
666 DYNAMIC_ARRAY (tryal, unsigned int, _max_key_len);
669 /* An increment of 1 is not always enough. Try higher increments
671 for (unsigned int inc = 1; ; inc++)
673 unsigned int best_duplicates_count = UINT_MAX;
675 for (unsigned int j = 0; j < nindices; j++)
677 memcpy (tryal, current, _max_key_len * sizeof (unsigned int));
678 tryal[indices[j]] += inc;
679 unsigned int try_duplicates_count =
680 count_duplicates_multiset (tryal);
682 /* We prefer 'try' to 'best' if it produces less
684 if (try_duplicates_count < best_duplicates_count)
686 memcpy (best, tryal, _max_key_len * sizeof (unsigned int));
687 best_duplicates_count = try_duplicates_count;
691 /* Stop this round when we got an improvement. */
692 if (best_duplicates_count < current_duplicates_count)
694 memcpy (current, best, _max_key_len * sizeof (unsigned int));
695 current_duplicates_count = best_duplicates_count;
700 while (current_duplicates_count > duplicates_goal);
701 FREE_DYNAMIC_ARRAY (tryal);
702 FREE_DYNAMIC_ARRAY (best);
706 /* Print the result. */
707 fprintf (stderr, "\nComputed alpha increments: ");
709 for (unsigned int j = nindices; j-- > 0; )
710 if (current[indices[j]] != 0)
713 fprintf (stderr, ", ");
714 fprintf (stderr, "%u:+%u",
715 indices[j] + 1, current[indices[j]]);
718 fprintf (stderr, "\n");
720 FREE_DYNAMIC_ARRAY (indices);
723 _alpha_inc = current;
724 _alpha_size = compute_alpha_size (_alpha_inc);
725 _alpha_unify = compute_alpha_unify (_key_positions, _alpha_inc);
728 /* ======================= Finding good asso_values ======================== */
730 /* Initializes the asso_values[] related parameters. */
733 Search::prepare_asso_values ()
735 KeywordExt_List *temp;
737 /* Initialize each keyword's _selchars array. */
738 init_selchars_multiset(_key_positions, _alpha_unify, _alpha_inc);
740 /* Compute the maximum _selchars_length over all keywords. */
741 _max_selchars_length = _key_positions.iterator(_max_key_len).remaining();
743 /* Check for duplicates, i.e. keywords with the same _selchars array
744 (and - if !option[NOLENGTH] - also the same length).
745 We deal with these by building an equivalence class, so that only
746 1 keyword is representative of the entire collection. Only this
747 representative remains in the keyword list; the others are accessible
748 through the _duplicate_link chain, starting at the representative.
749 This *greatly* simplifies processing during later stages of the program.
750 Set _total_duplicates and _list_len = _total_keys - _total_duplicates. */
752 _list_len = _total_keys;
753 _total_duplicates = 0;
754 /* Make hash table for efficiency. */
755 Hash_Table representatives (_list_len, option[NOLENGTH]);
757 KeywordExt_List *prev = NULL; /* list node before temp */
758 for (temp = _head; temp; )
760 KeywordExt *keyword = temp->first();
761 KeywordExt *other_keyword = representatives.insert (keyword);
762 KeywordExt_List *garbage = NULL;
768 /* Remove keyword from the main list. */
769 prev->rest() = temp->rest();
771 /* And insert it on other_keyword's duplicate list. */
772 keyword->_duplicate_link = other_keyword->_duplicate_link;
773 other_keyword->_duplicate_link = keyword;
775 /* Complain if user hasn't enabled the duplicate option. */
776 if (!option[DUP] || option[DEBUG])
778 fprintf (stderr, "Key link: \"%.*s\" = \"%.*s\", with key set \"",
779 keyword->_allchars_length, keyword->_allchars,
780 other_keyword->_allchars_length, other_keyword->_allchars);
781 for (int j = 0; j < keyword->_selchars_length; j++)
782 putc (keyword->_selchars[j], stderr);
783 fprintf (stderr, "\".\n");
788 keyword->_duplicate_link = NULL;
796 representatives.dump();
799 /* Exit program if duplicates exists and option[DUP] not set, since we
800 don't want to continue in this case. (We don't want to turn on
801 option[DUP] implicitly, because the generated code is usually much
803 if (_total_duplicates)
806 fprintf (stderr, "%d input keys have identical hash values, examine output carefully...\n",
810 fprintf (stderr, "%d input keys have identical hash values,\n",
812 if (option[POSITIONS])
813 fprintf (stderr, "try different key positions or use option -D.\n");
815 fprintf (stderr, "use option -D.\n");
820 /* Compute the occurrences of each character in the alphabet. */
821 _occurrences = new int[_alpha_size];
822 memset (_occurrences, 0, _alpha_size * sizeof (_occurrences[0]));
823 for (temp = _head; temp; temp = temp->rest())
825 KeywordExt *keyword = temp->first();
826 const unsigned int *ptr = keyword->_selchars;
827 for (int count = keyword->_selchars_length; count > 0; ptr++, count--)
828 _occurrences[*ptr]++;
831 /* Memory allocation. */
832 _asso_values = new int[_alpha_size];
834 int non_linked_length = _list_len;
835 unsigned int asso_value_max;
838 static_cast<unsigned int>(non_linked_length * option.get_size_multiple());
839 /* Round up to the next power of two. This makes it easy to ensure
840 an _asso_value[c] is >= 0 and < asso_value_max. Also, the jump value
841 being odd, it guarantees that Search::try_asso_value() will iterate
842 through different values for _asso_value[c]. */
843 if (asso_value_max == 0)
845 asso_value_max |= asso_value_max >> 1;
846 asso_value_max |= asso_value_max >> 2;
847 asso_value_max |= asso_value_max >> 4;
848 asso_value_max |= asso_value_max >> 8;
849 asso_value_max |= asso_value_max >> 16;
851 _asso_value_max = asso_value_max;
853 /* Given the bound for _asso_values[c], we have a bound for the possible
854 hash values, as computed in compute_hash(). */
855 _max_hash_value = (option[NOLENGTH] ? 0 : _max_key_len)
856 + (_asso_value_max - 1) * _max_selchars_length;
857 /* Allocate a sparse bit vector for detection of collisions of hash
859 _collision_detector = new Bool_Array (_max_hash_value + 1);
863 fprintf (stderr, "total non-linked keys = %d\nmaximum associated value is %d"
864 "\nmaximum size of generated hash table is %d\n",
865 non_linked_length, asso_value_max, _max_hash_value);
871 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
873 KeywordExt *keyword = temp->first();
874 if (field_width < keyword->_selchars_length)
875 field_width = keyword->_selchars_length;
879 fprintf (stderr, "\ndumping the keyword list without duplicates\n");
880 fprintf (stderr, "keyword #, %*s, keyword\n", field_width, "keysig");
882 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
884 KeywordExt *keyword = temp->first();
885 fprintf (stderr, "%9d, ", ++i);
886 if (field_width > keyword->_selchars_length)
887 fprintf (stderr, "%*s", field_width - keyword->_selchars_length, "");
888 for (int j = 0; j < keyword->_selchars_length; j++)
889 putc (keyword->_selchars[j], stderr);
890 fprintf (stderr, ", %.*s\n",
891 keyword->_allchars_length, keyword->_allchars);
893 fprintf (stderr, "\nend of keyword list\n\n");
896 if (option[RANDOM] || option.get_jump () == 0)
897 /* We will use rand(), so initialize the random number generator. */
898 srand (static_cast<long>(time (0)));
900 _initial_asso_value = (option[RANDOM] ? -1 : option.get_initial_asso_value ());
901 _jump = option.get_jump ();
904 /* Finds some _asso_values[] that fit. */
906 /* The idea is to choose the _asso_values[] one by one, in a way that
907 a choice that has been made never needs to be undone later. This
908 means that we split the work into several steps. Each step chooses
909 one or more _asso_values[c]. The result of choosing one or more
910 _asso_values[c] is that the partitioning of the keyword set gets
912 Look at this partitioning: After every step, the _asso_values[] of a
913 certain set C of characters are undetermined. (At the beginning, C
914 is the set of characters c with _occurrences[c] > 0. At the end, C
915 is empty.) To each keyword K, we associate the multiset of _selchars
916 for which the _asso_values[] are undetermined:
917 K --> K->_selchars intersect C.
918 Consider two keywords equivalent if their value under this mapping is
919 the same. This introduces an equivalence relation on the set of
920 keywords. The equivalence classes partition the keyword set. (At the
921 beginning, the partition is the finest possible: each K is an equivalence
922 class by itself, because all K have a different _selchars. At the end,
923 all K have been merged into a single equivalence class.)
924 The partition before a step is always a refinement of the partition
926 We choose the steps in such a way that the partition really becomes
927 broader at each step. (A step that only chooses an _asso_values[c]
928 without changing the partition is better merged with the previous step,
929 to avoid useless backtracking.) */
931 struct EquivalenceClass
933 /* The keywords in this equivalence class. */
934 KeywordExt_List * _keywords;
935 KeywordExt_List * _keywords_last;
936 /* The number of keywords in this equivalence class. */
937 unsigned int _cardinality;
938 /* The undetermined selected characters for the keywords in this
939 equivalence class, as a canonically reordered multiset. */
940 unsigned int * _undetermined_chars;
941 unsigned int _undetermined_chars_length;
943 EquivalenceClass * _next;
948 /* The characters whose values are being determined in this step. */
949 unsigned int _changing_count;
950 unsigned int * _changing;
951 /* Exclusive upper bound for the _asso_values[c] of this step.
953 unsigned int _asso_value_max;
954 /* The characters whose values will be determined after this step. */
955 bool * _undetermined;
956 /* The keyword set partition after this step. */
957 EquivalenceClass * _partition;
958 /* The expected number of iterations in this step. */
959 double _expected_lower;
960 double _expected_upper;
966 equals (const unsigned int *ptr1, const unsigned int *ptr2, unsigned int len)
980 Search::compute_partition (bool *undetermined) const
982 EquivalenceClass *partition = NULL;
983 EquivalenceClass *partition_last = NULL;
984 for (KeywordExt_List *temp = _head; temp; temp = temp->rest())
986 KeywordExt *keyword = temp->first();
988 /* Compute the undetermined characters for this keyword. */
989 unsigned int *undetermined_chars =
990 new unsigned int[keyword->_selchars_length];
991 unsigned int undetermined_chars_length = 0;
993 for (int i = 0; i < keyword->_selchars_length; i++)
994 if (undetermined[keyword->_selchars[i]])
995 undetermined_chars[undetermined_chars_length++] = keyword->_selchars[i];
997 /* Look up the equivalence class to which this keyword belongs. */
998 EquivalenceClass *equclass;
999 for (equclass = partition; equclass; equclass = equclass->_next)
1000 if (equclass->_undetermined_chars_length == undetermined_chars_length
1001 && equals (equclass->_undetermined_chars, undetermined_chars,
1002 undetermined_chars_length))
1004 if (equclass == NULL)
1006 equclass = new EquivalenceClass();
1007 equclass->_keywords = NULL;
1008 equclass->_keywords_last = NULL;
1009 equclass->_cardinality = 0;
1010 equclass->_undetermined_chars = undetermined_chars;
1011 equclass->_undetermined_chars_length = undetermined_chars_length;
1012 equclass->_next = NULL;
1014 partition_last->_next = equclass;
1016 partition = equclass;
1017 partition_last = equclass;
1020 delete[] undetermined_chars;
1022 /* Add the keyword to the equivalence class. */
1023 KeywordExt_List *cons = new KeywordExt_List(keyword);
1024 if (equclass->_keywords)
1025 equclass->_keywords_last->rest() = cons;
1027 equclass->_keywords = cons;
1028 equclass->_keywords_last = cons;
1029 equclass->_cardinality++;
1032 /* Free some of the allocated memory. The caller doesn't need it. */
1033 for (EquivalenceClass *cls = partition; cls; cls = cls->_next)
1034 delete[] cls->_undetermined_chars;
1040 delete_partition (EquivalenceClass *partition)
1042 while (partition != NULL)
1044 EquivalenceClass *equclass = partition;
1045 partition = equclass->_next;
1046 delete_list (equclass->_keywords);
1047 //delete[] equclass->_undetermined_chars; // already freed above
1052 /* Compute the possible number of collisions when _asso_values[c] is
1053 chosen, leading to the given partition. */
1055 Search::count_possible_collisions (EquivalenceClass *partition, unsigned int c) const
1057 /* Every equivalence class p is split according to the frequency of
1058 occurrence of c, leading to equivalence classes p1, p2, ...
1059 This leads to (|p|^2 - |p1|^2 - |p2|^2 - ...)/2 possible collisions.
1060 Return the sum of this expression over all equivalence classes. */
1061 unsigned int sum = 0;
1062 unsigned int m = _max_selchars_length;
1063 DYNAMIC_ARRAY (split_cardinalities, unsigned int, m + 1);
1064 for (EquivalenceClass *cls = partition; cls; cls = cls->_next)
1066 for (unsigned int i = 0; i <= m; i++)
1067 split_cardinalities[i] = 0;
1069 for (KeywordExt_List *temp = cls->_keywords; temp; temp = temp->rest())
1071 KeywordExt *keyword = temp->first();
1073 unsigned int count = 0;
1074 for (int i = 0; i < keyword->_selchars_length; i++)
1075 if (keyword->_selchars[i] == c)
1078 split_cardinalities[count]++;
1081 sum += cls->_cardinality * cls->_cardinality;
1082 for (unsigned int i = 0; i <= m; i++)
1083 sum -= split_cardinalities[i] * split_cardinalities[i];
1085 FREE_DYNAMIC_ARRAY (split_cardinalities);
1089 /* Test whether adding c to the undetermined characters changes the given
1092 Search::unchanged_partition (EquivalenceClass *partition, unsigned int c) const
1094 for (EquivalenceClass *cls = partition; cls; cls = cls->_next)
1096 unsigned int first_count = UINT_MAX;
1098 for (KeywordExt_List *temp = cls->_keywords; temp; temp = temp->rest())
1100 KeywordExt *keyword = temp->first();
1102 unsigned int count = 0;
1103 for (int i = 0; i < keyword->_selchars_length; i++)
1104 if (keyword->_selchars[i] == c)
1107 if (temp == cls->_keywords)
1108 first_count = count;
1109 else if (count != first_count)
1110 /* c would split this equivalence class. */
1118 Search::find_asso_values ()
1122 /* Determine the steps, starting with the last one. */
1129 undetermined = new bool[_alpha_size];
1130 for (unsigned int c = 0; c < _alpha_size; c++)
1131 undetermined[c] = false;
1133 determined = new bool[_alpha_size];
1134 for (unsigned int c = 0; c < _alpha_size; c++)
1135 determined[c] = true;
1139 /* Compute the partition that needs to be refined. */
1140 EquivalenceClass *partition = compute_partition (undetermined);
1142 /* Determine the main character to be chosen in this step.
1143 Choosing such a character c has the effect of splitting every
1144 equivalence class (according the the frequency of occurrence of c).
1145 We choose the c with the minimum number of possible collisions,
1146 so that characters which lead to a large number of collisions get
1147 handled early during the search. */
1148 unsigned int chosen_c;
1149 unsigned int chosen_possible_collisions;
1151 unsigned int best_c = 0;
1152 unsigned int best_possible_collisions = UINT_MAX;
1153 for (unsigned int c = 0; c < _alpha_size; c++)
1154 if (_occurrences[c] > 0 && determined[c])
1156 unsigned int possible_collisions =
1157 count_possible_collisions (partition, c);
1158 if (possible_collisions < best_possible_collisions)
1161 best_possible_collisions = possible_collisions;
1164 if (best_possible_collisions == UINT_MAX)
1166 /* All c with _occurrences[c] > 0 are undetermined. We are
1167 are the starting situation and don't need any more step. */
1168 delete_partition (partition);
1172 chosen_possible_collisions = best_possible_collisions;
1175 /* We need one more step. */
1176 Step *step = new Step();
1178 step->_undetermined = new bool[_alpha_size];
1179 memcpy (step->_undetermined, undetermined, _alpha_size*sizeof(bool));
1181 step->_partition = partition;
1183 /* Now determine how the equivalence classes will be before this
1185 undetermined[chosen_c] = true;
1186 partition = compute_partition (undetermined);
1188 /* Now determine which other characters should be determined in this
1189 step, because they will not change the equivalence classes at
1190 this point. It is the set of all c which, for all equivalence
1191 classes, have the same frequency of occurrence in every keyword
1192 of the equivalence class. */
1193 for (unsigned int c = 0; c < _alpha_size; c++)
1194 if (_occurrences[c] > 0 && determined[c]
1195 && unchanged_partition (partition, c))
1197 undetermined[c] = true;
1198 determined[c] = false;
1201 /* main_c must be one of these. */
1202 if (determined[chosen_c])
1205 /* Now the set of changing characters of this step. */
1206 unsigned int changing_count;
1209 for (unsigned int c = 0; c < _alpha_size; c++)
1210 if (undetermined[c] && !step->_undetermined[c])
1213 unsigned int *changing = new unsigned int[changing_count];
1215 for (unsigned int c = 0; c < _alpha_size; c++)
1216 if (undetermined[c] && !step->_undetermined[c])
1217 changing[changing_count++] = c;
1219 step->_changing = changing;
1220 step->_changing_count = changing_count;
1222 step->_asso_value_max = _asso_value_max;
1224 step->_expected_lower =
1225 exp (static_cast<double>(chosen_possible_collisions)
1226 / static_cast<double>(_max_hash_value));
1227 step->_expected_upper =
1228 exp (static_cast<double>(chosen_possible_collisions)
1229 / static_cast<double>(_asso_value_max));
1231 delete_partition (partition);
1233 step->_next = steps;
1237 delete[] determined;
1238 delete[] undetermined;
1243 unsigned int stepno = 0;
1244 for (Step *step = steps; step; step = step->_next)
1247 fprintf (stderr, "Step %u chooses _asso_values[", stepno);
1248 for (unsigned int i = 0; i < step->_changing_count; i++)
1251 fprintf (stderr, ",");
1252 fprintf (stderr, "'%c'", step->_changing[i]);
1254 fprintf (stderr, "], expected number of iterations between %g and %g.\n",
1255 step->_expected_lower, step->_expected_upper);
1256 fprintf (stderr, "Keyword equivalence classes:\n");
1257 for (EquivalenceClass *cls = step->_partition; cls; cls = cls->_next)
1259 fprintf (stderr, "\n");
1260 for (KeywordExt_List *temp = cls->_keywords; temp; temp = temp->rest())
1262 KeywordExt *keyword = temp->first();
1263 fprintf (stderr, " %.*s\n",
1264 keyword->_allchars_length, keyword->_allchars);
1267 fprintf (stderr, "\n");
1271 /* Initialize _asso_values[]. (The value given here matters only
1272 for those c which occur in all keywords with equal multiplicity.) */
1273 for (unsigned int c = 0; c < _alpha_size; c++)
1274 _asso_values[c] = 0;
1276 unsigned int stepno = 0;
1277 for (Step *step = steps; step; step = step->_next)
1281 /* Initialize the asso_values[]. */
1282 unsigned int k = step->_changing_count;
1283 for (unsigned int i = 0; i < k; i++)
1285 unsigned int c = step->_changing[i];
1287 (_initial_asso_value < 0 ? rand () : _initial_asso_value)
1288 & (step->_asso_value_max - 1);
1291 unsigned int iterations = 0;
1292 DYNAMIC_ARRAY (iter, unsigned int, k);
1293 for (unsigned int i = 0; i < k; i++)
1295 unsigned int ii = (_jump != 0 ? k - 1 : 0);
1299 /* Test whether these asso_values[] lead to collisions among
1300 the equivalence classes that should be collision-free. */
1301 bool has_collision = false;
1302 for (EquivalenceClass *cls = step->_partition; cls; cls = cls->_next)
1304 /* Iteration Number array is a win, O(1) initialization time! */
1305 _collision_detector->clear ();
1307 for (KeywordExt_List *ptr = cls->_keywords; ptr; ptr = ptr->rest())
1309 KeywordExt *keyword = ptr->first();
1311 /* Compute the new hash code for the keyword, leaving apart
1312 the yet undetermined asso_values[]. */
1315 int sum = option[NOLENGTH] ? 0 : keyword->_allchars_length;
1316 const unsigned int *p = keyword->_selchars;
1317 int i = keyword->_selchars_length;
1318 for (; i > 0; p++, i--)
1319 if (!step->_undetermined[*p])
1320 sum += _asso_values[*p];
1324 /* See whether it collides with another keyword's hash code,
1325 from the same equivalence class. */
1326 if (_collision_detector->set_bit (hashcode))
1328 has_collision = true;
1333 /* Don't need to continue looking at the other equivalence
1334 classes if we already have found a collision. */
1343 /* Try other asso_values[]. */
1346 /* The way we try various values for
1347 asso_values[step->_changing[0],...step->_changing[k-1]]
1349 for (bound = 0,1,...)
1350 for (ii = 0,...,k-1)
1352 iter[0..ii-1] := values <= bound
1353 iter[ii+1..k-1] := values < bound
1355 asso_values[step->_changing[i]] =
1356 _initial_asso_value + iter[i] * _jump.
1357 This makes it more likely to find small asso_values[].
1359 unsigned int bound = iter[ii];
1363 unsigned int c = step->_changing[i];
1366 (_asso_values[c] + _jump) & (step->_asso_value_max - 1);
1367 if (iter[i] <= bound)
1370 (_asso_values[c] - iter[i] * _jump)
1371 & (step->_asso_value_max - 1);
1378 unsigned int c = step->_changing[i];
1381 (_asso_values[c] + _jump) & (step->_asso_value_max - 1);
1382 if (iter[i] < bound)
1385 (_asso_values[c] - iter[i] * _jump)
1386 & (step->_asso_value_max - 1);
1390 /* Switch from one ii to the next. */
1392 unsigned int c = step->_changing[ii];
1394 (_asso_values[c] - bound * _jump)
1395 & (step->_asso_value_max - 1);
1398 /* Here all iter[i] == 0. */
1404 if (bound == step->_asso_value_max)
1406 /* Out of search space! We can either backtrack, or
1407 increase the available search space of this step.
1408 It seems simpler to choose the latter solution. */
1409 step->_asso_value_max = 2 * step->_asso_value_max;
1410 if (step->_asso_value_max > _asso_value_max)
1412 _asso_value_max = step->_asso_value_max;
1413 /* Reinitialize _max_hash_value. */
1415 (option[NOLENGTH] ? 0 : _max_key_len)
1416 + (_asso_value_max - 1) * _max_selchars_length;
1417 /* Reinitialize _collision_detector. */
1418 delete _collision_detector;
1419 _collision_detector =
1420 new Bool_Array (_max_hash_value + 1);
1425 unsigned int c = step->_changing[ii];
1428 (_asso_values[c] + bound * _jump)
1429 & (step->_asso_value_max - 1);
1436 unsigned int c = step->_changing[ii];
1438 (_asso_values[c] + rand ()) & (step->_asso_value_max - 1);
1439 /* Next time, change the next c. */
1445 FREE_DYNAMIC_ARRAY (iter);
1449 fprintf (stderr, "Step %u chose _asso_values[", stepno);
1450 for (unsigned int i = 0; i < step->_changing_count; i++)
1453 fprintf (stderr, ",");
1454 fprintf (stderr, "'%c'", step->_changing[i]);
1456 fprintf (stderr, "] in %u iterations.\n", iterations);
1460 /* Free allocated memory. */
1461 while (steps != NULL)
1464 steps = step->_next;
1465 delete[] step->_changing;
1466 delete[] step->_undetermined;
1467 delete_partition (step->_partition);
1472 /* Computes a keyword's hash value, relative to the current _asso_values[],
1473 and stores it in keyword->_hash_value. */
1476 Search::compute_hash (KeywordExt *keyword) const
1478 int sum = option[NOLENGTH] ? 0 : keyword->_allchars_length;
1480 const unsigned int *p = keyword->_selchars;
1481 int i = keyword->_selchars_length;
1482 for (; i > 0; p++, i--)
1483 sum += _asso_values[*p];
1485 return keyword->_hash_value = sum;
1488 /* Finds good _asso_values[]. */
1491 Search::find_good_asso_values ()
1493 prepare_asso_values ();
1495 /* Search for good _asso_values[]. */
1497 if ((asso_iteration = option.get_asso_iterations ()) == 0)
1498 /* Try only the given _initial_asso_value and _jump. */
1499 find_asso_values ();
1502 /* Try different pairs of _initial_asso_value and _jump, in the
1508 (4, 1) (2, 3) (0, 5)
1509 (5, 1) (3, 3) (1, 5)
1511 KeywordExt_List *saved_head = _head;
1512 int best_initial_asso_value = 0;
1514 int *best_asso_values = new int[_alpha_size];
1515 int best_collisions = INT_MAX;
1516 int best_max_hash_value = INT_MAX;
1518 _initial_asso_value = 0; _jump = 1;
1521 /* Restore the keyword list in its original order. */
1522 _head = copy_list (saved_head);
1523 /* Find good _asso_values[]. */
1524 find_asso_values ();
1525 /* Test whether it is the best solution so far. */
1527 int max_hash_value = INT_MIN;
1528 _collision_detector->clear ();
1529 for (KeywordExt_List *ptr = _head; ptr; ptr = ptr->rest())
1531 KeywordExt *keyword = ptr->first();
1532 int hashcode = compute_hash (keyword);
1533 if (max_hash_value < hashcode)
1534 max_hash_value = hashcode;
1535 if (_collision_detector->set_bit (hashcode))
1538 if (collisions < best_collisions
1539 || (collisions == best_collisions
1540 && max_hash_value < best_max_hash_value))
1542 memcpy (best_asso_values, _asso_values,
1543 _alpha_size * sizeof (_asso_values[0]));
1544 best_collisions = collisions;
1545 best_max_hash_value = max_hash_value;
1547 /* Delete the copied keyword list. */
1548 delete_list (_head);
1550 if (--asso_iteration == 0)
1552 /* Prepare for next iteration. */
1553 if (_initial_asso_value >= 2)
1554 _initial_asso_value -= 2, _jump += 2;
1556 _initial_asso_value += _jump, _jump = 1;
1559 /* Install the best found asso_values. */
1560 _initial_asso_value = best_initial_asso_value;
1562 memcpy (_asso_values, best_asso_values,
1563 _alpha_size * sizeof (_asso_values[0]));
1564 delete[] best_asso_values;
1565 /* The keywords' _hash_value fields are recomputed below. */
1569 /* ========================================================================= */
1571 /* Comparison function for sorting by increasing _hash_value. */
1573 less_by_hash_value (KeywordExt *keyword1, KeywordExt *keyword2)
1575 return keyword1->_hash_value < keyword2->_hash_value;
1578 /* Sorts the keyword list by hash value. */
1583 _head = mergesort_list (_head, less_by_hash_value);
1592 /* Step 1: Finding good byte positions. */
1595 /* Step 2: Finding good alpha increments. */
1598 /* Step 3: Finding good asso_values. */
1599 find_good_asso_values ();
1601 /* Make one final check, just to make sure nothing weird happened.... */
1602 _collision_detector->clear ();
1603 for (KeywordExt_List *curr_ptr = _head; curr_ptr; curr_ptr = curr_ptr->rest())
1605 KeywordExt *curr = curr_ptr->first();
1606 unsigned int hashcode = compute_hash (curr);
1607 if (_collision_detector->set_bit (hashcode))
1609 /* This shouldn't happen. proj1, proj2, proj3 must have been
1610 computed to be injective on the given keyword set. */
1612 "\nInternal error, unexpected duplicate hash code\n");
1613 if (option[POSITIONS])
1614 fprintf (stderr, "try options -m or -r, or use new key positions.\n\n");
1616 fprintf (stderr, "try options -m or -r.\n\n");
1621 /* Sorts the keyword list by hash value. */
1624 /* Set unused asso_values[c] to max_hash_value + 1. This is not absolutely
1625 necessary, but speeds up the lookup function in many cases of lookup
1626 failure: no string comparison is needed once the hash value of a string
1627 is larger than the hash value of any keyword. */
1630 KeywordExt_List *temp;
1631 for (temp = _head; temp->rest(); temp = temp->rest())
1633 max_hash_value = temp->first()->_hash_value;
1635 for (unsigned int c = 0; c < _alpha_size; c++)
1636 if (_occurrences[c] == 0)
1637 _asso_values[c] = max_hash_value + 1;
1639 /* Propagate unified asso_values. */
1641 for (unsigned int c = 0; c < _alpha_size; c++)
1642 if (_alpha_unify[c] != c)
1643 _asso_values[c] = _asso_values[_alpha_unify[c]];
1646 /* Prints out some diagnostics upon completion. */
1650 delete _collision_detector;
1653 fprintf (stderr, "\ndumping occurrence and associated values tables\n");
1655 for (unsigned int i = 0; i < _alpha_size; i++)
1656 if (_occurrences[i])
1657 fprintf (stderr, "asso_values[%c] = %6d, occurrences[%c] = %6d\n",
1658 i, _asso_values[i], i, _occurrences[i]);
1660 fprintf (stderr, "end table dumping\n");
1662 fprintf (stderr, "\nDumping key list information:\ntotal non-static linked keywords = %d"
1663 "\ntotal keywords = %d\ntotal duplicates = %d\nmaximum key length = %d\n",
1664 _list_len, _total_keys, _total_duplicates, _max_key_len);
1666 int field_width = _max_selchars_length;
1667 fprintf (stderr, "\nList contents are:\n(hash value, key length, index, %*s, keyword):\n",
1668 field_width, "selchars");
1669 for (KeywordExt_List *ptr = _head; ptr; ptr = ptr->rest())
1671 fprintf (stderr, "%11d,%11d,%6d, ",
1672 ptr->first()->_hash_value, ptr->first()->_allchars_length, ptr->first()->_final_index);
1673 if (field_width > ptr->first()->_selchars_length)
1674 fprintf (stderr, "%*s", field_width - ptr->first()->_selchars_length, "");
1675 for (int j = 0; j < ptr->first()->_selchars_length; j++)
1676 putc (ptr->first()->_selchars[j], stderr);
1677 fprintf (stderr, ", %.*s\n",
1678 ptr->first()->_allchars_length, ptr->first()->_allchars);
1681 fprintf (stderr, "End dumping list.\n\n");
1683 delete[] _asso_values;
1684 delete[] _occurrences;
1685 delete[] _alpha_unify;
1686 delete[] _alpha_inc;