yast2-core
SymbolTable.h
Go to the documentation of this file.
1 /*----------------------------------------------------------------------\
2 | |
3 | __ __ ____ _____ ____ |
4 | \ \ / /_ _/ ___|_ _|___ \ |
5 | \ V / _` \___ \ | | __) | |
6 | | | (_| |___) || | / __/ |
7 | |_|\__,_|____/ |_| |_____| |
8 | |
9 | core system |
10 | (C) SuSE GmbH |
11 \-----------------------------------------------------------------------/
12 
13  File: SymbolTable.h
14  hash table class
15 
16  Author: Klaus Kaempf <kkaempf@suse.de>
17  Maintainer: Klaus Kaempf <kkaempf@suse.de>
18 
19  SymbolTable implements a hash table of nested SymbolEntries
20 
21 /-*/
22 // -*- c++ -*-
23 
24 #ifndef SymbolTable_h
25 #define SymbolTable_h
26 
27 #include <string>
28 using std::string;
29 #include <list>
30 #include <stack>
31 
32 // MemUsage.h defines/undefines D_MEMUSAGE
33 #include <y2util/MemUsage.h>
34 
35 #include <y2/SymbolEntry.h>
36 
37 class SymbolTable;
38 class Point;
39 
40 // TableEntry
41 
43 #ifdef D_MEMUSAGE
44  : public MemUsage
45 #endif
46 {
47  // hash bucket pointers (all TableEntries of a bucket have the same hash value)
50 
51  // pointers to the next/prev entry with the same key and type -> overloaded
52  // entries. Only the first one has a valid m_outer pointer!!!
55 
56  // nesting pointers, implements stacked environments (of nested blocks)
57  // when adding a new entry (via SymbolTable::enter())
58  // and another entry with the same key (variable name) already exists,
59  // this adding must be the result of a new block (scope)
60  // since duplicate entries into the same block are checked by
61  // the parser.
62  // when looking up a key, we start with the innermost entry which
63  // represents the 'most recent' definition
64  // when removing a key, only the innermost entry is removed.
65 
67 
68  const char *m_key; // search key, usually the symbol name
69  SymbolEntryPtr m_entry; // complete symbol data, cannot be const since category might change
70  const Point *m_point; // definition point (file, line)
71 
72  SymbolTable *m_table; // backpointer to table
73 
74 protected:
75  friend class SymbolTable;
76 
77 public:
78  size_t mem_size () const { return sizeof (TableEntry); }
79  TableEntry (const char *key, SymbolEntryPtr entry, const Point *point, SymbolTable *table = 0);
81  ~TableEntry ();
82  const char *key () const;
83  TableEntry *next () const;
84  TableEntry *next_overloaded () const;
85  bool isOverloaded () const;
86  const SymbolTable *table () const;
87  SymbolEntryPtr sentry () const;
88  const Point *point () const;
89  string toString () const;
90  string toStringSymbols () const;
91  void makeDefinition (int line); // convert declaration to definition (exchanges m_point)
92  std::ostream & toStream (std::ostream & str) const;
93  std::ostream & toXml (std::ostream & str, int indent ) const;
94 
95  // remove yourself from the SymbolTable.
96  void remove ();
97 };
98 
99 
101 #ifdef D_MEMUSAGE
102  : public MemUsage
103 #endif
104 {
105 private:
106  // number of buckets in hash table
107  int m_prime;
108 
109  // the hash function
110  int hash (const char *s);
111 
112  // the hash table [0 ... prime-1]
113  // a bucket is a (doubly) linked list of TableEntries
114  // (via m_prev/m_next) each having the same hash value
115  // (standard hash table implementation)
116  // Additionally, scopes are represented by linking
117  // TableEntries with equal key values (and naturally the
118  // same hash value) via m_outer. The start of
119  // this chain always represents the innermost (most
120  // recent) definition of a symbol.
121 
123 
124  // these are the actually used entries of this table
125  // they are only stored if needed
127  std::map<const char *, TableEntry *> *m_used;
128 
129  // stack of external references, needed during bytecode I/O by YSImport
130  // (triggered by openReferences())
131  typedef std::stack <std::vector<TableEntry *> *> xrefs_t;
133 
134 public:
135  size_t mem_size () const { return sizeof (SymbolTable); }
136  //---------------------------------------------------------------
137  // Constructor/Destructor
138 
139  // create SymbolTable with hashsize prime
140  SymbolTable (int prime);
141  ~SymbolTable();
142 
143  //---------------------------------------------------------------
144  // Table access
145 
146  // full copy of the current table into a namespace
147  void tableCopy(Y2Namespace* tofill) const;
148 
149  // return size of hash table
150  int size() const;
151 
152  // consumer returns true to continue iterating
153  typedef bool (* EntryConsumer) (const SymbolEntry&);
167  void forEach (EntryConsumer consumer) const;
168 
169  //---------------------------------------------------------------
170  // enter/find/remove
171 
172  // enter SymbolEntry to table as innermost definition
173  TableEntry *enter (const char *key, SymbolEntryPtr entry, const Point *point);
174 
175  // enter TableEntry to table as innermost definition
176  TableEntry *enter (TableEntry *entry);
177 
178  // find (innermost) TableEntry by key and add to m_used
179  TableEntry *find (const char *key, SymbolEntry::category_t category = SymbolEntry::c_unspec);
180 
181  // find (innermost) TableEntry by key and add to m_xrefs
182  TableEntry *xref (const char *key);
183 
184  // remove the entry from table
185  void remove (TableEntry *entry);
186 
187  //---------------------------------------------------------------
188  // xref tracking
189 
190  // push empty list of references on top of m_references
191  // start tracking references, keep a list of actually referenced (-> find()) entries
192  void openXRefs ();
193 
194  // pop current list of references from top of m_references
195  void closeXRefs ();
196 
197  // return the vector of references from top of m_references
198  SymbolEntryPtr getXRef (unsigned int position) const;
199 
200  //---------------------------------------------------------------
201  // usage tracking
202 
203  void startUsage ();
204 
205  int countUsage ();
206 
207  void endUsage ();
208 
209  void enableUsage ();
210  void disableUsage ();
211 
212  //---------------------------------------------------------------
213  // write usage to stream, see YSImport
214 
215  std::ostream &writeUsage (std::ostream & str) const;
216  std::ostream &writeXmlUsage( std::ostream & str, int indent ) const;
217 
218  //---------------------------------------------------------------
219  // string
220 
221  string toString() const;
222  string toStringSymbols() const;
223 };
224 
225 #endif // SymbolTable_h
int size() const
Definition: SymbolTable.cc:559
SymbolTable(int prime)
Definition: SymbolTable.cc:239
void tableCopy(Y2Namespace *tofill) const
Definition: SymbolTable.cc:996
TableEntry * xref(const char *key)
Definition: SymbolTable.cc:734
Definition: SymbolEntry.h:41
void closeXRefs()
Definition: SymbolTable.cc:351
#define str
Definition: scanner.cc:997
const SymbolTable * table() const
Definition: SymbolTable.cc:119
const char * m_key
Definition: SymbolTable.h:68
void openXRefs()
Definition: SymbolTable.cc:334
TableEntry * enter(const char *key, SymbolEntryPtr entry, const Point *point)
Definition: SymbolTable.cc:566
SymbolTable * m_table
Definition: SymbolTable.h:72
TableEntry * next_overloaded() const
Definition: SymbolTable.cc:125
Definition: SymbolTable.h:100
string toString() const
Definition: SymbolTable.cc:152
const Point * m_point
Definition: SymbolTable.h:70
void endUsage()
Definition: SymbolTable.cc:413
Definition: Point.h:59
~SymbolTable()
Definition: SymbolTable.cc:255
category_t
Definition: SymbolEntry.h:54
TableEntry * m_overloaded_prev
Definition: SymbolTable.h:53
std::ostream & toStream(std::ostream &str) const
Definition: SymbolTable.cc:166
size_t mem_size() const
Definition: SymbolTable.h:78
int hash(const char *s)
Definition: SymbolTable.cc:220
string toString() const
Definition: SymbolTable.cc:853
void disableUsage()
Definition: SymbolTable.cc:438
bool isOverloaded() const
Definition: SymbolTable.cc:131
TableEntry * m_next
Definition: SymbolTable.h:49
SymbolEntryPtr m_entry
Definition: SymbolTable.h:69
TableEntry(const char *key, SymbolEntryPtr entry, const Point *point, SymbolTable *table=0)
Definition: SymbolTable.cc:42
Definition: SymbolEntry.h:55
std::ostream & writeXmlUsage(std::ostream &str, int indent) const
Definition: SymbolTable.cc:504
string toStringSymbols() const
Definition: SymbolTable.cc:925
TableEntry * m_overloaded_next
Definition: SymbolTable.h:54
TableEntry * m_outer
Definition: SymbolTable.h:66
void forEach(EntryConsumer consumer) const
Definition: SymbolTable.cc:1025
SymbolEntryPtr getXRef(unsigned int position) const
Definition: SymbolTable.cc:369
size_t mem_size() const
Definition: SymbolTable.h:135
TableEntry * m_prev
Definition: SymbolTable.h:48
std::stack< std::vector< TableEntry * > * > xrefs_t
Definition: SymbolTable.h:131
int countUsage()
Definition: SymbolTable.cc:402
TableEntry * find(const char *key, SymbolEntry::category_t category=SymbolEntry::c_unspec)
Definition: SymbolTable.cc:688
const char * key() const
Definition: SymbolTable.cc:91
std::map< const char *, TableEntry * > * m_used
Definition: SymbolTable.h:127
std::ostream & toXml(std::ostream &str, int indent) const
Definition: SymbolTable.cc:184
void makeDefinition(int line)
Definition: SymbolTable.cc:140
~TableEntry()
Definition: SymbolTable.cc:82
TableEntry * next() const
Definition: SymbolTable.cc:112
void enableUsage()
Definition: SymbolTable.cc:428
const Point * point() const
Definition: SymbolTable.cc:105
Definition: Y2Namespace.h:43
int m_prime
Definition: SymbolTable.h:107
void startUsage()
Definition: SymbolTable.cc:388
An istream that remembers some data about the bytecode.
Definition: Bytecode.h:42
Definition: SymbolTable.h:42
xrefs_t * m_xrefs
Definition: SymbolTable.h:132
bool m_track_usage
Definition: SymbolTable.h:126
string toStringSymbols() const
TableEntry ** m_table
Definition: SymbolTable.h:122
std::ostream & writeUsage(std::ostream &str) const
Definition: SymbolTable.cc:448
Definition: MemUsage.h:37
SymbolEntryPtr sentry() const
Definition: SymbolTable.cc:98
bool(* EntryConsumer)(const SymbolEntry &)
Definition: SymbolTable.h:153

Generated on a sunny day for yast2-core by doxygen 1.8.5