summaryrefslogtreecommitdiff
path: root/indra/llcommon/lllocalidhashmap.h
diff options
context:
space:
mode:
Diffstat (limited to 'indra/llcommon/lllocalidhashmap.h')
-rw-r--r--indra/llcommon/lllocalidhashmap.h877
1 files changed, 877 insertions, 0 deletions
diff --git a/indra/llcommon/lllocalidhashmap.h b/indra/llcommon/lllocalidhashmap.h
new file mode 100644
index 0000000000..12f2b3f2d7
--- /dev/null
+++ b/indra/llcommon/lllocalidhashmap.h
@@ -0,0 +1,877 @@
+/**
+ * @file lllocalidhashmap.h
+ * @brief Map specialized for dealing with local ids
+ *
+ * Copyright (c) 2003-$CurrentYear$, Linden Research, Inc.
+ * $License$
+ */
+
+#ifndef LL_LLLOCALIDHASHMAP_H
+#define LL_LLLOCALIDHASHMAP_H
+
+#include "stdtypes.h"
+#include "llerror.h"
+
+const S32 MAX_ITERS = 4;
+// LocalID hash map
+
+//
+// LLLocalIDHashNode
+//
+
+template <class DATA, int SIZE>
+class LLLocalIDHashNode
+{
+public:
+ LLLocalIDHashNode();
+
+public:
+ S32 mCount;
+ U32 mKey[SIZE];
+ DATA mData[SIZE];
+ LLLocalIDHashNode<DATA, SIZE> *mNextNodep;
+};
+
+
+//
+// LLLocalIDHashNode implementation
+//
+template <class DATA, int SIZE>
+LLLocalIDHashNode<DATA, SIZE>::LLLocalIDHashNode()
+{
+ mCount = 0;
+ mNextNodep = NULL;
+}
+
+//
+// LLLocalIDHashMapIter
+//
+template <class DATA_TYPE, int SIZE>
+class LLLocalIDHashMap;
+
+template <class DATA_TYPE, int SIZE>
+class LLLocalIDHashMapIter
+{
+public:
+ LLLocalIDHashMapIter(LLLocalIDHashMap<DATA_TYPE, SIZE> *hash_mapp);
+ ~LLLocalIDHashMapIter();
+
+ void setMap(LLLocalIDHashMap<DATA_TYPE, SIZE> *hash_mapp);
+ inline void first();
+ inline void next();
+ inline DATA_TYPE& current(); // *NOTE: Deprecate? Phoenix 2005-04-15
+ inline BOOL done() const;
+ inline S32 currentBin() const;
+ inline void setBin(S32 bin);
+
+ DATA_TYPE& operator*() const
+ {
+ return mCurHashNodep->mData[mCurHashNodeKey];
+ }
+ DATA_TYPE* operator->() const
+ {
+ return &(operator*());
+ }
+
+ LLLocalIDHashMap<DATA_TYPE, SIZE> *mHashMapp;
+ LLLocalIDHashNode<DATA_TYPE, SIZE> *mCurHashNodep;
+
+ S32 mCurHashMapNodeNum;
+ S32 mCurHashNodeKey;
+
+ DATA_TYPE mNull;
+
+ S32 mIterID;
+};
+
+
+
+template <class DATA_TYPE, int SIZE>
+class LLLocalIDHashMap
+{
+public:
+ friend class LLLocalIDHashMapIter<DATA_TYPE, SIZE>;
+
+ LLLocalIDHashMap(); // DO NOT use this unless you explicitly setNull, or the data type constructs a "null"
+ // object by default
+ // basic constructor including sorter
+ LLLocalIDHashMap(const DATA_TYPE &null_data);
+ // Hack, this should really be a const ref, but I'm not doing it that way because the sim
+ // usually uses pointers.
+ ~LLLocalIDHashMap();
+
+ inline DATA_TYPE &get(const U32 local_id);
+ inline BOOL check(const U32 local_id) const;
+ inline DATA_TYPE &set(const U32 local_id, const DATA_TYPE data);
+ inline BOOL remove(const U32 local_id);
+ void removeAll();
+
+ void setNull(const DATA_TYPE data) { mNull = data; }
+
+ inline S32 getLength() const; // Warning, NOT O(1!)
+
+ void dumpIter();
+ void dumpBin(U32 bin);
+
+protected:
+ // Only used by the iterator.
+ void addIter(LLLocalIDHashMapIter<DATA_TYPE, SIZE> *iter);
+ void removeIter(LLLocalIDHashMapIter<DATA_TYPE, SIZE> *iter);
+
+ // Remove the item and shift all items afterward down the list,
+ // fixing up iterators as we go.
+ BOOL removeWithShift(const U32 local_id);
+
+protected:
+ LLLocalIDHashNode<DATA_TYPE, SIZE> mNodes[256];
+
+ S32 mIterCount;
+ LLLocalIDHashMapIter<DATA_TYPE, SIZE> *mIters[MAX_ITERS];
+
+ DATA_TYPE mNull;
+};
+
+
+//
+// LLLocalIDHashMap implementation
+//
+
+template <class DATA_TYPE, int SIZE>
+LLLocalIDHashMap<DATA_TYPE, SIZE>::LLLocalIDHashMap()
+: mIterCount(0),
+ mNull()
+{
+ S32 i;
+ for (i = 0; i < MAX_ITERS; i++)
+ {
+ mIters[i] = NULL;
+ }
+}
+
+template <class DATA_TYPE, int SIZE>
+LLLocalIDHashMap<DATA_TYPE, SIZE>::LLLocalIDHashMap(const DATA_TYPE &null_data)
+: mIterCount(0),
+ mNull(null_data)
+{
+ S32 i;
+ for (i = 0; i < MAX_ITERS; i++)
+ {
+ mIters[i] = NULL;
+ }
+}
+
+template <class DATA_TYPE, int SIZE>
+LLLocalIDHashMap<DATA_TYPE, SIZE>::~LLLocalIDHashMap()
+{
+ S32 i;
+ for (i = 0; i < MAX_ITERS; i++)
+ {
+ if (mIters[i])
+ {
+ mIters[i]->mHashMapp = NULL;
+ mIterCount--;
+ }
+ }
+ removeAll();
+}
+
+template <class DATA_TYPE, int SIZE>
+void LLLocalIDHashMap<DATA_TYPE, SIZE>::removeAll()
+{
+ S32 bin;
+ for (bin = 0; bin < 256; bin++)
+ {
+ LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[bin];
+
+ BOOL first = TRUE;
+ do // First node guaranteed to be there
+ {
+ S32 i;
+ const S32 count = nodep->mCount;
+
+ // Iterate through all members of this node
+ for (i = 0; i < count; i++)
+ {
+ nodep->mData[i] = mNull;
+ }
+
+ nodep->mCount = 0;
+ // Done with all objects in this node, go to the next.
+
+ LLLocalIDHashNode<DATA_TYPE, SIZE>* curp = nodep;
+ nodep = nodep->mNextNodep;
+
+ // Delete the node if it's not the first node
+ if (first)
+ {
+ first = FALSE;
+ curp->mNextNodep = NULL;
+ }
+ else
+ {
+ delete curp;
+ }
+ } while (nodep);
+ }
+}
+
+template <class DATA_TYPE, int SIZE>
+void LLLocalIDHashMap<DATA_TYPE, SIZE>::dumpIter()
+{
+ std::cout << "Hash map with " << mIterCount << " iterators" << std::endl;
+
+ std::cout << "Hash Map Iterators:" << std::endl;
+ S32 i;
+ for (i = 0; i < MAX_ITERS; i++)
+ {
+ if (mIters[i])
+ {
+ llinfos << i << " " << mIters[i]->mCurHashNodep << " " << mIters[i]->mCurHashNodeKey << llendl;
+ }
+ else
+ {
+ llinfos << i << "null" << llendl;
+ }
+ }
+}
+
+template <class DATA_TYPE, int SIZE>
+void LLLocalIDHashMap<DATA_TYPE, SIZE>::dumpBin(U32 bin)
+{
+ std::cout << "Dump bin " << bin << std::endl;
+
+ LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[bin];
+ S32 node = 0;
+ do // First node guaranteed to be there.
+ {
+ std::cout << "Bin " << bin
+ << " node " << node
+ << " count " << nodep->mCount
+ << " contains " << std::flush;
+
+ S32 i;
+ for (i = 0; i < nodep->mCount; i++)
+ {
+ std::cout << nodep->mData[i] << " " << std::flush;
+ }
+
+ std::cout << std::endl;
+
+ nodep = nodep->mNextNodep;
+ node++;
+ } while (nodep);
+}
+
+template <class DATA_TYPE, int SIZE>
+inline S32 LLLocalIDHashMap<DATA_TYPE, SIZE>::getLength() const
+{
+ S32 count = 0;
+ S32 bin;
+ for (bin = 0; bin < 256; bin++)
+ {
+ const LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[bin];
+ while (nodep)
+ {
+ count += nodep->mCount;
+ nodep = nodep->mNextNodep;
+ }
+ }
+ return count;
+}
+
+template <class DATA_TYPE, int SIZE>
+inline DATA_TYPE &LLLocalIDHashMap<DATA_TYPE, SIZE>::get(const U32 local_id)
+{
+ LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[local_id & 0xff];
+
+ do // First node guaranteed to be there
+ {
+ S32 i;
+ const S32 count = nodep->mCount;
+
+ // Iterate through all members of this node
+ for (i = 0; i < count; i++)
+ {
+ if (nodep->mKey[i] == local_id)
+ {
+ // We found it.
+ return nodep->mData[i];
+ }
+ }
+
+ // Done with all objects in this node, go to the next.
+ nodep = nodep->mNextNodep;
+ } while (nodep);
+
+ return mNull;
+}
+
+
+template <class DATA_TYPE, int SIZE>
+inline BOOL LLLocalIDHashMap<DATA_TYPE, SIZE>::check(const U32 local_id) const
+{
+ const LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[local_id & 0xff];
+
+ do // First node guaranteed to be there
+ {
+ S32 i;
+ const S32 count = nodep->mCount;
+
+ // Iterate through all members of this node
+ for (i = 0; i < count; i++)
+ {
+ if (nodep->mKey[i] == local_id)
+ {
+ // We found it.
+ return TRUE;
+ }
+ }
+
+ // Done with all objects in this node, go to the next.
+ nodep = nodep->mNextNodep;
+ } while (nodep);
+
+ // Didn't find anything
+ return FALSE;
+}
+
+
+template <class DATA_TYPE, int SIZE>
+inline DATA_TYPE &LLLocalIDHashMap<DATA_TYPE, SIZE>::set(const U32 local_id, const DATA_TYPE data)
+{
+ // Set is just like a normal find, except that if we find a match
+ // we replace it with the input value.
+ // If we don't find a match, we append to the end of the list.
+
+ LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[local_id & 0xff];
+
+ while (1)
+ {
+ const S32 count = nodep->mCount;
+
+ S32 i;
+ for (i = 0; i < count; i++)
+ {
+ if (nodep->mKey[i] == local_id)
+ {
+ // We found a match for this key, replace the data with
+ // the incoming data.
+ nodep->mData[i] = data;
+ return nodep->mData[i];
+ }
+ }
+ if (!nodep->mNextNodep)
+ {
+ // We've iterated through all of the keys without finding a match
+ if (i < SIZE)
+ {
+ // There's still some space on this node, append
+ // the key and data to it.
+ nodep->mKey[i] = local_id;
+ nodep->mData[i] = data;
+ nodep->mCount++;
+
+ return nodep->mData[i];
+ }
+ else
+ {
+ // This node is full, append a new node to the end.
+ nodep->mNextNodep = new LLLocalIDHashNode<DATA_TYPE, SIZE>;
+ nodep->mNextNodep->mKey[0] = local_id;
+ nodep->mNextNodep->mData[0] = data;
+ nodep->mNextNodep->mCount = 1;
+
+ return nodep->mNextNodep->mData[0];
+ }
+ }
+
+ // No match on this node, go to the next
+ nodep = nodep->mNextNodep;
+ }
+}
+
+
+template <class DATA_TYPE, int SIZE>
+inline BOOL LLLocalIDHashMap<DATA_TYPE, SIZE>::remove(const U32 local_id)
+{
+ // Remove is the trickiest operation.
+ // What we want to do is swap the last element of the last
+ // node if we find the one that we want to remove, but we have
+ // to deal with deleting the node from the tail if it's empty, but
+ // NOT if it's the only node left.
+
+ const S32 node_index = local_id & 0xff;
+
+ LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[node_index];
+
+ // A modification of the standard search algorithm.
+ do // First node guaranteed to be there
+ {
+ const S32 count = nodep->mCount;
+
+ S32 i;
+ for (i = 0; i < count; i++)
+ {
+ if (nodep->mKey[i] == local_id)
+ {
+ // If we're removing the item currently pointed to by one
+ // or more iterators, we can just swap in the last item
+ // and back the iterator(s) up by one.
+ // Otherwise, we need to do a slow and safe shift of all
+ // items back to one position to fill the hole and fix up
+ // all iterators we find.
+ BOOL need_shift = FALSE;
+ S32 cur_iter;
+ if (mIterCount)
+ {
+ for (cur_iter = 0; cur_iter < MAX_ITERS; cur_iter++)
+ {
+ if (mIters[cur_iter])
+ {
+ // We only care if the hash map node is on the one
+ // that we're working on. If it's before, we've already
+ // traversed it, if it's after, changing the order doesn't
+ // matter.
+ if (mIters[cur_iter]->mCurHashMapNodeNum == node_index)
+ {
+ if ((mIters[cur_iter]->mCurHashNodep == nodep)
+ && (mIters[cur_iter]->mCurHashNodeKey == i))
+ {
+ // it's on the one we're deleting, we'll
+ // fix the iterator quickly below.
+ }
+ else
+ {
+ // We're trying to remove an item on this
+ // iterator's chain that this
+ // iterator doesn't point to! We need to do
+ // the slow remove-and-shift-down case.
+ need_shift = TRUE;
+ }
+ }
+ }
+ }
+ }
+
+ // Removing an item that isn't pointed to by all iterators
+ if (need_shift)
+ {
+ return removeWithShift(local_id);
+ }
+
+ // Fix the iterators that point to this node/i pair, the
+ // one we're deleting
+ for (cur_iter = 0; cur_iter < MAX_ITERS; cur_iter++)
+ {
+ if (mIters[cur_iter])
+ {
+ // We only care if the hash map node is on the one
+ // that we're working on. If it's before, we've already
+ // traversed it, if it's after, changing the order doesn't
+ // matter.
+ if (mIters[cur_iter]->mCurHashMapNodeNum == node_index)
+ {
+ if ((mIters[cur_iter]->mCurHashNodep == nodep)
+ && (mIters[cur_iter]->mCurHashNodeKey == i))
+ {
+ // We can handle the case where we're deleting
+ // the element we're on trivially (sort of).
+ if (nodep->mCount > 1)
+ {
+ // If we're not going to delete this node,
+ // it's OK.
+ mIters[cur_iter]->mCurHashNodeKey--;
+ }
+ else
+ {
+ // We're going to delete this node, because this
+ // is the last element on it.
+
+ // Find the next node, and then back up one.
+ mIters[cur_iter]->next();
+ mIters[cur_iter]->mCurHashNodeKey--;
+ }
+ }
+ }
+ }
+ }
+
+ // We found the node that we want to remove.
+ // Find the last (and next-to-last) node, and the index of the last
+ // element. We could conceviably start from the node we're on,
+ // but that makes it more complicated, this is easier.
+
+ LLLocalIDHashNode<DATA_TYPE, SIZE> *prevp = &mNodes[node_index];
+ LLLocalIDHashNode<DATA_TYPE, SIZE> *lastp = prevp;
+
+ // Find the last and next-to-last
+ while (lastp->mNextNodep)
+ {
+ prevp = lastp;
+ lastp = lastp->mNextNodep;
+ }
+
+ // First, swap in the last to the current location.
+ nodep->mKey[i] = lastp->mKey[lastp->mCount - 1];
+ nodep->mData[i] = lastp->mData[lastp->mCount - 1];
+
+ // Now, we delete the entry
+ lastp->mCount--;
+ lastp->mData[lastp->mCount] = mNull;
+
+ if (!lastp->mCount)
+ {
+ // We deleted the last element!
+ if (lastp != &mNodes[local_id & 0xff])
+ {
+ // Only blitz the node if it's not the head
+ // Set the previous node to point to NULL, then
+ // blitz the empty last node
+ prevp->mNextNodep = NULL;
+ delete lastp;
+ }
+ }
+
+ return TRUE;
+ }
+ }
+
+ // Iterate to the next node, we've scanned all the entries in this one.
+ nodep = nodep->mNextNodep;
+ } while (nodep);
+
+ return FALSE;
+}
+
+template <class DATA_TYPE, int SIZE>
+BOOL LLLocalIDHashMap<DATA_TYPE, SIZE>::removeWithShift(const U32 local_id)
+{
+ const S32 node_index = local_id & 0xFF;
+ LLLocalIDHashNode<DATA_TYPE, SIZE>* nodep = &mNodes[node_index];
+ LLLocalIDHashNode<DATA_TYPE, SIZE>* prevp = NULL;
+ BOOL found = FALSE;
+
+ do // First node guaranteed to be there
+ {
+ const S32 count = nodep->mCount;
+ S32 i;
+ for (i = 0; i < count; i++)
+ {
+ if (nodep->mKey[i] == local_id)
+ {
+ // Found the item. Start shifting items from later
+ // in the list over this item.
+ found = TRUE;
+ }
+
+ if (found)
+ {
+ // If there is an iterator on this node, we need to
+ // back it up.
+ S32 cur_iter;
+ for (cur_iter = 0; cur_iter <MAX_ITERS; cur_iter++)
+ {
+ LLLocalIDHashMapIter<DATA_TYPE, SIZE>* iter;
+ iter = mIters[cur_iter];
+ // If an iterator is on this node,i pair, then back it up.
+ if (iter
+ && iter->mCurHashMapNodeNum == node_index
+ && iter->mCurHashNodep == nodep
+ && iter->mCurHashNodeKey == i)
+ {
+ if (i > 0)
+ {
+ // Don't need to move iterator nodep, since
+ // we're in the same node.
+ iter->mCurHashNodeKey--;
+ }
+ else if (prevp)
+ {
+ // need to go the previous node, last item
+ iter->mCurHashNodep = prevp;
+ iter->mCurHashNodeKey = prevp->mCount - 1;
+ }
+ else
+ {
+ // we're on the first item in the list, but
+ // need to go back anyhow.
+
+ // BUG: If this deletion empties the list,
+ // iter->done() will be wrong until
+ // iter->next() is called.
+ iter->mCurHashNodeKey = -1;
+ }
+ }
+ }
+
+ // Copy data from the next position into this position.
+ if (i < count-1)
+ {
+ // we're not on the last item in the node,
+ // so we can copy within the node
+ nodep->mKey[i] = nodep->mKey[i+1];
+ nodep->mData[i] = nodep->mData[i+1];
+ }
+ else if (nodep->mNextNodep)
+ {
+ // we're on the last item in the node,
+ // but there's a next node we can copy from
+ nodep->mKey[i] = nodep->mNextNodep->mKey[0];
+ nodep->mData[i] = nodep->mNextNodep->mData[0];
+ }
+ else
+ {
+ // We're on the last position in the list.
+ // No one to copy from. Replace with nothing.
+ nodep->mKey[i] = 0;
+ nodep->mData[i] = mNull;
+ }
+ }
+ }
+
+ // Last node in chain, so delete the last node
+ if (found
+ && !nodep->mNextNodep)
+ {
+ // delete the last item off the last node
+ nodep->mCount--;
+
+ if (nodep->mCount == 0)
+ {
+ // We deleted the last element!
+ if (nodep != &mNodes[node_index])
+ {
+ // Always have a prevp if we're not the head.
+ llassert(prevp);
+
+ // Only blitz the node if it's not the head
+ // Set the previous node to point to NULL, then
+ // blitz the empty last node
+ prevp->mNextNodep = NULL;
+ delete nodep;
+ nodep = NULL;
+ }
+ }
+
+ // Deleted last item in chain, so we're done.
+ return found;
+ }
+
+ prevp = nodep;
+ nodep = nodep->mNextNodep;
+ } while (nodep);
+
+ return found;
+}
+
+template <class DATA_TYPE, int SIZE>
+void LLLocalIDHashMap<DATA_TYPE, SIZE>::removeIter(LLLocalIDHashMapIter<DATA_TYPE, SIZE> *iter)
+{
+ S32 i;
+ for (i = 0; i < MAX_ITERS; i++)
+ {
+ if (mIters[i] == iter)
+ {
+ mIters[i] = NULL;
+ mIterCount--;
+ return;
+ }
+ }
+ llerrs << "Iterator " << iter << " not found for removal in hash map!" << llendl;
+}
+
+template <class DATA_TYPE, int SIZE>
+void LLLocalIDHashMap<DATA_TYPE, SIZE>::addIter(LLLocalIDHashMapIter<DATA_TYPE, SIZE> *iter)
+{
+ S32 i;
+ for (i = 0; i < MAX_ITERS; i++)
+ {
+ if (mIters[i] == NULL)
+ {
+ mIters[i] = iter;
+ mIterCount++;
+ return;
+ }
+ }
+ llerrs << "More than " << MAX_ITERS << " iterating over a map simultaneously!" << llendl;
+}
+
+
+
+//
+// LLLocalIDHashMapIter Implementation
+//
+template <class DATA_TYPE, int SIZE>
+LLLocalIDHashMapIter<DATA_TYPE, SIZE>::LLLocalIDHashMapIter(LLLocalIDHashMap<DATA_TYPE, SIZE> *hash_mapp)
+{
+ mHashMapp = NULL;
+ setMap(hash_mapp);
+}
+
+template <class DATA_TYPE, int SIZE>
+LLLocalIDHashMapIter<DATA_TYPE, SIZE>::~LLLocalIDHashMapIter()
+{
+ if (mHashMapp)
+ {
+ mHashMapp->removeIter(this);
+ }
+}
+
+template <class DATA_TYPE, int SIZE>
+void LLLocalIDHashMapIter<DATA_TYPE, SIZE>::setMap(LLLocalIDHashMap<DATA_TYPE, SIZE> *hash_mapp)
+{
+ if (mHashMapp)
+ {
+ mHashMapp->removeIter(this);
+ }
+ mHashMapp = hash_mapp;
+ if (mHashMapp)
+ {
+ mHashMapp->addIter(this);
+ }
+
+ mCurHashNodep = NULL;
+ mCurHashMapNodeNum = -1;
+ mCurHashNodeKey = 0;
+}
+
+template <class DATA_TYPE, int SIZE>
+inline void LLLocalIDHashMapIter<DATA_TYPE, SIZE>::first()
+{
+ // Iterate through until we find the first non-empty node;
+ S32 i;
+ for (i = 0; i < 256; i++)
+ {
+ if (mHashMapp->mNodes[i].mCount)
+ {
+
+ mCurHashNodep = &mHashMapp->mNodes[i];
+ mCurHashMapNodeNum = i;
+ mCurHashNodeKey = 0;
+ //return mCurHashNodep->mData[0];
+ return;
+ }
+ }
+
+ // Completely empty!
+ mCurHashNodep = NULL;
+ //return mNull;
+ return;
+}
+
+template <class DATA_TYPE, int SIZE>
+inline BOOL LLLocalIDHashMapIter<DATA_TYPE, SIZE>::done() const
+{
+ return mCurHashNodep ? FALSE : TRUE;
+}
+
+template <class DATA_TYPE, int SIZE>
+inline S32 LLLocalIDHashMapIter<DATA_TYPE, SIZE>::currentBin() const
+{
+ if ( (mCurHashMapNodeNum > 255)
+ ||(mCurHashMapNodeNum < 0))
+ {
+ return 0;
+ }
+ else
+ {
+ return mCurHashMapNodeNum;
+ }
+}
+
+template <class DATA_TYPE, int SIZE>
+inline void LLLocalIDHashMapIter<DATA_TYPE, SIZE>::setBin(S32 bin)
+{
+ // Iterate through until we find the first non-empty node;
+ S32 i;
+ bin = llclamp(bin, 0, 255);
+ for (i = bin; i < 256; i++)
+ {
+ if (mHashMapp->mNodes[i].mCount)
+ {
+
+ mCurHashNodep = &mHashMapp->mNodes[i];
+ mCurHashMapNodeNum = i;
+ mCurHashNodeKey = 0;
+ return;
+ }
+ }
+ for (i = 0; i < bin; i++)
+ {
+ if (mHashMapp->mNodes[i].mCount)
+ {
+
+ mCurHashNodep = &mHashMapp->mNodes[i];
+ mCurHashMapNodeNum = i;
+ mCurHashNodeKey = 0;
+ return;
+ }
+ }
+ // Completely empty!
+ mCurHashNodep = NULL;
+}
+
+template <class DATA_TYPE, int SIZE>
+inline DATA_TYPE &LLLocalIDHashMapIter<DATA_TYPE, SIZE>::current()
+{
+ if (!mCurHashNodep)
+ {
+ return mNull;
+ }
+ return mCurHashNodep->mData[mCurHashNodeKey];
+}
+
+template <class DATA_TYPE, int SIZE>
+inline void LLLocalIDHashMapIter<DATA_TYPE, SIZE>::next()
+{
+ // No current entry, this iterator is done
+ if (!mCurHashNodep)
+ {
+ //return mNull;
+ return;
+ }
+
+ // Go to the next element
+ mCurHashNodeKey++;
+ if (mCurHashNodeKey < mCurHashNodep->mCount)
+ {
+ // We're not done with this node, return the current element
+ //return mCurHashNodep->mData[mCurHashNodeKey];
+ return;
+ }
+
+ // Done with this node, move to the next
+ mCurHashNodep = mCurHashNodep->mNextNodep;
+ if (mCurHashNodep)
+ {
+ // Return the first element
+ mCurHashNodeKey = 0;
+ //return mCurHashNodep->mData[0];
+ return;
+ }
+
+ // Find the next non-empty node (keyed on the first byte)
+ mCurHashMapNodeNum++;
+
+ S32 i;
+ for (i = mCurHashMapNodeNum; i < 256; i++)
+ {
+ if (mHashMapp->mNodes[i].mCount)
+ {
+ // We found one that wasn't empty
+ mCurHashNodep = &mHashMapp->mNodes[i];
+ mCurHashMapNodeNum = i;
+ mCurHashNodeKey = 0;
+ //return mCurHashNodep->mData[0];
+ return;
+ }
+ }
+
+ // OK, we're done, nothing else to iterate
+ mCurHashNodep = NULL;
+ mHashMapp->mIterCount--; // Decrement since we're safe to do removes now
+ //return mNull;
+ return;
+}
+
+#endif // LL_LLLOCALIDHASHMAP_H
generated by cgit v1.2.3 (git 2.25.1) at 2025-02-08 12:38:23 +0000