1 files changed, 342 insertions, 0 deletions

diff --git a/linden/indra/llcommon/llstringtable.cpp b/linden/indra/llcommon/llstringtable.cpp
new file mode 100644
index 0000000..4a76ed6
--- /dev/null
+++ b/linden/indra/llcommon/llstringtable.cpp
@@ -0,0 +1,342 @@
+/** 
+ * @file llstringtable.cpp
+ * @brief The LLStringTable class provides a _fast_ method for finding
+ * unique copies of strings.
+ *
+ * Copyright (c) 2001-2007, Linden Research, Inc.
+ * 
+ * The source code in this file ("Source Code") is provided by Linden Lab
+ * to you under the terms of the GNU General Public License, version 2.0
+ * ("GPL"), unless you have obtained a separate licensing agreement
+ * ("Other License"), formally executed by you and Linden Lab.  Terms of
+ * the GPL can be found in doc/GPL-license.txt in this distribution, or
+ * online at http://secondlife.com/developers/opensource/gplv2
+ * 
+ * There are special exceptions to the terms and conditions of the GPL as
+ * it is applied to this Source Code. View the full text of the exception
+ * in the file doc/FLOSS-exception.txt in this software distribution, or
+ * online at http://secondlife.com/developers/opensource/flossexception
+ * 
+ * By copying, modifying or distributing this software, you acknowledge
+ * that you have read and understood your obligations described above,
+ * and agree to abide by those obligations.
+ * 
+ * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
+ * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
+ * COMPLETENESS OR PERFORMANCE.
+ */
+
+#include "linden_common.h"
+
+#include "llstringtable.h"
+#include "llstl.h"
+
+LLStringTable gStringTable(32768);
+
+LLStringTable::LLStringTable(int tablesize)
+: mUniqueEntries(0)
+{
+        S32 i;
+        if (!tablesize)
+                tablesize = 4096; // some arbitrary default
+        // Make sure tablesize is power of 2
+        for (i = 31; i>0; i--)
+        {
+                if (tablesize & (1<<i))
+                {
+                        if (tablesize >= (3<<(i-1)))
+                                tablesize = (1<<(i+1));
+                        else
+                                tablesize = (1<<i);
+                        break;
+                }
+        }
+        mMaxEntries = tablesize;
+
+#if !STRING_TABLE_HASH_MAP
+        // ALlocate strings
+        mStringList = new string_list_ptr_t[mMaxEntries];
+        // Clear strings
+        for (i = 0; i < mMaxEntries; i++)
+        {
+                mStringList[i] = NULL;
+        }
+#endif
+}
+
+LLStringTable::~LLStringTable()
+{
+#if !STRING_TABLE_HASH_MAP
+        if (mStringList)
+        {
+                for (S32 i = 0; i < mMaxEntries; i++)
+                {
+                        if (mStringList[i])
+                        {
+                                string_list_t::iterator iter;
+                                for (iter = mStringList[i]->begin(); iter != mStringList[i]->end(); iter++)
+                                        delete *iter; // *iter = (LLStringTableEntry*)
+                        }
+                        delete mStringList[i];
+                }
+                delete [] mStringList;
+                mStringList = NULL;
+        }
+#else
+        // Need to clean up the string hash
+        for_each(mStringHash.begin(), mStringHash.end(), DeletePairedPointer());
+        mStringHash.clear();
+#endif
+}
+
+
+static U32 hash_my_string(const char *str, int max_entries)
+{
+        U32 retval = 0;
+#if 0
+        while (*str)
+        {
+                retval <<= 1;
+                retval += *str++;
+        }
+#else
+        while (*str)
+        {
+                retval = (retval<<4) + *str;
+                U32 x = (retval & 0xf0000000);
+                if (x) retval = retval ^ (x>>24);
+                retval = retval & (~x);
+                str++;
+        }
+#endif
+        return (retval & (max_entries-1)); // max_entries is gauranteed to be power of 2
+}
+
+char* LLStringTable::checkString(const std::string& str)
+{
+        return checkString(str.c_str());
+}
+
+char* LLStringTable::checkString(const char *str)
+{
+    LLStringTableEntry* entry = checkStringEntry(str);
+    if (entry)
+    {
+        return entry->mString;
+    }
+    else
+    {
+        return NULL;
+    }
+}
+
+LLStringTableEntry* LLStringTable::checkStringEntry(const std::string& str)
+{
+    return checkStringEntry(str.c_str());
+}
+
+LLStringTableEntry* LLStringTable::checkStringEntry(const char *str)
+{
+        if (str)
+        {
+                char *ret_val;
+                LLStringTableEntry      *entry;
+                U32                                     hash_value = hash_my_string(str, mMaxEntries);
+#if STRING_TABLE_HASH_MAP
+#if 1 // Microsoft
+                string_hash_t::iterator lower = mStringHash.lower_bound(hash_value);
+                string_hash_t::iterator upper = mStringHash.upper_bound(hash_value);
+#else // stlport
+                std::pair<string_hash_t::iterator, string_hash_t::iterator> P = mStringHash.equal_range(hash_value);
+                string_hash_t::iterator lower = P.first;
+                string_hash_t::iterator upper = P.second;
+#endif
+                for (string_hash_t::iterator iter = lower; iter != upper; iter++)
+                {
+                        entry = iter->second;
+                        ret_val = entry->mString;
+                        if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
+                        {
+                                return entry;
+                        }
+                }
+#else
+                string_list_t           *strlist = mStringList[hash_value];
+                if (strlist)
+                {
+                        string_list_t::iterator iter;
+                        for (iter = strlist->begin(); iter != strlist->end(); iter++)
+                        {
+                                entry = *iter;
+                                ret_val = entry->mString;
+                                if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
+                                {
+                                        return entry;
+                                }
+                        }
+                }
+#endif
+        }
+        return NULL;
+}
+
+char* LLStringTable::addString(const std::string& str)
+{
+        //RN: safe to use temporary c_str since string is copied
+        return addString(str.c_str());
+}
+
+char* LLStringTable::addString(const char *str)
+{
+
+    LLStringTableEntry* entry = addStringEntry(str);
+    if (entry)
+    {
+        return entry->mString;
+    }
+    else
+    {
+        return NULL;
+    }
+}
+
+LLStringTableEntry* LLStringTable::addStringEntry(const std::string& str)
+{
+    return addStringEntry(str.c_str());
+}
+
+LLStringTableEntry* LLStringTable::addStringEntry(const char *str)
+{
+        if (str)
+        {
+                char *ret_val = NULL;
+                LLStringTableEntry      *entry;
+                U32                                     hash_value = hash_my_string(str, mMaxEntries);
+#if STRING_TABLE_HASH_MAP
+#if 1 // Microsoft
+                string_hash_t::iterator lower = mStringHash.lower_bound(hash_value);
+                string_hash_t::iterator upper = mStringHash.upper_bound(hash_value);
+#else // stlport
+                std::pair<string_hash_t::iterator, string_hash_t::iterator> P = mStringHash.equal_range(hash_value);
+                string_hash_t::iterator lower = P.first;
+                string_hash_t::iterator upper = P.second;
+#endif
+                for (string_hash_t::iterator iter = lower; iter != upper; iter++)
+                {
+                        entry = iter->second;
+                        ret_val = entry->mString;
+                        if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
+                        {
+                                entry->incCount();
+                                return entry;
+                        }
+                }
+
+                // not found, so add!
+                LLStringTableEntry* newentry = new LLStringTableEntry(str);
+                ret_val = newentry->mString;
+                mStringHash.insert(string_hash_t::value_type(hash_value, newentry));
+#else
+                string_list_t           *strlist = mStringList[hash_value];
+
+                if (strlist)
+                {
+                        string_list_t::iterator iter;
+                        for (iter = strlist->begin(); iter != strlist->end(); iter++)
+                        {
+                                entry = *iter;
+                                ret_val = entry->mString;
+                                if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
+                                {
+                                        entry->incCount();
+                                        return entry;
+                                }
+                        }
+                }
+                else
+                {
+                        mStringList[hash_value] = new string_list_t;
+                        strlist = mStringList[hash_value];
+                }
+
+                // not found, so add!
+                LLStringTableEntry *newentry = new LLStringTableEntry(str);
+                //ret_val = newentry->mString;
+                strlist->push_front(newentry);
+#endif
+                mUniqueEntries++;
+                return newentry;
+        }
+        else
+        {
+                return NULL;
+        }
+}
+
+void LLStringTable::removeString(const char *str)
+{
+        if (str)
+        {
+                char *ret_val;
+                LLStringTableEntry      *entry;
+                U32                                     hash_value = hash_my_string(str, mMaxEntries);
+#if STRING_TABLE_HASH_MAP
+                {
+#if 1 // Microsoft
+                        string_hash_t::iterator lower = mStringHash.lower_bound(hash_value);
+                        string_hash_t::iterator upper = mStringHash.upper_bound(hash_value);
+#else // stlport
+                        std::pair<string_hash_t::iterator, string_hash_t::iterator> P = mStringHash.equal_range(hash_value);
+                        string_hash_t::iterator lower = P.first;
+                        string_hash_t::iterator upper = P.second;
+#endif
+                        for (string_hash_t::iterator iter = lower; iter != upper; iter++)
+                        {
+                                entry = iter->second;
+                                ret_val = entry->mString;
+                                if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
+                                {
+                                        if (!entry->decCount())
+                                        {
+                                                mUniqueEntries--;
+                                                if (mUniqueEntries < 0)
+                                                {
+                                                        llerror("LLStringTable:removeString trying to remove too many strings!", 0);
+                                                }
+                                                delete iter->second;
+                                                mStringHash.erase(iter);
+                                        }
+                                        return;
+                                }
+                        }
+                }
+#else
+                string_list_t           *strlist = mStringList[hash_value];
+
+                if (strlist)
+                {
+                        string_list_t::iterator iter;
+                        for (iter = strlist->begin(); iter != strlist->end(); iter++)
+                        {
+                                entry = *iter;
+                                ret_val = entry->mString;
+                                if (!strncmp(ret_val, str, MAX_STRINGS_LENGTH))
+                                {
+                                        if (!entry->decCount())
+                                        {
+                                                mUniqueEntries--;
+                                                if (mUniqueEntries < 0)
+                                                {
+                                                        llerror("LLStringTable:removeString trying to remove too many strings!", 0);
+                                                }
+                                                strlist->remove(entry);
+                                                delete entry;
+                                        }
+                                        return;
+                                }
+                        }
+                }
+#endif
+        }
+}
+