html/suif1_92.html

   1 <HTML>
   2 <HEAD>
   3 <!-- This HTML file has been created by texi2html 1.54
   4      from suif1.texi on 28 April 1999 -->
   5
   6 <TITLE>The SUIF Version 1 Library - Generic Lists</TITLE>
   7 <link href="suif1_93.html" rel=Next>
   8 <link href="suif1_91.html" rel=Previous>
   9 <link href="suif1_toc.html" rel=ToC>
  10
  11 </HEAD>
  12 <BODY>
  13 <p>Go to the <A HREF="suif1_1.html">first</A>, <A HREF="suif1_91.html">previous</A>, <A HREF="suif1_93.html">next</A>, <A HREF="suif1_113.html">last</A> section, <A HREF="suif1_toc.html">table of contents</A>.
  14 <P><HR><P>
  15
  16
  17 <H2><A NAME="SEC92" HREF="suif1_toc.html#TOC92">Generic Lists</A></H2>
  18 <P>
  19 <A NAME="IDX654"></A>
  20 <A NAME="IDX655"></A>
  21 <A NAME="IDX656"></A>
  22
  23 </P>
  24 <P>
  25 <A NAME="IDX657"></A>
  26 While linked lists are not very efficient data structures, they are
  27 flexible and work well for a research compiler like SUIF.  Various kinds
  28 of lists are used throughout the SUIF library and most SUIF programs.
  29 Almost all of these lists are derived from the <CODE>glist</CODE> base class.
  30 The files <TT>`glist.h'</TT> and <TT>`glist.cc'</TT> contain the declaration and
  31 implementation of this class.
  32
  33 </P>
  34 <P>
  35 <A NAME="IDX658"></A>
  36 The individual elements of these lists are derived from the
  37 <CODE>glist_e</CODE> class.  The base class only contains a pointer to the
  38 next element.  To make a useful list, a derived class must add data
  39 fields to the list elements.  For doubly-linked lists, the list elements
  40 are further extended to include backwards pointers (see section <A HREF="suif1_95.html#SEC95">Doubly-Linked Lists</A>).
  41
  42 </P>
  43 <P>
  44 The <CODE>glist</CODE> class includes pointers to the head and tail elements.
  45 This makes it possible to efficiently add elements at either end of the
  46 list.  A variety of methods are provided to insert and remove individual
  47 elements, as well as to combine entire lists in different ways.  All of
  48 these operations are straightforward and are clearly documented in the
  49 code.
  50
  51 </P>
  52 <P>
  53 <A NAME="IDX659"></A>
  54 <A NAME="IDX660"></A>
  55 The SUIF library also provides iterators for lists.  This allows you to
  56 write code at a higher level of abstraction.  Instead of rewriting the
  57 same code everywhere that your program traverses lists, you can just use
  58 the built-in iterators.  The base iterator class is <CODE>glist_iter</CODE>.
  59 An iterator is initialized with a pointer to a particular list.  It then
  60 returns successive elements from the list (via the <CODE>step</CODE> method)
  61 until the <CODE>is_empty</CODE> method returns <CODE>TRUE</CODE>.  Other methods are
  62 available to access the current and next list elements without advancing
  63 the iterator.
  64
  65 </P>
  66 <P>
  67 <A NAME="IDX661"></A>
  68 To make a list with a particular type of elements, one must derive new
  69 list classes that inherit from the base classes described above.  While
  70 this is not difficult, it is cumbersome and time consuming.  Instead of
  71 explicitly declaring these derived classes, the
  72 <CODE>DECLARE_LIST_CLASS</CODE> macro may be used to declare them
  73 automatically.  This macro takes two arguments: the name of the new list
  74 class and the type for the data in the list elements.  It then creates
  75 classes derived from <CODE>glist</CODE>, <CODE>glist_e</CODE>, and <CODE>glist_iter</CODE>
  76 that use the specified type for the element data <A NAME="DOCF6" HREF="suif1_foot.html#FOOT6">(6)</A>.
  77 For example, <CODE>DECLARE_LIST_CLASS(string_list, char*)</CODE> generates
  78 classes named <CODE>string_list</CODE>, <CODE>string_list_e</CODE>, and
  79 <CODE>string_list_iter</CODE>.  The <CODE>string_list_e</CODE> class includes a
  80 <CODE>contents</CODE> field with type <CODE>char*</CODE>.  The methods in all of
  81 these classes are changed to use the <CODE>char*</CODE> type where appropriate
  82 and some new methods are added.  (Once the element data type is known,
  83 it is possible to provide methods, such as <CODE>copy</CODE>, that must access
  84 the data fields.)
  85
  86 </P>
  87 <P>
  88 The <CODE>DECLARE_LIST_CLASS</CODE> macro is implemented by other macros, one
  89 for each kind of class.  Using these other macros directly gives you
  90 more control over the names of the new classes and allows you to add
  91 more methods in the derived classes.  There are several examples of this
  92 in the library code.  Another advanced feature of the
  93 <CODE>DECLARE_LIST_CLASS</CODE> macro is the virtual <CODE>set_elem</CODE> method
  94 which is included in the generated list class.  This method is called
  95 for every element that is added to a list.  The base <CODE>set_elem</CODE>
  96 method does nothing, but a derived class can change this method to
  97 automatically update information in list elements when they are
  98 added to a list.
  99
 100 </P>
 101
 102 <P><HR><P>
 103 <p>Go to the <A HREF="suif1_1.html">first</A>, <A HREF="suif1_91.html">previous</A>, <A HREF="suif1_93.html">next</A>, <A HREF="suif1_113.html">last</A> section, <A HREF="suif1_toc.html">table of contents</A>.
 104 </BODY>
 105 </HTML>