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. */ |
33 | static 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 | |
74 | unsigned int * |
75 | KeywordExt::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 | |
113 | void |
114 | KeywordExt::init_selchars_tuple (const Positions& positions, const unsigned int *alpha_unify) |
115 | { |
116 | init_selchars_low (positions, alpha_unify, NULL); |
117 | } |
118 | |
119 | void |
120 | KeywordExt::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. */ |
130 | void |
131 | KeywordExt::delete_selchars () |
132 | { |
133 | delete[] const_cast<unsigned int *>(_selchars); |
134 | } |
135 | |
136 | |
137 | /* ------------------------- Keyword_Factory class ------------------------- */ |
138 | |
139 | Keyword_Factory::Keyword_Factory () |
140 | { |
141 | } |
142 | |
143 | Keyword_Factory::~Keyword_Factory () |
144 | { |
145 | } |
146 | |
147 | |
148 | /* ------------------------------------------------------------------------- */ |
149 | |
150 | char 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 | |