mstring.c

/*-
 * Copyright (c) 1996 Dave Richards <dave@synergy.org>
 * Copyright (c) 1996 Thorsten Lockert <tholo@sigmasoft.com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * and exceptions are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the authors may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 4. The code can not be used by Gary Random, Random Communications, Inc.,
 *    the employees of Random Communications, Inc. or its subsidiaries,
 *    including Defiance MUD, without prior written permission from the
 *    authors.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <sys/types.h>

#include "config.h"
#include "lint.h"
#include "mstring.h"
#include "hash.h"
#include "simulate.h"

int num_distinct_strings_shared;
long bytes_distinct_strings_shared;
long overhead_bytes_shared;

int num_distinct_strings_malloced;
long bytes_distinct_strings_malloced;
long overhead_bytes_malloced;

static long long search_len;
static long long num_str_searches;
static long allocd_bytes_malloced;
static int allocd_strings_malloced;
static long allocd_bytes_shared;
static int allocd_strings_shared;

static char *sstring_table[HTABLE_SIZE];

/* 1 G characters should be big enough */
#define MAX_STRING_SIZE (1<<30)

char *
allocate_mstring(size_t len)
{
    char *cp;
    if (len < 0 || len > MAX_STRING_SIZE)
        error("Illegal string size.\n");

    cp = (char *)xalloc(mstring_header + len + 1) + mstring_header;
#ifdef DEBUG
    mstring_magic(cp) = MSTRING_MAGIC;
#endif
    mstring_count(cp) = 1;
    mstring_len(cp) = len;
    allocd_strings_malloced++;
    allocd_bytes_malloced += mstring_header + len + 1;
    num_distinct_strings_malloced++;
    bytes_distinct_strings_malloced += len + 1;
    overhead_bytes_malloced += mstring_header;
    return cp;
}

char *
make_mstring(const char *cp)
{
    size_t len;
    char *xp;

    len = strlen(cp);
    xp = allocate_mstring(len);
    (void)memcpy(xp, cp, len + 1);
    return xp;
}

char *
reference_mstring(char *cp)
{
#ifdef DEBUG
    if (mstring_magic(cp) != MSTRING_MAGIC)
        fatal("Bad m-magic: %lx %x\n", mstring_magic(cp), MSTRING_MAGIC);
#endif

    if (mstring_count(cp) != 0)
        mstring_count(cp)++;

    allocd_strings_malloced++;
    allocd_bytes_malloced += mstring_header + mstring_len(cp) + 1;

    return cp;
}

void
free_mstring(char *cp)
{
#ifdef DEBUG
    if (mstring_magic(cp) != MSTRING_MAGIC)
        fatal("Bad m-magic: %lx %x\n", mstring_magic(cp), MSTRING_MAGIC);
#endif

    if (mstring_count(cp) != 0) {
        allocd_strings_malloced--;
        allocd_bytes_malloced -= mstring_header + mstring_len(cp) + 1;
        if (--mstring_count(cp) == 0)
        {
#ifdef DEBUG
            mstring_magic(cp) = 0;
#endif
            num_distinct_strings_malloced--;
            bytes_distinct_strings_malloced -= mstring_len(cp) + 1;
            overhead_bytes_malloced -= mstring_header;
            free(cp - mstring_header);
        }
    }
}

char *
reference_sstring(char *cp)
{
#ifdef DEBUG
    if (sstring_magic(cp) != SSTRING_MAGIC)
        fatal("Bad s-magic: %lx %x\n", sstring_magic(cp), SSTRING_MAGIC);
#endif

    if (sstring_count(cp) != 0)
        sstring_count(cp)++;

    allocd_strings_shared++;
    allocd_bytes_shared += sstring_header + sstring_len(cp) + 1;

    return cp;
}

char *
find_sstring(char *cp)
{
    unsigned int hash;
    char *xp;

    hash = HASH_SSTRING(cp);
    xp = sstring_table[hash];
    num_str_searches++;
    while (xp != NULL)
    {
        search_len++;
#ifdef DEBUG
        if (sstring_magic(xp) != SSTRING_MAGIC)
            fatal("Bad s-magic: %lx %x\n", sstring_magic(xp), SSTRING_MAGIC);
#endif
        if (xp == cp || (*xp == *cp && strcmp(xp, cp) == 0))
        {
            if (sstring_prev(xp) != NULL) {
                sstring_next(sstring_prev(xp)) = sstring_next(xp);
                if (sstring_next(xp) != NULL)
                    sstring_prev(sstring_next(xp)) = sstring_prev(xp);
                sstring_prev(xp) = NULL;
                sstring_next(xp) = sstring_table[hash];
                sstring_prev(sstring_table[hash]) = xp;
                sstring_table[hash] = xp;
            }
            return xp;
        }
        xp = sstring_next(xp);
    }

    return NULL;
}

char *
make_sstring(const char *cp)
{
    size_t len;
    unsigned int hash;
    char *xp;

    hash = HASH_SSTRING(cp);
    xp = sstring_table[hash];
    num_str_searches++;
    while (xp != NULL)
    {
        search_len++;
#ifdef DEBUG
        if (sstring_magic(xp) != SSTRING_MAGIC)
            fatal("Bad s-magic: %lx %x\n", sstring_magic(xp), SSTRING_MAGIC);
#endif
        if (xp == cp || (*xp == *cp && strcmp(xp, cp) == 0))
        {
            if (sstring_prev(xp) != NULL) {
                sstring_next(sstring_prev(xp)) = sstring_next(xp);
                if (sstring_next(xp) != NULL)
                    sstring_prev(sstring_next(xp)) = sstring_prev(xp);
                sstring_prev(xp) = NULL;
                sstring_next(xp) = sstring_table[hash];
                sstring_prev(sstring_table[hash]) = xp;
                sstring_table[hash] = xp;
            }
            return reference_sstring(xp);
        }
        xp = sstring_next(xp);
    }
    len = strlen(cp);
    if (len < 0 || len > MAX_STRING_SIZE)
        error("Illegal string size.\n");

    xp = (char *)xalloc(sstring_header + len + 1) + sstring_header;
#ifdef DEBUG
    sstring_magic(xp) = SSTRING_MAGIC;
#endif
    sstring_prev(xp) = NULL;
    sstring_next(xp) = sstring_table[hash];
    if (sstring_next(xp) != NULL)
        sstring_prev(sstring_next(xp)) = xp;
    sstring_hash(xp) = hash;
    sstring_count(xp) = 1;
    sstring_len(xp) = len;
    (void)memcpy(xp, cp, len + 1);
    sstring_table[hash] = xp;
    num_distinct_strings_shared++;
    bytes_distinct_strings_shared += len + 1;
    overhead_bytes_shared += sstring_header;
    allocd_strings_shared++;
    allocd_bytes_shared += sstring_header + sstring_len(xp) + 1;

    return xp;
}

void
free_sstring(char *cp)
{
#ifdef DEBUG
    if (sstring_magic(cp) != SSTRING_MAGIC)
        fatal("Bad s-magic: %lx %x\n", sstring_magic(cp), SSTRING_MAGIC);
#endif

    if (sstring_count(cp) != 0) {
        allocd_strings_shared--;
        allocd_bytes_shared -= sstring_header + sstring_len(cp) + 1;

        if (--sstring_count(cp) == 0)
        {
            if (sstring_prev(cp) != NULL)
                sstring_next(sstring_prev(cp)) = sstring_next(cp);
            else
                sstring_table[sstring_hash(cp)] = sstring_next(cp);
            if (sstring_next(cp) != NULL)
                sstring_prev(sstring_next(cp)) = sstring_prev(cp);
#ifdef DEBUG
            sstring_magic(cp) = 0;
#endif
            num_distinct_strings_shared--;
            bytes_distinct_strings_shared -= sstring_len(cp) + 1;
            overhead_bytes_shared -= sstring_header;
            free(cp - sstring_header);
        }
    }
}

char *
multiply_string(char *str, long long factor)
{
    char *result;
    long long size, newsize, offset;

    if (factor <= 0 || (size = strlen(str)) == 0) {
        return make_mstring("");
    }

    if (factor > MAX_STRING_SIZE)
        error("Illegal string size.\n");

    newsize = size * factor;
    result = allocate_mstring(newsize);
    for (offset = 0; offset < newsize; offset += size) {
        strcpy(result + offset, str);
    }
    return result;
}


void
add_string_status(char *debinf)
{
    int i, n;
    char *cp;
    int min = INT_MAX;
    int max = INT_MIN;
    long sum1 = 0;
    long sum2 = 0;
    double mean, stddev;

    /*
     * Compute the min, max, sum of n and sum of n^2.
     */
    for (i = 0; i < HTABLE_SIZE; i++)
    {
        n = 0;
        for (cp = sstring_table[i]; cp != NULL; cp = sstring_next(cp))
            n++;
        if (min > n)
            min = n;
        if (max < n)
            max = n;
        sum1 += n;
        sum2 += (long)n * n;
    }

    if (sum1 == 0)
    {
        min = 0;
        max = 0;
    }

    /*
     * Compute the mean.
     */
    mean = (double)sum1 / HTABLE_SIZE;

    /*
     * Compute the standard deviation.
     */
    stddev = sqrt(((double)sum2 -
        (((double)sum1 * (double)sum1) / HTABLE_SIZE)) / HTABLE_SIZE);

    (void)strcat(debinf, "\nShared string hash table:\n");
    (void)strcat(debinf, "-------------------------     Strings        Bytes\n");

    (void)sprintf(debinf + strlen(debinf), "Total asked for\t\t%12d %12ld\n",
            allocd_strings_shared, allocd_bytes_shared);
    (void)sprintf(debinf + strlen(debinf), "Actually used\t\t%12d %12ld\n",
            num_distinct_strings_shared,
            bytes_distinct_strings_shared + overhead_bytes_shared);

    (void)sprintf(debinf + strlen(debinf),
            "Space actually required/total string bytes %6.2f%%\n",
            (bytes_distinct_strings_shared + overhead_bytes_shared)*100.0 /
            (double)allocd_bytes_shared);

    (void)sprintf(debinf + strlen(debinf),
            "Searches     : %12lld  Average search: %7.3f\n",
            num_str_searches,
            (double)search_len / (double)num_str_searches);

    (void)sprintf(debinf + strlen(debinf),
            "Hash size    : %12d\n", HTABLE_SIZE);
    (void)sprintf(debinf + strlen(debinf),
            "Minimum depth: %12d  Average depth : %7.3f\n",
            min, mean);
    (void)sprintf(debinf + strlen(debinf),
            "Maximum depth: %12d  Std. deviation: %7.3f\n",
            max, stddev);

    (void)strcat(debinf, "\nMalloced string table:\n");
    (void)strcat(debinf, "----------------------\t     Strings        Bytes\n");

    (void)sprintf(debinf + strlen(debinf), "Total asked for\t\t%12d %12ld\n",
            allocd_strings_malloced, allocd_bytes_malloced);
    (void)sprintf(debinf + strlen(debinf), "Actually used\t\t%12d %12ld\n",
            num_distinct_strings_malloced,
            bytes_distinct_strings_malloced + overhead_bytes_malloced);

    (void)sprintf(debinf + strlen(debinf),
            "Space actually required/total string bytes %6.2f%%\n",
            (bytes_distinct_strings_malloced + overhead_bytes_malloced)*100.0 /
            (double)allocd_bytes_malloced);
}

#ifdef DEBUG
void
dump_sstrings(void)
{
    char *str;
    short len;
    FILE *fp;
    int i;

    if ((fp = fopen("SSTRING_DUMP", "w")) == NULL)
        return;
    for (i = 0; i < HTABLE_SIZE; i++) {
        str = sstring_table[i];
        while (str) {
            if (sstring_magic(str) != SSTRING_MAGIC)
                fatal("Bad s-magic: %lx %x\n", sstring_magic(str), SSTRING_MAGIC);
            len = sstring_len(str);
            (void)fwrite(&len, sizeof(len), 1, fp);
            (void)fwrite(str, sizeof(char), strlen(str) + 1, fp);
            str = sstring_next(str);
        }
    }
    (void)fclose(fp);
}
#endif /* DEBUG */

#ifdef DEALLOCATE_MEMORY_AT_SHUTDOWN
void
remove_string_hash()
{
    int i;

    for (i = 0 ; i < HTABLE_SIZE ; i++)
        sstring_table[i] = NULL;
}
#endif /* DEALLOCATE_MEMORY_AT_SHUTDOWN */