1 /*
2 * Copyright (C) 1999, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2011,
3 * 2012, 2013 Free Software Foundation, Inc.
4 *
5 * This file is part of GNU libmatheval
6 *
7 * GNU libmatheval is free software: you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as
9 * published by the Free Software Foundation, either version 3 of the
10 * License, or (at your option) any later version.
11 *
12 * GNU libmatheval is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with GNU libmatheval. If not, see
19 * <http://www.gnu.org/licenses/>.
20 */
21
22 #if HAVE_CONFIG_H
23 #include "config.h"
24 #endif
25
26 #include <assert.h>
27 #include <stdarg.h>
28 #include "common.h"
29 #include "symbol_table.h"
30 #include "xmath.h"
31
32 /* Type definition for function accepting single argument of double type
33 * and returning double value. */
34 typedef double (*function_type) (double);
35
36 /* Calculate hash value for given name and hash table length. */
37 static int hash(char *name, int length);
38
39 SymbolTable *
symbol_table_create(int length)40 symbol_table_create(int length)
41 {
42 SymbolTable *symbol_table; /* Pointer to symbol table. */
43 static char *constants_names[] = {
44 "e", "log2e", "log10e", "ln2", "ln10", "pi", "pi_2",
45 "pi_4", "1_pi", "2_pi", "2_sqrtpi", "sqrt2", "sqrt1_2"
46 }; /* Symbol table predefined constants
47 * names. */
48 static double constants[] = {
49 2.7182818284590452354, 1.4426950408889634074,
50 0.43429448190325182765, 0.69314718055994530942,
51 2.30258509299404568402, 3.14159265358979323846,
52 1.57079632679489661923, 0.78539816339744830962,
53 0.31830988618379067154, 0.63661977236758134308,
54 1.12837916709551257390, 1.41421356237309504880,
55 0.70710678118654752440
56 }; /* Symbol table predefined constants
57 * values. */
58 static char *functions_names[] = {
59 "exp", "log", "sqrt", "sin", "cos", "tan", "cot", "sec",
60 "csc", "asin", "acos", "atan", "acot", "asec", "acsc",
61 "sinh", "cosh", "tanh", "coth", "sech", "csch",
62 "asinh", "acosh", "atanh", "acoth", "asech", "acsch",
63 "abs", "step", "delta", "nandelta", "erf",
64 }; /* Symbol table predefined functions
65 * names. */
66 static double (*functions[]) (double) = {
67 exp, log, sqrt, sin, cos, tan, math_cot, math_sec, math_csc, asin, acos, atan, math_acot, math_asec, math_acsc, sinh, cosh, tanh, math_coth, math_sech, math_csch, math_asinh, math_acosh, math_atanh, math_acoth, math_asech, math_acsch, fabs, math_step, math_delta, math_nandelta, erf}; /* Symbol
68 * table
69 * predefined
70 * functions
71 * pointers
72 * to
73 * functions
74 * to
75 * calculate
76 * them.
77 */
78 int i; /* Loop counter. */
79
80 /* Allocate memory for symbol table data structure as well as for
81 * corresponding hash table. */
82 symbol_table = XMALLOC(SymbolTable, 1);
83 symbol_table->length = length;
84 symbol_table->records = XCALLOC(Record, symbol_table->length);
85
86 /* Insert predefined constants into symbol table. */
87 for (i = 0;
88 i < sizeof(constants_names) / sizeof(constants_names[0]); i++)
89 symbol_table_insert(symbol_table, constants_names[i], 'c',
90 constants[i]);
91
92 /* Insert predefined functions into symbol table. */
93 for (i = 0;
94 i < sizeof(functions_names) / sizeof(functions_names[0]); i++)
95 symbol_table_insert(symbol_table, functions_names[i], 'f',
96 functions[i]);
97
98 /* Initialize symbol table reference count. */
99 symbol_table->reference_count = 1;
100
101 return symbol_table;
102 }
103
104 void
symbol_table_destroy(SymbolTable * symbol_table)105 symbol_table_destroy(SymbolTable * symbol_table)
106 {
107 Record *curr,
108 *next; /* Pointers to current and next record
109 * while traversing hash table bucket. */
110 int i; /* Loop counter. */
111
112 /* Decrement refernce count and return if symbol table still used
113 * elsewhere. */
114 if (--symbol_table->reference_count > 0)
115 return;
116
117 /* Delete hash table as well as data structure representing symbol
118 * table. */
119 for (i = 0; i < symbol_table->length; i++)
120 for (curr = symbol_table->records[i].next; curr;) {
121 next = curr->next;
122 XFREE(curr->name);
123 XFREE(curr);
124 curr = next;
125 }
126 XFREE(symbol_table->records);
127 XFREE(symbol_table);
128 }
129
130 Record *
symbol_table_insert(SymbolTable * symbol_table,char * name,char type,...)131 symbol_table_insert(SymbolTable * symbol_table, char *name, char type, ...)
132 {
133 Record *record; /* Pointer to symbol table record
134 * corresponding to name given. */
135 va_list ap; /* Function variable argument list. */
136 int i; /* Loop counter. */
137
138 /* Check if symbol already in table and, if affirmative and record
139 * type same as type given, return corresponding record
140 * immediately. */
141 if ((record = symbol_table_lookup(symbol_table, name))) {
142 assert(record->type == type);
143 return record;
144 }
145
146 /* Allocate memory for and initialize new record. */
147 record = XMALLOC(Record, 1);
148 record->name = XMALLOC(char, strlen(name) + 1);
149 strcpy(record->name, name);
150 record->type = type;
151 record->flag = FALSE;
152
153 /* Parse function variable argument list to complete record
154 * initialization. */
155 va_start(ap, type);
156 switch (record->type) {
157 case 'c':
158 record->data.value = va_arg(ap, double);
159 break;
160
161 case 'v':
162 record->data.value = 0;
163 break;
164
165 case 'f':
166 record->data.function = va_arg(ap, function_type);
167 break;
168 }
169 va_end(ap);
170
171 /* Calculate hash value and put record in corresponding hash table
172 * bucket. */
173 i = hash(name, symbol_table->length);
174 record->next = symbol_table->records[i].next;
175 symbol_table->records[i].next = record;
176
177 return record;
178 }
179
180 Record *
symbol_table_lookup(SymbolTable * symbol_table,char * name)181 symbol_table_lookup(SymbolTable * symbol_table, char *name)
182 {
183 int i; /* Hash value. */
184 Record *curr; /* Pointer to current symbol table record.
185 */
186
187 /*
188 * Calcuate hash value for name given.
189 */
190 i = hash(name, symbol_table->length);
191
192 /* Lookup for name in hash table bucket corresponding to above
193 * hash value. */
194 for (curr = symbol_table->records[i].next; curr; curr = curr->next)
195 if (!strcmp(curr->name, name))
196 return curr;
197
198 return NULL;
199 }
200
201 void
symbol_table_clear_flags(SymbolTable * symbol_table)202 symbol_table_clear_flags(SymbolTable * symbol_table)
203 {
204 Record *curr; /* Pointer to current symbol table record
205 * while traversing hash table bucket. */
206 int i; /* Loop counter. */
207
208 /* Clear flag for all records in symbol table. */
209 for (i = 0; i < symbol_table->length; i++)
210 for (curr = symbol_table->records[i].next; curr;
211 curr = curr->next)
212 curr->flag = FALSE;
213 }
214
215 int
symbol_table_get_flagged_count(SymbolTable * symbol_table)216 symbol_table_get_flagged_count(SymbolTable * symbol_table)
217 {
218 int count; /* Number of flagged symbol table records.
219 */
220 Record *curr; /* Pointer to current symbol table record
221 * while traversing hash table bucket. */
222 int i; /* Loop counter. */
223
224 /* Calculate number of records in symbol table with flag set. */
225 count = 0;
226 for (i = 0; i < symbol_table->length; i++)
227 for (curr = symbol_table->records[i].next; curr;
228 curr = curr->next)
229 if (curr->flag)
230 count++;
231 return count;
232 }
233
234 int
symbol_table_get_flagged(SymbolTable * symbol_table,Record ** records,int length)235 symbol_table_get_flagged(SymbolTable * symbol_table, Record ** records,
236 int length)
237 {
238 int count; /* Number of pointers to symbol table
239 * records put into given array. */
240 Record *curr; /* Pointers to current symbol table record
241 * while traversing hash table bucket. */
242 int i; /* Loop counter. */
243
244 /* Put pointers to records in symbol table with flag set into
245 * given array. */
246 count = 0;
247 for (i = 0; i < symbol_table->length; i++)
248 for (curr = symbol_table->records[i].next; curr;
249 curr = curr->next)
250 if (curr->flag) {
251 records[count++] = curr;
252 if (count == length)
253 return count;
254 }
255 return count;
256 }
257
258 SymbolTable *
symbol_table_assign(SymbolTable * symbol_table)259 symbol_table_assign(SymbolTable * symbol_table)
260 {
261 /* Increase symbol table reference count and return pointer to
262 * data structure representing table. */
263 symbol_table->reference_count++;
264 return symbol_table;
265 }
266
267 /* Function below reused from A.V. Aho, R. Sethi, J.D. Ullman, "Compilers
268 * - Principle, Techniques, and Tools", Addison-Wesley, 1986, pp 435-437,
269 * and in turn from P.J. Weineberger's C compiler. */
270 static int
hash(char * s,int n)271 hash(char *s, int n)
272 {
273 char *p;
274 unsigned h,
275 g;
276
277 h = 0;
278
279 for (p = s; *p; p++) {
280 h = (h << 4) + *p;
281 if ((g = h & 0xf0000000)) {
282 h = h ^ (g >> 24);
283 h = h ^ g;
284 }
285 }
286
287 return h % n;
288 }
289