1 /********************************************************************/
2 /* */
3 /* s7 Seed7 interpreter */
4 /* Copyright (C) 1990 - 2016 Thomas Mertes */
5 /* */
6 /* This program is free software; you can redistribute it and/or */
7 /* modify it under the terms of the GNU General Public License as */
8 /* published by the Free Software Foundation; either version 2 of */
9 /* the License, or (at your option) any later version. */
10 /* */
11 /* This program 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 */
14 /* GNU General Public License for more details. */
15 /* */
16 /* You should have received a copy of the GNU General Public */
17 /* License along with this program; if not, write to the */
18 /* Free Software Foundation, Inc., 51 Franklin Street, */
19 /* Fifth Floor, Boston, MA 02110-1301, USA. */
20 /* */
21 /* Module: General */
22 /* File: seed7/src/actutl.c */
23 /* Changes: 1992, 1993, 1994, 2014, 2016 Thomas Mertes */
24 /* Content: Conversion of strings to ACTIONs and back. */
25 /* */
26 /* Actions are searched with a binary search. Normally a detailed */
27 /* implementation of the binary search algorithm is used. With the */
28 /* USE_BSEARCH flag it is possible to use the bsearch procedure of */
29 /* the c-library instead. */
30 /* */
31 /********************************************************************/
32
33 #define LOG_FUNCTIONS 0
34 #define VERBOSE_EXCEPTIONS 0
35
36 #include "version.h"
37
38 #include "stdlib.h"
39 #include "stdio.h"
40 #include "string.h"
41
42 #include "common.h"
43 #include "data.h"
44 #include "heaputl.h"
45 #include "striutl.h"
46
47 #undef EXTERN
48 #define EXTERN
49 #define DO_INIT
50 #include "actutl.h"
51
52
53 #define USE_BSEARCH 0
54 #define MAX_CSTRI_BUFFER_LEN 40
55
56
57 typedef struct {
58 unsigned int size;
59 actEntryType *table;
60 } actEntryMapType;
61
62 static actEntryMapType actEntryMap = {0, NULL};
63
64
65
66 #if USE_BSEARCH
67 #ifdef USE_CDECL
actTableCmp(char * strg1,char * strg2)68 static int _cdecl actTableCmp (char *strg1, char *strg2)
69 #else
70 static int actTableCmp (void const *strg1, void const *strg2)
71 #endif
72
73 {
74 int comparison;
75
76 /* actTableCmp */
77 logFunction(printf("actTableCmp(\"%s\", \"%s\")\n",
78 strg1, ((actEntryType) strg2)->name););
79 comparison = strcmp(strg1, ((actEntryType) strg2)->name);
80 logFunction(printf("actTableCmp --> %d\n", comparison););
81 return comparison;
82 } /* actTableCmp */
83 #endif
84
85
86
87 #ifdef USE_CDECL
actEntryMapCmp(char * act_ptr1,char * act_ptr2)88 static int _cdecl actEntryMapCmp (char *act_ptr1, char *act_ptr2)
89 #else
90 static int actEntryMapCmp (const void *act_ptr1, const void *act_ptr2)
91 #endif
92
93 {
94 int signumValue;
95
96 /* actEntryMapCmp */
97 logFunction(printf("actEntryMapCmp(" FMT_U_MEM ", " FMT_U_MEM ")\n",
98 (memSizeType) (*(const actEntryType *) act_ptr1)->action,
99 (memSizeType) (*(const actEntryType *) act_ptr2)->action););
100 if ((memSizeType) (*(const actEntryType *) act_ptr1)->action <
101 (memSizeType) (*(const actEntryType *) act_ptr2)->action) {
102 signumValue = -1;
103 } else {
104 signumValue = (memSizeType) (*(const actEntryType *) act_ptr1)->action >
105 (memSizeType) (*(const actEntryType *) act_ptr2)->action;
106 } /* if */
107 logFunction(printf("actEntryMapCmp --> %d\n", signumValue););
108 return signumValue;
109 } /* actEntryMapCmp */
110
111
112
113 /**
114 * Search for the action with the given ''actionName''.
115 * @param actionName Name of the action searched.
116 * @return The action found, or NULL if no such action exists.
117 */
searchAction(cstriType actionName)118 static actType searchAction (cstriType actionName)
119
120 {
121 #if USE_BSEARCH
122 actEntryType found;
123 #else
124 unsigned int lower;
125 unsigned int upper;
126 unsigned int middle;
127 int comparison;
128 #endif
129 unsigned int actionNumber;
130 actType actionFound;
131
132 /* searchAction */
133 logFunction(printf("searchAction(\"%s\")\n", actionName););
134 #if USE_BSEARCH
135 if ((found = (actEntryType) bsearch(actionName, &actTable.table[1],
136 actTable.size - 1, sizeof(actEntryRecord), actTableCmp)) != NULL) {
137 actionNumber = (unsigned int) (found - &actTable.table[0]);
138 } else {
139 actionNumber = 0;
140 } /* if */
141 /* printf("action number: %u\n", actionNumber); */
142 #else
143 actionNumber = 0;
144 lower = 0;
145 upper = actTable.size;
146 while (lower + 1 < upper) {
147 middle = (lower + upper) >> 1;
148 /* printf("%u %u %u >%s< >%s<\n", lower, middle, upper,
149 actTable.table[middle].name, actionName); */
150 if ((comparison = strcmp(actTable.table[middle].name, actionName)) < 0) {
151 lower = middle;
152 } else if (comparison == 0) {
153 lower = upper - 1;
154 actionNumber = middle;
155 } else {
156 upper = middle;
157 } /* if */
158 } /* while */
159 #endif
160 if (actTable.table != NULL && actionNumber != 0) {
161 /* printf("action(\"%s\")\n", actTable.table[actionNumber].name); */
162 actionFound = actTable.table[actionNumber].action;
163 } else {
164 actionFound = NULL;
165 } /* if */
166 logFunction(printf("searchAction --> " FMT_U_MEM "\n",
167 (memSizeType) actionFound););
168 return actionFound;
169 } /* searchAction */
170
171
172
173 /**
174 * Find the action with the given ''actionName''.
175 * @param actionName Name of the action searched.
176 * @return The action found, or NULL if no such action exists.
177 */
findAction(const const_striType actionName)178 actType findAction (const const_striType actionName)
179
180 {
181 char actName[MAX_CSTRI_BUFFER_LEN + NULL_TERMINATION_LEN];
182 actType actionFound;
183
184 /* findAction */
185 logFunction(printf("findAction(\"%s\")\n",
186 striAsUnquotedCStri(actionName)););
187 if (unlikely(actionName->size > MAX_CSTRI_BUFFER_LEN)) {
188 actionFound = NULL;
189 } else {
190 if (unlikely(conv_to_cstri(actName, actionName) == NULL)) {
191 actionFound = NULL;
192 } else {
193 actionFound = searchAction(actName);
194 } /* if */
195 } /* if */
196 logFunction(printf("findAction --> " FMT_U_MEM "\n",
197 (memSizeType) actionFound););
198 return actionFound;
199 } /* findAction */
200
201
202
203 /**
204 * Get the action ACT_ILLEGAL.
205 * @return a function pointer to the function act_illegal().
206 */
getActIllegal(void)207 actType getActIllegal (void)
208
209 {
210 actType actionFound;
211
212 /* getActIllegal */
213 if (actTable.table != NULL) {
214 actionFound = actTable.table[0].action;
215 } else {
216 actionFound = NULL;
217 } /* if */
218 return actionFound;
219 } /* getActIllegal */
220
221
222
223 /**
224 * Create actEntryMap and remove double actType values from it.
225 * The table actEntryMap is used by getActEntry() to map actType
226 * function pointers to corresponding entries in actTable. If
227 * the C compiler recognizes that the code of two functions is
228 * identical it may decide to reuse the code. In this case two
229 * or more actType function pointers refer to the same function.
230 * To have predictable results double actType values are removed
231 * from actEntryMap. The actType function pointer that refers to
232 * the action with the alphabetically lower action name is kept.
233 * Since the action names in actTable are sorted alphabetically
234 * this is the entry that is nearer to the beginning of actTable.
235 */
genActPtrTable(void)236 static void genActPtrTable (void)
237
238 {
239 unsigned int number;
240
241 /* genActPtrTable */
242 logFunction(printf("genActPtrTable\n"););
243 actEntryMap.size = actTable.size;
244 if (ALLOC_TABLE(actEntryMap.table, actEntryType, actEntryMap.size)) {
245 for (number = 0; number < actEntryMap.size; number++) {
246 actEntryMap.table[number] = (actEntryType) &actTable.table[number];
247 } /* for */
248 qsort(actEntryMap.table, actEntryMap.size, sizeof(actEntryType),
249 actEntryMapCmp);
250 for (number = 1; number < actEntryMap.size; number++) {
251 if (actEntryMap.table[number]->action ==
252 actEntryMap.table[number - 1]->action) {
253 /* printf("*** Actions %s and %s implemented by the same function\n",
254 actEntryMap.table[number - 1]->name,
255 actEntryMap.table[number]->name); */
256 /* Remove double entries */
257 if ((memSizeType) actEntryMap.table[number - 1] >
258 (memSizeType) actEntryMap.table[number]) {
259 memmove(&actEntryMap.table[number - 1],
260 &actEntryMap.table[number],
261 (actEntryMap.size - number) * sizeof(actEntryType));
262 } else {
263 memmove(&actEntryMap.table[number],
264 &actEntryMap.table[number + 1],
265 (actEntryMap.size - number - 1) * sizeof(actEntryType));
266 } /* if */
267 actEntryMap.size--;
268 number--;
269 /* printf("size=%u, number=%u\n", actEntryMap.size, number); */
270 } /* if */
271 } /* for */
272 } /* if */
273 logFunction(printf("genActPtrTable -->\n"););
274 } /* genActPtrTable */
275
276
277
278 /**
279 * Get an actEntry that corresponds to actionSearched.
280 * @param actionSearched The action to be searched in actTable.
281 * @return a pointer to an actEntry. If actionSearched
282 * is not found a pointer to the actEntry of
283 * the action ACT_ILLEGAL is returned.
284 */
getActEntry(actType actionSearched)285 const_actEntryType getActEntry (actType actionSearched)
286
287 {
288 int lower;
289 int upper;
290 int middle;
291 const_actEntryType entryFound;
292
293 /* getActEntry */
294 logFunction(printf("getActEntry(" FMT_U_MEM ")\n",
295 (memSizeType) actionSearched););
296 if (unlikely(actEntryMap.table == NULL)) {
297 genActPtrTable();
298 if (unlikely(actEntryMap.table == NULL)) {
299 actionSearched = actTable.table[0].action;
300 } /* if */
301 } /* if */
302
303 entryFound = &actTable.table[0];
304 if (likely(actionSearched != actTable.table[0].action)) {
305 lower = -1;
306 upper = (int) actEntryMap.size;
307 while (lower + 1 < upper) {
308 middle = (lower + upper) >> 1;
309 /* printf("%d %d %d <" FMT_U_MEM "> <" FMT_U_MEM ">\n", lower, middle, upper,
310 (memSizeType) actEntryMap.table[middle]->action,
311 (memSizeType) actionSearched); */
312 if (((memSizeType) actEntryMap.table[middle]->action) <
313 ((memSizeType) actionSearched)) {
314 lower = middle;
315 } else if (actEntryMap.table[middle]->action == actionSearched) {
316 lower = upper - 1;
317 entryFound = actEntryMap.table[middle];
318 } else {
319 upper = middle;
320 } /* if */
321 } /* while */
322 } /* if */
323 logFunction(printf("getActEntry --> %s\n", entryFound->name););
324 return entryFound;
325 } /* getActEntry */
326