Logo Search packages:      
Sourcecode: tardy version File versions  Download package

symtab.cc

/*
 *    tardy - a tar post-processor
 *    Copyright (C) 1998, 1999, 2002 Peter Miller;
 *    All rights reserved.
 *
 *    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 program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
 *
 * MANIFEST: functions to manipulate symbol tables
 */

#include <error.h>
#include <fstrcmp.h>
#include <mem.h>
#include <symtab.h>


symtab::symtab()
{
      chain = 0;
      reap = 0;
      hash_modulus = 1 << 4; /* MUST be a power of 2 */
      hash_cutover = hash_modulus;
      hash_split = hash_modulus - hash_cutover;
      hash_cutover_mask = hash_cutover - 1;
      hash_cutover_split_mask = (hash_cutover * 2) - 1;
      hash_load = 0;
      hash_table = (row **)mem_alloc(hash_modulus * sizeof(row *));
      for (str_hash_ty j = 0; j < hash_modulus; ++j)
            hash_table[j] = 0;
}


symtab::~symtab()
{
      for (str_hash_ty j = 0; j < hash_modulus; ++j)
      {
            row **rpp = &hash_table[j];
            while (*rpp)
            {
                  row *rp = *rpp; 
                  *rpp = rp->overflow;
                  if (reap)
                        reap(rp->data);
                  delete rp;
            }
      }
}


/*
 * NAME
 *    split - reduce symbol table load
 *
 * SYNOPSIS
 *    void split(symtab_ty);
 *
 * DESCRIPTION
 *    The split function is used to split symbols in the bucket indicated by
 *    the split point.  The symbols are split between that bucket and the one
 *    after the current end of the table.
 *
 * CAVEAT
 *    It is only sensable to do this when the symbol table load exceeds some
 *    reasonable threshold.  A threshold of 80% is suggested.
 */

void
symtab::split()
{
      /*
       * get the list to be split across buckets 
       */
      row *p = hash_table[hash_split];
      hash_table[hash_split] = 0;

      /*
       * increase the modulus by one
       */
      hash_modulus++;
      hash_table =
            (row **)
            mem_change_size
            (
                  hash_table,
                  hash_modulus * sizeof(row *)
            );
      hash_table[hash_modulus - 1] = 0;
      hash_split = hash_modulus - hash_cutover;
      if (hash_split >= hash_cutover)
      {
            hash_cutover = hash_modulus;
            hash_split = 0;
            hash_cutover_mask = hash_cutover - 1;
            hash_cutover_split_mask = (hash_cutover * 2) - 1;
      }

      /*
       * now redistribute the list elements
       *
       * It is important to preserve the order of the links because
       * they can be push-down stacks, and to simply add them to the
       * head of the list will reverse the order of the stack!
       */
      while (p)
      {
            row *p2 = p;
            p = p2->overflow;
            p2->overflow = 0;

            str_hash_ty index = p2->key.hash() & hash_cutover_mask;
            if (index < hash_split)
            {
                  index =
                        (
                              p2->key.hash()
                        &
                              hash_cutover_split_mask
                        );
            }
            row **ipp;
            for
            (
                  ipp = &hash_table[index];
                  *ipp;
                  ipp = &(*ipp)->overflow
            )
                  ;
            *ipp = p2;
      }
}


/*
 * NAME
 *    symtab_query - search for a variable
 *
 * SYNOPSIS
 *    int symtab_query(symtab_ty *, string_ty *key);
 *
 * DESCRIPTION
 *    The symtab_query function is used to reference a variable.
 *
 * RETURNS
 *    If the variable has been defined, the function returns a non-zero value
 *    and the value is returned through the 'value' pointer.
 *    If the variable has not been defined, it returns zero,
 *    and 'value' is unaltered.
 */

void *
symtab::query(const rcstring &key)
      const
{
      str_hash_ty index = key.hash() & hash_cutover_mask;
      if (index < hash_split)
            index = key.hash() & hash_cutover_split_mask;
      for (row *p = hash_table[index]; p; p = p->overflow)
      {
            if (key == p->key)
                  return p->data;
      }
      return 0;
}


/*
 * NAME
 *    symtab_query_fuzzy - search for a variable name
 *
 * SYNOPSIS
 *    string_ty *symtab_query_fuzzy(symtab_ty *, string_ty *key);
 *
 * DESCRIPTION
 *    The symtab_query_fuzzy function is used to search for a variable name.
 *
 * RETURNS
 *    The closest match for the variable name given.
 *    If no match is particularly close, it returns 0.
 */

rcstring
symtab::query_fuzzy(const rcstring &key)
      const
{
      rcstring best_name;
      double best_weight = 0.6;
      for (str_hash_ty index = 0; index < hash_modulus; ++index)
      {
            for (row *p = hash_table[index]; p; p = p->overflow)
            {
                  double weight =
                        fmemcmp
                        (
                              key.to_c_string(),
                              key.length(),
                              p->key.to_c_string(),
                              p->key.length()
                        );
                  if (weight > best_weight)
                        best_name = p->key;
            }
      }
      return best_name;
}


/*
 * NAME
 *    symtab_assign - assign a variable
 *
 * SYNOPSIS
 *    void symtab_assign(symtab_ty *, string_ty *key, void *data);
 *
 * DESCRIPTION
 *    The symtab_assign function is used to assign
 *    a value to a given variable.
 *
 * CAVEAT
 *    The name is copied, the data is not.
 */

void
symtab::assign(const rcstring &key, void *data)
{
      str_hash_ty index = key.hash() & hash_cutover_mask;
      if (index < hash_split)
            index = key.hash() & hash_cutover_split_mask;

      row *p;
      for (p = hash_table[index]; p; p = p->overflow)
      {
            if (key == p->key)
            {
                  if (reap)
                        reap(p->data);
                  p->data = data;
                  return;
            }
      }

      p = new row();
      p->key = key;
      p->overflow = hash_table[index];
      p->data = data;
      hash_table[index] = p;

      hash_load++;
      while (hash_load * 10 >= hash_modulus * 8)
            split();
}


/*
 * NAME
 *    symtab_assign_push - assign a variable
 *
 * SYNOPSIS
 *    void symtab_assign_push(symtab_ty *, string_ty *key, void *data);
 *
 * DESCRIPTION
 *    The symtab_assign function is used to assign
 *    a value to a given variable.
 *    Any previous value will be obscured until this one
 *    is deleted with symtab_delete.
 *
 * CAVEAT
 *    The name is copied, the data is not.
 */

void
symtab::assign_push(const rcstring &key, void *data)
{
      str_hash_ty index = key.hash() & hash_cutover_mask;
      if (index < hash_split)
            index = key.hash() & hash_cutover_split_mask;

      row *p = new row();
      p->key = key;
      p->overflow = hash_table[index];
      p->data = data;
      hash_table[index] = p;

      hash_load++;
      while (hash_load * 10 >= hash_modulus * 8)
            split();
}


/*
 * NAME
 *    symtab_delete - delete a variable
 *
 * SYNOPSIS
 *    void symtab_delete(string_ty *name, symtab_class_ty class);
 *
 * DESCRIPTION
 *    The symtab_delete function is used to delete variables.
 *
 * CAVEAT
 *    The name is freed, the data is reaped.
 *    (By default, reap does nothing.)
 */

void
symtab::remove(const rcstring &key)
{
      str_hash_ty index = key.hash() & hash_cutover_mask;
      if (index < hash_split)
            index = key.hash() & hash_cutover_split_mask;

      row **rpp = &hash_table[index];
      for (;;)
      {
            row *rp = *rpp;
            if (!rp)
                  break;
            if (key == rp->key)
            {
                  if (reap)
                        reap(rp->data);
                  *rpp = rp->overflow;
                  delete rp;
                  hash_load--;
                  break;
            }
            rpp = &rp->overflow;
      }
}


/*
 * NAME
 *    symtab_dump - dump id table
 *
 * SYNOPSIS
 *    void symtab_dump(symtab_ty *stp, char *caption);
 *
 * DESCRIPTION
 *    The symtab_dump function is used to dump the contents of the
 *    symbol table.  The caption will be used to indicate why the
 *    symbol table was dumped.
 *
 * CAVEAT
 *    This function is only available when symbol DEBUG is defined.
 */

void
symtab::dump(const char *caption)
      const
{
      error("symbol table %s = {", caption);
      for (str_hash_ty j = 0; j < hash_modulus; ++j)
      {
            for (row *p = hash_table[j]; p; p = p->overflow)
            {
                  error
                  (
                        "key = \"%s\", data = %08lX",
                        p->key.to_c_string(),
                        (long)p->data
                  );
            }
      }
      error("}");
}


void
symtab::walk(void (*func)(const symtab &, const rcstring &, void *, void *),
      void *arg)
{
      for (str_hash_ty j = 0; j < hash_modulus; ++j)
            for (row *rp = hash_table[j]; rp; rp = rp->overflow)
                  func(*this, rp->key, rp->data, arg);
}

Generated by  Doxygen 1.6.0   Back to index