diff options
Diffstat (limited to 'indra/llcommon/llindexedqueue.h')
| -rwxr-xr-x | indra/llcommon/llindexedqueue.h | 155 |
1 files changed, 0 insertions, 155 deletions
diff --git a/indra/llcommon/llindexedqueue.h b/indra/llcommon/llindexedqueue.h deleted file mode 100755 index aa2675d87d..0000000000 --- a/indra/llcommon/llindexedqueue.h +++ /dev/null @@ -1,155 +0,0 @@ -/** - * @file llindexedqueue.h - * @brief An indexed FIFO queue, where only one element with each key - * can be in the queue. - * - * $LicenseInfo:firstyear=2003&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_LLINDEXEDQUEUE_H -#define LL_LLINDEXEDQUEUE_H - -// An indexed FIFO queue, where only one element with each key can be in the queue. -// This is ONLY used in the interest list, you'll probably want to review this code -// carefully if you want to use it elsewhere - Doug - -template <typename Type> -class LLIndexedQueue -{ -protected: - typedef std::deque<Type> type_deque; - type_deque mQueue; - std::set<Type> mKeySet; - -public: - LLIndexedQueue() {} - - // move_if_there is an O(n) operation - bool push_back(const Type &value, bool move_if_there = false) - { - if (mKeySet.find(value) != mKeySet.end()) - { - // Already on the queue - if (move_if_there) - { - // Remove the existing entry. - typename type_deque::iterator it; - for (it = mQueue.begin(); it != mQueue.end(); ++it) - { - if (*it == value) - { - break; - } - } - - // This HAS to succeed, otherwise there's a serious bug in the keyset implementation - // (although this isn't thread safe, at all) - - mQueue.erase(it); - } - else - { - // We're not moving it, leave it alone - return false; - } - } - else - { - // Doesn't exist, add it to the key set - mKeySet.insert(value); - } - - mQueue.push_back(value); - - // We succeeded in adding the new element. - return true; - } - - bool push_front(const Type &value, bool move_if_there = false) - { - if (mKeySet.find(value) != mKeySet.end()) - { - // Already on the queue - if (move_if_there) - { - // Remove the existing entry. - typename type_deque::iterator it; - for (it = mQueue.begin(); it != mQueue.end(); ++it) - { - if (*it == value) - { - break; - } - } - - // This HAS to succeed, otherwise there's a serious bug in the keyset implementation - // (although this isn't thread safe, at all) - - mQueue.erase(it); - } - else - { - // We're not moving it, leave it alone - return false; - } - } - else - { - // Doesn't exist, add it to the key set - mKeySet.insert(value); - } - - mQueue.push_front(value); - return true; - } - - void pop() - { - Type value = mQueue.front(); - mKeySet.erase(value); - mQueue.pop_front(); - } - - Type &front() - { - return mQueue.front(); - } - - S32 size() const - { - return mQueue.size(); - } - - bool empty() const - { - return mQueue.empty(); - } - - void clear() - { - // Clear out all elements on the queue - mQueue.clear(); - mKeySet.clear(); - } -}; - -#endif // LL_LLINDEXEDQUEUE_H |