/** * @file sstring.c * * Shared string objects. * * @author Geoff Davis <geoff@circlemudsquared.org> * * @par Copyright: * Copyright (C) 2006 Geoff Davis <geoff@circlemudsquared.org><br> * Greg Buxton <greg@circlemudsquared.org> * * @par * Copyright (C) 1993, 94 by the Trustees of the Johns Hopkins University<br> * CircleMUD is based on DikuMUD, Copyright (C) 1990, 1991. * * @par * All rights reserved. See license.doc for complete information. * * @ingroup sstring * @package cs * @version 1.0 */ #define __SSTRING_C__ #include "base.h" #include "log.h" #include "memory.h" #include "sstring.h" #include "structs.h" #include "utils.h" /** * Gets the byte size of a shared string entry. * @param e the shared string hash entry whose size is to be gotten * @return the size of the entry */ #define SSTRING_ENTRY_SIZE(e) \ ((e) != NULL ? sizeof((e)[0]) + (e)->length + 1 : 0) /** * The maximum number of bytes allocated. * @ingroup sstring * @var size_t */ size_t g_maxRealStringBytes = 0; /** * The maximum number of string objects allocated. * @ingroup sstring * @var size_t */ size_t g_maxRealStringCount = 0; /** * The maximum number of virtual bytes allocated. * @ingroup sstring * @var size_t */ size_t g_maxVirtualStringBytes = 0; /** * The maximum number of virtual string objects allocated. * @ingroup sstring * @var size_t */ size_t g_maxVirtualStringCount = 0; /** * The current number of bytes allocated. * @ingroup sstring * @var size_t */ size_t g_realStringBytes = 0; /** * The current number of string objects allocated. * @ingroup sstring * @var size_t */ size_t g_realStringCount = 0; /** * The current number of virtual bytes allocated. * @ingroup sstring * @var size_t */ size_t g_virtualStringBytes = 0; /** * The current number of virtual string objects allocated. * @ingroup sstring * @var size_t */ size_t g_virtualStringCount = 0; /** * The hash table containing the shared string objects. * @ingroup sstring * @var sstring_t *[STRING_TABLE_SIZE] */ sstring_t *g_stringTable[STRING_TABLE_SIZE] = {NULL}; /** * Creates a shared string with one reference. * @param format the printf-style format specifier string * @return the new shared string, or NULL */ char *sstr_create(const char *format, ...) { char *string = NULL; if (format == NULL) { log("sstr_create(): invalid 'format' string."); } else { /* Declare a local buffer to contain the formatted string. */ char buf[MAX_STRING_LENGTH] = {'\0'}; /* Declare a variable argument list. */ va_list args; /* Build the string using VA formatting. */ va_start(args, format); vsnprintf(buf, sizeof(buf), format, args); va_end(args); /* Call sstr_createRaw() to allocated the shared string. */ string = sstr_createRaw(buf); } return (string); } /** * Creates a shared string with one reference. * @param str the contents of the shared string to be created * @return the new shared string, or NULL */ char *sstr_createRaw(const char *str) { sstring_t *entry = NULL; if (str) { /* Cache the length of the string. */ const size_t length = strlen(str); /* Generate a hash code for this string. */ const unsigned long hashCode = sstr_getHashCode(str); /* Translate the hash code into a hash table index. */ const size_t bucket = hashCode % STRING_TABLE_SIZE; /* Try to find a shared string hash entry for the hash code. */ for (entry = g_stringTable[bucket]; entry; entry = entry->next) { if (entry->hashCode == hashCode) break; } /* If we've found a entry, use it. */ if (entry) { entry->references++; } else { /* Allocate memory for the new shared string entry. */ char *dummy = CIRCLE_ALLOCN(char, sizeof(sstring_t) + length + 1); if (dummy == NULL) { /* Write an error message to the log file. */ log("sstr_createRaw(): CIRCLE_ALLOCN() failed: errno=%d.", errno); } else { /* Cast dummy to a shared string hash entry. */ entry = (sstring_t*) dummy; /* Initialize the entry structure. */ entry->data = (char*) &entry[1]; entry->hashCode = hashCode; entry->length = length; entry->references = 1; entry->next = NULL; /* Copy in the new string data. */ strncpy(entry->data, str, length); /* Add the new string entry to the hash table. */ entry->next = g_stringTable[bucket]; g_stringTable[bucket] = entry; /* Adjust the real string byte count. */ g_realStringBytes += SSTRING_ENTRY_SIZE(entry); /* Adjust the real string count. */ g_realStringCount += 1; } } if (entry) { /* Adjust the virtual string byte count. */ g_virtualStringBytes += SSTRING_ENTRY_SIZE(entry); /* Adjust the virtual string count. */ g_virtualStringCount += 1; } /* Adjust maximum real string bytes if needed. */ if (g_realStringBytes > g_maxRealStringBytes) { g_maxRealStringBytes = g_realStringBytes; } /* Adjust maximum real string count if needed. */ if (g_realStringCount > g_maxRealStringCount) { g_maxRealStringCount = g_realStringCount; } /* Adjust maximum virtual string bytes if needed. */ if (g_virtualStringBytes > g_maxVirtualStringBytes) { g_maxVirtualStringBytes = g_virtualStringBytes; } /* Adjust maximum virtual string count if needed. */ if (g_virtualStringCount > g_maxVirtualStringCount) { g_maxVirtualStringCount = g_virtualStringCount; } } return (entry && entry->data ? entry->data : NULL); } /** * Releases one refrence to a shared string. When no references remain, the * shared string is freed. * @param str the shared string to which one reference is to be released * @return none */ void sstr_free(const char *str) { if (str) { /* Look up the shared string hash entry. */ sstring_t *entry = sstr_getEntry(str); if (entry) { /* Adjust the virtual byte count. */ g_virtualStringBytes -= SSTRING_ENTRY_SIZE(entry); /* Adjust the virtual string count. */ g_virtualStringCount -= 1; /* Decrement the shared string's reference count. */ if (entry->references) { entry->references--; } if (entry->references == 0UL) { /* Declare an iterator variable. */ register sstring_t *temp = NULL; /* Figger out which index we want to look at. */ const size_t index = entry->hashCode % STRING_TABLE_SIZE; /* Adjust the real byte count. */ g_realStringBytes -= SSTRING_ENTRY_SIZE(entry); /* Adjust the real string count. */ g_realStringCount -= 1; /* Remove the entry string the hash table. */ REMOVE_FROM_LIST(entry, g_stringTable[index], next); /* Free any non-embedded string data. */ if (entry->data && entry->data != str) { free(entry->data); } /* free string entry resources */ free(entry); } } else { /* Call free() to release the string. */ free((char*) str); } } } /** * Gets the shared string hash entry for a string. * @param str the string for which the hash entry is to be gotten * @return the shared string entry, or NULL if the string is not shared */ sstring_t *sstr_getEntry(const char *str) { if (str) { /* Calculate the hash code for the string. */ const unsigned long hashCode = sstr_getHashCode(str); /* Calculate the hash bucket to search for the string entry. */ const size_t bucket = hashCode % STRING_TABLE_SIZE; /* Declare an iterator variable. */ register sstring_t *temp = NULL; /* Iterate over the string entries in the hash bucket. */ for (temp = g_stringTable[bucket]; temp; temp = temp->next) { /* Determine if this is the string entry we're looking for. */ if (temp->hashCode == hashCode && temp->data == str) return (temp); } } return (NULL); } /** * Gets a hash code suitable for representing the specified string in a hash * table. Note: Strings differing in cases will generate unique hash code. * @param str the string for which to get a hash code * @return the hash code */ unsigned long sstr_getHashCode(const char *str) { unsigned long hashCode = 0UL; if (str) { /* Declare an iterator variable. */ register int n = 0; /* Prime the hash code with a prime number. How punny. */ hashCode = 37UL; /* Iterate over the string. */ for (n = 0; str[n] != '\0'; n++) { /* * each iteration the key is multiplied by a prime number and the * ASCII value of the next character is then added */ hashCode = (hashCode * 17) + (int) str[n]; } } return (hashCode); } /** * Adds a reference to a shared string. * @param str the string to which a reference is to be added * @return none */ char *sstr_share(const char *str) { char *copy = NULL; if (str) { /* Look up the shared string hash entry. */ sstring_t *entry = sstr_getEntry(str); if (entry) { /* Increment reference count for the string entry. */ entry->references++; /* Adjust virtual string byte count. */ g_virtualStringBytes += SSTRING_ENTRY_SIZE(entry); /* Adjust virtual string count. */ g_virtualStringCount++; /* The copy is the shared string itself. */ copy = (char*) str; /* Adjust maximum virtual string bytes if needed. */ if (g_virtualStringBytes > g_maxVirtualStringBytes) { g_maxVirtualStringBytes = g_virtualStringBytes; } /* Adjust maximum virtual string count if needed. */ if (g_virtualStringCount > g_maxVirtualStringCount) { g_maxVirtualStringCount = g_virtualStringCount; } } else { /* If its not shared, just strdup() it instead. */ copy = strdup(str); /* Check whether the allocation was successful. */ if (copy == NULL) { /* Write an error message to the log. */ log("sstr_share(): strdup() failed: errno=%d.", errno); } } } return (copy); }