lib/rcstring.cc

Go to the documentation of this file.

//
// nis-util - NIS Administration Utilities
// Copyright (C) 2001-2003, 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/assert.h>
#include <lib/ac/ctype.h>
#include <lib/ac/stdlib.h>
#include <lib/ac/string.h>
#include <libexplain/malloc.h>
#include <libexplain/output.h>
#include <libexplain/realloc.h>

#include <lib/rcstring.h>
#include <lib/mprintf.h>

rcstring::string_ty **rcstring::string_ty::hash_table;
rcstring::hash_ty rcstring::string_ty::hash_modulus;
rcstring::hash_ty rcstring::string_ty::hash_mask;
rcstring::hash_ty rcstring::string_ty::hash_load;

//
// maximum conversion width for numbers
//
#define MAX_WIDTH 509

#define MAX_HASH_LEN 20


static rcstring::hash_ty
hash_generate(const char *s, size_t n)
{
    if (n > MAX_HASH_LEN)
    {
        s += n - MAX_HASH_LEN;
        n = MAX_HASH_LEN;
    }

    rcstring::hash_ty retval = 0;
    while (n > 0)
    {
        retval = (retval + (retval << 1)) ^ (unsigned char)*s++;
        --n;
    }
    return retval;
}


void
rcstring::string_ty::initialize(void)
{
    if (hash_table)
        return;
    hash_modulus = 1 << 8; // MUST be a power of 2
    hash_mask = hash_modulus - 1;
    hash_load = 0;
    hash_table = new string_ty * [hash_modulus];
    for (rcstring::hash_ty j = 0; j < hash_modulus; ++j)
        hash_table[j] = 0;
}


void
rcstring::string_ty::split(void)
{
    //
    // double the modulus
    //
    // This is subtle.  If we only increase the modulus by one, the
    // load always hovers around 80%, so we have to do a split for
    // every insert.  I.e. the malloc burden os O(n) for the lifetime of
    // the program.  BUT if we double the modulus, the length of time
    // until the next split also doubles, making the probablity of a
    // split halve, and sigma(2**-n)=1, so the malloc burden becomes O(1)
    // for the lifetime of the program.
    //
    size_t new_hash_modulus = hash_modulus * 2;
    string_ty **new_hash_table = new string_ty * [new_hash_modulus];
    size_t new_hash_mask = new_hash_modulus - 1;

    //
    // now redistribute the list elements
    //
    for (size_t idx = 0; idx < hash_modulus; ++idx)
    {
        new_hash_table[idx] = 0;
        new_hash_table[idx + hash_modulus] = 0;
        string_ty *p = hash_table[idx];
        while (p)
        {
            string_ty *p2 = p;
            p = p->next;

            assert((p2->str_hash & hash_mask) == idx);
            rcstring::hash_ty new_idx = p2->str_hash & new_hash_mask;
            p2->next = new_hash_table[new_idx];
            new_hash_table[new_idx] = p2;
        }
    }

    //
    // replace old hash table with new one
    //
    delete [] hash_table;
    hash_table = new_hash_table;
    hash_modulus = new_hash_modulus;
    hash_mask = new_hash_mask;
}


rcstring::string_ty *
rcstring::string_ty::from_c(const char *s)
{
    return n_from_c(s, strlen(s));
}


rcstring::string_ty::string_ty()
{
    construct("", 0);
}


rcstring::string_ty::string_ty(const char *s)
{
    construct(s, strlen(s));
}


rcstring::string_ty::string_ty(const char *s, size_t len)
{
    construct(s, len);
}


void
rcstring::string_ty::construct(const char *s, size_t length)
{
    text = (char *)explain_malloc_or_die(length + 1);
    memcpy(text, s, length);
    text[length] = 0;

    str_length = length;
    references = 1;

    str_hash = 0; // caller will tickle
    next = 0; // caller will tickle
}


rcstring::string_ty *
rcstring::string_ty::n_from_c(const char *s, size_t length)
{
    rcstring::hash_ty hash = hash_generate(s, length);
    if (!hash_table)
        initialize();
    rcstring::hash_ty index = hash & hash_mask;
    assert(index < hash_modulus);

    for (string_ty *p = hash_table[index]; p; p = p->next)
    {
        if
        (
            p->str_hash == hash
        &&
            p->str_length == length
        &&
            !memcmp(p->text, s, length)
        )
        {
            p->one_more();
            return p;
        }
    }

    string_ty *np = new string_ty(s, length);
    np->str_hash = hash;
    np->next = hash_table[index];
    hash_table[index] = np;

    hash_load++;
    if (hash_load * 10 > hash_modulus * 8)
        split();
    return np;
}


rcstring::string_ty::~string_ty()
{
    //
    //  find the hash bucket it was in,
    //  and remove it
    //
    rcstring::hash_ty index = str_hash & hash_mask;
    assert(index < hash_modulus);
    for
    (
        string_ty **spp = &hash_table[index];
        *spp;
        spp = &(*spp)->next
    )
    {
        if (*spp == this)
        {
            *spp = next;
            --hash_load;

            //
            // Now nuke the instance variables
            //
            delete text;
            str_hash = 0;
            next = 0;
            references = 0;
            str_length = 0;
            text = 0;
            return;
        }
    }
    // should never reach here!
    explain_output_error_and_die("attempted to free non-existent string (bug)");
}


rcstring
rcstring::catenate(const rcstring &lhs, const rcstring &rhs)
{
    static char *tmp;
    static size_t tmplen;
    size_t length = lhs.size() + rhs.size();
    if (tmplen < length)
    {
        tmplen = length;
        tmp = (char *)explain_realloc_or_die(tmp, tmplen);
    }
    memcpy(tmp, lhs.c_str(), lhs.size());
    memcpy(tmp + lhs.size(), rhs.c_str(), rhs.size());
    return rcstring(tmp, length);
}


bool
operator<(const rcstring &lhs, const rcstring &rhs)
{
    return (strcmp(lhs.c_str(), rhs.c_str()) < 0);
}

bool
operator<=(const rcstring &lhs, const rcstring &rhs)
{
    return (strcmp(lhs.c_str(), rhs.c_str()) <= 0);
}

bool
operator>(const rcstring &lhs, const rcstring &rhs)
{
    return (strcmp(lhs.c_str(), rhs.c_str()) > 0);
}

bool
operator>=(const rcstring &lhs, const rcstring &rhs)
{
    return (strcmp(lhs.c_str(), rhs.c_str()) >= 0);
}


rcstring
rcstring::upcase(void)
    const
{
    static char *tmp;
    static size_t tmplen;
    if (tmplen < size())
    {
        tmplen = size();
        tmp = (char *)explain_realloc_or_die(tmp, tmplen);
    }

    const char *cp1;
    char *cp2;
    for (cp1 = c_str(), cp2 = tmp; *cp1; ++cp1, ++cp2)
    {
        int c = (unsigned char)*cp1;
        if (islower(c))
            c = toupper(c);
        *cp2 = c;
    }
    return rcstring(tmp, size());
}


rcstring
rcstring::downcase(void)
    const
{
    static char *tmp;
    static size_t tmplen;
    if (tmplen < size())
    {
        tmplen = size();
        tmp = (char *)explain_realloc_or_die(tmp, tmplen);
    }

    const char *cp1;
    char *cp2;
    for (cp1 = c_str(), cp2 = tmp; *cp1; ++cp1, ++cp2)
    {
        int c = (unsigned char)*cp1;
        if (isupper(c))
            c = tolower(c);
        *cp2 = c;
    }
    return rcstring(tmp, size());
}


rcstring
rcstring::format(const char *fmt, ...)
{
    va_list ap;
    va_start(ap, fmt);
    rcstring result(vmprintfe(fmt, ap));
    va_end(ap);
    return result;
}


rcstring
rcstring::vformat(const char *fmt, va_list ap)
{
    return rcstring(vmprintfe(fmt, ap));
}


void
rcstring::string_ty::one_more(void)
{
    // assert(references > 0);
    references++;
}


void
rcstring::string_ty::one_less(void)
{
    // assert(references > 0);
    references--;
    if (references <= 0)
        delete this;
}


std::vector<rcstring>
rcstring::break_up(const char *sep, bool ewhite)
    const
{
    if (!sep)
    {
        sep = " \t\n\f\r";
        ewhite = 1;
    }
    std::vector<rcstring> slp;
    const char *cp = c_str();
    bool more = false;
    while (*cp || more)
    {
        if (ewhite)
            while (isspace((unsigned char)*cp))
                cp++;
        if (!*cp && !more)
            break;
        more = 0;
        const char *cp1 = cp;
        while (*cp && !strchr(sep, *cp))
            cp++;
        const char *cp2 = cp;
        if (*cp)
        {
            cp2 = cp + 1;
            more = 1;
        }
        if (ewhite)
        {
            while (cp > cp1 && isspace((unsigned char)cp[-1]))
                cp--;
        }
        slp.push_back(rcstring(cp1, cp - cp1));
        cp = cp2;
    }
    return slp;
}


rcstring
rcstring::substr(size_t start, size_t len)
    const
{
    if (start >= size())
        return rcstring("");
    if (start + len > size())
        len = size() - start;
    return rcstring(c_str() + start, len);
}


bool
rcstring::to_long(long &n, int base)
    const
{
    char *end = 0;
    n = strtol(c_str(), &end, base);
    return (end != c_str() && *end == 0);
}


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