symbol_table.cpp

Go to the documentation of this file.

#ifndef SYMBOL_TABLE_IMPLEMENTATION
#define SYMBOL_TABLE_IMPLEMENTATION

/*****************************************************************************\
*                                                                             *
*  Name   : symbol_table                                                      *
*  Author : Chris Koeritz                                                     *
*                                                                             *
*******************************************************************************
* Copyright (c) 1991-$now By Author.  This program is free software; you can  *
* redistribute it and/or modify it under the terms of the GNU General Public  *
* License as published by the Free Software Foundation; either version 2 of   *
* the License or (at your option) any later version.  This is online at:      *
*     http://www.fsf.org/copyleft/gpl.html                                    *
* Please send any updates to: fred@gruntose.com                               *
\*****************************************************************************/

#include "pointer_hash.cpp"
#include "string_hash.cpp"
#include "symbol_table.h"

#include <basis/function.h>
#include <basis/guards.h>
#include <basis/istring.h>
#include <basis/log_base.h>

//#define DEBUG_SYMBOL_TABLE
  // uncomment for noisier debugging.

#ifdef DEBUG_SYMBOL_TABLE
  #undef LOG
  #define LOG(s) CLASS_EMERGENCY_LOG(program_wide_logger(), s)
#endif


// this structure keeps track of our symbol table elements.

template <class contents>
class internal_symbol_info
{
public:
  contents _content;  // the object provided by the user.
  istring _name;  // symbol's name.

  internal_symbol_info(const contents &content, const istring &name)
  : _content(content), _name(name) {}
};


// this is our tracking system that allows us to offer array like services.
// each symbol held has an address as one of our wrappers.  thus we can
// list those addresses in a hash table along with listing the contents
// in the main hash table.  the pointer_hash gives us a list of ids set, so
// we can have some ordering for the items in the table.

template <class contents>
class internal_pointer_hider
{
public:
  internal_symbol_info<contents> *_held;

  internal_pointer_hider(internal_symbol_info<contents> *held) : _held(held) {}
};

template <class contents>
class internal_symbol_indexer
: public pointer_hash<internal_pointer_hider<contents> >
{
public:
  internal_symbol_indexer(int max_bits)
      : pointer_hash<internal_pointer_hider<contents> >(max_bits) {}
};
//hmmm: danger, danger.  when OS uses a 64 bit pointer length, this will
//      be terribly awfully busted.  we then need a void * hash.  what about
//      that?  would serve as handy way to ensure we know a pointer is valid
//      too; store all in the main hash.


// this object maintains the symbol table's contents.

template <class contents>
class internal_symbol_list
: public string_hash<internal_symbol_info<contents> >
{
public:
  internal_symbol_list(int max_bits)
      : string_hash<internal_symbol_info<contents> >(max_bits) {}
};


// the main algorithms class implementing the external interface.

#undef static_class_name
#define static_class_name() "symbol_table"

template <class contents>
symbol_table<contents>::symbol_table(int max_bits)
: _symbol_list(new internal_symbol_list<contents>(max_bits)),
  _tracker(new internal_symbol_indexer<contents>(max_bits))
{}

template <class contents>
symbol_table<contents>::symbol_table(const symbol_table<contents> &to_copy)
: _symbol_list(new internal_symbol_list<contents>
      (to_copy._symbol_list->max_bits())),
  _tracker(new internal_symbol_indexer<contents>(to_copy.max_bits()))
{ *this = to_copy; }

template <class contents>
symbol_table<contents>::~symbol_table()
{
  WHACK(_symbol_list);
  WHACK(_tracker);
}

template <class contents>
int symbol_table<contents>::max_bits() const
{ return _symbol_list->max_bits(); }

template <class contents>
void symbol_table<contents>::rehash(int max_bits)
{
  _symbol_list->rehash(max_bits);
  _tracker->rehash(max_bits);
}

//hmmm: provide shrink capability too.
template <class contents>
void symbol_table<contents>::hash_appropriately(int max_per_bucket)
{
  FUNCDEF("hash_appropriately");
  if (max_per_bucket < 1) max_per_bucket = 1;
  int new_bits = max_bits();  // start with the current number of bits.
  int current_average_size = symbols() / int(pow(2.0, new_bits));
    // this is what the average travel size is currently.
#ifdef DEBUG_SYMBOL_TABLE
  int curr_bits = max_bits();
  int orig_elems = symbols();
#endif
  while (current_average_size > max_per_bucket) {
    // loop until we find a nice size.
    new_bits++;
//hmmm: better would be to calculate size needed with logarithmic formula.
    current_average_size = symbols() / int(pow(2.0, new_bits));
  }
  if (new_bits == max_bits()) return;  // no changes.
#ifdef DEBUG_SYMBOL_TABLE
  LOG(isprintf("size desired=%d, current bits=%d, elems=%d, "
      "new bits=%d, new avg size=%d", max_per_bucket, curr_bits, orig_elems,
      new_bits, current_average_size));
#endif
  if (new_bits > 30) return;
    // too big for us to help you; we don't want to blow away too much memory.
  rehash(new_bits);
}

template <class contents>
int symbol_table<contents>::symbols() const
{ return _tracker->ids().elements(); }

template <class contents>
symbol_table<contents> &symbol_table<contents>::
    operator =(const symbol_table &to_copy)
{
  if (this == &to_copy) return *this;
  reset();
  for (int i = 0; i < to_copy.symbols(); i++) {
    internal_symbol_info<contents> *info = to_copy.get_index(i);
    if (info) {
      internal_symbol_info<contents> *new_info
          = new internal_symbol_info<contents>(*info);
      _symbol_list->add(info->_name, new_info);
      internal_pointer_hider<contents> *new_track = 
          new internal_pointer_hider<contents>(new_info);
      _tracker->add(new_info, new_track);
    }
  }
  return *this;
}

template <class contents>
void symbol_table<contents>::reset()
{
  _symbol_list->reset();
  _tracker->reset();
}

template <class contents>
const istring &symbol_table<contents>::name(int index) const
{
  bounds_return(index, 0, symbols() - 1, bogonic<istring>());
  return get_index(index)->_name;
}

template <class contents>
void symbol_table<contents>::names(string_set &to_fill) const
{
  to_fill.reset();
  for (int i = 0; i < symbols(); i++)
    to_fill += get_index(i)->_name;
}

template <class contents>
internal_symbol_info<contents> *symbol_table<contents>::
    get_index(int index) const
{
  bounds_return(index, 0, symbols() - 1, NIL);
  return _tracker->find(_tracker->ids()[index])->_held;
}

template <class contents>
const contents &symbol_table<contents>::operator [] (int index) const
{
  bounds_return(index, 0, symbols() - 1, bogonic<contents>());
  internal_symbol_info<contents> *found = get_index(index);
  if (!found) return bogonic<contents>();
  return found->_content;
}

template <class contents>
contents &symbol_table<contents>::operator [] (int index)
{
  bounds_return(index, 0, symbols() - 1, bogonic<contents>());
  internal_symbol_info<contents> *found = get_index(index);
  if (!found) return bogonic<contents>();
  return found->_content;
}

template <class contents>
contents *symbol_table<contents>::find(const istring &name) const
{ 
  FUNCDEF("find [name]");
  internal_symbol_info<contents> *found = _symbol_list->find(name);
  if (!found) return NIL;
  return &found->_content;
}

template <class contents>
int symbol_table<contents>::dep_find(const istring &name) const
{
  internal_symbol_info<contents> *entry = _symbol_list->find(name);
  if (!entry) return common::NOT_FOUND;

  for (int i = 0; i < symbols(); i++) {
    if (_tracker->ids()[i] == entry) return i;
  }
  return common::NOT_FOUND;  // this is bad; it should have been found.
}

template <class contents>
struct sym_tab_apply_data {
  string_comparator_function *_scf;
  contents *_found;
  istring _to_find;

  sym_tab_apply_data() : _scf(NIL), _found(NIL) {}
};

template <class contents>
bool sym_tab_finder_apply(const istring &key, contents &current,
    void *data_link)
{
  FUNCDEF("sym_tab_finder_apply");
  sym_tab_apply_data<contents> *package
      = (sym_tab_apply_data<contents> *)data_link;
#ifdef DEBUG_SYMBOL_TABLE
  LOG(istring("  checking ") + key);
#endif
  bool equals = package->_scf(key, package->_to_find);
  if (equals) {
    package->_found = &current;
    return false;  // done.
  }
  return true;  // keep going.
}

template <class contents>
contents *symbol_table<contents>::find(const istring &name,
    string_comparator_function *comparator) const
{
  FUNCDEF("find [comparator]");
  if (!comparator) return find(name);  // devolve to simplified call.
#ifdef DEBUG_SYMBOL_TABLE
  LOG(istring("looking for ") + name);
#endif
  sym_tab_apply_data<contents> pack;
  pack._to_find = name;
  pack._scf = comparator;
  // iterate across all the items in the hash.
  _symbol_list->apply(sym_tab_finder_apply, &pack);
  return pack._found;
}

template <class contents>
outcome symbol_table<contents>::add(const istring &name, const contents &to_add)
{
  FUNCDEF("add");
  internal_symbol_info<contents> *found = _symbol_list->find(name);
  if (!found) {
    // not there already.
    internal_symbol_info<contents> *new_item
        = new internal_symbol_info<contents>(to_add, name);
    _symbol_list->add(name, new_item);
    internal_pointer_hider<contents> *new_track = 
        new internal_pointer_hider<contents>(new_item);
    _tracker->add(new_item, new_track);
    return common::IS_NEW;
  }
  // overwrite the existing contents.
  found->_content = to_add;
  return common::EXISTING;
}

template <class contents>
outcome symbol_table<contents>::zap_index(int index)
{
  istring dead_name = name(index);
  return whack(dead_name);
}

template <class contents>
outcome symbol_table<contents>::whack(const istring &name)
{
  FUNCDEF("whack");
  internal_symbol_info<contents> *sep_ind = _symbol_list->find(name);
    // we need this pointer so we can find the tracker entry easily.
  bool found_it = _symbol_list->zap(name);
  if (found_it) {
    _tracker->zap(sep_ind);
  }
  return found_it? common::OKAY : common::NOT_FOUND;
}

template <class contents>
outcome symbol_table<contents>::retrieve(int index, istring &name,
    contents &got) const
{
  bounds_return(index, 0, symbols() - 1, common::NOT_FOUND);
  internal_symbol_info<contents> *found = get_index(index);
  name = found->_name;
  got = found->_content;
  return common::OKAY;
}


template <class contents>
bool symbol_table_compare(const symbol_table<contents> &a,
    const symbol_table<contents> &b)
{
  FUNCDEF("symbol_table_compare");

  string_set names_a;
  a.names(names_a);
  string_set names_b;
  b.names(names_b);
  if (names_a != names_b) return false;

  for (int i = 0; i < names_a.elements(); i++) {
    const istring &current_key = names_a[i];
    const contents *a_value = a.find(current_key);
    const contents *b_value = b.find(current_key);
    if (!a_value || !b_value) continue;  // not good.
    if (*a_value != *b_value) return false;
  }
  return true;
}

#undef static_class_name

#endif

---