Visual Servoing Platform  version 3.5.1 under development (2022-09-25)
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 
52 static void open_hash(void);
53 static void close_hash(void);
54 static int hashpjw(const char *str);
55 static void insert_keyword(const char *str, Index token);
56 
57 #ifdef debug
58 static void delete_keyword(void);
59 static char *get_keyword(void);
60 #endif /* debug */
61 
62 #define PRIME 211
63 #define NEXT(x) (x) = (x)->next
64 
65 typedef 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 
72 static 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  */
80 void 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  */
91 void close_keyword(void) { close_hash(); }
92 
93 /*
94  * La procedure "open_hash" alloue et initialise la table de codage.
95  */
96 static 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  */
114 static 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  */
142 static 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  */
165 static 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  */
197 Index 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