Mastering Algorithms With C - Kyle Loudon [71]
* *
* Remove the data from the bucket. *
* *
***********************************************************************/
if (list_rem_next(&htbl->table[bucket], prev, data) == 0) {
htbl->size--;
return 0;
}
else {
return -1;
}
}
prev = element;
}
/*****************************************************************************
* *
* Return that the data was not found. *
* *
*****************************************************************************/
return -1;
}
/*****************************************************************************
* *
* ----------------------------- chtbl_lookup ----------------------------- *
* *
*****************************************************************************/
int chtbl_lookup(const CHTbl *htbl, void **data) {
ListElmt *element;
int bucket;
/*****************************************************************************
* *
* Hash the key. *
* *
*****************************************************************************/
bucket = htbl->h(*data) % htbl->buckets;
/*****************************************************************************
* *
* Search for the data in the bucket. *
* *
*****************************************************************************/
for (element = list_head(&htbl->table[bucket]); element != NULL; element =
list_next(element)) {
if (htbl->match(*data, list_data(element))) {
/***********************************************************************
* *
* Pass back the data from the table. *
* *
***********************************************************************/
*data = list_data(element);
return 0;
}
}
/*****************************************************************************
* *
* Return that the data was not found. *
* *
*****************************************************************************/
return -1;
}
Chained Hash Table Example: Symbol Tables
An important application of hash tables is the way compilers maintain information about symbols encountered in a program. Formally, a compiler translates a program written in one language, a source language such as C, into another language, which is a set of instructions for the machine on which the program will run. In order to maintain information about the symbols in a program, compilers make use of a data structure called a symbol table. Symbol tables are often implemented as hash tables because a compiler must be able to store and retrieve information about symbols very quickly.
Several parts of a compiler access the symbol table during various phases of the compilation process. One part, the lexical analyzer, inserts symbols. The lexical analyzer is the part of a compiler charged with grouping characters from the source code into meaningful strings, called lexemes. These are translated into syntactic elements, called tokens , that are passed on to the parser . The parser performs syntactical analysis. As the lexical analyzer encounters symbols in its input stream, it stores information about them into the symbol table. Two important attributes stored by the lexical analyzer are a symbol's lexeme and the type of token the lexeme constitutes (e.g., an identifier or an operator).
The example presented here is a very simple lexical analyzer that analyzes a string of characters and then groups the characters into one of two types of tokens: a token consisting only of digits or a token consisting of something other than digits alone. For simplicity, we assume that tokens are separated in the input stream by a single blank. The lexical analyzer is implemented as a function, lex (see Examples Example 8.4 and Example 8.5), which a parser calls each time it requires another token.
The function works by first calling the next_token function (whose implementation is not shown) to get the next blank-delimited string from the input stream istream. If next_token returns NULL, there are no more tokens in the input stream. In this case, the function returns lexit, which tells the parser that