Visual Servoing Platform version 3.5.0
vpKeyword.cpp
1/****************************************************************************
2 *
3 * ViSP, open source Visual Servoing Platform software.
4 * Copyright (C) 2005 - 2019 by Inria. All rights reserved.
5 *
6 * This software is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 * See the file LICENSE.txt at the root directory of this source
11 * distribution for additional information about the GNU GPL.
12 *
13 * For using ViSP with software that can not be combined with the GNU
14 * GPL, please contact Inria about acquiring a ViSP Professional
15 * Edition License.
16 *
17 * See http://visp.inria.fr for more information.
18 *
19 * This software was developed at:
20 * Inria Rennes - Bretagne Atlantique
21 * Campus Universitaire de Beaulieu
22 * 35042 Rennes Cedex
23 * France
24 *
25 * If you have questions regarding the use of this file, please contact
26 * Inria at visp@inria.fr
27 *
28 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
29 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
30 *
31 * Description:
32 * Le module "keyword.c" contient les procedures de gestion
33 * des mots cles retournes par l'analyseur lexical "lex".
34 *
35 * Authors:
36 * Jean-Luc CORRE
37 *
38 *****************************************************************************/
39
40#include <visp3/core/vpConfig.h>
41#include <visp3/core/vpException.h>
42
43#include "vpKeyword.h"
44#include "vpMy.h"
45#include "vpToken.h"
46
47#include <stdio.h>
48#include <stdlib.h>
49#include <string.h>
50#ifndef DOXYGEN_SHOULD_SKIP_THIS
51
52static void open_hash(void);
53static void close_hash(void);
54static int hashpjw(const char *str);
55static void insert_keyword(const char *str, Index token);
56
57#ifdef debug
58static void delete_keyword(void);
59static char *get_keyword(void);
60#endif /* debug */
61
62#define PRIME 211
63#define NEXT(x) (x) = (x)->next
64
65typedef struct bucket {
66 struct bucket *next; /* element suivant */
67 char *ident; /* identifateur */
68 Byte length; /* longueur de "ident" */
69 Index token; /* code du jeton */
70} Bucket;
71
72static Bucket **hash_tbl; /* table de "hash-coding" */
73
74/*
75 * La procedure "open_keyword" alloue et initialise les variables utilisees
76 * par les procedures de gestion des mots cles.
77 * Entree :
78 * kwp Tableau des mots cles termine par NULL.
79 */
80void open_keyword(Keyword *kwp)
81{
82 open_hash();
83 for (; kwp->ident != NULL; kwp++) /* recopie les mots cles */
84 insert_keyword(kwp->ident, kwp->token);
85}
86
87/*
88 * La procedure "close_keyword" libere les variables utilisees
89 * par les procedures de gestion des mots cles.
90 */
91void close_keyword(void) { close_hash(); }
92
93/*
94 * La procedure "open_hash" alloue et initialise la table de codage.
95 */
96static void open_hash(void)
97{
98 Bucket **head, **bend;
99
100 if ((hash_tbl = (Bucket **)malloc(sizeof(Bucket *) * PRIME)) == NULL) {
101 static char proc_name[] = "open_hash";
102 perror(proc_name);
103 throw vpException(vpException::fatalError, "Error in open_hash");
104 }
105 head = hash_tbl;
106 bend = head + PRIME;
107 for (; head < bend; *head++ = NULL) {
108 };
109}
110
111/*
112 * La procedure "close_hash" libere la table de codage et ses elements.
113 */
114static void close_hash(void)
115{
116 Bucket **head = hash_tbl;
117 Bucket **bend = head + PRIME;
118 Bucket *bp; /* element courant */
119 Bucket *next; /* element suivant */
120
121 for (; head < bend; head++) { /* libere les listes */
122 for (bp = *head; bp != NULL; bp = next) {
123 next = bp->next;
124 free((char *)bp);
125 }
126 }
127 free((char *)hash_tbl); /* libere la table */
128}
129
130/*
131 * La procedure "hashpjw" calcule un indice code a partir de la chaine
132 * de caracteres "str".
133 * Pour plus de renseignements, voir :
134 * "Compilers. Principles, Techniques, and Tools",
135 * A.V. AHO, R. SETHI, J.D. ULLMAN,
136 * ADDISON-WESLEY PUBLISHING COMPANY, pp 436.
137 * Entree :
138 * str Chaine de caracteres a coder.
139 * Sortie :
140 * Le code de la chaine.
141 */
142static int hashpjw(const char *str)
143{
144 unsigned h = 0; /* "hash value" */
145
146 for (; *str != '\0'; str++) {
147 unsigned g;
148 h = (h << 4) + (unsigned)(*str);
149 if ((g = h & ~0xfffffff) != 0) {
150 h ^= g >> 24;
151 h ^= g;
152 }
153 }
154 return ((int)(h % PRIME));
155}
156
157/*
158 * La procedure "insert_keyword" insere en tete d'un point d'entree
159 * de la table de "hachage" le mot cle ayant pour identificateur
160 * la chaine de caracteres "str" et pour valeur "token".
161 * Entree :
162 * str Chaine de caracteres du mot cle.
163 * token Valeur du jeton associe au mot cle.
164 */
165static void insert_keyword(const char *str, Index token)
166{
167 Bucket **head = hash_tbl + hashpjw(str);
168 Bucket *bp;
169 Byte length;
170
171 length = (Byte)(strlen(str)); // Warning! Overflow possible!
172 if ((bp = (Bucket *)malloc(sizeof(Bucket) + length + 1)) == NULL) {
173 static const char proc_name[] = "insert_keyword";
174 perror(proc_name);
175 throw vpException(vpException::fatalError, "Error in insert_keyword");
176 }
177 bp->length = length;
178 bp->token = token;
179 bp->ident = (char *)(bp + 1);
180 strcpy(bp->ident, str);
181
182 bp->next = *head; /* insere "b" en tete de "head" */
183 *head = bp;
184}
185
186/*
187 * La pocedure "get_symbol" verifie que la chaine pointee par "ident"
188 * de longeur "length" est un mot cle.
189 * Entree :
190 * ident Chaine de l'identificateur.
191 * length Nombre de caracteres de la chaine.
192 * Note :
193 * La chaine "ident" n'est pas terminee par '\0'.
194 * Sortie :
195 * Valeur du jeton associe si c'est un mot cle, 0 sinon.
196 */
197Index get_symbol(char *ident, int length)
198{
199 Bucket *bp;
200 const char *kwd;
201 char *idn = ident;
202 int len = length;
203
204 { /* calcule le code de hachage (voir "hashpjw") */
205 unsigned h = 0; /* "hash value" */
206
207 for (; len != 0; idn++, len--) {
208 unsigned g;
209 h = (h << 4) + (unsigned)(*idn);
210 if ((g = h & ~0xfffffff) != 0) {
211 h ^= g >> 24;
212 h ^= g;
213 }
214 }
215 bp = hash_tbl[h % PRIME];
216 }
217
218 /* recherche le mot cle */
219
220 for (; bp != NULL; NEXT(bp)) {
221 if (length == bp->length) {
222 idn = ident;
223 len = length;
224 kwd = bp->ident;
225 for (; *idn == *kwd; idn++, kwd++) {
226 --len;
227 if (len == 0)
228 return (bp->token);
229 }
230 }
231 }
232 return (0); /* identificateur */
233}
234
235#endif
error that can be emited by ViSP classes.
Definition: vpException.h:72
@ fatalError
Fatal error.
Definition: vpException.h:96