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 std::ostream & toXml (std::ostream & str, int indent ) const; 00094 00095 // remove yourself from the SymbolTable. 00096 void remove (); 00097 }; 00098 00099 00100 class SymbolTable 00101 #ifdef D_MEMUSAGE 00102 : public MemUsage 00103 #endif 00104 { 00105 private: 00106 // number of buckets in hash table 00107 int m_prime; 00108 00109 // the hash function 00110 int hash (const char *s); 00111 00112 // the hash table [0 ... prime-1] 00113 // a bucket is a (doubly) linked list of TableEntries 00114 // (via m_prev/m_next) each having the same hash value 00115 // (standard hash table implementation) 00116 // Additionally, scopes are represented by linking 00117 // TableEntries with equal key values (and naturally the 00118 // same hash value) via m_outer. The start of 00119 // this chain always represents the innermost (most 00120 // recent) definition of a symbol. 00121 00122 TableEntry **m_table; 00123 00124 // these are the actually used entries of this table 00125 // they are only stored if needed 00126 bool m_track_usage; 00127 std::map<const char *, TableEntry *> *m_used; 00128 00129 // stack of external references, needed during bytecode I/O by YSImport 00130 // (triggered by openReferences()) 00131 typedef std::stack <std::vector<TableEntry *> *> xrefs_t; 00132 xrefs_t* m_xrefs; 00133 00134 public: 00135 size_t mem_size () const { return sizeof (SymbolTable); } 00136 //--------------------------------------------------------------- 00137 // Constructor/Destructor 00138 00139 // create SymbolTable with hashsize prime 00140 SymbolTable (int prime); 00141 ~SymbolTable(); 00142 00143 //--------------------------------------------------------------- 00144 // Table access 00145 00146 // full copy of the current table into a namespace 00147 void tableCopy(Y2Namespace* tofill) const; 00148 00149 // return size of hash table 00150 int size() const; 00151 00152 // consumer returns true to continue iterating 00153 typedef bool (* EntryConsumer) (const SymbolEntry&); 00167 void forEach (EntryConsumer consumer) const; 00168 00169 //--------------------------------------------------------------- 00170 // enter/find/remove 00171 00172 // enter SymbolEntry to table as innermost definition 00173 TableEntry *enter (const char *key, SymbolEntryPtr entry, const Point *point); 00174 00175 // enter TableEntry to table as innermost definition 00176 TableEntry *enter (TableEntry *entry); 00177 00178 // find (innermost) TableEntry by key and add to m_used 00179 TableEntry *find (const char *key, SymbolEntry::category_t category = SymbolEntry::c_unspec); 00180 00181 // find (innermost) TableEntry by key and add to m_xrefs 00182 TableEntry *xref (const char *key); 00183 00184 // remove the entry from table 00185 void remove (TableEntry *entry); 00186 00187 //--------------------------------------------------------------- 00188 // xref tracking 00189 00190 // push empty list of references on top of m_references 00191 // start tracking references, keep a list of actually referenced (-> find()) entries 00192 void openXRefs (); 00193 00194 // pop current list of references from top of m_references 00195 void closeXRefs (); 00196 00197 // return the vector of references from top of m_references 00198 SymbolEntryPtr getXRef (unsigned int position) const; 00199 00200 //--------------------------------------------------------------- 00201 // usage tracking 00202 00203 void startUsage (); 00204 00205 int countUsage (); 00206 00207 void endUsage (); 00208 00209 void enableUsage (); 00210 void disableUsage (); 00211 00212 //--------------------------------------------------------------- 00213 // write usage to stream, see YSImport 00214 00215 std::ostream &writeUsage (std::ostream & str) const; 00216 std::ostream &writeXmlUsage( std::ostream & str, int indent ) const; 00217 00218 //--------------------------------------------------------------- 00219 // string 00220 00221 string toString() const; 00222 string toStringSymbols() const; 00223 }; 00224 00225 #endif // SymbolTable_h