lib/symtab.cc

Go to the documentation of this file.

//
// nis-util - NIS Administration Utilities
// Copyright (C) 2001, 2002, 2008, 2009, 2011, 2012 Peter Miller
//
// 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, see <http://www.gnu.org/licenses/>.
//

#include <lib/ac/stdlib.h>
#include <libexplain/malloc.h>
#include <libexplain/output.h>
#include <libexplain/realloc.h>

#include <lib/symtab.h>


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


symtab::symtab()
{
    hash_ty size = 5;
    reap = 0;
    hash_modulus = 1 << 2; // MUST be a power of 2
    while (hash_modulus < size)
        hash_modulus <<= 1;
    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_ty **)explain_malloc_or_die(hash_modulus * sizeof(row_ty *));
    for (hash_ty j = 0; j < hash_modulus; ++j)
        hash_table[j] = 0;
}


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

    //
    // increase the modulus by one
    //
    hash_modulus++;
    hash_table =
        (row_ty **)
        explain_realloc_or_die(hash_table, hash_modulus * sizeof(row_ty *));
    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_ty *p2 = p;
        p = p2->overflow;
        p2->overflow = 0;

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


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


void
symtab::assign(const rcstring &key, void *data)
{
    hash_ty index = key.get_hash() & hash_cutover_mask;
    if (index < hash_split)
        index = key.get_hash() & hash_cutover_split_mask;
    for (row_ty *p = hash_table[index]; p; p = p->overflow)
    {
        if (key == p->key)
        {
            if (reap)
                reap(p->data);
            p->data = data;
            return;
        }
    }

    row_ty *np = new row_ty;
    np->key = key;
    np->overflow = hash_table[index];
    np->data = data;
    hash_table[index] = np;

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


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

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


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


void
symtab::walk(walk_t &arg)
{
    for (hash_ty j = 0; j < hash_modulus; ++j)
        for (row_ty *p = hash_table[j]; p; p = p->overflow)
            arg.action(p->key, p->data);
}


symtab::key_list_t
symtab::keys()
    const
{
    symtab::key_list_t result;
    for (hash_ty j = 0; j < hash_modulus; ++j)
        for (row_ty *p = hash_table[j]; p; p = p->overflow)
            result.push_back(p->key);
    return result;
}


void
symtab::set_reaper(void (*fp)(void *))
{
    reap = fp;
}


// vim: set ts=8 sw=4 et :