Merge branch 'main' of feistymeow.org:feisty_meow
[feisty_meow.git] / structures / symbol_table.h
1 #ifndef SYMBOL_TABLE_CLASS
2 #define SYMBOL_TABLE_CLASS
3
4 /*****************************************************************************\
5 *                                                                             *
6 *  Name   : symbol_table                                                      *
7 *  Author : Chris Koeritz                                                     *
8 *                                                                             *
9 *******************************************************************************
10 * Copyright (c) 1991-$now By Author.  This program is free software; you can  *
11 * redistribute it and/or modify it under the terms of the GNU General Public  *
12 * License as published by the Free Software Foundation; either version 2 of   *
13 * the License or (at your option) any later version.  This is online at:      *
14 *     http://www.fsf.org/copyleft/gpl.html                                    *
15 * Please send any updates to: fred@gruntose.com                               *
16 \*****************************************************************************/
17
18 #include "pointer_hash.h"
19 #include "string_hash.h"
20 #include "symbol_table.h"
21
22 #include <basis/astring.h>
23 #include <basis/functions.h>
24 #include <basis/guards.h>
25
26 namespace structures {
27
28 template <class contents> class internal_symbol_indexer;
29 template <class contents> class internal_symbol_info;
30 template <class contents> class internal_symbol_list;
31
32 //! Maintains a list of names, where each name has a type and some contents.
33
34 template <class contents>
35 class symbol_table
36 {
37 public:
38   //! constructs a symbol table with sufficient size for "estimated_elements".
39   /*! the "estimated_elements" dictates how large the symbol table's key space is.  the
40   number of keys that can be stored without collisions (assuming perfect distribution
41   from the hash function) will be close to the number of elements specified. */
42   symbol_table(int estimated_elements = 100);
43
44   symbol_table(const symbol_table<contents> &to_copy);
45
46   ~symbol_table();
47
48   int symbols() const;
49     //!< returns the number of symbols listed in the table.
50
51   int estimated_elements() const;
52     //!< returns the number of symbols the table is optimized for.
53
54   void rehash(int estimated_elements);
55     //!< resizes underlying table to support "estimated_elements".
56
57   void hash_appropriately(int estimated_elements);
58     //!< Resizes the number of table slots to have space for "estimated_elements".
59
60   symbol_table &operator =(const symbol_table<contents> &to_copy);
61
62   basis::outcome add(const basis::astring &name, const contents &storage);
63     //!< Enters a symbol name into the table along with some contents.
64     /*!< If the name already exists in the table, then the previous contents
65     are replaced with these, but EXISTING is returned.  If this is a new entry,
66     then IS_NEW is returned instead. */
67
68   const basis::astring &name(int index) const;
69     //!< returns the name held at the "index".
70     /*!< if the index is invalid, then a bogus name is returned. */
71
72   void names(string_set &to_fill) const;
73     //!< returns the names of all the symbols currently held.
74
75   contents &operator [] (int index);
76     //!< provides access to the symbol_table's contents at the "index".
77   const contents &operator [] (int index) const;
78     //!< provides a constant peek at the contents at the "index".
79
80   const contents &get(int index) const { return operator[](index); }
81     //!< named equivalent for the bracket operator.
82   contents &use(int index) { return operator[](index); }
83     //!< named equivalent for the bracket operator.
84
85   contents *find(const basis::astring &name) const;
86     //!< returns the contents held for "name" or NULL_POINTER if it wasn't found.
87
88   contents *find(const basis::astring &name,
89           basis::string_comparator_function *comparator) const;
90     //!< Specialized search via a comparison method "comparator".
91     /*!< Searches for a symbol by its "name" but uses a special comparison
92     function "comparator" to determine if the name is really equal.  This
93     method is by its nature slower than the main find method, since all buckets
94     must be searched until a match is found.  It is just intended to provide
95     extensibility. */
96
97   int dep_find(const basis::astring &name) const;
98     //!< Searches for a symbol by its "name".
99     /*!< Returns the index or NOT_FOUND.  NOTE: this is deprecated; it is far
100     faster to use the first find method above. */
101
102   //! Locates the symbol at position "index" and stores it to the parameters.
103   /*! retrieve() accesses the "index"th symbol in the table and returns the
104       held contents for it as well as its name.  if the outcome is OKAY, then
105       the returned information is valid.  otherwise, the search failed. */
106   basis::outcome retrieve(int index, basis::astring &symbol_name, contents &contains) const;
107
108   basis::outcome whack(const basis::astring &name);
109     //!< removes a symbol from the table.
110     /*!< this succeeds only if the symbol name is present in the table. */
111
112   basis::outcome zap_index(int index);
113     //!< zaps the entry at the specified index.  slower than whack().
114
115   void reset();  //<! removes all symbols from the table.
116
117 private:
118   internal_symbol_list<contents> *_symbol_list;  //!< our table of symbols.
119   internal_symbol_indexer<contents> *_tracker;  //!< indexed lookup support.
120
121   internal_symbol_info<contents> *get_index(int index) const;
122     //!< returns the info item at "index" or NULL_POINTER.
123 };
124
125 //////////////
126
127 template <class contents>
128 bool symbol_table_compare(const symbol_table<contents> &a,
129     const symbol_table<contents> &b);
130   //!< returns true if table "a" and table "b" have the same contents.
131
132 //////////////
133
134 // implementations below...
135
136 //#define DEBUG_SYMBOL_TABLE
137   // uncomment for noisier debugging.
138
139 #ifdef DEBUG_SYMBOL_TABLE
140   #undef LOG
141   #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger::get(), s)
142 #endif
143
144 //////////////
145
146 // this structure keeps track of our symbol table elements.
147
148 template <class contents>
149 class internal_symbol_info
150 {
151 public:
152   contents _content;  // the object provided by the user.
153   basis::astring _name;  // symbol's name.
154
155   internal_symbol_info(const contents &content, const basis::astring &name)
156   : _content(content), _name(name) {}
157 };
158
159 //////////////
160
161 // this is our tracking system that allows us to offer array like services.
162 // each symbol held has an address as one of our wrappers.  thus we can
163 // list those addresses in a hash table along with listing the contents
164 // in the main hash table.  the pointer_hash gives us a list of ids set, so
165 // we can have some ordering for the items in the table.
166
167 template <class contents>
168 class internal_pointer_hider
169 {
170 public:
171   internal_symbol_info<contents> *_held;
172
173   internal_pointer_hider(internal_symbol_info<contents> *held) : _held(held) {}
174 };
175
176 template <class contents>
177 class internal_symbol_indexer
178 : public pointer_hash<internal_pointer_hider<contents> >
179 {
180 public:
181   internal_symbol_indexer(int elems)
182       : pointer_hash<internal_pointer_hider<contents> >(elems) {}
183 };
184
185 //////////////
186
187 // this object maintains the symbol table's contents.
188
189 template <class contents>
190 class internal_symbol_list
191 : public string_hash<internal_symbol_info<contents> >
192 {
193 public:
194   internal_symbol_list(int elems)
195       : string_hash<internal_symbol_info<contents> >(elems) {}
196 };
197
198 //////////////
199
200 // the main algorithms class implementing the external interface.
201
202 #undef static_class_name
203 #define static_class_name() "symbol_table"
204
205 template <class contents>
206 symbol_table<contents>::symbol_table(int estimated_elements)
207 : _symbol_list(new internal_symbol_list<contents>(estimated_elements)),
208   _tracker(new internal_symbol_indexer<contents>(estimated_elements))
209 {}
210
211 template <class contents>
212 symbol_table<contents>::symbol_table(const symbol_table<contents> &to_copy)
213 : _symbol_list(new internal_symbol_list<contents>
214       (to_copy._symbol_list->estimated_elements())),
215   _tracker(new internal_symbol_indexer<contents>(to_copy.estimated_elements()))
216 { *this = to_copy; }
217
218 template <class contents>
219 symbol_table<contents>::~symbol_table()
220 {
221   WHACK(_symbol_list);
222   WHACK(_tracker);
223 }
224
225 template <class contents>
226 int symbol_table<contents>::estimated_elements() const
227 { return _symbol_list->estimated_elements(); }
228
229 template <class contents>
230 void symbol_table<contents>::rehash(int estimated_elements)
231 {
232   _symbol_list->rehash(estimated_elements);
233   _tracker->rehash(estimated_elements);
234 }
235
236 template <class contents>
237 void symbol_table<contents>::hash_appropriately(int new_elements)
238 { rehash(new_elements); }
239
240 template <class contents>
241 int symbol_table<contents>::symbols() const
242 { return _tracker->ids().elements(); }
243
244 template <class contents>
245 symbol_table<contents> &symbol_table<contents>::
246     operator =(const symbol_table &to_copy)
247 {
248   if (this == &to_copy) return *this;
249   reset();
250   for (int i = 0; i < to_copy.symbols(); i++) {
251     internal_symbol_info<contents> *info = to_copy.get_index(i);
252     if (info) {
253       internal_symbol_info<contents> *new_info
254           = new internal_symbol_info<contents>(*info);
255       _symbol_list->add(info->_name, new_info);
256       internal_pointer_hider<contents> *new_track = 
257           new internal_pointer_hider<contents>(new_info);
258       _tracker->add(new_info, new_track);
259     }
260   }
261   return *this;
262 }
263
264 template <class contents>
265 void symbol_table<contents>::reset()
266 {
267   _symbol_list->reset();
268   _tracker->reset();
269 }
270
271 template <class contents>
272 const basis::astring &symbol_table<contents>::name(int index) const
273 {
274   bounds_return(index, 0, symbols() - 1, basis::bogonic<basis::astring>());
275   return get_index(index)->_name;
276 }
277
278 template <class contents>
279 void symbol_table<contents>::names(string_set &to_fill) const
280 {
281   to_fill.reset();
282   for (int i = 0; i < symbols(); i++)
283     to_fill += get_index(i)->_name;
284 }
285
286 template <class contents>
287 internal_symbol_info<contents> *symbol_table<contents>::
288     get_index(int index) const
289 {
290   bounds_return(index, 0, symbols() - 1, NULL_POINTER);
291   return _tracker->find(_tracker->ids()[index])->_held;
292 }
293
294 template <class contents>
295 const contents &symbol_table<contents>::operator [] (int index) const
296 {
297   bounds_return(index, 0, symbols() - 1, basis::bogonic<contents>());
298   internal_symbol_info<contents> *found = get_index(index);
299   if (!found) return basis::bogonic<contents>();
300   return found->_content;
301 }
302
303 template <class contents>
304 contents &symbol_table<contents>::operator [] (int index)
305 {
306   bounds_return(index, 0, symbols() - 1, basis::bogonic<contents>());
307   internal_symbol_info<contents> *found = get_index(index);
308   if (!found) return basis::bogonic<contents>();
309   return found->_content;
310 }
311
312 template <class contents>
313 contents *symbol_table<contents>::find(const basis::astring &name) const
314
315 //  FUNCDEF("find [name]");
316   internal_symbol_info<contents> *found = _symbol_list->find(name);
317   if (!found) return NULL_POINTER;
318   return &found->_content;
319 }
320
321 template <class contents>
322 int symbol_table<contents>::dep_find(const basis::astring &name) const
323 {
324   internal_symbol_info<contents> *entry = _symbol_list->find(name);
325   if (!entry) return basis::common::NOT_FOUND;
326
327   for (int i = 0; i < symbols(); i++) {
328     if (_tracker->ids()[i] == entry) return i;
329   }
330   return basis::common::NOT_FOUND;  // this is bad; it should have been found.
331 }
332
333 template <class contents>
334 struct sym_tab_apply_data
335 {
336   basis::string_comparator_function *_scf;
337   contents *_found;
338   basis::astring _to_find;
339
340   sym_tab_apply_data() : _scf(NULL_POINTER), _found(NULL_POINTER) {}
341 };
342
343 template <class contents>
344 bool sym_tab_finder_apply(const basis::astring &key, contents &current,
345     void *data_link)
346 {
347 #ifdef DEBUG_SYMBOL_TABLE
348   FUNCDEF("sym_tab_finder_apply");
349 #endif
350   sym_tab_apply_data<contents> *package
351       = (sym_tab_apply_data<contents> *)data_link;
352 #ifdef DEBUG_SYMBOL_TABLE
353   LOG(basis::astring("  checking ") + key);
354 #endif
355   bool equals = package->_scf(key, package->_to_find);
356   if (equals) {
357     package->_found = &current;
358     return false;  // done.
359   }
360   return true;  // keep going.
361 }
362
363 template <class contents>
364 contents *symbol_table<contents>::find(const basis::astring &name,
365     basis::string_comparator_function *comparator) const
366 {
367 #ifdef DEBUG_SYMBOL_TABLE
368   FUNCDEF("find [comparator]");
369 #endif
370   if (!comparator) return find(name);  // devolve to simplified call.
371 #ifdef DEBUG_SYMBOL_TABLE
372   LOG(basis::astring("looking for ") + name);
373 #endif
374   sym_tab_apply_data<contents> pack;
375   pack._to_find = name;
376   pack._scf = comparator;
377   // iterate across all the items in the hash.
378   _symbol_list->apply(sym_tab_finder_apply, &pack);
379   return pack._found;
380 }
381
382 template <class contents>
383 basis::outcome symbol_table<contents>::add(const basis::astring &name, const contents &to_add)
384 {
385 //  FUNCDEF("add");
386   internal_symbol_info<contents> *found = _symbol_list->find(name);
387   if (!found) {
388     // not there already.
389     internal_symbol_info<contents> *new_item
390         = new internal_symbol_info<contents>(to_add, name);
391     _symbol_list->add(name, new_item);
392     internal_pointer_hider<contents> *new_track = 
393         new internal_pointer_hider<contents>(new_item);
394     _tracker->add(new_item, new_track);
395     return basis::common::IS_NEW;
396   }
397   // overwrite the existing contents.
398   found->_content = to_add;
399   return basis::common::EXISTING;
400 }
401
402 template <class contents>
403 basis::outcome symbol_table<contents>::zap_index(int index)
404 {
405   basis::astring dead_name = name(index);
406   return whack(dead_name);
407 }
408
409 template <class contents>
410 basis::outcome symbol_table<contents>::whack(const basis::astring &name)
411 {
412 //  FUNCDEF("whack");
413   internal_symbol_info<contents> *sep_ind = _symbol_list->find(name);
414     // we need this pointer so we can find the tracker entry easily.
415   bool found_it = _symbol_list->zap(name);
416   if (found_it) {
417     _tracker->zap(sep_ind);
418   }
419   return found_it? basis::common::OKAY : basis::common::NOT_FOUND;
420 }
421
422 template <class contents>
423 basis::outcome symbol_table<contents>::retrieve(int index, basis::astring &name,
424     contents &got) const
425 {
426   bounds_return(index, 0, symbols() - 1, basis::common::NOT_FOUND);
427   internal_symbol_info<contents> *found = get_index(index);
428   name = found->_name;
429   got = found->_content;
430   return basis::common::OKAY;
431 }
432
433 //////////////
434
435 template <class contents>
436 bool symbol_table_compare(const symbol_table<contents> &a,
437     const symbol_table<contents> &b)
438 {
439 //  FUNCDEF("symbol_table_compare");
440
441   string_set names_a;
442   a.names(names_a);
443   string_set names_b;
444   b.names(names_b);
445   if (names_a != names_b) return false;
446
447   for (int i = 0; i < names_a.elements(); i++) {
448     const basis::astring &current_key = names_a[i];
449     const contents *a_value = a.find(current_key);
450     const contents *b_value = b.find(current_key);
451     if (!a_value || !b_value) continue;  // not good.
452     if (*a_value != *b_value) return false;
453   }
454   return true;
455 }
456
457 #ifdef DEBUG_SYMBOL_TABLE
458   #undef LOG
459 #endif
460
461 #undef static_class_name
462
463 } //namespace.
464
465 #endif
466
467