From df08808640031bd27a11177ea49a08f797d2d570 Mon Sep 17 00:00:00 2001
From: "Graham Madarasz (Graham)" <graham@lindenlab.com>
Date: Thu, 28 Feb 2013 09:33:41 -0800
Subject: Improve perf of GLSL uniform lookups by name

---
 indra/llcommon/llstringtable.h | 480 ++++++++++++++++++++++-------------------
 1 file changed, 263 insertions(+), 217 deletions(-)

(limited to 'indra/llcommon/llstringtable.h')

diff --git a/indra/llcommon/llstringtable.h b/indra/llcommon/llstringtable.h
index 59d7372ed4..4f6417328c 100644
--- a/indra/llcommon/llstringtable.h
+++ b/indra/llcommon/llstringtable.h
@@ -1,217 +1,263 @@
-/** 
- * @file llstringtable.h
- * @brief The LLStringTable class provides a _fast_ method for finding
- * unique copies of strings.
- *
- * $LicenseInfo:firstyear=2001&license=viewerlgpl$
- * Second Life Viewer Source Code
- * Copyright (C) 2010, Linden Research, Inc.
- * 
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation;
- * version 2.1 of the License only.
- * 
- * This library 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
- * Lesser General Public License for more details.
- * 
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
- * 
- * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
- * $/LicenseInfo$
- */
-
-#ifndef LL_STRING_TABLE_H
-#define LL_STRING_TABLE_H
-
-#include "lldefs.h"
-#include "llformat.h"
-#include "llstl.h"
-#include <list>
-#include <set>
-
-#if LL_WINDOWS
-# if (_MSC_VER >= 1300 && _MSC_VER < 1400)
-#  define STRING_TABLE_HASH_MAP 1
-# endif
-#else
-//# define STRING_TABLE_HASH_MAP 1
-#endif
-
-#if STRING_TABLE_HASH_MAP
-# if LL_WINDOWS
-#  include <hash_map>
-# else
-#  include <ext/hash_map>
-# endif
-#endif
-
-const U32 MAX_STRINGS_LENGTH = 256;
-
-class LL_COMMON_API LLStringTableEntry
-{
-public:
-	LLStringTableEntry(const char *str);
-	~LLStringTableEntry();
-
-	void incCount()		{ mCount++; }
-	BOOL decCount()		{ return --mCount; }
-
-	char *mString;
-	S32  mCount;
-};
-
-class LL_COMMON_API LLStringTable
-{
-public:
-	LLStringTable(int tablesize);
-	~LLStringTable();
-
-	char *checkString(const char *str);
-	char *checkString(const std::string& str);
-	LLStringTableEntry *checkStringEntry(const char *str);
-	LLStringTableEntry *checkStringEntry(const std::string& str);
-
-	char *addString(const char *str);
-	char *addString(const std::string& str);
-	LLStringTableEntry *addStringEntry(const char *str);
-	LLStringTableEntry *addStringEntry(const std::string& str);
-	void  removeString(const char *str);
-
-	S32 mMaxEntries;
-	S32 mUniqueEntries;
-	
-#if STRING_TABLE_HASH_MAP
-#if LL_WINDOWS
-	typedef std::hash_multimap<U32, LLStringTableEntry *> string_hash_t;
-#else
-	typedef __gnu_cxx::hash_multimap<U32, LLStringTableEntry *> string_hash_t;
-#endif
-	string_hash_t mStringHash;
-#else
-	typedef std::list<LLStringTableEntry *> string_list_t;
-	typedef string_list_t * string_list_ptr_t;
-	string_list_ptr_t	*mStringList;
-#endif	
-};
-
-extern LL_COMMON_API LLStringTable gStringTable;
-
-//============================================================================
-
-// This class is designed to be used locally,
-// e.g. as a member of an LLXmlTree
-// Strings can be inserted only, then quickly looked up
-
-typedef const std::string* LLStdStringHandle;
-
-class LL_COMMON_API LLStdStringTable
-{
-public:
-	LLStdStringTable(S32 tablesize = 0)
-	{
-		if (tablesize == 0)
-		{
-			tablesize = 256; // default
-		}
-		// Make sure tablesize is power of 2
-		for (S32 i = 31; i>0; i--)
-		{
-			if (tablesize & (1<<i))
-			{
-				if (tablesize >= (3<<(i-1)))
-					tablesize = (1<<(i+1));
-				else
-					tablesize = (1<<i);
-				break;
-			}
-		}
-		mTableSize = tablesize;
-		mStringList = new string_set_t[tablesize];
-	}
-	~LLStdStringTable()
-	{
-		cleanup();
-		delete[] mStringList;
-	}
-	void cleanup()
-	{
-		// remove strings
-		for (S32 i = 0; i<mTableSize; i++)
-		{
-			string_set_t& stringset = mStringList[i];
-			for (string_set_t::iterator iter = stringset.begin(); iter != stringset.end(); iter++)
-			{
-				delete *iter;
-			}
-			stringset.clear();
-		}
-	}
-
-	LLStdStringHandle lookup(const std::string& s)
-	{
-		U32 hashval = makehash(s);
-		return lookup(hashval, s);
-	}
-	
-	LLStdStringHandle checkString(const std::string& s)
-	{
-		U32 hashval = makehash(s);
-		return lookup(hashval, s);
-	}
-
-	LLStdStringHandle insert(const std::string& s)
-	{
-		U32 hashval = makehash(s);
-		LLStdStringHandle result = lookup(hashval, s);
-		if (result == NULL)
-		{
-			result = new std::string(s);
-			mStringList[hashval].insert(result);
-		}
-		return result;
-	}
-	LLStdStringHandle addString(const std::string& s)
-	{
-		return insert(s);
-	}
-	
-private:
-	U32 makehash(const std::string& s)
-	{
-		S32 len = (S32)s.size();
-		const char* c = s.c_str();
-		U32 hashval = 0;
-		for (S32 i=0; i<len; i++)
-		{
-			hashval = ((hashval<<5) + hashval) + *c++;
-		}
-		return hashval & (mTableSize-1);
-	}
-	LLStdStringHandle lookup(U32 hashval, const std::string& s)
-	{
-		string_set_t& stringset = mStringList[hashval];
-		LLStdStringHandle handle = &s;
-		string_set_t::iterator iter = stringset.find(handle); // compares actual strings
-		if (iter != stringset.end())
-		{
-			return *iter;
-		}
-		else
-		{
-			return NULL;
-		}
-	}
-	
-private:
-	S32 mTableSize;
-	typedef std::set<LLStdStringHandle, compare_pointer_contents<std::string> > string_set_t;
-	string_set_t* mStringList; // [mTableSize]
-};
-
-
-#endif
+/** 
+ * @file llstringtable.h
+ * @brief The LLStringTable class provides a _fast_ method for finding
+ * unique copies of strings.
+ *
+ * $LicenseInfo:firstyear=2001&license=viewerlgpl$
+ * Second Life Viewer Source Code
+ * Copyright (C) 2010, Linden Research, Inc.
+ * 
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation;
+ * version 2.1 of the License only.
+ * 
+ * This library 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
+ * Lesser General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ * 
+ * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
+ * $/LicenseInfo$
+ */
+
+#ifndef LL_STRING_TABLE_H
+#define LL_STRING_TABLE_H
+
+#include "lldefs.h"
+#include "llformat.h"
+#include "llstl.h"
+#include <list>
+#include <set>
+#include <hash_map>
+
+#if LL_WINDOWS
+# if (_MSC_VER >= 1300 && _MSC_VER < 1400)
+#  define STRING_TABLE_HASH_MAP 1
+# endif
+#else
+//# define STRING_TABLE_HASH_MAP 1
+#endif
+
+#if STRING_TABLE_HASH_MAP
+# if LL_WINDOWS
+#  include <hash_map>
+# else
+#  include <ext/hash_map>
+# endif
+#endif
+
+class LLStaticHashedString
+{
+public:
+
+	LLStaticHashedString(const std::string& s)
+	{
+		string_hash = makehash(s);
+		string		= s;
+	}
+
+	const std::string&	String() const { return string;		}
+	size_t				Hash()	 const { return string_hash;  }
+
+protected:
+
+	size_t makehash(const std::string& s)
+	{
+		size_t len = s.size();
+		const char* c = s.c_str();
+		size_t hashval = 0;
+		for (size_t i=0; i<len; i++)
+		{
+			hashval = ((hashval<<5) + hashval) + *c++;
+		}
+		return hashval;
+	}
+
+	std::string string;
+	size_t		string_hash;
+};
+
+template<class T>
+struct LLStaticStringHasher
+{
+	enum { bucket_size = 8 };
+	size_t operator()(const T& key_value)		   const { return key_value.Hash();			  }
+	bool operator()(const T& left, const T& right) const { return left.Hash() < right.Hash(); }
+};
+
+template< typename MappedObject >
+class LL_COMMON_API LLStaticStringTable
+	: public std::hash_map< LLStaticHashedString , MappedObject, LLStaticStringHasher< LLStaticHashedString > >
+{
+};
+
+const U32 MAX_STRINGS_LENGTH = 256;
+
+class LL_COMMON_API LLStringTableEntry
+{
+public:
+	LLStringTableEntry(const char *str);
+	~LLStringTableEntry();
+
+	void incCount()		{ mCount++; }
+	BOOL decCount()		{ return --mCount; }
+
+	char *mString;
+	S32  mCount;
+};
+
+class LL_COMMON_API LLStringTable
+{
+public:
+	LLStringTable(int tablesize);
+	~LLStringTable();
+
+	char *checkString(const char *str);
+	char *checkString(const std::string& str);
+	LLStringTableEntry *checkStringEntry(const char *str);
+	LLStringTableEntry *checkStringEntry(const std::string& str);
+
+	char *addString(const char *str);
+	char *addString(const std::string& str);
+	LLStringTableEntry *addStringEntry(const char *str);
+	LLStringTableEntry *addStringEntry(const std::string& str);
+	void  removeString(const char *str);
+
+	S32 mMaxEntries;
+	S32 mUniqueEntries;
+	
+#if STRING_TABLE_HASH_MAP
+#if LL_WINDOWS
+	typedef std::hash_multimap<U32, LLStringTableEntry *> string_hash_t;
+#else
+	typedef __gnu_cxx::hash_multimap<U32, LLStringTableEntry *> string_hash_t;
+#endif
+	string_hash_t mStringHash;
+#else
+	typedef std::list<LLStringTableEntry *> string_list_t;
+	typedef string_list_t * string_list_ptr_t;
+	string_list_ptr_t	*mStringList;
+#endif	
+};
+
+extern LL_COMMON_API LLStringTable gStringTable;
+
+//============================================================================
+
+// This class is designed to be used locally,
+// e.g. as a member of an LLXmlTree
+// Strings can be inserted only, then quickly looked up
+
+typedef const std::string* LLStdStringHandle;
+
+class LL_COMMON_API LLStdStringTable
+{
+public:
+	LLStdStringTable(S32 tablesize = 0)
+	{
+		if (tablesize == 0)
+		{
+			tablesize = 256; // default
+		}
+		// Make sure tablesize is power of 2
+		for (S32 i = 31; i>0; i--)
+		{
+			if (tablesize & (1<<i))
+			{
+				if (tablesize >= (3<<(i-1)))
+					tablesize = (1<<(i+1));
+				else
+					tablesize = (1<<i);
+				break;
+			}
+		}
+		mTableSize = tablesize;
+		mStringList = new string_set_t[tablesize];
+	}
+	~LLStdStringTable()
+	{
+		cleanup();
+		delete[] mStringList;
+	}
+	void cleanup()
+	{
+		// remove strings
+		for (S32 i = 0; i<mTableSize; i++)
+		{
+			string_set_t& stringset = mStringList[i];
+			for (string_set_t::iterator iter = stringset.begin(); iter != stringset.end(); iter++)
+			{
+				delete *iter;
+			}
+			stringset.clear();
+		}
+	}
+
+	LLStdStringHandle lookup(const std::string& s)
+	{
+		U32 hashval = makehash(s);
+		return lookup(hashval, s);
+	}
+	
+	LLStdStringHandle checkString(const std::string& s)
+	{
+		U32 hashval = makehash(s);
+		return lookup(hashval, s);
+	}
+
+	LLStdStringHandle insert(const std::string& s)
+	{
+		U32 hashval = makehash(s);
+		LLStdStringHandle result = lookup(hashval, s);
+		if (result == NULL)
+		{
+			result = new std::string(s);
+			mStringList[hashval].insert(result);
+		}
+		return result;
+	}
+	LLStdStringHandle addString(const std::string& s)
+	{
+		return insert(s);
+	}
+	
+private:
+	U32 makehash(const std::string& s)
+	{
+		S32 len = (S32)s.size();
+		const char* c = s.c_str();
+		U32 hashval = 0;
+		for (S32 i=0; i<len; i++)
+		{
+			hashval = ((hashval<<5) + hashval) + *c++;
+		}
+		return hashval & (mTableSize-1);
+	}
+	LLStdStringHandle lookup(U32 hashval, const std::string& s)
+	{
+		string_set_t& stringset = mStringList[hashval];
+		LLStdStringHandle handle = &s;
+		string_set_t::iterator iter = stringset.find(handle); // compares actual strings
+		if (iter != stringset.end())
+		{
+			return *iter;
+		}
+		else
+		{
+			return NULL;
+		}
+	}
+	
+private:
+	S32 mTableSize;
+	typedef std::set<LLStdStringHandle, compare_pointer_contents<std::string> > string_set_t;
+	string_set_t* mStringList; // [mTableSize]
+};
+
+
+#endif
-- 
cgit v1.2.3


From dfda8826eb4654845430520dac48c011e058e1c0 Mon Sep 17 00:00:00 2001
From: "Graham Madarasz (Graham)" <graham@lindenlab.com>
Date: Fri, 1 Mar 2013 11:21:35 -0800
Subject: Make WL updates use pre-hashed strings for uniform sets

---
 indra/llcommon/llstringtable.h | 54 ------------------------------------------
 1 file changed, 54 deletions(-)

(limited to 'indra/llcommon/llstringtable.h')

diff --git a/indra/llcommon/llstringtable.h b/indra/llcommon/llstringtable.h
index 4f6417328c..787a046741 100644
--- a/indra/llcommon/llstringtable.h
+++ b/indra/llcommon/llstringtable.h
@@ -33,7 +33,6 @@
 #include "llstl.h"
 #include <list>
 #include <set>
-#include <hash_map>
 
 #if LL_WINDOWS
 # if (_MSC_VER >= 1300 && _MSC_VER < 1400)
@@ -43,59 +42,6 @@
 //# define STRING_TABLE_HASH_MAP 1
 #endif
 
-#if STRING_TABLE_HASH_MAP
-# if LL_WINDOWS
-#  include <hash_map>
-# else
-#  include <ext/hash_map>
-# endif
-#endif
-
-class LLStaticHashedString
-{
-public:
-
-	LLStaticHashedString(const std::string& s)
-	{
-		string_hash = makehash(s);
-		string		= s;
-	}
-
-	const std::string&	String() const { return string;		}
-	size_t				Hash()	 const { return string_hash;  }
-
-protected:
-
-	size_t makehash(const std::string& s)
-	{
-		size_t len = s.size();
-		const char* c = s.c_str();
-		size_t hashval = 0;
-		for (size_t i=0; i<len; i++)
-		{
-			hashval = ((hashval<<5) + hashval) + *c++;
-		}
-		return hashval;
-	}
-
-	std::string string;
-	size_t		string_hash;
-};
-
-template<class T>
-struct LLStaticStringHasher
-{
-	enum { bucket_size = 8 };
-	size_t operator()(const T& key_value)		   const { return key_value.Hash();			  }
-	bool operator()(const T& left, const T& right) const { return left.Hash() < right.Hash(); }
-};
-
-template< typename MappedObject >
-class LL_COMMON_API LLStaticStringTable
-	: public std::hash_map< LLStaticHashedString , MappedObject, LLStaticStringHasher< LLStaticHashedString > >
-{
-};
-
 const U32 MAX_STRINGS_LENGTH = 256;
 
 class LL_COMMON_API LLStringTableEntry
-- 
cgit v1.2.3


From f111b5b1135ee31434acb81d5a3e63e4812e257f Mon Sep 17 00:00:00 2001
From: simon <none@none>
Date: Tue, 14 May 2013 09:24:58 -0700
Subject: Fix EOL characters

---
 indra/llcommon/llstringtable.h | 418 ++++++++++++++++++++---------------------
 1 file changed, 209 insertions(+), 209 deletions(-)

(limited to 'indra/llcommon/llstringtable.h')

diff --git a/indra/llcommon/llstringtable.h b/indra/llcommon/llstringtable.h
index 787a046741..ff09e71677 100755
--- a/indra/llcommon/llstringtable.h
+++ b/indra/llcommon/llstringtable.h
@@ -1,209 +1,209 @@
-/** 
- * @file llstringtable.h
- * @brief The LLStringTable class provides a _fast_ method for finding
- * unique copies of strings.
- *
- * $LicenseInfo:firstyear=2001&license=viewerlgpl$
- * Second Life Viewer Source Code
- * Copyright (C) 2010, Linden Research, Inc.
- * 
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation;
- * version 2.1 of the License only.
- * 
- * This library 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
- * Lesser General Public License for more details.
- * 
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
- * 
- * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
- * $/LicenseInfo$
- */
-
-#ifndef LL_STRING_TABLE_H
-#define LL_STRING_TABLE_H
-
-#include "lldefs.h"
-#include "llformat.h"
-#include "llstl.h"
-#include <list>
-#include <set>
-
-#if LL_WINDOWS
-# if (_MSC_VER >= 1300 && _MSC_VER < 1400)
-#  define STRING_TABLE_HASH_MAP 1
-# endif
-#else
-//# define STRING_TABLE_HASH_MAP 1
-#endif
-
-const U32 MAX_STRINGS_LENGTH = 256;
-
-class LL_COMMON_API LLStringTableEntry
-{
-public:
-	LLStringTableEntry(const char *str);
-	~LLStringTableEntry();
-
-	void incCount()		{ mCount++; }
-	BOOL decCount()		{ return --mCount; }
-
-	char *mString;
-	S32  mCount;
-};
-
-class LL_COMMON_API LLStringTable
-{
-public:
-	LLStringTable(int tablesize);
-	~LLStringTable();
-
-	char *checkString(const char *str);
-	char *checkString(const std::string& str);
-	LLStringTableEntry *checkStringEntry(const char *str);
-	LLStringTableEntry *checkStringEntry(const std::string& str);
-
-	char *addString(const char *str);
-	char *addString(const std::string& str);
-	LLStringTableEntry *addStringEntry(const char *str);
-	LLStringTableEntry *addStringEntry(const std::string& str);
-	void  removeString(const char *str);
-
-	S32 mMaxEntries;
-	S32 mUniqueEntries;
-	
-#if STRING_TABLE_HASH_MAP
-#if LL_WINDOWS
-	typedef std::hash_multimap<U32, LLStringTableEntry *> string_hash_t;
-#else
-	typedef __gnu_cxx::hash_multimap<U32, LLStringTableEntry *> string_hash_t;
-#endif
-	string_hash_t mStringHash;
-#else
-	typedef std::list<LLStringTableEntry *> string_list_t;
-	typedef string_list_t * string_list_ptr_t;
-	string_list_ptr_t	*mStringList;
-#endif	
-};
-
-extern LL_COMMON_API LLStringTable gStringTable;
-
-//============================================================================
-
-// This class is designed to be used locally,
-// e.g. as a member of an LLXmlTree
-// Strings can be inserted only, then quickly looked up
-
-typedef const std::string* LLStdStringHandle;
-
-class LL_COMMON_API LLStdStringTable
-{
-public:
-	LLStdStringTable(S32 tablesize = 0)
-	{
-		if (tablesize == 0)
-		{
-			tablesize = 256; // default
-		}
-		// Make sure tablesize is power of 2
-		for (S32 i = 31; i>0; i--)
-		{
-			if (tablesize & (1<<i))
-			{
-				if (tablesize >= (3<<(i-1)))
-					tablesize = (1<<(i+1));
-				else
-					tablesize = (1<<i);
-				break;
-			}
-		}
-		mTableSize = tablesize;
-		mStringList = new string_set_t[tablesize];
-	}
-	~LLStdStringTable()
-	{
-		cleanup();
-		delete[] mStringList;
-	}
-	void cleanup()
-	{
-		// remove strings
-		for (S32 i = 0; i<mTableSize; i++)
-		{
-			string_set_t& stringset = mStringList[i];
-			for (string_set_t::iterator iter = stringset.begin(); iter != stringset.end(); iter++)
-			{
-				delete *iter;
-			}
-			stringset.clear();
-		}
-	}
-
-	LLStdStringHandle lookup(const std::string& s)
-	{
-		U32 hashval = makehash(s);
-		return lookup(hashval, s);
-	}
-	
-	LLStdStringHandle checkString(const std::string& s)
-	{
-		U32 hashval = makehash(s);
-		return lookup(hashval, s);
-	}
-
-	LLStdStringHandle insert(const std::string& s)
-	{
-		U32 hashval = makehash(s);
-		LLStdStringHandle result = lookup(hashval, s);
-		if (result == NULL)
-		{
-			result = new std::string(s);
-			mStringList[hashval].insert(result);
-		}
-		return result;
-	}
-	LLStdStringHandle addString(const std::string& s)
-	{
-		return insert(s);
-	}
-	
-private:
-	U32 makehash(const std::string& s)
-	{
-		S32 len = (S32)s.size();
-		const char* c = s.c_str();
-		U32 hashval = 0;
-		for (S32 i=0; i<len; i++)
-		{
-			hashval = ((hashval<<5) + hashval) + *c++;
-		}
-		return hashval & (mTableSize-1);
-	}
-	LLStdStringHandle lookup(U32 hashval, const std::string& s)
-	{
-		string_set_t& stringset = mStringList[hashval];
-		LLStdStringHandle handle = &s;
-		string_set_t::iterator iter = stringset.find(handle); // compares actual strings
-		if (iter != stringset.end())
-		{
-			return *iter;
-		}
-		else
-		{
-			return NULL;
-		}
-	}
-	
-private:
-	S32 mTableSize;
-	typedef std::set<LLStdStringHandle, compare_pointer_contents<std::string> > string_set_t;
-	string_set_t* mStringList; // [mTableSize]
-};
-
-
-#endif
+/** 
+ * @file llstringtable.h
+ * @brief The LLStringTable class provides a _fast_ method for finding
+ * unique copies of strings.
+ *
+ * $LicenseInfo:firstyear=2001&license=viewerlgpl$
+ * Second Life Viewer Source Code
+ * Copyright (C) 2010, Linden Research, Inc.
+ * 
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation;
+ * version 2.1 of the License only.
+ * 
+ * This library 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
+ * Lesser General Public License for more details.
+ * 
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ * 
+ * Linden Research, Inc., 945 Battery Street, San Francisco, CA  94111  USA
+ * $/LicenseInfo$
+ */
+
+#ifndef LL_STRING_TABLE_H
+#define LL_STRING_TABLE_H
+
+#include "lldefs.h"
+#include "llformat.h"
+#include "llstl.h"
+#include <list>
+#include <set>
+
+#if LL_WINDOWS
+# if (_MSC_VER >= 1300 && _MSC_VER < 1400)
+#  define STRING_TABLE_HASH_MAP 1
+# endif
+#else
+//# define STRING_TABLE_HASH_MAP 1
+#endif
+
+const U32 MAX_STRINGS_LENGTH = 256;
+
+class LL_COMMON_API LLStringTableEntry
+{
+public:
+	LLStringTableEntry(const char *str);
+	~LLStringTableEntry();
+
+	void incCount()		{ mCount++; }
+	BOOL decCount()		{ return --mCount; }
+
+	char *mString;
+	S32  mCount;
+};
+
+class LL_COMMON_API LLStringTable
+{
+public:
+	LLStringTable(int tablesize);
+	~LLStringTable();
+
+	char *checkString(const char *str);
+	char *checkString(const std::string& str);
+	LLStringTableEntry *checkStringEntry(const char *str);
+	LLStringTableEntry *checkStringEntry(const std::string& str);
+
+	char *addString(const char *str);
+	char *addString(const std::string& str);
+	LLStringTableEntry *addStringEntry(const char *str);
+	LLStringTableEntry *addStringEntry(const std::string& str);
+	void  removeString(const char *str);
+
+	S32 mMaxEntries;
+	S32 mUniqueEntries;
+	
+#if STRING_TABLE_HASH_MAP
+#if LL_WINDOWS
+	typedef std::hash_multimap<U32, LLStringTableEntry *> string_hash_t;
+#else
+	typedef __gnu_cxx::hash_multimap<U32, LLStringTableEntry *> string_hash_t;
+#endif
+	string_hash_t mStringHash;
+#else
+	typedef std::list<LLStringTableEntry *> string_list_t;
+	typedef string_list_t * string_list_ptr_t;
+	string_list_ptr_t	*mStringList;
+#endif	
+};
+
+extern LL_COMMON_API LLStringTable gStringTable;
+
+//============================================================================
+
+// This class is designed to be used locally,
+// e.g. as a member of an LLXmlTree
+// Strings can be inserted only, then quickly looked up
+
+typedef const std::string* LLStdStringHandle;
+
+class LL_COMMON_API LLStdStringTable
+{
+public:
+	LLStdStringTable(S32 tablesize = 0)
+	{
+		if (tablesize == 0)
+		{
+			tablesize = 256; // default
+		}
+		// Make sure tablesize is power of 2
+		for (S32 i = 31; i>0; i--)
+		{
+			if (tablesize & (1<<i))
+			{
+				if (tablesize >= (3<<(i-1)))
+					tablesize = (1<<(i+1));
+				else
+					tablesize = (1<<i);
+				break;
+			}
+		}
+		mTableSize = tablesize;
+		mStringList = new string_set_t[tablesize];
+	}
+	~LLStdStringTable()
+	{
+		cleanup();
+		delete[] mStringList;
+	}
+	void cleanup()
+	{
+		// remove strings
+		for (S32 i = 0; i<mTableSize; i++)
+		{
+			string_set_t& stringset = mStringList[i];
+			for (string_set_t::iterator iter = stringset.begin(); iter != stringset.end(); iter++)
+			{
+				delete *iter;
+			}
+			stringset.clear();
+		}
+	}
+
+	LLStdStringHandle lookup(const std::string& s)
+	{
+		U32 hashval = makehash(s);
+		return lookup(hashval, s);
+	}
+	
+	LLStdStringHandle checkString(const std::string& s)
+	{
+		U32 hashval = makehash(s);
+		return lookup(hashval, s);
+	}
+
+	LLStdStringHandle insert(const std::string& s)
+	{
+		U32 hashval = makehash(s);
+		LLStdStringHandle result = lookup(hashval, s);
+		if (result == NULL)
+		{
+			result = new std::string(s);
+			mStringList[hashval].insert(result);
+		}
+		return result;
+	}
+	LLStdStringHandle addString(const std::string& s)
+	{
+		return insert(s);
+	}
+	
+private:
+	U32 makehash(const std::string& s)
+	{
+		S32 len = (S32)s.size();
+		const char* c = s.c_str();
+		U32 hashval = 0;
+		for (S32 i=0; i<len; i++)
+		{
+			hashval = ((hashval<<5) + hashval) + *c++;
+		}
+		return hashval & (mTableSize-1);
+	}
+	LLStdStringHandle lookup(U32 hashval, const std::string& s)
+	{
+		string_set_t& stringset = mStringList[hashval];
+		LLStdStringHandle handle = &s;
+		string_set_t::iterator iter = stringset.find(handle); // compares actual strings
+		if (iter != stringset.end())
+		{
+			return *iter;
+		}
+		else
+		{
+			return NULL;
+		}
+	}
+	
+private:
+	S32 mTableSize;
+	typedef std::set<LLStdStringHandle, compare_pointer_contents<std::string> > string_set_t;
+	string_set_t* mStringList; // [mTableSize]
+};
+
+
+#endif
-- 
cgit v1.2.3