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