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