Character table in C

Question

I am currently developing a static analysis tool that performs pattern matching. I use Flex to create a lexical analyzer, and I wrote code to manage a character table. I am not very experienced with C , so I decided to implement the symbol table as a linear linked list.

#include <stdlib.h> #include <stdio.h> #include <string.h> struct symtab { int id; char *name; int type; struct symtab *next; }; enum types { KEYWORD = 1, CONSTANT, IDENTIFIER, OPERATOR, DELIMITER, WHITESPACE }; struct symtab *last_entry(struct symtab *start) { struct symtab *p; p = start; while(p -> next != NULL) { p = p -> next; } return p; } void add_entry(char* name, int type, struct symtab *start) { struct symtab *new; new = last_entry(start); int id; if(new == start) { new = start; id = 0; } else { new = malloc(sizeof(struct symtab)); id = last_entry(start) -> id; last_entry(start) -> next = new; } new -> id = id + 1; new -> name = name; new -> type = type; new -> next = NULL; } struct symtab *find_entry(char* name, struct symtab *start) { struct symtab *p; p = start; while(p -> next != NULL) { if(strcmp(p -> name, name) == 0) { return p; } } } 

However, when I use add_entry() to add characters, and then try to find them with find_entry() , find_entry() returns null. Can anybody help?

Answer 1

It looks like you are trying to present the list as a header object (start), followed by the actual elements of the list. This is a good idea because it simplifies dealing with an empty list, but you do not have the correct implementation.

When you add, you need to remove the special case code that you have to run last_entry. The start node will never contain character data.

When searching, you must make sure that you miss the head (beginning), since it does not contain character data. The second mistake in your search code is that you stop searching when p-> next is NULL (this means you can never return the final element in your list.) You must stop when p is NULL.

Of course, you should not use a linked list at all: a hash table would be a better choice, since it had better performance and memory efficiency.