Visual Servoing Platform  version 3.1.0
vpKeyword.cpp
1 /****************************************************************************
2  *
3  * This file is part of the ViSP software.
4  * Copyright (C) 2005 - 2017 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 "vpKeyword.h"
41 #include "vpMy.h"
42 #include "vpToken.h"
43 
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <string.h>
47 #ifndef DOXYGEN_SHOULD_SKIP_THIS
48 
49 static void open_hash(void);
50 static void close_hash(void);
51 static int hashpjw(const char *str);
52 static void insert_keyword(const char *str, Index token);
53 
54 #ifdef debug
55 static void delete_keyword(void);
56 static char *get_keyword(void);
57 #endif /* debug */
58 
59 #define PRIME 211
60 #define NEXT(x) (x) = (x)->next
61 
62 typedef struct bucket {
63  struct bucket *next; /* element suivant */
64  char *ident; /* identifateur */
65  Byte length; /* longueur de "ident" */
66  Index token; /* code du jeton */
67 } Bucket;
68 
69 static Bucket **hash_tbl; /* table de "hash-coding" */
70 
71 /*
72  * La procedure "open_keyword" alloue et initialise les variables utilisees
73  * par les procedures de gestion des mots cles.
74  * Entree :
75  * kwp Tableau des mots cles termine par NULL.
76  */
77 void open_keyword(Keyword *kwp)
78 {
79  open_hash();
80  for (; kwp->ident != NULL; kwp++) /* recopie les mots cles */
81  insert_keyword(kwp->ident, kwp->token);
82 }
83 
84 /*
85  * La procedure "close_keyword" libere les variables utilisees
86  * par les procedures de gestion des mots cles.
87  */
88 void close_keyword(void) { close_hash(); }
89 
90 /*
91  * La procedure "open_hash" alloue et initialise la table de codage.
92  */
93 static void open_hash(void)
94 {
95  Bucket **head, **bend;
96 
97  if ((hash_tbl = (Bucket **)malloc(sizeof(Bucket *) * PRIME)) == NULL) {
98  static char proc_name[] = "open_hash";
99  perror(proc_name);
100  exit(1);
101  }
102  head = hash_tbl;
103  bend = head + PRIME;
104  for (; head < bend; *head++ = NULL) {
105  };
106 }
107 
108 /*
109  * La procedure "close_hash" libere la table de codage et ses elements.
110  */
111 static void close_hash(void)
112 {
113  Bucket **head = hash_tbl;
114  Bucket **bend = head + PRIME;
115  Bucket *bp; /* element courant */
116  Bucket *next; /* element suivant */
117 
118  for (; head < bend; head++) { /* libere les listes */
119  for (bp = *head; bp != NULL; bp = next) {
120  next = bp->next;
121  free((char *)bp);
122  }
123  }
124  free((char *)hash_tbl); /* libere la table */
125 }
126 
127 /*
128  * La procedure "hashpjw" calcule un indice code a partir de la chaine
129  * de caracteres "str".
130  * Pour plus de renseignements, voir :
131  * "Compilers. Principles, Techniques, and Tools",
132  * A.V. AHO, R. SETHI, J.D. ULLMAN,
133  * ADDISON-WESLEY PUBLISHING COMPANY, pp 436.
134  * Entree :
135  * str Chaine de caracteres a coder.
136  * Sortie :
137  * Le code de la chaine.
138  */
139 static int hashpjw(const char *str)
140 {
141  unsigned h = 0; /* "hash value" */
142 
143  for (; *str != '\0'; str++) {
144  unsigned g;
145  h = (h << 4) + (unsigned)(*str);
146  if ((g = h & ~0xfffffff) != 0) {
147  h ^= g >> 24;
148  h ^= g;
149  }
150  }
151  return ((int)(h % PRIME));
152 }
153 
154 /*
155  * La procedure "insert_keyword" insere en tete d'un point d'entree
156  * de la table de "hachage" le mot cle ayant pour identificateur
157  * la chaine de caracteres "str" et pour valeur "token".
158  * Entree :
159  * str Chaine de caracteres du mot cle.
160  * token Valeur du jeton associe au mot cle.
161  */
162 static void insert_keyword(const char *str, Index token)
163 {
164  Bucket **head = hash_tbl + hashpjw(str);
165  Bucket *bp;
166  Byte length;
167 
168  length = (Byte)(strlen(str)); // Warning! Overflow possible!
169  if ((bp = (Bucket *)malloc(sizeof(Bucket) + length + 1)) == NULL) {
170  static const char proc_name[] = "insert_keyword";
171  perror(proc_name);
172  exit(1);
173  }
174  bp->length = length;
175  bp->token = token;
176  bp->ident = (char *)(bp + 1);
177  strcpy(bp->ident, str);
178 
179  bp->next = *head; /* insere "b" en tete de "head" */
180  *head = bp;
181 }
182 
183 /*
184  * La pocedure "get_symbol" verifie que la chaine pointee par "ident"
185  * de longeur "length" est un mot cle.
186  * Entree :
187  * ident Chaine de l'identificateur.
188  * length Nombre de caracteres de la chaine.
189  * Note :
190  * La chaine "ident" n'est pas terminee par '\0'.
191  * Sortie :
192  * Valeur du jeton associe si c'est un mot cle, 0 sinon.
193  */
194 Index get_symbol(char *ident, int length)
195 {
196  Bucket *bp;
197  const char *kwd;
198  char *idn = ident;
199  int len = length;
200 
201  { /* calcule le code de hachage (voir "hashpjw") */
202  unsigned h = 0; /* "hash value" */
203 
204  for (; len != 0; idn++, len--) {
205  unsigned g;
206  h = (h << 4) + (unsigned)(*idn);
207  if ((g = h & ~0xfffffff) != 0) {
208  h ^= g >> 24;
209  h ^= g;
210  }
211  }
212  bp = hash_tbl[h % PRIME];
213  }
214 
215  /* recherche le mot cle */
216 
217  for (; bp != NULL; NEXT(bp)) {
218  if (length == bp->length) {
219  idn = ident;
220  len = length;
221  kwd = bp->ident;
222  for (; *idn == *kwd; idn++, kwd++) {
223  --len;
224  if (len == 0)
225  return (bp->token);
226  }
227  }
228  }
229  return (0); /* identificateur */
230 }
231 
232 #endif