Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members | Examples

SymbolTable.h

Go to the documentation of this file.
00001 /*----------------------------------------------------------------------\
00002 |                                                                       |
00003 |                     __   __    ____ _____ ____                        |
00004 |                     \ \ / /_ _/ ___|_   _|___ \                       |
00005 |                      \ V / _` \___ \ | |   __) |                      |
00006 |                       | | (_| |___) || |  / __/                       |
00007 |                       |_|\__,_|____/ |_| |_____|                      |
00008 |                                                                       |
00009 |                               core system                             |
00010 |                                                         (C) SuSE GmbH |
00011 \-----------------------------------------------------------------------/
00012 
00013    File:        SymbolTable.h
00014                 hash table class
00015 
00016    Author:      Klaus Kaempf <kkaempf@suse.de>
00017    Maintainer:  Klaus Kaempf <kkaempf@suse.de>
00018 
00019    SymbolTable implements a hash table of nested SymbolEntries
00020 
00021 /-*/
00022 // -*- c++ -*-
00023 
00024 #ifndef SymbolTable_h
00025 #define SymbolTable_h
00026 
00027 #include <string>
00028 using std::string;
00029 #include <list>
00030 #include <stack>
00031 
00032 // MemUsage.h defines/undefines D_MEMUSAGE
00033 #include <y2util/MemUsage.h>
00034 #include "ycp/SymbolEntryPtr.h"
00035 #include "ycp/Point.h"
00036 
00037 class SymbolTable;
00038 
00039 // TableEntry
00040 
00041 class TableEntry
00042 #ifdef D_MEMUSAGE
00043    : public MemUsage
00044 #endif
00045 {
00046     // hash bucket pointers (all TableEntries of a bucket have the same hash value)
00047     TableEntry *m_prev;
00048     TableEntry *m_next;
00049 
00050     // nesting pointers, implements stacked environments (of nested blocks)
00051     //   when adding a new entry (via SymbolTable::enter())
00052     //   and another entry with the same key (variable name) already exists,
00053     //   this adding must be the result of a new block (scope)
00054     //   since duplicate entries into the same block are checked by
00055     //   the parser.
00056     // when looking up a key, we start with the innermost entry which
00057     //   represents the 'most recent' definition
00058     // when removing a key, only the innermost entry is removed.
00059 
00060     TableEntry *m_outer;
00061 
00062     const char *m_key;                  // search key, usually the symbol name
00063     SymbolEntryPtr m_entry;             // complete symbol data, cannot be const since category might change
00064     const Point *m_point;               // definition point (file, line)
00065 
00066     SymbolTable *m_table;               // backpointer to table
00067 
00068 protected:
00069     friend class SymbolTable;
00070 
00071 public:
00072     size_t mem_size () const { return sizeof (TableEntry); }
00073     TableEntry (const char *key, SymbolEntryPtr entry, const Point *point, SymbolTable *table = 0);
00074     TableEntry (std::istream & str);
00075     ~TableEntry ();
00076     const char *key () const;
00077     TableEntry *next () const;
00078     const SymbolTable *table () const;
00079     SymbolEntryPtr sentry () const;
00080     const Point *point () const;
00081     string toString () const;
00082     string toStringSymbols () const;
00083     void makeDefinition (int line);     // convert declaration to definition (exchanges m_point)
00084     std::ostream & toStream (std::ostream & str) const;
00085 
00086     // remove yourself from the SymbolTable.
00087     void remove ();
00088 };
00089 
00090 
00091 class SymbolTable
00092 #ifdef D_MEMUSAGE
00093    : public MemUsage
00094 #endif
00095 {
00096 private:
00097     // number of buckets in hash table
00098     int m_prime;
00099 
00100     // the hash function
00101     int hash (const char *s);
00102 
00103     // the hash table [0 ... prime-1]
00104     // a bucket is a (doubly) linked list of TableEntries
00105     // (via m_prev/m_next) each having the same hash value
00106     // (standard hash table implementation)
00107     // Additionally, scopes are represented by linking
00108     // TableEntries with equal key values (and naturally the
00109     // same hash value) via m_outer. The start of
00110     // this chain always represents the innermost (most
00111     // recent) definition of a symbol.
00112 
00113     TableEntry **m_table;
00114 
00115     // these are the actually used entries of this table
00116     // they are only stored if needed
00117     bool m_track_usage;
00118     std::map<const char *, TableEntry *> *m_used;
00119 
00120     // stack of external references, needed during bytecode I/O by YSImport
00121     //  (triggered by openReferences())
00122     std::stack <std::vector<TableEntry *> *> m_xrefs;
00123 
00124 public:
00125     size_t mem_size () const { return sizeof (SymbolTable); }
00126     //---------------------------------------------------------------
00127     // Constructor/Destructor
00128 
00129     // create SymbolTable with hashsize prime
00130     SymbolTable (int prime);
00131     ~SymbolTable();
00132 
00133     //---------------------------------------------------------------
00134     // Table access
00135 
00136     // access table (for traversal)
00137     const TableEntry **table() const;
00138 
00139     // return size of hash table
00140     int size() const;
00141 
00142     //---------------------------------------------------------------
00143     // enter/find/remove
00144 
00145     // enter SymbolEntry to table as innermost definition
00146     TableEntry *enter (const char *key, SymbolEntryPtr entry, const Point *point);
00147 
00148     // enter TableEntry to table as innermost definition
00149     TableEntry *enter (TableEntry *entry);
00150 
00151     // find (innermost) TableEntry by key and add to m_used
00152     TableEntry *find (const char *key, SymbolEntry::category_t category = SymbolEntry::c_unspec);
00153 
00154     // find (innermost) TableEntry by key and add to m_xrefs
00155     TableEntry *xref (const char *key);
00156 
00157     // remove the entry from table
00158     void remove (TableEntry *entry);
00159 
00160     //---------------------------------------------------------------
00161     // xref tracking
00162 
00163     // push empty list of references on top of m_references
00164     // start tracking references, keep a list of actually referenced (-> find()) entries
00165     void openXRefs ();
00166 
00167     // pop current list of references from top of m_references
00168     void closeXRefs ();
00169 
00170     // return the vector of references from top of m_references
00171     SymbolEntryPtr getXRef (unsigned int position) const;
00172 
00173     //---------------------------------------------------------------
00174     // usage tracking
00175 
00176     void startUsage ();
00177 
00178     int countUsage ();
00179 
00180     void endUsage ();
00181 
00182     void enableUsage ();
00183     void disableUsage ();
00184 
00185     //---------------------------------------------------------------
00186     // write usage to stream, see YSImport
00187 
00188     std::ostream &SymbolTable::writeUsage (std::ostream & str) const;
00189 
00190     //---------------------------------------------------------------
00191     // string
00192 
00193     string toString() const;
00194     string toStringSymbols() const;
00195 };
00196 
00197 #endif // SymbolTable_h

Generated on Fri Nov 9 18:15:22 2007 for yast2-core by doxygen 1.3.6