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