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 
00035 #include <y2/SymbolEntry.h>
00036 
00037 class SymbolTable;
00038 class Point;
00039 
00040 // TableEntry
00041 
00042 class TableEntry
00043 #ifdef D_MEMUSAGE
00044    : public MemUsage
00045 #endif
00046 {
00047     // hash bucket pointers (all TableEntries of a bucket have the same hash value)
00048     TableEntry *m_prev;
00049     TableEntry *m_next;
00050     
00051     // pointers to the next/prev entry with the same key and type -> overloaded
00052     // entries. Only the first one has a valid m_outer pointer!!!
00053     TableEntry *m_overloaded_prev;
00054     TableEntry *m_overloaded_next;
00055 
00056     // nesting pointers, implements stacked environments (of nested blocks)
00057     //   when adding a new entry (via SymbolTable::enter())
00058     //   and another entry with the same key (variable name) already exists,
00059     //   this adding must be the result of a new block (scope)
00060     //   since duplicate entries into the same block are checked by
00061     //   the parser.
00062     // when looking up a key, we start with the innermost entry which
00063     //   represents the 'most recent' definition
00064     // when removing a key, only the innermost entry is removed.
00065 
00066     TableEntry *m_outer;
00067 
00068     const char *m_key;                  // search key, usually the symbol name
00069     SymbolEntryPtr m_entry;             // complete symbol data, cannot be const since category might change
00070     const Point *m_point;               // definition point (file, line)
00071 
00072     SymbolTable *m_table;               // backpointer to table
00073 
00074 protected:
00075     friend class SymbolTable;
00076 
00077 public:
00078     size_t mem_size () const { return sizeof (TableEntry); }
00079     TableEntry (const char *key, SymbolEntryPtr entry, const Point *point, SymbolTable *table = 0);
00080     TableEntry (bytecodeistream & str);
00081     ~TableEntry ();
00082     const char *key () const;
00083     TableEntry *next () const;
00084     TableEntry *next_overloaded () const;
00085     bool isOverloaded () const;
00086     const SymbolTable *table () const;
00087     SymbolEntryPtr sentry () const;
00088     const Point *point () const;
00089     string toString () const;
00090     string toStringSymbols () const;
00091     void makeDefinition (int line);     // convert declaration to definition (exchanges m_point)
00092     std::ostream & toStream (std::ostream & str) const;
00093 
00094     // remove yourself from the SymbolTable.
00095     void remove ();
00096 };
00097 
00098 
00099 class SymbolTable
00100 #ifdef D_MEMUSAGE
00101    : public MemUsage
00102 #endif
00103 {
00104 private:
00105     // number of buckets in hash table
00106     int m_prime;
00107 
00108     // the hash function
00109     int hash (const char *s);
00110 
00111     // the hash table [0 ... prime-1]
00112     // a bucket is a (doubly) linked list of TableEntries
00113     // (via m_prev/m_next) each having the same hash value
00114     // (standard hash table implementation)
00115     // Additionally, scopes are represented by linking
00116     // TableEntries with equal key values (and naturally the
00117     // same hash value) via m_outer. The start of
00118     // this chain always represents the innermost (most
00119     // recent) definition of a symbol.
00120 
00121     TableEntry **m_table;
00122 
00123     // these are the actually used entries of this table
00124     // they are only stored if needed
00125     bool m_track_usage;
00126     std::map<const char *, TableEntry *> *m_used;
00127 
00128     // stack of external references, needed during bytecode I/O by YSImport
00129     //  (triggered by openReferences())
00130     typedef std::stack <std::vector<TableEntry *> *> xrefs_t;
00131     xrefs_t* m_xrefs;
00132 
00133 public:
00134     size_t mem_size () const { return sizeof (SymbolTable); }
00135     //---------------------------------------------------------------
00136     // Constructor/Destructor
00137 
00138     // create SymbolTable with hashsize prime
00139     SymbolTable (int prime);
00140     ~SymbolTable();
00141 
00142     //---------------------------------------------------------------
00143     // Table access
00144 
00145     // full copy of the current table into a namespace
00146     void tableCopy(Y2Namespace* tofill) const;
00147 
00148     // return size of hash table
00149     int size() const;
00150 
00151     //---------------------------------------------------------------
00152     // enter/find/remove
00153 
00154     // enter SymbolEntry to table as innermost definition
00155     TableEntry *enter (const char *key, SymbolEntryPtr entry, const Point *point);
00156 
00157     // enter TableEntry to table as innermost definition
00158     TableEntry *enter (TableEntry *entry);
00159 
00160     // find (innermost) TableEntry by key and add to m_used
00161     TableEntry *find (const char *key, SymbolEntry::category_t category = SymbolEntry::c_unspec);
00162 
00163     // find (innermost) TableEntry by key and add to m_xrefs
00164     TableEntry *xref (const char *key);
00165 
00166     // remove the entry from table
00167     void remove (TableEntry *entry);
00168 
00169     //---------------------------------------------------------------
00170     // xref tracking
00171 
00172     // push empty list of references on top of m_references
00173     // start tracking references, keep a list of actually referenced (-> find()) entries
00174     void openXRefs ();
00175 
00176     // pop current list of references from top of m_references
00177     void closeXRefs ();
00178 
00179     // return the vector of references from top of m_references
00180     SymbolEntryPtr getXRef (unsigned int position) const;
00181 
00182     //---------------------------------------------------------------
00183     // usage tracking
00184 
00185     void startUsage ();
00186 
00187     int countUsage ();
00188 
00189     void endUsage ();
00190 
00191     void enableUsage ();
00192     void disableUsage ();
00193 
00194     //---------------------------------------------------------------
00195     // write usage to stream, see YSImport
00196 
00197     std::ostream &writeUsage (std::ostream & str) const;
00198 
00199     //---------------------------------------------------------------
00200     // string
00201 
00202     string toString() const;
00203     string toStringSymbols() const;
00204 };
00205 
00206 #endif // SymbolTable_h

Generated on Fri Jun 16 18:07:45 2006 for yast2-core by  doxygen 1.4.6