1 files changed, 156 insertions, 0 deletions

diff --git a/linden/indra/llcommon/llsimplehash.h b/linden/indra/llcommon/llsimplehash.h
new file mode 100644
index 0000000..259f140
--- /dev/null
+++ b/linden/indra/llcommon/llsimplehash.h
@@ -0,0 +1,156 @@
+/** 
+ * @file llsimplehash.h
+ *
+ * Copyright (c) 2003-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.
+ */
+
+#ifndef LL_LLSIMPLEHASH_H
+#define LL_LLSIMPLEHASH_H
+
+#include "llstl.h"
+
+template <typename HASH_KEY_TYPE>
+class LLSimpleHashEntry
+{
+protected:
+        HASH_KEY_TYPE mHashKey;
+        LLSimpleHashEntry<HASH_KEY_TYPE>* mNextEntry;
+public:
+        LLSimpleHashEntry(HASH_KEY_TYPE key) :
+                mHashKey(key),
+                mNextEntry(0)
+        {
+        }
+        virtual ~LLSimpleHashEntry()
+        {
+        }
+        HASH_KEY_TYPE getHashKey() const
+        {
+                return mHashKey;
+        }
+        LLSimpleHashEntry<HASH_KEY_TYPE>* getNextEntry() const
+        {
+                return mNextEntry;
+        }
+        void setNextEntry(LLSimpleHashEntry<HASH_KEY_TYPE>* next)
+        {
+                mNextEntry = next;
+        }
+};
+
+template <typename HASH_KEY_TYPE, int TABLE_SIZE>
+class LLSimpleHash
+{
+public:
+        LLSimpleHash()
+        {
+                llassert(TABLE_SIZE);
+                llassert((TABLE_SIZE ^ (TABLE_SIZE-1)) == (TABLE_SIZE | (TABLE_SIZE-1))); // power of 2
+                memset(mEntryTable, 0, sizeof(mEntryTable));
+        }
+        virtual ~LLSimpleHash()
+        {
+        }
+
+        virtual int getIndex(HASH_KEY_TYPE key)
+        {
+                return key & (TABLE_SIZE-1);
+        }
+        
+        bool insert(LLSimpleHashEntry<HASH_KEY_TYPE>* entry)
+        {
+                llassert(entry->getNextEntry() == 0);
+                int index = getIndex(entry->getHashKey());
+                entry->setNextEntry(mEntryTable[index]);
+                mEntryTable[index] = entry;
+                return true;
+        }
+        LLSimpleHashEntry<HASH_KEY_TYPE>* find(HASH_KEY_TYPE key)
+        {
+                int index = getIndex(key);
+                LLSimpleHashEntry<HASH_KEY_TYPE>* res = mEntryTable[index];
+                while(res && (res->getHashKey() != key))
+                {
+                        res = res->getNextEntry();
+                }
+                return res;
+        }
+        bool erase(LLSimpleHashEntry<HASH_KEY_TYPE>* entry)
+        {
+                return erase(entry->getHashKey());
+        }
+        bool erase(HASH_KEY_TYPE key)
+        {
+                int index = getIndex(key);
+                LLSimpleHashEntry<HASH_KEY_TYPE>* prev = 0;
+                LLSimpleHashEntry<HASH_KEY_TYPE>* res = mEntryTable[index];
+                while(res && (res->getHashKey() != key))
+                {
+                        prev = res;
+                        res = res->getNextEntry();
+                }
+                if (res)
+                {
+                        LLSimpleHashEntry<HASH_KEY_TYPE>* next = res->getNextEntry();
+                        if (prev)
+                        {
+                                prev->setNextEntry(next);
+                        }
+                        else
+                        {
+                                mEntryTable[index] = next;
+                        }
+                        return true;
+                }
+                else
+                {
+                        return false;
+                }
+        }
+        // Removes and returns an arbitrary ("first") element from the table
+        // Used for deleting the entire table.
+        LLSimpleHashEntry<HASH_KEY_TYPE>* pop_element()
+        {
+                for (int i=0; i<TABLE_SIZE; i++)
+                {
+                        LLSimpleHashEntry<HASH_KEY_TYPE>* entry = mEntryTable[i];
+                        if (entry)
+                        {
+                                mEntryTable[i] = entry->getNextEntry();
+                                return entry;
+                        }
+                }
+                return 0;
+        }
+        // debugging
+        LLSimpleHashEntry<HASH_KEY_TYPE>* get_element_at_index(S32 index) const
+        {
+                return mEntryTable[index];
+        }
+        
+        
+private:
+        LLSimpleHashEntry<HASH_KEY_TYPE>* mEntryTable[TABLE_SIZE];
+};
+
+#endif // LL_LLSIMPLEHASH_H