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