/*- * Copyright (c) 1996 Dave Richards * Copyright (c) 1996 Thorsten Lockert * 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 #include #include #include #include #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 += 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 */