Go to the previous, next section.

Generic Lists

While linked lists are not very efficient data structures, they are flexible and work well for a research compiler like SUIF. Various kinds of lists are used throughout the SUIF library and most SUIF programs. Almost all of these lists are derived from the glist base class. The files `glist.h' and `glist.cc' contain the declaration and implementation of this class.

The individual elements of these lists are derived from the glist_e class. The base class only contains a pointer to the next element. To make a useful list, a derived class must add data fields to the list elements. For doubly-linked lists, the list elements are further extended to include backwards pointers (see section Doubly-Linked Lists).

The glist class includes pointers to the head and tail elements. This makes it possible to efficiently add elements at either end of the list. A variety of methods are provided to insert and remove individual elements, as well as to combine entire lists in different ways. All of these operations are straightforward and are clearly documented in the code.

The SUIF library also provides iterators for lists. This allows you to write code at a higher level of abstraction. Instead of rewriting the same code everywhere that your program traverses lists, you can just use the built-in iterators. The base iterator class is glist_iter. An iterator is initialized with a pointer to a particular list. It then returns successive elements from the list (via the step method) until the is_empty method returns TRUE. Other methods are available to access the current and next list elements without advancing the iterator.

To make a list with a particular type of elements, one must derive new list classes that inherit from the base classes described above. While this is not difficult, it is cumbersome and time consuming. Instead of explicitly declaring these derived classes, the DECLARE_LIST_CLASS macro may be used to declare them automatically. This macro takes two arguments: the name of the new list class and the type for the data in the list elements. It then creates classes derived from glist, glist_e, and glist_iter that use the specified type for the element data (6). For example, DECLARE_LIST_CLASS(string_list, char*) generates classes named string_list, string_list_e, and string_list_iter. The string_list_e class includes a contents field with type char*. The methods in all of these classes are changed to use the char* type where appropriate and some new methods are added. (Once the element data type is known, it is possible to provide methods, such as copy, that must access the data fields.)

The DECLARE_LIST_CLASS macro is implemented by other macros, one for each kind of class. Using these other macros directly gives you more control over the names of the new classes and allows you to add more methods in the derived classes. There are several examples of this in the library code. Another advanced feature of the DECLARE_LIST_CLASS macro is the virtual set_elem method which is included in the generated list class. This method is called for every element that is added to a list. The base set_elem method does nothing, but a derived class can change this method to automatically update information in list elements when they are added to a list.

Go to the previous, next section.