1/* Keyword data.
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>.
5
6 This file is part of GNU GPERF.
7
8 This program 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 3 of the License, or
11 (at your option) any later version.
12
13 This program 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.
17
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
20
21/* Specification. */
22#include "keyword.h"
23
24#include <stddef.h>
25#include <stdio.h>
26#include <stdlib.h>
27#include "positions.h"
28
29
30/* --------------------------- KeywordExt class --------------------------- */
31
32/* Sort a small set of 'unsigned int', base[0..len-1], in place. */
33static inline void sort_char_set (unsigned int *base, int len)
34{
35 /* Bubble sort is sufficient here. */
36 for (int i = 1; i < len; i++)
37 {
38 int j;
39 unsigned int tmp;
40
41 for (j = i, tmp = base[j]; j > 0 && tmp < base[j - 1]; j--)
42 base[j] = base[j - 1];
43
44 base[j] = tmp;
45 }
46}
47
48/* Initializes selchars and selchars_length.
49
50 General idea:
51 The hash function will be computed as
52 asso_values[allchars[key_pos[0]]] +
53 asso_values[allchars[key_pos[1]]] + ...
54 We compute selchars as the multiset
55 { allchars[key_pos[0]], allchars[key_pos[1]], ... }
56 so that the hash function becomes
57 asso_values[selchars[0]] + asso_values[selchars[1]] + ...
58 Furthermore we sort the selchars array, to ease detection of duplicates
59 later.
60
61 More in detail: The arguments alpha_unify (used for case-insensitive
62 hash functions) and alpha_inc (used to disambiguate permutations)
63 apply slight modifications. The hash function will be computed as
64 sum (j=0,1,...: k = key_pos[j]:
65 asso_values[alpha_unify[allchars[k]+alpha_inc[k]]])
66 + (allchars_length if !option[NOLENGTH], 0 otherwise).
67 We compute selchars as the multiset
68 { alpha_unify[allchars[k]+alpha_inc[k]] : j=0,1,..., k = key_pos[j] }
69 so that the hash function becomes
70 asso_values[selchars[0]] + asso_values[selchars[1]] + ...
71 + (allchars_length if !option[NOLENGTH], 0 otherwise).
72 */
73
74unsigned int *
75KeywordExt::init_selchars_low (const Positions& positions, const unsigned int *alpha_unify, const unsigned int *alpha_inc)
76{
77 /* Iterate through the list of positions, initializing selchars
78 (via ptr). */
79 PositionIterator iter = positions.iterator(_allchars_length);
80
81 unsigned int *key_set = new unsigned int[iter.remaining()];
82 unsigned int *ptr = key_set;
83
84 for (int i; (i = iter.next ()) != PositionIterator::EOS; )
85 {
86 unsigned int c;
87 if (i == Positions::LASTCHAR)
88 /* Special notation for last KEY position, i.e. '$'. */
89 c = static_cast<unsigned char>(_allchars[_allchars_length - 1]);
90 else if (i < _allchars_length)
91 {
92 /* Within range of KEY length, so we'll keep it. */
93 c = static_cast<unsigned char>(_allchars[i]);
94 if (alpha_inc)
95 c += alpha_inc[i];
96 }
97 else
98 /* Out of range of KEY length, the iterator should not have
99 produced this. */
100 abort ();
101 if (alpha_unify)
102 c = alpha_unify[c];
103 *ptr = c;
104 ptr++;
105 }
106
107 _selchars = key_set;
108 _selchars_length = ptr - key_set;
109
110 return key_set;
111}
112
113void
114KeywordExt::init_selchars_tuple (const Positions& positions, const unsigned int *alpha_unify)
115{
116 init_selchars_low (positions, alpha_unify, NULL);
117}
118
119void
120KeywordExt::init_selchars_multiset (const Positions& positions, const unsigned int *alpha_unify, const unsigned int *alpha_inc)
121{
122 unsigned int *selchars =
123 init_selchars_low (positions, alpha_unify, alpha_inc);
124
125 /* Sort the selchars elements alphabetically. */
126 sort_char_set (selchars, _selchars_length);
127}
128
129/* Deletes selchars. */
130void
131KeywordExt::delete_selchars ()
132{
133 delete[] const_cast<unsigned int *>(_selchars);
134}
135
136
137/* ------------------------- Keyword_Factory class ------------------------- */
138
139Keyword_Factory::Keyword_Factory ()
140{
141}
142
143Keyword_Factory::~Keyword_Factory ()
144{
145}
146
147
148/* ------------------------------------------------------------------------- */
149
150char empty_string[1] = "";
151
152
153#ifndef __OPTIMIZE__
154
155#define INLINE /* not inline */
156#include "keyword.icc"
157#undef INLINE
158
159#endif /* not defined __OPTIMIZE__ */
160