From 05a3203d8274a0a0999faad128f629614b8d62c5 Mon Sep 17 00:00:00 2001 From: Richard Linden Date: Wed, 26 Sep 2012 17:04:57 -0700 Subject: SH-3275 WIP Run viewer metrics for object update messages fixed various issues related to unit tests and LLThreadLocalPtr initialization and teardown --- indra/test/test.cpp | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-) (limited to 'indra/test') diff --git a/indra/test/test.cpp b/indra/test/test.cpp index dc8580fe69..2b66c6aa26 100644 --- a/indra/test/test.cpp +++ b/indra/test/test.cpp @@ -512,15 +512,10 @@ int main(int argc, char **argv) ctype_workaround(); #endif - apr_initialize(); - apr_pool_t* pool = NULL; - if(APR_SUCCESS != apr_pool_create(&pool, NULL)) - { - std::cerr << "Unable to initialize pool" << std::endl; - return 1; - } + ll_init_apr(); + apr_getopt_t* os = NULL; - if(APR_SUCCESS != apr_getopt_init(&os, pool, argc, argv)) + if(APR_SUCCESS != apr_getopt_init(&os, gAPRPoolp, argc, argv)) { std::cerr << "apr_getopt_init() failed" << std::endl; return 1; @@ -602,7 +597,7 @@ int main(int argc, char **argv) if (LOGFAIL) { LLError::ELevel level = LLError::decodeLevel(LOGFAIL); - replayer.reset(new LLReplayLogReal(level, pool)); + replayer.reset(new LLReplayLogReal(level, gAPRPoolp)); } else { @@ -646,7 +641,7 @@ int main(int argc, char **argv) s.close(); } - apr_terminate(); + ll_cleanup_apr(); int retval = (success ? 0 : 1); return retval; -- cgit v1.3 From c136b432140f892a56d4996d5ed77e903ff0b32d Mon Sep 17 00:00:00 2001 From: Richard Linden Date: Thu, 15 Nov 2012 19:46:09 -0800 Subject: SH-3406 WIP convert fast timers to lltrace system eliminated min and max macros from windows.h got rest of viewer to compile against llfasttimer changes --- indra/cmake/00-Common.cmake | 1 + indra/llcommon/llapr.h | 1 + indra/llcommon/llfasttimer.cpp | 5 +++++ indra/llcommon/llfasttimer.h | 3 ++- indra/llcommon/llthread.h | 2 ++ indra/llcommon/lltrace.cpp | 1 - indra/llcommon/llwin32headers.h | 2 -- indra/llcommon/llwin32headerslean.h | 1 - indra/llmessage/lliopipe.h | 1 + indra/llmessage/lliosocket.h | 2 +- indra/newview/llappviewer.cpp | 2 +- indra/newview/llfasttimerview.cpp | 8 ++++---- indra/newview/llfloatermodelpreview.cpp | 2 -- indra/newview/llviewerstatsrecorder.h | 2 +- indra/newview/llxmlrpctransaction.cpp | 2 ++ indra/test/test.cpp | 4 +++- 16 files changed, 24 insertions(+), 15 deletions(-) (limited to 'indra/test') diff --git a/indra/cmake/00-Common.cmake b/indra/cmake/00-Common.cmake index 21cb87237d..180714c9c9 100644 --- a/indra/cmake/00-Common.cmake +++ b/indra/cmake/00-Common.cmake @@ -58,6 +58,7 @@ if (WINDOWS) add_definitions( /DLL_WINDOWS=1 + /DNOMINMAX /DDOM_DYNAMIC /DUNICODE /D_UNICODE diff --git a/indra/llcommon/llapr.h b/indra/llcommon/llapr.h index c77d96c1c9..d9fe257e86 100644 --- a/indra/llcommon/llapr.h +++ b/indra/llcommon/llapr.h @@ -40,6 +40,7 @@ #include "apr_getopt.h" #include "apr_signal.h" #include "apr_atomic.h" + #include "llstring.h" #include "llinstancetracker.h" diff --git a/indra/llcommon/llfasttimer.cpp b/indra/llcommon/llfasttimer.cpp index d007f76e5f..4ecca12832 100644 --- a/indra/llcommon/llfasttimer.cpp +++ b/indra/llcommon/llfasttimer.cpp @@ -121,6 +121,11 @@ void BlockTimer::pushLog(LLSD log) sLogQueue.push(log); } +void BlockTimer::setLogLock(LLMutex* lock) +{ + sLogLock = lock; +} + //static #if (LL_DARWIN || LL_LINUX || LL_SOLARIS) && !(defined(__i386__) || defined(__amd64__)) diff --git a/indra/llcommon/llfasttimer.h b/indra/llcommon/llfasttimer.h index 69a6773b12..af9b360e01 100644 --- a/indra/llcommon/llfasttimer.h +++ b/indra/llcommon/llfasttimer.h @@ -98,6 +98,7 @@ public: static BlockTimer& getRootTimer(); static void pushLog(LLSD sd); + static void setLogLock(LLMutex* mutex); friend class Time; @@ -329,6 +330,6 @@ LL_FORCE_INLINE Time::~Time() } -typedef LLTrace::Time LLFastTimer; +typedef LLTrace::Time LLFastTimer; #endif // LL_LLFASTTIMER_H diff --git a/indra/llcommon/llthread.h b/indra/llcommon/llthread.h index 82ab5f47d2..93c752754d 100644 --- a/indra/llcommon/llthread.h +++ b/indra/llcommon/llthread.h @@ -32,6 +32,8 @@ #include "apr_thread_cond.h" #include "llmutex.h" +LL_COMMON_API void assert_main_thread(); + class LL_COMMON_API LLThread { private: diff --git a/indra/llcommon/lltrace.cpp b/indra/llcommon/lltrace.cpp index 9346aa7a45..9bf9ae6c8e 100644 --- a/indra/llcommon/lltrace.cpp +++ b/indra/llcommon/lltrace.cpp @@ -59,7 +59,6 @@ LLThreadLocalPointer& get_thread_recorder() { static LLThreadLocalPointer s_thread_recorder; return s_thread_recorder; - } } diff --git a/indra/llcommon/llwin32headers.h b/indra/llcommon/llwin32headers.h index 80fd2e1768..9c89b6b280 100644 --- a/indra/llcommon/llwin32headers.h +++ b/indra/llcommon/llwin32headers.h @@ -28,11 +28,9 @@ #define LL_LLWINDOWS_H #ifdef LL_WINDOWS -#define NOMINMAX #undef WIN32_LEAN_AND_MEAN #include #include -#undef NOMINMAX #endif #endif diff --git a/indra/llcommon/llwin32headerslean.h b/indra/llcommon/llwin32headerslean.h index ab6e9c09e2..d3fb90d4b1 100644 --- a/indra/llcommon/llwin32headerslean.h +++ b/indra/llcommon/llwin32headerslean.h @@ -28,7 +28,6 @@ #define LL_LLWINDOWS_H #ifdef LL_WINDOWS -#define NOMINMAX #define WIN32_LEAN_AND_MEAN #include #include diff --git a/indra/llmessage/lliopipe.h b/indra/llmessage/lliopipe.h index cbd17b5a3d..9a0a427efd 100644 --- a/indra/llmessage/lliopipe.h +++ b/indra/llmessage/lliopipe.h @@ -31,6 +31,7 @@ #include #include +#include "llwin32headerslean.h" #include "apr_poll.h" #include "llsd.h" diff --git a/indra/llmessage/lliosocket.h b/indra/llmessage/lliosocket.h index 4e07963af8..ec998552d0 100644 --- a/indra/llmessage/lliosocket.h +++ b/indra/llmessage/lliosocket.h @@ -38,8 +38,8 @@ */ #include "lliopipe.h" -#include "apr_pools.h" #include "llwin32headerslean.h" +#include "apr_pools.h" #include "apr_network_io.h" #include "llchainio.h" diff --git a/indra/newview/llappviewer.cpp b/indra/newview/llappviewer.cpp index c6ed8d5071..9d4ed833b8 100644 --- a/indra/newview/llappviewer.cpp +++ b/indra/newview/llappviewer.cpp @@ -2033,7 +2033,7 @@ bool LLAppViewer::initThreads() if (LLTrace::BlockTimer::sLog || LLTrace::BlockTimer::sMetricLog) { - LLTrace::BlockTimer::sLogLock = new LLMutex(NULL); + LLTrace::BlockTimer::setLogLock(new LLMutex(NULL)); mFastTimerLogThread = new LLFastTimerLogThread(LLTrace::BlockTimer::sLogName); mFastTimerLogThread->start(); } diff --git a/indra/newview/llfasttimerview.cpp b/indra/newview/llfasttimerview.cpp index d0bb75225c..7a5c9dba46 100644 --- a/indra/newview/llfasttimerview.cpp +++ b/indra/newview/llfasttimerview.cpp @@ -92,7 +92,7 @@ LLFastTimerView::LLFastTimerView(const LLSD& key) mScrollIndex = 0; mHoverID = NULL; mHoverBarIndex = -1; - FTV_NUM_TIMERS = LLTrace::BlockTimer::instanceCount(); + FTV_NUM_TIMERS = LLInstanceTracker::instanceCount(); mPrintStats = -1; } @@ -235,7 +235,7 @@ BOOL LLFastTimerView::handleHover(S32 x, S32 y, MASK mask) if(LLTrace::BlockTimer::sPauseHistory && mBarRect.pointInRect(x, y)) { - mHoverBarIndex = llmin(LLFastTimer::getCurFrameIndex() - 1, + mHoverBarIndex = llmin(LLTrace::BlockTimer::getCurFrameIndex() - 1, MAX_VISIBLE_HISTORY - ((y - mBarRect.mBottom) * (MAX_VISIBLE_HISTORY + 2) / mBarRect.getHeight())); if (mHoverBarIndex == 0) { @@ -292,7 +292,7 @@ BOOL LLFastTimerView::handleHover(S32 x, S32 y, MASK mask) static std::string get_tooltip(LLTrace::BlockTimer& timer, S32 history_index = -1) { - F64 ms_multiplier = 1000.0 / (F64)LLFastTimer::countsPerSecond(); + F64 ms_multiplier = 1000.0 / (F64)LLTrace::BlockTimer::countsPerSecond(); std::string tooltip; if (history_index < 0) @@ -364,7 +364,7 @@ void LLFastTimerView::draw() std::string tdesc; - F64 clock_freq = (F64)LLFastTimer::countsPerSecond(); + F64 clock_freq = (F64)LLTrace::BlockTimer::countsPerSecond(); F64 iclock_freq = 1000.0 / clock_freq; S32 margin = 10; diff --git a/indra/newview/llfloatermodelpreview.cpp b/indra/newview/llfloatermodelpreview.cpp index a071f338ba..a5e3cd404d 100755 --- a/indra/newview/llfloatermodelpreview.cpp +++ b/indra/newview/llfloatermodelpreview.cpp @@ -113,8 +113,6 @@ #include "llviewernetwork.h" #include "llviewershadermgr.h" #include "glod/glod.h" -#include - const S32 SLM_SUPPORTED_VERSION = 3; diff --git a/indra/newview/llviewerstatsrecorder.h b/indra/newview/llviewerstatsrecorder.h index ce6dd63ec5..d1744f4910 100644 --- a/indra/newview/llviewerstatsrecorder.h +++ b/indra/newview/llviewerstatsrecorder.h @@ -32,7 +32,7 @@ // for analysis. // This is normally 0. Set to 1 to enable viewer stats recording -#define LL_RECORD_VIEWER_STATS 1 +#define LL_RECORD_VIEWER_STATS 0 #include "llframetimer.h" diff --git a/indra/newview/llxmlrpctransaction.cpp b/indra/newview/llxmlrpctransaction.cpp index 0da70d398b..583196fb7a 100644 --- a/indra/newview/llxmlrpctransaction.cpp +++ b/indra/newview/llxmlrpctransaction.cpp @@ -25,6 +25,8 @@ */ #include "llviewerprecompiledheaders.h" +// include this to get winsock2 because openssl attempts to include winsock1 +#include "llwin32headerslean.h" #include #include #include "llsecapi.h" diff --git a/indra/test/test.cpp b/indra/test/test.cpp index 2b66c6aa26..8bd302ce7a 100644 --- a/indra/test/test.cpp +++ b/indra/test/test.cpp @@ -40,6 +40,7 @@ #include "tests/wrapllerrs.h" // RecorderProxy #include "stringize.h" #include "namedtempfile.h" +#include "lltrace.h" #include "apr_pools.h" #include "apr_getopt.h" @@ -513,7 +514,8 @@ int main(int argc, char **argv) #endif ll_init_apr(); - + LLTrace::init(); + apr_getopt_t* os = NULL; if(APR_SUCCESS != apr_getopt_init(&os, gAPRPoolp, argc, argv)) { -- cgit v1.3 From 68413515029f50713c70e4adec3ce6fd1022d59f Mon Sep 17 00:00:00 2001 From: Richard Linden Date: Sun, 6 Jan 2013 21:37:31 -0800 Subject: SH-3468 WIP add memory tracking base class fix for unit test failures...cleanup apr without destroying pools, allowing LLProxy to clean itself up as a singleton (and avoiding spurious dependencies associated with manually destorying singletons that rely on apr pools) --- indra/llcommon/llapr.cpp | 4 ++-- indra/llcommon/llapr.h | 2 +- indra/llcommon/lltracethreadrecorder.cpp | 2 +- indra/llimage/tests/llimageworker_test.cpp | 3 +++ indra/llkdu/tests/llimagej2ckdu_test.cpp | 4 +++- indra/llmessage/llproxy.cpp | 3 +-- indra/test/test.cpp | 2 +- 7 files changed, 12 insertions(+), 8 deletions(-) (limited to 'indra/test') diff --git a/indra/llcommon/llapr.cpp b/indra/llcommon/llapr.cpp index d911f258b6..8a87911315 100644 --- a/indra/llcommon/llapr.cpp +++ b/indra/llcommon/llapr.cpp @@ -60,7 +60,7 @@ void ll_init_apr() } -void ll_cleanup_apr() +void ll_cleanup_apr(bool destroy_pools) { LL_INFOS("APR") << "Cleaning up APR" << LL_ENDL; @@ -83,7 +83,7 @@ void ll_cleanup_apr() LLThreadLocalPointerBase::destroyAllThreadLocalStorage(); - if (gAPRPoolp) + if (gAPRPoolp && destroy_pools) { apr_pool_destroy(gAPRPoolp); gAPRPoolp = NULL; diff --git a/indra/llcommon/llapr.h b/indra/llcommon/llapr.h index b3c9bfd58c..424ddc6505 100644 --- a/indra/llcommon/llapr.h +++ b/indra/llcommon/llapr.h @@ -70,7 +70,7 @@ void LL_COMMON_API ll_init_apr(); /** * @brief Cleanup those common apr constructs. */ -void LL_COMMON_API ll_cleanup_apr(); +void LL_COMMON_API ll_cleanup_apr(bool destroy_pools = true); // //LL apr_pool diff --git a/indra/llcommon/lltracethreadrecorder.cpp b/indra/llcommon/lltracethreadrecorder.cpp index 9fb789c62d..7b493a651e 100644 --- a/indra/llcommon/lltracethreadrecorder.cpp +++ b/indra/llcommon/lltracethreadrecorder.cpp @@ -127,7 +127,7 @@ std::list::iterator ThreadRecorder::update( Rec if (it == end_it) { - llerrs << "Recording not active on this thread" << llendl; + llwarns << "Recording not active on this thread" << llendl; } return it; diff --git a/indra/llimage/tests/llimageworker_test.cpp b/indra/llimage/tests/llimageworker_test.cpp index 29497257ac..4118896768 100644 --- a/indra/llimage/tests/llimageworker_test.cpp +++ b/indra/llimage/tests/llimageworker_test.cpp @@ -44,6 +44,9 @@ // * Do not make any assumption as to how those classes or methods work (i.e. don't copy/paste code) // * A simulator for a class can be implemented here. Please comment and document thoroughly. +LLTrace::MemStat LLImageBase::sMemStat("LLImage"); + + LLImageBase::LLImageBase() : mData(NULL), mDataSize(0), diff --git a/indra/llkdu/tests/llimagej2ckdu_test.cpp b/indra/llkdu/tests/llimagej2ckdu_test.cpp index 62c245f125..c28f121eb8 100755 --- a/indra/llkdu/tests/llimagej2ckdu_test.cpp +++ b/indra/llkdu/tests/llimagej2ckdu_test.cpp @@ -43,7 +43,9 @@ // End Stubbing // ------------------------------------------------------------------------------------------- -// Stubb the LL Image Classes +// Stub the LL Image Classes +LLTrace::MemStat LLImageBase::sMemStat("LLImage"); + LLImageRaw::LLImageRaw() { } LLImageRaw::~LLImageRaw() { } U8* LLImageRaw::allocateData(S32 ) { return NULL; } diff --git a/indra/llmessage/llproxy.cpp b/indra/llmessage/llproxy.cpp index 9988fcd9c0..aa474fabd2 100644 --- a/indra/llmessage/llproxy.cpp +++ b/indra/llmessage/llproxy.cpp @@ -57,8 +57,7 @@ LLProxy::LLProxy(): mAuthMethodSelected(METHOD_NOAUTH), mSocksUsername(), mSocksPassword() -{ -} +{} LLProxy::~LLProxy() { diff --git a/indra/test/test.cpp b/indra/test/test.cpp index 8bd302ce7a..d75040393c 100644 --- a/indra/test/test.cpp +++ b/indra/test/test.cpp @@ -643,7 +643,7 @@ int main(int argc, char **argv) s.close(); } - ll_cleanup_apr(); + ll_cleanup_apr(false); int retval = (success ? 0 : 1); return retval; -- cgit v1.3 From 3c341a11ab7b8f3fd18afcf3f50af6dfafa632c2 Mon Sep 17 00:00:00 2001 From: Richard Linden Date: Tue, 8 Jan 2013 00:25:07 -0800 Subject: SH-3468 WIP add memory tracking base class more fixes for unit test crashes added llcommon initialization/teardown for unit tests that indirectly trigger lltrace changed access of atomic refcount to use preincrement/decrement operators to reflect desired semantics always call apr_initialize in LLCommon::initClass, even if already initialized...apr does internal reference counting to keep things straight --- indra/llcommon/llapr.cpp | 19 +++++++++++++++---- indra/llcommon/llapr.h | 5 ++++- indra/llcommon/llmutex.cpp | 11 +++++++---- indra/llcorehttp/_refcounted.h | 4 ++-- indra/llmessage/llproxy.cpp | 7 +++++-- indra/test/io.cpp | 11 ++++++++++- indra/test/llhttpdate_tut.cpp | 9 +++++++++ indra/test/lliohttpserver_tut.cpp | 7 +++++++ indra/test/test.cpp | 2 +- 9 files changed, 60 insertions(+), 15 deletions(-) (limited to 'indra/test') diff --git a/indra/llcommon/llapr.cpp b/indra/llcommon/llapr.cpp index 8a87911315..0556fadb26 100644 --- a/indra/llcommon/llapr.cpp +++ b/indra/llcommon/llapr.cpp @@ -38,12 +38,15 @@ apr_thread_mutex_t *gCallStacksLogMutexp = NULL; const S32 FULL_VOLATILE_APR_POOL = 1024 ; //number of references to LLVolatileAPRPool +bool gAPRInitialized = false; + void ll_init_apr() { + // Initialize APR and create the global pool + apr_initialize(); + if (!gAPRPoolp) { - // Initialize APR and create the global pool - apr_initialize(); apr_pool_create(&gAPRPoolp, NULL); // Initialize the logging mutex @@ -57,11 +60,19 @@ void ll_init_apr() } LLThreadLocalPointerBase::initAllThreadLocalStorage(); + gAPRInitialized = true; } -void ll_cleanup_apr(bool destroy_pools) +bool ll_apr_is_initialized() +{ + return gAPRInitialized; +} + +void ll_cleanup_apr() { + gAPRInitialized = false; + LL_INFOS("APR") << "Cleaning up APR" << LL_ENDL; if (gLogMutexp) @@ -83,7 +94,7 @@ void ll_cleanup_apr(bool destroy_pools) LLThreadLocalPointerBase::destroyAllThreadLocalStorage(); - if (gAPRPoolp && destroy_pools) + if (gAPRPoolp) { apr_pool_destroy(gAPRPoolp); gAPRPoolp = NULL; diff --git a/indra/llcommon/llapr.h b/indra/llcommon/llapr.h index 424ddc6505..3b65c0dc34 100644 --- a/indra/llcommon/llapr.h +++ b/indra/llcommon/llapr.h @@ -70,7 +70,10 @@ void LL_COMMON_API ll_init_apr(); /** * @brief Cleanup those common apr constructs. */ -void LL_COMMON_API ll_cleanup_apr(bool destroy_pools = true); +void LL_COMMON_API ll_cleanup_apr(); + +bool LL_COMMON_API ll_apr_is_initialized(); + // //LL apr_pool diff --git a/indra/llcommon/llmutex.cpp b/indra/llcommon/llmutex.cpp index b685bb4d60..ad0287c6d5 100644 --- a/indra/llcommon/llmutex.cpp +++ b/indra/llcommon/llmutex.cpp @@ -56,12 +56,15 @@ LLMutex::~LLMutex() //bad assertion, the subclass LLSignal might be "locked", and that's OK //llassert_always(!isLocked()); // better not be locked! #endif - apr_thread_mutex_destroy(mAPRMutexp); - mAPRMutexp = NULL; - if (mIsLocalPool) + if (ll_apr_is_initialized()) { - apr_pool_destroy(mAPRPoolp); + apr_thread_mutex_destroy(mAPRMutexp); + if (mIsLocalPool) + { + apr_pool_destroy(mAPRPoolp); + } } + mAPRMutexp = NULL; } diff --git a/indra/llcorehttp/_refcounted.h b/indra/llcorehttp/_refcounted.h index 21a916b13b..402e725152 100644 --- a/indra/llcorehttp/_refcounted.h +++ b/indra/llcorehttp/_refcounted.h @@ -72,7 +72,7 @@ private: inline void RefCounted::addRef() const { - S32 count(mRefCount++); + S32 count(++mRefCount); llassert_always(count >= 0); } @@ -82,7 +82,7 @@ inline void RefCounted::release() const S32 count(mRefCount); llassert_always(count != NOT_REF_COUNTED); llassert_always(count > 0); - count = mRefCount--; + count = --mRefCount; // clean ourselves up if that was the last reference if (0 == count) diff --git a/indra/llmessage/llproxy.cpp b/indra/llmessage/llproxy.cpp index aa474fabd2..9b8d19cc3e 100644 --- a/indra/llmessage/llproxy.cpp +++ b/indra/llmessage/llproxy.cpp @@ -61,8 +61,11 @@ LLProxy::LLProxy(): LLProxy::~LLProxy() { - stopSOCKSProxy(); - disableHTTPProxy(); + if (ll_apr_is_initialized()) + { + stopSOCKSProxy(); + disableHTTPProxy(); + } } /** diff --git a/indra/test/io.cpp b/indra/test/io.cpp index ce747f667d..f2b4a5339c 100644 --- a/indra/test/io.cpp +++ b/indra/test/io.cpp @@ -44,6 +44,7 @@ #include "llsdrpcclient.h" #include "llsdrpcserver.h" #include "llsdserialize.h" +#include "llcommon.h" #include "lluuid.h" #include "llinstantmessage.h" @@ -830,6 +831,7 @@ namespace tut public: PumpAndChainTestData() { + LLCommon::initClass(); apr_pool_create(&mPool, NULL); mPump = new LLPumpIO(mPool); } @@ -839,6 +841,7 @@ namespace tut mChain.clear(); delete mPump; apr_pool_destroy(mPool); + LLCommon::cleanupClass(); } }; typedef test_group PumpAndChainTestGroup; @@ -909,6 +912,7 @@ namespace tut pipe_and_pump_fitness() { + LLCommon::initClass(); LLFrameTimer::updateFrameTime(); apr_pool_create(&mPool, NULL); mPump = new LLPumpIO(mPool); @@ -923,6 +927,7 @@ namespace tut mSocket.reset(); delete mPump; apr_pool_destroy(mPool); + LLCommon::cleanupClass(); } protected: @@ -1186,8 +1191,12 @@ namespace tut LLSimpleRPCResponse(LLSD* response) : mResponsePtr(response) { + LLCommon::initClass(); + } + ~LLSimpleRPCResponse() + { + LLCommon::cleanupClass(); } - ~LLSimpleRPCResponse() {} virtual bool response(LLPumpIO* pump) { *mResponsePtr = mReturnValue; diff --git a/indra/test/llhttpdate_tut.cpp b/indra/test/llhttpdate_tut.cpp index 46684bb9dc..d6f0ba5e66 100644 --- a/indra/test/llhttpdate_tut.cpp +++ b/indra/test/llhttpdate_tut.cpp @@ -29,6 +29,7 @@ #include "lltut.h" #include "lldate.h" +#include "llcommon.h" #include "llframetimer.h" #include @@ -38,6 +39,14 @@ namespace tut { struct httpdate_data { + httpdate_data() + { + LLCommon::initClass(); + } + ~httpdate_data() + { + LLCommon::cleanupClass(); + } LLDate some_date; }; typedef test_group httpdate_test; diff --git a/indra/test/lliohttpserver_tut.cpp b/indra/test/lliohttpserver_tut.cpp index 2fdc455f45..e7af09f80b 100644 --- a/indra/test/lliohttpserver_tut.cpp +++ b/indra/test/lliohttpserver_tut.cpp @@ -31,6 +31,7 @@ #include "lliohttpserver.h" #include "llsdhttpserver.h" #include "llsdserialize.h" +#include "llcommon.h" #include "llpipeutil.h" @@ -76,11 +77,17 @@ namespace tut HTTPServiceTestData() : mResponse(NULL) { + LLCommon::initClass(); LLHTTPStandardServices::useServices(); LLHTTPRegistrar::buildAllServices(mRoot); mRoot.addNode("/delayed/echo", new DelayedEcho(this)); mRoot.addNode("/wire/hello", new LLHTTPNodeForPipe); } + + ~HTTPServiceTestData() + { + LLCommon::cleanupClass(); + } LLHTTPNode mRoot; LLHTTPNode::ResponsePtr mResponse; diff --git a/indra/test/test.cpp b/indra/test/test.cpp index d75040393c..8bd302ce7a 100644 --- a/indra/test/test.cpp +++ b/indra/test/test.cpp @@ -643,7 +643,7 @@ int main(int argc, char **argv) s.close(); } - ll_cleanup_apr(false); + ll_cleanup_apr(); int retval = (success ? 0 : 1); return retval; -- cgit v1.3 From 0ba9a00c3116b69745f2d5070ce772d5d4965dbf Mon Sep 17 00:00:00 2001 From: Richard Linden Date: Tue, 8 Jan 2013 23:50:27 -0800 Subject: SH-3468 WIP add memory tracking base class cleaned up hacks used to get unit tests working LLTrace::init now supports recursive initialization/cleanup put NOMINMAX back in win32 header wrappers --- indra/llcommon/lltrace.cpp | 17 +++++++++++------ indra/llcommon/llwin32headers.h | 4 ++++ indra/llcommon/llwin32headerslean.h | 4 ++++ indra/test/io.cpp | 6 ------ indra/test/llhttpdate_tut.cpp | 2 -- indra/test/lliohttpserver_tut.cpp | 2 -- indra/test/test.cpp | 2 +- indra/test_apps/llplugintest/llmediaplugintest.cpp | 1 - 8 files changed, 20 insertions(+), 18 deletions(-) (limited to 'indra/test') diff --git a/indra/llcommon/lltrace.cpp b/indra/llcommon/lltrace.cpp index 9cadd70dd8..463048008f 100644 --- a/indra/llcommon/lltrace.cpp +++ b/indra/llcommon/lltrace.cpp @@ -30,7 +30,7 @@ #include "lltracethreadrecorder.h" #include "llfasttimer.h" -static bool sInitialized; +static S32 sInitializationCount = 0; namespace LLTrace { @@ -39,19 +39,24 @@ static MasterThreadRecorder* gMasterThreadRecorder = NULL; void init() { - gMasterThreadRecorder = new MasterThreadRecorder(); - sInitialized = true; + if (sInitializationCount++ == 0) + { + gMasterThreadRecorder = new MasterThreadRecorder(); + } } bool isInitialized() { - return sInitialized; + return sInitializationCount > 0; } void cleanup() { - delete gMasterThreadRecorder; - gMasterThreadRecorder = NULL; + if (--sInitializationCount == 0) + { + delete gMasterThreadRecorder; + gMasterThreadRecorder = NULL; + } } MasterThreadRecorder& getMasterThreadRecorder() diff --git a/indra/llcommon/llwin32headers.h b/indra/llcommon/llwin32headers.h index 9c89b6b280..8534ed6298 100644 --- a/indra/llcommon/llwin32headers.h +++ b/indra/llcommon/llwin32headers.h @@ -28,9 +28,13 @@ #define LL_LLWINDOWS_H #ifdef LL_WINDOWS +#ifndef NOMINMAX +#define NOMINMAX +#endif #undef WIN32_LEAN_AND_MEAN #include #include +#undef NOMINMAX #endif #endif diff --git a/indra/llcommon/llwin32headerslean.h b/indra/llcommon/llwin32headerslean.h index d3fb90d4b1..f7e71301a8 100644 --- a/indra/llcommon/llwin32headerslean.h +++ b/indra/llcommon/llwin32headerslean.h @@ -28,9 +28,13 @@ #define LL_LLWINDOWS_H #ifdef LL_WINDOWS +#ifndef NOMINMAX +#define NOMINMAX +#endif #define WIN32_LEAN_AND_MEAN #include #include +#undef NOMINMAX #endif #endif diff --git a/indra/test/io.cpp b/indra/test/io.cpp index f2b4a5339c..b3eabc2e8a 100644 --- a/indra/test/io.cpp +++ b/indra/test/io.cpp @@ -831,7 +831,6 @@ namespace tut public: PumpAndChainTestData() { - LLCommon::initClass(); apr_pool_create(&mPool, NULL); mPump = new LLPumpIO(mPool); } @@ -841,7 +840,6 @@ namespace tut mChain.clear(); delete mPump; apr_pool_destroy(mPool); - LLCommon::cleanupClass(); } }; typedef test_group PumpAndChainTestGroup; @@ -912,7 +910,6 @@ namespace tut pipe_and_pump_fitness() { - LLCommon::initClass(); LLFrameTimer::updateFrameTime(); apr_pool_create(&mPool, NULL); mPump = new LLPumpIO(mPool); @@ -927,7 +924,6 @@ namespace tut mSocket.reset(); delete mPump; apr_pool_destroy(mPool); - LLCommon::cleanupClass(); } protected: @@ -1191,11 +1187,9 @@ namespace tut LLSimpleRPCResponse(LLSD* response) : mResponsePtr(response) { - LLCommon::initClass(); } ~LLSimpleRPCResponse() { - LLCommon::cleanupClass(); } virtual bool response(LLPumpIO* pump) { diff --git a/indra/test/llhttpdate_tut.cpp b/indra/test/llhttpdate_tut.cpp index d6f0ba5e66..ecf734ee90 100644 --- a/indra/test/llhttpdate_tut.cpp +++ b/indra/test/llhttpdate_tut.cpp @@ -41,11 +41,9 @@ namespace tut { httpdate_data() { - LLCommon::initClass(); } ~httpdate_data() { - LLCommon::cleanupClass(); } LLDate some_date; }; diff --git a/indra/test/lliohttpserver_tut.cpp b/indra/test/lliohttpserver_tut.cpp index e7af09f80b..3fa5c8dd42 100644 --- a/indra/test/lliohttpserver_tut.cpp +++ b/indra/test/lliohttpserver_tut.cpp @@ -77,7 +77,6 @@ namespace tut HTTPServiceTestData() : mResponse(NULL) { - LLCommon::initClass(); LLHTTPStandardServices::useServices(); LLHTTPRegistrar::buildAllServices(mRoot); mRoot.addNode("/delayed/echo", new DelayedEcho(this)); @@ -86,7 +85,6 @@ namespace tut ~HTTPServiceTestData() { - LLCommon::cleanupClass(); } LLHTTPNode mRoot; diff --git a/indra/test/test.cpp b/indra/test/test.cpp index 8bd302ce7a..28de88201c 100644 --- a/indra/test/test.cpp +++ b/indra/test/test.cpp @@ -514,8 +514,8 @@ int main(int argc, char **argv) #endif ll_init_apr(); - LLTrace::init(); + LLTrace::init(); apr_getopt_t* os = NULL; if(APR_SUCCESS != apr_getopt_init(&os, gAPRPoolp, argc, argv)) { diff --git a/indra/test_apps/llplugintest/llmediaplugintest.cpp b/indra/test_apps/llplugintest/llmediaplugintest.cpp index 99a82ed555..fa4f5abd28 100644 --- a/indra/test_apps/llplugintest/llmediaplugintest.cpp +++ b/indra/test_apps/llplugintest/llmediaplugintest.cpp @@ -41,7 +41,6 @@ #if LL_WINDOWS #pragma warning(disable: 4263) #pragma warning(disable: 4264) -#undef NOMINMAX #endif #if __APPLE__ -- cgit v1.3 From ae028e79872f166db8e514ca3b442c7807d6ebdb Mon Sep 17 00:00:00 2001 From: Richard Linden Date: Thu, 11 Apr 2013 19:08:57 -0700 Subject: removed unused data structures --- indra/llcharacter/llmotioncontroller.h | 1 - indra/llcommon/CMakeLists.txt | 5 - indra/llcommon/llptrskiplist.h | 724 ---------------- indra/llcommon/llptrskipmap.h | 1239 ---------------------------- indra/llcommon/llskiplist.h | 517 ------------ indra/llcommon/llskipmap.h | 1020 ----------------------- indra/llcommon/lluuidhashmap.h | 583 ------------- indra/newview/llviewerprecompiledheaders.h | 1 - indra/test/CMakeLists.txt | 1 - indra/test/lluuidhashmap_tut.cpp | 455 ---------- 10 files changed, 4546 deletions(-) delete mode 100644 indra/llcommon/llptrskiplist.h delete mode 100644 indra/llcommon/llptrskipmap.h delete mode 100644 indra/llcommon/llskiplist.h delete mode 100644 indra/llcommon/llskipmap.h delete mode 100644 indra/llcommon/lluuidhashmap.h delete mode 100644 indra/test/lluuidhashmap_tut.cpp (limited to 'indra/test') diff --git a/indra/llcharacter/llmotioncontroller.h b/indra/llcharacter/llmotioncontroller.h index 52eaf557b1..2bd5271c4f 100644 --- a/indra/llcharacter/llmotioncontroller.h +++ b/indra/llcharacter/llmotioncontroller.h @@ -34,7 +34,6 @@ #include #include -#include "lluuidhashmap.h" #include "llmotion.h" #include "llpose.h" #include "llframetimer.h" diff --git a/indra/llcommon/CMakeLists.txt b/indra/llcommon/CMakeLists.txt index f8f1c010f7..5117224ddb 100644 --- a/indra/llcommon/CMakeLists.txt +++ b/indra/llcommon/CMakeLists.txt @@ -212,8 +212,6 @@ set(llcommon_HEADER_FILES llpriqueuemap.h llprocess.h llprocessor.h - llptrskiplist.h - llptrskipmap.h llptrto.h llqueuedthread.h llrand.h @@ -230,8 +228,6 @@ set(llcommon_HEADER_FILES llsecondlifeurls.h llsimplehash.h llsingleton.h - llskiplist.h - llskipmap.h llsortedvector.h llstack.h llstacktrace.h @@ -255,7 +251,6 @@ set(llcommon_HEADER_FILES llunit.h lluri.h lluuid.h - lluuidhashmap.h llversionserver.h llversionviewer.h llwin32headers.h diff --git a/indra/llcommon/llptrskiplist.h b/indra/llcommon/llptrskiplist.h deleted file mode 100644 index 67c7cde352..0000000000 --- a/indra/llcommon/llptrskiplist.h +++ /dev/null @@ -1,724 +0,0 @@ -/** - * @file llptrskiplist.h - * @brief Skip list implementation. - * - * $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_LLPTRSKIPLIST_H -#define LL_LLPTRSKIPLIST_H - -#include "llerror.h" -#include "llrand.h" -//#include "vmath.h" -#include "llrand.h" - -///////////////////////////////////////////// -// -// LLPtrSkipList implementation - skip list for pointers to objects -// - -template -class LLPtrSkipList -{ -public: - friend class LLPtrSkipNode; - - // basic constructor - LLPtrSkipList(); - // basic constructor including sorter - LLPtrSkipList(BOOL (*insert_first)(DATA_TYPE *first, DATA_TYPE *second), - BOOL (*equals)(DATA_TYPE *first, DATA_TYPE *second)); - ~LLPtrSkipList(); - - inline void setInsertFirst(BOOL (*insert_first)(const DATA_TYPE *first, const DATA_TYPE *second)); - inline void setEquals(BOOL (*equals)(const DATA_TYPE *first, const DATA_TYPE *second)); - - inline BOOL addData(DATA_TYPE *data); - - inline BOOL checkData(const DATA_TYPE *data); - - inline S32 getLength(); // returns number of items in the list - NOT constant time! - - inline BOOL removeData(const DATA_TYPE *data); - - // note that b_sort is ignored - inline BOOL moveData(const DATA_TYPE *data, LLPtrSkipList *newlist, BOOL b_sort); - - inline BOOL moveCurrentData(LLPtrSkipList *newlist, BOOL b_sort); - - // resort -- use when the value we're sorting by changes - /* IW 12/6/02 - This doesn't work! - Instead, remove the data BEFORE you change it - Then re-insert it after you change it - BOOL resortData(DATA_TYPE *data) - */ - - // remove all nodes from the list but do not delete data - inline void removeAllNodes(); - - inline BOOL deleteData(const DATA_TYPE *data); - - // remove all nodes from the list and delete data - inline void deleteAllData(); - - // place mCurrentp on first node - inline void resetList(); - - // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - inline DATA_TYPE *getCurrentData(); - - // same as getCurrentData() but a more intuitive name for the operation - inline DATA_TYPE *getNextData(); - - // remove the Node at mCurentOperatingp - // leave mCurrentp and mCurentOperatingp on the next entry - inline void removeCurrentData(); - - // delete the Node at mCurentOperatingp - // leave mCurrentp and mCurentOperatingp on the next entry - inline void deleteCurrentData(); - - // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - inline DATA_TYPE *getFirstData(); - - // TRUE if nodes are not in sorted order - inline BOOL corrupt(); - -protected: - class LLPtrSkipNode - { - public: - LLPtrSkipNode() - : mData(NULL) - { - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - } - - LLPtrSkipNode(DATA_TYPE *data) - : mData(data) - { - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - } - - ~LLPtrSkipNode() - { - if (mData) - { - llerror("Attempting to call LLPtrSkipNode destructor with a non-null mDatap!", 1); - } - } - - // delete associated data and NULLs out pointer - void deleteData() - { - delete mData; - mData = NULL; - } - - // NULLs out pointer - void removeData() - { - mData = NULL; - } - - DATA_TYPE *mData; - LLPtrSkipNode *mForward[BINARY_DEPTH]; - }; - - static BOOL defaultEquals(const DATA_TYPE *first, const DATA_TYPE *second) - { - return first == second; - } - - - LLPtrSkipNode mHead; - LLPtrSkipNode *mUpdate[BINARY_DEPTH]; - LLPtrSkipNode *mCurrentp; - LLPtrSkipNode *mCurrentOperatingp; - S32 mLevel; - BOOL (*mInsertFirst)(const DATA_TYPE *first, const DATA_TYPE *second); - BOOL (*mEquals)(const DATA_TYPE *first, const DATA_TYPE *second); -}; - - -// basic constructor -template -LLPtrSkipList::LLPtrSkipList() - : mInsertFirst(NULL), mEquals(defaultEquals) -{ - if (BINARY_DEPTH < 2) - { - llerrs << "Trying to create skip list with too little depth, " - "must be 2 or greater" << llendl; - } - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mUpdate[i] = NULL; - } - mLevel = 1; - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -// basic constructor including sorter -template -LLPtrSkipList::LLPtrSkipList(BOOL (*insert_first)(DATA_TYPE *first, DATA_TYPE *second), - BOOL (*equals)(DATA_TYPE *first, DATA_TYPE *second)) - :mInsertFirst(insert_first), mEquals(equals) -{ - if (BINARY_DEPTH < 2) - { - llerrs << "Trying to create skip list with too little depth, " - "must be 2 or greater" << llendl; - } - mLevel = 1; - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mHead.mForward[i] = NULL; - mUpdate[i] = NULL; - } - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -template -inline LLPtrSkipList::~LLPtrSkipList() -{ - removeAllNodes(); -} - -template -inline void LLPtrSkipList::setInsertFirst(BOOL (*insert_first)(const DATA_TYPE *first, const DATA_TYPE *second)) -{ - mInsertFirst = insert_first; -} - -template -inline void LLPtrSkipList::setEquals(BOOL (*equals)(const DATA_TYPE *first, const DATA_TYPE *second)) -{ - mEquals = equals; -} - -template -inline BOOL LLPtrSkipList::addData(DATA_TYPE *data) -{ - S32 level; - LLPtrSkipNode *current = &mHead; - LLPtrSkipNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mData, data))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mData < data)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - // now add the new node - S32 newlevel; - for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) - { - if (ll_frand() < 0.5f) - break; - } - - LLPtrSkipNode *snode = new LLPtrSkipNode(data); - - if (newlevel > mLevel) - { - mHead.mForward[mLevel] = NULL; - mUpdate[mLevel] = &mHead; - mLevel = newlevel; - } - - for (level = 0; level < newlevel; level++) - { - snode->mForward[level] = mUpdate[level]->mForward[level]; - mUpdate[level]->mForward[level] = snode; - } - return TRUE; -} - -template -inline BOOL LLPtrSkipList::checkData(const DATA_TYPE *data) -{ - S32 level; - LLPtrSkipNode *current = &mHead; - LLPtrSkipNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mData, data))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mData < data)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - if (current) - { - return mEquals(current->mData, data); - } - else - { - return FALSE; - } -} - -// returns number of items in the list -template -inline S32 LLPtrSkipList::getLength() -{ - U32 length = 0; - for (LLPtrSkipNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) - { - length++; - } - return length; -} - -template -inline BOOL LLPtrSkipList::removeData(const DATA_TYPE *data) -{ - S32 level; - LLPtrSkipNode *current = &mHead; - LLPtrSkipNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mData, data))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mData < data)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - if (!current) - { - // empty list or beyond the end! - return FALSE; - } - - // is this the one we want? - if (!mEquals(current->mData, data)) - { - // nope! - return FALSE; - } - else - { - // yes it is! change pointers as required - for (level = 0; level < mLevel; level++) - { - if (mUpdate[level]->mForward[level] != current) - { - // cool, we've fixed all the pointers! - break; - } - mUpdate[level]->mForward[level] = current->mForward[level]; - } - - // clean up cuurent - current->removeData(); - delete current; - - // clean up mHead - while ( (mLevel > 1) - &&(!mHead.mForward[mLevel - 1])) - { - mLevel--; - } - } - return TRUE; -} - -// note that b_sort is ignored -template -inline BOOL LLPtrSkipList::moveData(const DATA_TYPE *data, LLPtrSkipList *newlist, BOOL b_sort) -{ - BOOL removed = removeData(data); - BOOL added = newlist->addData(data); - return removed && added; -} - -template -inline BOOL LLPtrSkipList::moveCurrentData(LLPtrSkipList *newlist, BOOL b_sort) -{ - if (mCurrentOperatingp) - { - mCurrentp = mCurrentOperatingp->mForward[0]; - BOOL removed = removeData(mCurrentOperatingp); - BOOL added = newlist->addData(mCurrentOperatingp); - mCurrentOperatingp = mCurrentp; - return removed && added; - } - return FALSE; -} - -// resort -- use when the value we're sorting by changes -/* IW 12/6/02 - This doesn't work! - Instead, remove the data BEFORE you change it - Then re-insert it after you change it -BOOL resortData(DATA_TYPE *data) -{ - removeData(data); - addData(data); -} -*/ - -// remove all nodes from the list but do not delete data -template -inline void LLPtrSkipList::removeAllNodes() -{ - LLPtrSkipNode *temp; - // reset mCurrentp - mCurrentp = *(mHead.mForward); - - while (mCurrentp) - { - temp = mCurrentp->mForward[0]; - mCurrentp->removeData(); - delete mCurrentp; - mCurrentp = temp; - } - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mHead.mForward[i] = NULL; - mUpdate[i] = NULL; - } - - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -template -inline BOOL LLPtrSkipList::deleteData(const DATA_TYPE *data) -{ - S32 level; - LLPtrSkipNode *current = &mHead; - LLPtrSkipNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mData, data))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mData < data)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - if (!current) - { - // empty list or beyond the end! - return FALSE; - } - - // is this the one we want? - if (!mEquals(current->mData, data)) - { - // nope! - return FALSE; - } - else - { - // do we need to fix current or currentop? - if (current == mCurrentp) - { - mCurrentp = current->mForward[0]; - } - - if (current == mCurrentOperatingp) - { - mCurrentOperatingp = current->mForward[0]; - } - - // yes it is! change pointers as required - for (level = 0; level < mLevel; level++) - { - if (mUpdate[level]->mForward[level] != current) - { - // cool, we've fixed all the pointers! - break; - } - mUpdate[level]->mForward[level] = current->mForward[level]; - } - - // clean up cuurent - current->deleteData(); - delete current; - - // clean up mHead - while ( (mLevel > 1) - &&(!mHead.mForward[mLevel - 1])) - { - mLevel--; - } - } - return TRUE; -} - -// remove all nodes from the list and delete data -template -inline void LLPtrSkipList::deleteAllData() -{ - LLPtrSkipNode *temp; - // reset mCurrentp - mCurrentp = *(mHead.mForward); - - while (mCurrentp) - { - temp = mCurrentp->mForward[0]; - mCurrentp->deleteData(); - delete mCurrentp; - mCurrentp = temp; - } - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mHead.mForward[i] = NULL; - mUpdate[i] = NULL; - } - - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -// place mCurrentp on first node -template -inline void LLPtrSkipList::resetList() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template -inline DATA_TYPE *LLPtrSkipList::getCurrentData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = *mCurrentp->mForward; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes compile warning - return 0; // equivalent, but no warning - } -} - -// same as getCurrentData() but a more intuitive name for the operation -template -inline DATA_TYPE *LLPtrSkipList::getNextData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = *mCurrentp->mForward; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes compile warning - return 0; // equivalent, but no warning - } -} - -// remove the Node at mCurentOperatingp -// leave mCurrentp and mCurentOperatingp on the next entry -template -inline void LLPtrSkipList::removeCurrentData() -{ - if (mCurrentOperatingp) - { - removeData(mCurrentOperatingp->mData); - } -} - -// delete the Node at mCurentOperatingp -// leave mCurrentp and mCurentOperatingp on the next entry -template -inline void LLPtrSkipList::deleteCurrentData() -{ - if (mCurrentOperatingp) - { - deleteData(mCurrentOperatingp->mData); - } -} - -// reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template -inline DATA_TYPE *LLPtrSkipList::getFirstData() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes compile warning - return 0; // equivalent, but no warning - } -} - -template -inline BOOL LLPtrSkipList::corrupt() -{ - LLPtrSkipNode *previous = mHead.mForward[0]; - - // Empty lists are not corrupt. - if (!previous) return FALSE; - - LLPtrSkipNode *current = previous->mForward[0]; - while(current) - { - if (!mInsertFirst(previous->mData, current->mData)) - { - // prev shouldn't be in front of cur! - return TRUE; - } - current = current->mForward[0]; - } - return FALSE; -} - -#endif diff --git a/indra/llcommon/llptrskipmap.h b/indra/llcommon/llptrskipmap.h deleted file mode 100644 index 94bc71ec55..0000000000 --- a/indra/llcommon/llptrskipmap.h +++ /dev/null @@ -1,1239 +0,0 @@ -/** - * @file llptrskipmap.h - * @brief Just like a LLSkipMap, but since it's pointers, you can call - * deleteAllData - * - * $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_LLPTRSKIPMAP_H -#define LL_LLPTRSKIPMAP_H - -#include "llerror.h" -#include "llrand.h" - -template -class LLPtrSkipMapNode -{ -public: - LLPtrSkipMapNode() - { - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - - U8 *zero = (U8 *)&mIndex; - - for (i = 0; i < (S32)sizeof(INDEX_T); i++) - { - *(zero + i) = 0; - } - - zero = (U8 *)&mData; - - for (i = 0; i < (S32)sizeof(DATA_T); i++) - { - *(zero + i) = 0; - } - } - - LLPtrSkipMapNode(const INDEX_T &index) - : mIndex(index) - { - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - - U8 *zero = (U8 *)&mData; - - for (i = 0; i < (S32)sizeof(DATA_T); i++) - { - *(zero + i) = 0; - } - } - - LLPtrSkipMapNode(const INDEX_T &index, DATA_T datap) - : mIndex(index) - { - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - - mData = datap; - } - - ~LLPtrSkipMapNode() - { - } - - // delete associated data and NULLs out pointer - void deleteData() - { - delete mData; - mData = 0; - } - - // NULLs out pointer - void removeData() - { - mData = 0; - } - - INDEX_T mIndex; - DATA_T mData; - LLPtrSkipMapNode *mForward[BINARY_DEPTH]; - -private: - // Disallow copying of LLPtrSkipMapNodes by not implementing these methods. - LLPtrSkipMapNode(const LLPtrSkipMapNode &); - LLPtrSkipMapNode &operator=(const LLPtrSkipMapNode &rhs); -}; - -//--------------------------------------------------------------------------- - -template -class LLPtrSkipMap -{ -public: - typedef BOOL (*compare)(const DATA_T& first, const DATA_T& second); - typedef compare insert_func; - typedef compare equals_func; - - void init(); - - // basic constructor - LLPtrSkipMap(); - - // basic constructor including sorter - LLPtrSkipMap(insert_func insert_first, equals_func equals); - - ~LLPtrSkipMap(); - - void setInsertFirst(insert_func insert_first); - void setEquals(equals_func equals); - - DATA_T &addData(const INDEX_T &index, DATA_T datap); - DATA_T &addData(const INDEX_T &index); - DATA_T &getData(const INDEX_T &index); - DATA_T &operator[](const INDEX_T &index); - - // If index present, returns data. - // If index not present, adds and returns NULL. - DATA_T &getData(const INDEX_T &index, BOOL &b_new_entry); - - // returns data entry before and after index - BOOL getInterval(const INDEX_T &index, INDEX_T &index_before, INDEX_T &index_after, - DATA_T &data_before, DATA_T &data_after ); - - // Returns TRUE if data present in map. - BOOL checkData(const INDEX_T &index); - - // Returns TRUE if key is present in map. This is useful if you - // are potentially storing NULL pointers in the map - BOOL checkKey(const INDEX_T &index); - - // If there, returns the data. - // If not, returns NULL. - // Never adds entries to the map. - DATA_T getIfThere(const INDEX_T &index); - - INDEX_T reverseLookup(const DATA_T datap); - - // returns number of items in the list - S32 getLength(); // WARNING! getLength is O(n), not O(1)! - - BOOL removeData(const INDEX_T &index); - BOOL deleteData(const INDEX_T &index); - - // remove all nodes from the list but do not delete data - void removeAllData(); - void deleteAllData(); - - // place mCurrentp on first node - void resetList(); - - // return the data currently pointed to - DATA_T getCurrentDataWithoutIncrement(); - - // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - DATA_T getCurrentData(); - - // same as getCurrentData() but a more intuitive name for the operation - DATA_T getNextData(); - - INDEX_T getNextKey(); - - // return the key currently pointed to - INDEX_T getCurrentKeyWithoutIncrement(); - - // remove the Node at mCurentOperatingp - // leave mCurrentp and mCurentOperatingp on the next entry - void removeCurrentData(); - - void deleteCurrentData(); - - // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - DATA_T getFirstData(); - - INDEX_T getFirstKey(); - - static BOOL defaultEquals(const INDEX_T &first, const INDEX_T &second) - { - return first == second; - } - -private: - // don't generate implicit copy constructor or copy assignment - LLPtrSkipMap(const LLPtrSkipMap &); - LLPtrSkipMap &operator=(const LLPtrSkipMap &); - -private: - LLPtrSkipMapNode mHead; - LLPtrSkipMapNode *mUpdate[BINARY_DEPTH]; - LLPtrSkipMapNode *mCurrentp; - LLPtrSkipMapNode *mCurrentOperatingp; - S32 mLevel; - BOOL (*mInsertFirst)(const INDEX_T &first, const INDEX_T &second); - BOOL (*mEquals)(const INDEX_T &first, const INDEX_T &second); - S32 mNumberOfSteps; -}; - -////////////////////////////////////////////////// -// -// LLPtrSkipMap implementation -// -// - -template -inline LLPtrSkipMap::LLPtrSkipMap() - : mInsertFirst(NULL), - mEquals(defaultEquals), - mNumberOfSteps(0) -{ - if (BINARY_DEPTH < 2) - { - llerrs << "Trying to create skip list with too little depth, " - "must be 2 or greater" << llendl; - } - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mUpdate[i] = NULL; - } - mLevel = 1; - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -template -inline LLPtrSkipMap::LLPtrSkipMap(insert_func insert_first, - equals_func equals) -: mInsertFirst(insert_first), - mEquals(equals), - mNumberOfSteps(0) -{ - if (BINARY_DEPTH < 2) - { - llerrs << "Trying to create skip list with too little depth, " - "must be 2 or greater" << llendl; - } - mLevel = 1; - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mHead.mForward[i] = NULL; - mUpdate[i] = NULL; - } - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -template -inline LLPtrSkipMap::~LLPtrSkipMap() -{ - removeAllData(); -} - -template -inline void LLPtrSkipMap::setInsertFirst(insert_func insert_first) -{ - mInsertFirst = insert_first; -} - -template -inline void LLPtrSkipMap::setEquals(equals_func equals) -{ - mEquals = equals; -} - -template -inline DATA_T &LLPtrSkipMap::addData(const INDEX_T &index, DATA_T datap) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - // replace the existing data if a node is already there - if ( (current) - &&(mEquals(current->mIndex, index))) - { - current->mData = datap; - return current->mData; - } - - // now add the new node - S32 newlevel; - for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) - { - if (ll_frand() < 0.5f) - { - break; - } - } - - LLPtrSkipMapNode *snode - = new LLPtrSkipMapNode(index, datap); - - if (newlevel > mLevel) - { - mHead.mForward[mLevel] = NULL; - mUpdate[mLevel] = &mHead; - mLevel = newlevel; - } - - for (level = 0; level < newlevel; level++) - { - snode->mForward[level] = mUpdate[level]->mForward[level]; - mUpdate[level]->mForward[level] = snode; - } - return snode->mData; -} - -template -inline DATA_T &LLPtrSkipMap::addData(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - // now add the new node - S32 newlevel; - for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) - { - if (ll_frand() < 0.5f) - break; - } - - LLPtrSkipMapNode *snode - = new LLPtrSkipMapNode(index); - - if (newlevel > mLevel) - { - mHead.mForward[mLevel] = NULL; - mUpdate[mLevel] = &mHead; - mLevel = newlevel; - } - - for (level = 0; level < newlevel; level++) - { - snode->mForward[level] = mUpdate[level]->mForward[level]; - mUpdate[level]->mForward[level] = snode; - } - return snode->mData; -} - -template -inline DATA_T &LLPtrSkipMap::getData(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *temp; - - mNumberOfSteps = 0; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - mNumberOfSteps++; - - if ( (current) - &&(mEquals(current->mIndex, index))) - { - - return current->mData; - } - - // now add the new node - S32 newlevel; - for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) - { - if (ll_frand() < 0.5f) - break; - } - - LLPtrSkipMapNode *snode - = new LLPtrSkipMapNode(index); - - if (newlevel > mLevel) - { - mHead.mForward[mLevel] = NULL; - mUpdate[mLevel] = &mHead; - mLevel = newlevel; - } - - for (level = 0; level < newlevel; level++) - { - snode->mForward[level] = mUpdate[level]->mForward[level]; - mUpdate[level]->mForward[level] = snode; - } - - return snode->mData; -} - -template -inline BOOL LLPtrSkipMap::getInterval(const INDEX_T &index, - INDEX_T &index_before, - INDEX_T &index_after, - DATA_T &data_before, - DATA_T &data_after) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *temp; - - mNumberOfSteps = 0; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - - BOOL both_found = TRUE; - - if (current != &mHead) - { - index_before = current->mIndex; - data_before = current->mData; - } - else - { - data_before = 0; - index_before = 0; - both_found = FALSE; - } - - // we're now just in front of where we want to be . . . take one step forward - mNumberOfSteps++; - current = *current->mForward; - - if (current) - { - data_after = current->mData; - index_after = current->mIndex; - } - else - { - data_after = 0; - index_after = 0; - both_found = FALSE; - } - - return both_found; -} - - -template -inline DATA_T &LLPtrSkipMap::operator[](const INDEX_T &index) -{ - - return getData(index); -} - -// If index present, returns data. -// If index not present, adds and returns NULL. -template -inline DATA_T &LLPtrSkipMap::getData(const INDEX_T &index, BOOL &b_new_entry) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *temp; - - mNumberOfSteps = 0; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - mNumberOfSteps++; - current = *current->mForward; - - if ( (current) - &&(mEquals(current->mIndex, index))) - { - - return current->mData; - } - b_new_entry = TRUE; - addData(index); - - return current->mData; -} - -// Returns TRUE if data present in map. -template -inline BOOL LLPtrSkipMap::checkData(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - if (current) - { - // Gets rid of some compiler ambiguity for the LLPointer<> templated class. - if (current->mData) - { - return mEquals(current->mIndex, index); - } - } - - return FALSE; -} - -// Returns TRUE if key is present in map. This is useful if you -// are potentially storing NULL pointers in the map -template -inline BOOL LLPtrSkipMap::checkKey(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - if (current) - { - return mEquals(current->mIndex, index); - } - - return FALSE; -} - -// If there, returns the data. -// If not, returns NULL. -// Never adds entries to the map. -template -inline DATA_T LLPtrSkipMap::getIfThere(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *temp; - - mNumberOfSteps = 0; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - mNumberOfSteps++; - current = *current->mForward; - - if (current) - { - if (mEquals(current->mIndex, index)) - { - return current->mData; - } - } - - // Avoid Linux compiler warning on returning NULL. - return (DATA_T)0; -} - -template -inline INDEX_T LLPtrSkipMap::reverseLookup(const DATA_T datap) -{ - LLPtrSkipMapNode *current = &mHead; - - while (current) - { - if (datap == current->mData) - { - - return current->mIndex; - } - current = *current->mForward; - } - - // not found! return NULL - return INDEX_T(); -} - -// returns number of items in the list -template -inline S32 LLPtrSkipMap::getLength() -{ - U32 length = 0; - LLPtrSkipMapNode* temp; - for (temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) - { - length++; - } - - return length; -} - -template -inline BOOL LLPtrSkipMap::removeData(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - if (!current) - { - // empty list or beyond the end! - - return FALSE; - } - - // is this the one we want? - if (!mEquals(current->mIndex, index)) - { - // nope! - - return FALSE; - } - else - { - // do we need to fix current or currentop? - if (current == mCurrentp) - { - mCurrentp = *current->mForward; - } - - if (current == mCurrentOperatingp) - { - mCurrentOperatingp = *current->mForward; - } - // yes it is! change pointers as required - for (level = 0; level < mLevel; level++) - { - if (*((*(mUpdate + level))->mForward + level) != current) - { - // cool, we've fixed all the pointers! - break; - } - *((*(mUpdate + level))->mForward + level) = *(current->mForward + level); - } - - // clean up cuurent - current->removeData(); - delete current; - - // clean up mHead - while ( (mLevel > 1) - &&(!*(mHead.mForward + mLevel - 1))) - { - mLevel--; - } - } - - return TRUE; -} - -template -inline BOOL LLPtrSkipMap::deleteData(const INDEX_T &index) -{ - S32 level; - LLPtrSkipMapNode *current = &mHead; - LLPtrSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - if (!current) - { - // empty list or beyond the end! - - return FALSE; - } - - // is this the one we want? - if (!mEquals(current->mIndex, index)) - { - // nope! - - return FALSE; - } - else - { - // do we need to fix current or currentop? - if (current == mCurrentp) - { - mCurrentp = *current->mForward; - } - - if (current == mCurrentOperatingp) - { - mCurrentOperatingp = *current->mForward; - } - // yes it is! change pointers as required - for (level = 0; level < mLevel; level++) - { - if (*((*(mUpdate + level))->mForward + level) != current) - { - // cool, we've fixed all the pointers! - break; - } - *((*(mUpdate + level))->mForward + level) = *(current->mForward + level); - } - - // clean up cuurent - current->deleteData(); - delete current; - - // clean up mHead - while ( (mLevel > 1) - &&(!*(mHead.mForward + mLevel - 1))) - { - mLevel--; - } - } - - return TRUE; -} - -// remove all nodes from the list but do not delete data -template -void LLPtrSkipMap::removeAllData() -{ - LLPtrSkipMapNode *temp; - // reset mCurrentp - mCurrentp = *(mHead.mForward); - - while (mCurrentp) - { - temp = mCurrentp->mForward[0]; - mCurrentp->removeData(); - delete mCurrentp; - mCurrentp = temp; - } - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mHead.mForward[i] = NULL; - mUpdate[i] = NULL; - } - - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -template -inline void LLPtrSkipMap::deleteAllData() -{ - LLPtrSkipMapNode *temp; - // reset mCurrentp - mCurrentp = *(mHead.mForward); - - while (mCurrentp) - { - temp = mCurrentp->mForward[0]; - mCurrentp->deleteData(); - delete mCurrentp; - mCurrentp = temp; - } - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mHead.mForward[i] = NULL; - mUpdate[i] = NULL; - } - - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -// place mCurrentp on first node -template -inline void LLPtrSkipMap::resetList() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - - -// return the data currently pointed to -template -inline DATA_T LLPtrSkipMap::getCurrentDataWithoutIncrement() -{ - if (mCurrentOperatingp) - { - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes warning - return (DATA_T)0; // equivalent, but no warning - } -} - -// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template -inline DATA_T LLPtrSkipMap::getCurrentData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes warning - return (DATA_T)0; // equivalent, but no warning - } -} - -// same as getCurrentData() but a more intuitive name for the operation -template -inline DATA_T LLPtrSkipMap::getNextData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes compile warning - return (DATA_T)0; // equivalent, but removes warning - } -} - -template -inline INDEX_T LLPtrSkipMap::getNextKey() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mIndex; - } - else - { - return mHead.mIndex; - } -} - -// return the key currently pointed to -template -inline INDEX_T LLPtrSkipMap::getCurrentKeyWithoutIncrement() -{ - if (mCurrentOperatingp) - { - return mCurrentOperatingp->mIndex; - } - else - { - //return NULL; // causes compile warning - return (INDEX_T)0; // equivalent, but removes warning - } -} - - -// remove the Node at mCurentOperatingp -// leave mCurrentp and mCurentOperatingp on the next entry -template -inline void LLPtrSkipMap::removeCurrentData() -{ - if (mCurrentOperatingp) - { - removeData(mCurrentOperatingp->mIndex); - } -} - -template -inline void LLPtrSkipMap::deleteCurrentData() -{ - if (mCurrentOperatingp) - { - deleteData(mCurrentOperatingp->mIndex); - } -} - -// reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template -inline DATA_T LLPtrSkipMap::getFirstData() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes compile warning - return (DATA_T)0; // equivalent, but removes warning - } -} - -template -inline INDEX_T LLPtrSkipMap::getFirstKey() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mIndex; - } - else - { - return mHead.mIndex; - } -} - -#endif diff --git a/indra/llcommon/llskiplist.h b/indra/llcommon/llskiplist.h deleted file mode 100644 index ed132381f9..0000000000 --- a/indra/llcommon/llskiplist.h +++ /dev/null @@ -1,517 +0,0 @@ -/** - * @file llskiplist.h - * @brief skip list implementation - * - * $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_LLSKIPLIST_H -#define LL_LLSKIPLIST_H - -#include "llrand.h" -#include "llrand.h" - -// NOTA BENE: Insert first needs to be < NOT <= -// Binary depth must be >= 2 -template -class LLSkipList -{ -public: - typedef BOOL (*compare)(const DATA_TYPE& first, const DATA_TYPE& second); - typedef compare insert_func; - typedef compare equals_func; - - void init(); - - // basic constructor - LLSkipList(); - - // basic constructor including sorter - LLSkipList(insert_func insert_first, equals_func equals); - ~LLSkipList(); - - inline void setInsertFirst(insert_func insert_first); - inline void setEquals(equals_func equals); - - inline BOOL addData(const DATA_TYPE& data); - inline BOOL checkData(const DATA_TYPE& data); - - // returns number of items in the list - inline S32 getLength() const; // NOT a constant time operation, traverses entire list! - - inline BOOL moveData(const DATA_TYPE& data, LLSkipList *newlist); - - inline BOOL removeData(const DATA_TYPE& data); - - // remove all nodes from the list but do not delete data - inline void removeAllNodes(); - - // place mCurrentp on first node - inline void resetList(); - - // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - inline DATA_TYPE getCurrentData(); - - // same as getCurrentData() but a more intuitive name for the operation - inline DATA_TYPE getNextData(); - - // remove the Node at mCurentOperatingp - // leave mCurrentp and mCurentOperatingp on the next entry - inline void removeCurrentData(); - - // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - inline DATA_TYPE getFirstData(); - - class LLSkipNode - { - public: - LLSkipNode() - : mData(0) - { - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - } - - LLSkipNode(DATA_TYPE data) - : mData(data) - { - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - } - - ~LLSkipNode() - { - } - - DATA_TYPE mData; - LLSkipNode *mForward[BINARY_DEPTH]; - - private: - // Disallow copying of LLSkipNodes by not implementing these methods. - LLSkipNode(const LLSkipNode &); - LLSkipNode &operator=(const LLSkipNode &); - }; - - static BOOL defaultEquals(const DATA_TYPE& first, const DATA_TYPE& second) - { - return first == second; - } - -private: - LLSkipNode mHead; - LLSkipNode *mUpdate[BINARY_DEPTH]; - LLSkipNode *mCurrentp; - LLSkipNode *mCurrentOperatingp; - S32 mLevel; - insert_func mInsertFirst; - equals_func mEquals; - -private: - // Disallow copying of LLSkipNodes by not implementing these methods. - LLSkipList(const LLSkipList &); - LLSkipList &operator=(const LLSkipList &); -}; - - -/////////////////////// -// -// Implementation -// - - -// Binary depth must be >= 2 -template -inline void LLSkipList::init() -{ - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mHead.mForward[i] = NULL; - mUpdate[i] = NULL; - } - mLevel = 1; - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - - -// basic constructor -template -inline LLSkipList::LLSkipList() -: mInsertFirst(NULL), - mEquals(defaultEquals) -{ - init(); -} - -// basic constructor including sorter -template -inline LLSkipList::LLSkipList(insert_func insert, - equals_func equals) -: mInsertFirst(insert), - mEquals(equals) -{ - init(); -} - -template -inline LLSkipList::~LLSkipList() -{ - removeAllNodes(); -} - -template -inline void LLSkipList::setInsertFirst(insert_func insert_first) -{ - mInsertFirst = insert_first; -} - -template -inline void LLSkipList::setEquals(equals_func equals) -{ - mEquals = equals; -} - -template -inline BOOL LLSkipList::addData(const DATA_TYPE& data) -{ - S32 level; - LLSkipNode *current = &mHead; - LLSkipNode *temp; - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mData, data))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mData < data)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - // now add the new node - S32 newlevel; - for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) - { - if (ll_frand() < 0.5f) - break; - } - - LLSkipNode *snode = new LLSkipNode(data); - - if (newlevel > mLevel) - { - mHead.mForward[mLevel] = NULL; - mUpdate[mLevel] = &mHead; - mLevel = newlevel; - } - - for (level = 0; level < newlevel; level++) - { - snode->mForward[level] = mUpdate[level]->mForward[level]; - mUpdate[level]->mForward[level] = snode; - } - return TRUE; -} - -template -inline BOOL LLSkipList::checkData(const DATA_TYPE& data) -{ - S32 level; - LLSkipNode *current = &mHead; - LLSkipNode *temp; - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mData, data))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mData < data)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - - if (current) - { - return mEquals(current->mData, data); - } - - return FALSE; -} - -// returns number of items in the list -template -inline S32 LLSkipList::getLength() const -{ - U32 length = 0; - for (LLSkipNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) - { - length++; - } - return length; -} - - -template -inline BOOL LLSkipList::moveData(const DATA_TYPE& data, LLSkipList *newlist) -{ - BOOL removed = removeData(data); - BOOL added = newlist->addData(data); - return removed && added; -} - - -template -inline BOOL LLSkipList::removeData(const DATA_TYPE& data) -{ - S32 level; - LLSkipNode *current = &mHead; - LLSkipNode *temp; - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mData, data))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mData < data)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - - if (!current) - { - // empty list or beyond the end! - return FALSE; - } - - // is this the one we want? - if (!mEquals(current->mData, data)) - { - // nope! - return FALSE; - } - else - { - // do we need to fix current or currentop? - if (current == mCurrentp) - { - mCurrentp = current->mForward[0]; - } - - if (current == mCurrentOperatingp) - { - mCurrentOperatingp = current->mForward[0]; - } - // yes it is! change pointers as required - for (level = 0; level < mLevel; level++) - { - if (mUpdate[level]->mForward[level] != current) - { - // cool, we've fixed all the pointers! - break; - } - mUpdate[level]->mForward[level] = current->mForward[level]; - } - - // clean up cuurent - delete current; - - // clean up mHead - while ( (mLevel > 1) - &&(!mHead.mForward[mLevel - 1])) - { - mLevel--; - } - } - return TRUE; -} - -// remove all nodes from the list but do not delete data -template -inline void LLSkipList::removeAllNodes() -{ - LLSkipNode *temp; - // reset mCurrentp - mCurrentp = *(mHead.mForward); - - while (mCurrentp) - { - temp = mCurrentp->mForward[0]; - delete mCurrentp; - mCurrentp = temp; - } - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mHead.mForward[i] = NULL; - mUpdate[i] = NULL; - } - - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -// place mCurrentp on first node -template -inline void LLSkipList::resetList() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template -inline DATA_TYPE LLSkipList::getCurrentData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes compile warning - return (DATA_TYPE)0; // equivalent, but no warning - } -} - -// same as getCurrentData() but a more intuitive name for the operation -template -inline DATA_TYPE LLSkipList::getNextData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes compile warning - return (DATA_TYPE)0; // equivalent, but no warning - } -} - -// remove the Node at mCurentOperatingp -// leave mCurrentp and mCurentOperatingp on the next entry -template -inline void LLSkipList::removeCurrentData() -{ - if (mCurrentOperatingp) - { - removeData(mCurrentOperatingp->mData); - } -} - -// reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template -inline DATA_TYPE LLSkipList::getFirstData() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mData; - } - else - { - //return NULL; // causes compile warning - return (DATA_TYPE)0; // equivalent, but no warning - } -} - - -#endif diff --git a/indra/llcommon/llskipmap.h b/indra/llcommon/llskipmap.h deleted file mode 100644 index ed53973baa..0000000000 --- a/indra/llcommon/llskipmap.h +++ /dev/null @@ -1,1020 +0,0 @@ -/** - * @file llskipmap.h - * @brief Associative container based on the skiplist algorithm. - * - * $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_LLSKIPMAP_H -#define LL_LLSKIPMAP_H - -#include "llerror.h" - -template -class LLSkipMap -{ -public: - // basic constructor - LLSkipMap(); - - // basic constructor including sorter - LLSkipMap(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second), - BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)); - - ~LLSkipMap(); - - void setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second)); - void setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)); - - DATA_TYPE &addData(const INDEX_TYPE &index, DATA_TYPE datap); - DATA_TYPE &addData(const INDEX_TYPE &index); - DATA_TYPE &getData(const INDEX_TYPE &index); - DATA_TYPE &operator[](const INDEX_TYPE &index); - - // If index present, returns data. - // If index not present, adds and returns NULL. - DATA_TYPE &getData(const INDEX_TYPE &index, BOOL &b_new_entry); - - // Returns TRUE if data present in map. - BOOL checkData(const INDEX_TYPE &index); - - // Returns TRUE if key is present in map. This is useful if you - // are potentially storing NULL pointers in the map - BOOL checkKey(const INDEX_TYPE &index); - - // If there, returns the data. - // If not, returns NULL. - // Never adds entries to the map. - DATA_TYPE getIfThere(const INDEX_TYPE &index); - - INDEX_TYPE reverseLookup(const DATA_TYPE datap); - - // returns number of items in the list - S32 getLength(); // WARNING! getLength is O(n), not O(1)! - - BOOL removeData(const INDEX_TYPE &index); - - // remove all nodes from the list but do not delete data - void removeAllData(); - - // place mCurrentp on first node - void resetList(); - - // return the data currently pointed to - DATA_TYPE getCurrentDataWithoutIncrement(); - - // return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - DATA_TYPE getCurrentData(); - - // same as getCurrentData() but a more intuitive name for the operation - DATA_TYPE getNextData(); - - INDEX_TYPE getNextKey(); - - // return the key currently pointed to - INDEX_TYPE getCurrentKeyWithoutIncrement(); - - // The internal iterator is at the end of the list. - BOOL notDone() const; - - // remove the Node at mCurentOperatingp - // leave mCurrentp and mCurentOperatingp on the next entry - void removeCurrentData(); - - void deleteCurrentData(); - - // reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp - DATA_TYPE getFirstData(); - - INDEX_TYPE getFirstKey(); - - class LLSkipMapNode - { - public: - LLSkipMapNode() - { - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - - U8 *zero = (U8 *)&mIndex; - - for (i = 0; i < (S32)sizeof(INDEX_TYPE); i++) - { - *(zero + i) = 0; - } - - zero = (U8 *)&mData; - - for (i = 0; i < (S32)sizeof(DATA_TYPE); i++) - { - *(zero + i) = 0; - } - } - - LLSkipMapNode(const INDEX_TYPE &index) - : mIndex(index) - { - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - - U8 *zero = (U8 *)&mData; - - for (i = 0; i < (S32)sizeof(DATA_TYPE); i++) - { - *(zero + i) = 0; - } - } - - LLSkipMapNode(const INDEX_TYPE &index, DATA_TYPE datap) - : mIndex(index) - { - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mForward[i] = NULL; - } - - mData = datap; - } - - ~LLSkipMapNode() - { - } - - - INDEX_TYPE mIndex; - DATA_TYPE mData; - LLSkipMapNode *mForward[BINARY_DEPTH]; - - private: - // Disallow copying of LLSkipMapNodes by not implementing these methods. - LLSkipMapNode(const LLSkipMapNode &); - LLSkipMapNode &operator=(const LLSkipMapNode &rhs); - }; - - static BOOL defaultEquals(const INDEX_TYPE &first, const INDEX_TYPE &second) - { - return first == second; - } - -private: - // don't generate implicit copy constructor or copy assignment - LLSkipMap(const LLSkipMap &); - LLSkipMap &operator=(const LLSkipMap &); - -private: - LLSkipMapNode mHead; - LLSkipMapNode *mUpdate[BINARY_DEPTH]; - LLSkipMapNode *mCurrentp; - LLSkipMapNode *mCurrentOperatingp; - S32 mLevel; - BOOL (*mInsertFirst)(const INDEX_TYPE &first, const INDEX_TYPE &second); - BOOL (*mEquals)(const INDEX_TYPE &first, const INDEX_TYPE &second); - S32 mNumberOfSteps; -}; - -////////////////////////////////////////////////// -// -// LLSkipMap implementation -// - -template -inline LLSkipMap::LLSkipMap() - : mInsertFirst(NULL), - mEquals(defaultEquals) -{ - llstatic_assert(BINARY_DEPTH >= 2, "Skipmaps must have binary depth of at least 2"); - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mUpdate[i] = NULL; - } - mLevel = 1; - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -template -inline LLSkipMap::LLSkipMap(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second), - BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)) - : mInsertFirst(insert_first), - mEquals(equals) -{ - llstatic_assert(BINARY_DEPTH >= 2, "Skipmaps must have binary depth of at least 2"); - - mLevel = 1; - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mHead.mForward[i] = NULL; - mUpdate[i] = NULL; - } - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - -template -inline LLSkipMap::~LLSkipMap() -{ - removeAllData(); -} - -template -inline void LLSkipMap::setInsertFirst(BOOL (*insert_first)(const INDEX_TYPE &first, const INDEX_TYPE &second)) -{ - mInsertFirst = insert_first; -} - -template -inline void LLSkipMap::setEquals(BOOL (*equals)(const INDEX_TYPE &first, const INDEX_TYPE &second)) -{ - mEquals = equals; -} - -template -inline DATA_TYPE &LLSkipMap::addData(const INDEX_TYPE &index, DATA_TYPE datap) -{ - S32 level; - LLSkipMapNode *current = &mHead; - LLSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - // replace the existing data if a node is already there - if ( (current) - &&(mEquals(current->mIndex, index))) - { - current->mData = datap; - return current->mData; - } - - // now add the new node - S32 newlevel; - for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) - { - if (rand() & 1) - { - break; - } - } - - LLSkipMapNode *snode = new LLSkipMapNode(index, datap); - - if (newlevel > mLevel) - { - mHead.mForward[mLevel] = NULL; - mUpdate[mLevel] = &mHead; - mLevel = newlevel; - } - - for (level = 0; level < newlevel; level++) - { - snode->mForward[level] = mUpdate[level]->mForward[level]; - mUpdate[level]->mForward[level] = snode; - } - return snode->mData; -} - -template -inline DATA_TYPE &LLSkipMap::addData(const INDEX_TYPE &index) -{ - S32 level; - LLSkipMapNode *current = &mHead; - LLSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - // now add the new node - S32 newlevel; - for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) - { - if (rand() & 1) - break; - } - - LLSkipMapNode *snode = new LLSkipMapNode(index); - - if (newlevel > mLevel) - { - mHead.mForward[mLevel] = NULL; - mUpdate[mLevel] = &mHead; - mLevel = newlevel; - } - - for (level = 0; level < newlevel; level++) - { - snode->mForward[level] = mUpdate[level]->mForward[level]; - mUpdate[level]->mForward[level] = snode; - } - return snode->mData; -} - -template -inline DATA_TYPE &LLSkipMap::getData(const INDEX_TYPE &index) -{ - S32 level; - LLSkipMapNode *current = &mHead; - LLSkipMapNode *temp; - - mNumberOfSteps = 0; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - mNumberOfSteps++; - - if ( (current) - &&(mEquals(current->mIndex, index))) - { - - return current->mData; - } - - // now add the new node - S32 newlevel; - for (newlevel = 1; newlevel <= mLevel && newlevel < BINARY_DEPTH; newlevel++) - { - if (rand() & 1) - break; - } - - LLSkipMapNode *snode = new LLSkipMapNode(index); - - if (newlevel > mLevel) - { - mHead.mForward[mLevel] = NULL; - mUpdate[mLevel] = &mHead; - mLevel = newlevel; - } - - for (level = 0; level < newlevel; level++) - { - snode->mForward[level] = mUpdate[level]->mForward[level]; - mUpdate[level]->mForward[level] = snode; - } - - return snode->mData; -} - -template -inline DATA_TYPE &LLSkipMap::operator[](const INDEX_TYPE &index) -{ - - return getData(index); -} - -// If index present, returns data. -// If index not present, adds and returns NULL. -template -inline DATA_TYPE &LLSkipMap::getData(const INDEX_TYPE &index, BOOL &b_new_entry) -{ - S32 level; - LLSkipMapNode *current = &mHead; - LLSkipMapNode *temp; - - mNumberOfSteps = 0; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - mNumberOfSteps++; - current = *current->mForward; - - if ( (current) - &&(mEquals(current->mIndex, index))) - { - - return current->mData; - } - b_new_entry = TRUE; - addData(index); - - return current->mData; -} - -// Returns TRUE if data present in map. -template -inline BOOL LLSkipMap::checkData(const INDEX_TYPE &index) -{ - S32 level; - LLSkipMapNode *current = &mHead; - LLSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - if (current) - { - // Gets rid of some compiler ambiguity for the LLPointer<> templated class. - if (current->mData) - { - return mEquals(current->mIndex, index); - } - } - - return FALSE; -} - -// Returns TRUE if key is present in map. This is useful if you -// are potentially storing NULL pointers in the map -template -inline BOOL LLSkipMap::checkKey(const INDEX_TYPE &index) -{ - S32 level; - LLSkipMapNode *current = &mHead; - LLSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - if (current) - { - return mEquals(current->mIndex, index); - } - - return FALSE; -} - -// If there, returns the data. -// If not, returns NULL. -// Never adds entries to the map. -template -inline DATA_TYPE LLSkipMap::getIfThere(const INDEX_TYPE &index) -{ - S32 level; - LLSkipMapNode *current = &mHead; - LLSkipMapNode *temp; - - mNumberOfSteps = 0; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - mNumberOfSteps++; - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - mNumberOfSteps++; - current = *current->mForward; - - if (current) - { - if (mEquals(current->mIndex, index)) - { - return current->mData; - } - } - - // Avoid Linux compiler warning on returning NULL. - return DATA_TYPE(); -} - -template -inline INDEX_TYPE LLSkipMap::reverseLookup(const DATA_TYPE datap) -{ - LLSkipMapNode *current = &mHead; - - while (current) - { - if (datap == current->mData) - { - - return current->mIndex; - } - current = *current->mForward; - } - - // not found! return NULL - return INDEX_TYPE(); -} - -// returns number of items in the list -template -inline S32 LLSkipMap::getLength() -{ - U32 length = 0; - for (LLSkipMapNode* temp = *(mHead.mForward); temp != NULL; temp = temp->mForward[0]) - { - length++; - } - - return length; -} - -template -inline BOOL LLSkipMap::removeData(const INDEX_TYPE &index) -{ - S32 level; - LLSkipMapNode *current = &mHead; - LLSkipMapNode *temp; - - // find the pointer one in front of the one we want - if (mInsertFirst) - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(mInsertFirst(temp->mIndex, index))) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - else - { - for (level = mLevel - 1; level >= 0; level--) - { - temp = *(current->mForward + level); - while ( (temp) - &&(temp->mIndex < index)) - { - current = temp; - temp = *(current->mForward + level); - } - *(mUpdate + level) = current; - } - } - - // we're now just in front of where we want to be . . . take one step forward - current = *current->mForward; - - if (!current) - { - // empty list or beyond the end! - - return FALSE; - } - - // is this the one we want? - if (!mEquals(current->mIndex, index)) - { - // nope! - - return FALSE; - } - else - { - // do we need to fix current or currentop? - if (current == mCurrentp) - { - mCurrentp = *current->mForward; - } - - if (current == mCurrentOperatingp) - { - mCurrentOperatingp = *current->mForward; - } - // yes it is! change pointers as required - for (level = 0; level < mLevel; level++) - { - if (*((*(mUpdate + level))->mForward + level) != current) - { - // cool, we've fixed all the pointers! - break; - } - *((*(mUpdate + level))->mForward + level) = *(current->mForward + level); - } - - delete current; - - // clean up mHead - while ( (mLevel > 1) - &&(!*(mHead.mForward + mLevel - 1))) - { - mLevel--; - } - } - - return TRUE; -} - - -// remove all nodes from the list but do not delete data -template -void LLSkipMap::removeAllData() -{ - LLSkipMapNode *temp; - // reset mCurrentp - mCurrentp = *(mHead.mForward); - - while (mCurrentp) - { - temp = mCurrentp->mForward[0]; - delete mCurrentp; - mCurrentp = temp; - } - - S32 i; - for (i = 0; i < BINARY_DEPTH; i++) - { - mHead.mForward[i] = NULL; - mUpdate[i] = NULL; - } - - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - - -// place mCurrentp on first node -template -inline void LLSkipMap::resetList() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); -} - - -// return the data currently pointed to -template -inline DATA_TYPE LLSkipMap::getCurrentDataWithoutIncrement() -{ - if (mCurrentOperatingp) - { - return mCurrentOperatingp->mData; - } - else - { - return DATA_TYPE(); - } -} - -// return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template -inline DATA_TYPE LLSkipMap::getCurrentData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mData; - } - else - { - // Basic types, like int, have default constructors that initialize - // them to zero. g++ 2.95 supports this. "int()" is zero. - // This also is nice for LLUUID() - return DATA_TYPE(); - } -} - -// same as getCurrentData() but a more intuitive name for the operation -template -inline DATA_TYPE LLSkipMap::getNextData() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mData; - } - else - { - // Basic types, like int, have default constructors that initialize - // them to zero. g++ 2.95 supports this. "int()" is zero. - // This also is nice for LLUUID() - return DATA_TYPE(); - } -} - -template -inline INDEX_TYPE LLSkipMap::getNextKey() -{ - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mIndex; - } - else - { - return mHead.mIndex; - } -} - -// return the key currently pointed to -template -inline INDEX_TYPE LLSkipMap::getCurrentKeyWithoutIncrement() -{ - if (mCurrentOperatingp) - { - return mCurrentOperatingp->mIndex; - } - else - { - // See comment for getNextData() - return INDEX_TYPE(); - } -} - -template -inline BOOL LLSkipMap::notDone() const -{ - if (mCurrentOperatingp) - { - return TRUE; - } - else - { - return FALSE; - } -} - - -// remove the Node at mCurentOperatingp -// leave mCurrentp and mCurentOperatingp on the next entry -template -inline void LLSkipMap::removeCurrentData() -{ - if (mCurrentOperatingp) - { - removeData(mCurrentOperatingp->mIndex); - } -} - -template -inline void LLSkipMap::deleteCurrentData() -{ - if (mCurrentOperatingp) - { - deleteData(mCurrentOperatingp->mIndex); - } -} - -// reset the list and return the data currently pointed to, set mCurentOperatingp to that node and bump mCurrentp -template -inline DATA_TYPE LLSkipMap::getFirstData() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mData; - } - else - { - // See comment for getNextData() - return DATA_TYPE(); - } -} - -template -inline INDEX_TYPE LLSkipMap::getFirstKey() -{ - mCurrentp = *(mHead.mForward); - mCurrentOperatingp = *(mHead.mForward); - if (mCurrentp) - { - mCurrentOperatingp = mCurrentp; - mCurrentp = mCurrentp->mForward[0]; - return mCurrentOperatingp->mIndex; - } - else - { - return mHead.mIndex; - } -} - -#endif diff --git a/indra/llcommon/lluuidhashmap.h b/indra/llcommon/lluuidhashmap.h deleted file mode 100644 index e294670030..0000000000 --- a/indra/llcommon/lluuidhashmap.h +++ /dev/null @@ -1,583 +0,0 @@ -/** - * @file lluuidhashmap.h - * @brief A uuid based hash map. - * - * $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_LLUUIDHASHMAP_H -#define LL_LLUUIDHASHMAP_H - -#include "stdtypes.h" -#include "llerror.h" -#include "lluuid.h" - -// UUID hash map - - /* - LLUUIDHashMap foo(test_equals); - LLUUIDHashMapIter bar(&foo); - - LLDynamicArray source_ids; - const S32 COUNT = 100000; - S32 q; - for (q = 0; q < COUNT; q++) - { - llinfos << "Creating" << llendl; - LLUUID id; - id.generate(); - //llinfos << q << ":" << id << llendl; - uuid_pair pair; - pair.mUUID = id; - pair.mValue = q; - foo.set(id, pair); - source_ids.put(id); - //ms_sleep(1); - } - - uuid_pair cur; - llinfos << "Iterating" << llendl; - for (cur = bar.first(); !bar.done(); cur = bar.next()) - { - if (source_ids[cur.mValue] != cur.mUUID) - { - llerrs << "Incorrect value iterated!" << llendl; - } - //llinfos << cur.mValue << ":" << cur.mUUID << llendl; - //ms_sleep(1); - } - - llinfos << "Finding" << llendl; - for (q = 0; q < COUNT; q++) - { - cur = foo.get(source_ids[q]); - if (source_ids[cur.mValue] != cur.mUUID) - { - llerrs << "Incorrect value found!" << llendl; - } - //llinfos << res.mValue << ":" << res.mUUID << llendl; - //ms_sleep(1); - } - - llinfos << "Removing" << llendl; - for (q = 0; q < COUNT/2; q++) - { - if (!foo.remove(source_ids[q])) - { - llerrs << "Remove failed!" << llendl; - } - //ms_sleep(1); - } - - llinfos << "Iterating" << llendl; - for (cur = bar.first(); !bar.done(); cur = bar.next()) - { - if (source_ids[cur.mValue] != cur.mUUID) - { - llerrs << "Incorrect value found!" << llendl; - } - //llinfos << cur.mValue << ":" << cur.mUUID << llendl; - //ms_sleep(1); - } - llinfos << "Done with UUID map test" << llendl; - - return 0; - */ - - -// -// LLUUIDHashNode -// - -template -class LLUUIDHashNode -{ -public: - LLUUIDHashNode(); - -public: - S32 mCount; - U8 mKey[SIZE]; - DATA mData[SIZE]; - LLUUIDHashNode *mNextNodep; -}; - - -// -// LLUUIDHashNode implementation -// -template -LLUUIDHashNode::LLUUIDHashNode() -{ - mCount = 0; - mNextNodep = NULL; -} - - -template -class LLUUIDHashMap -{ -public: - // basic constructor including sorter - LLUUIDHashMap(BOOL (*equals)(const LLUUID &uuid, const DATA_TYPE &data), - const DATA_TYPE &null_data); - ~LLUUIDHashMap(); - - inline DATA_TYPE &get(const LLUUID &uuid); - inline BOOL check(const LLUUID &uuid) const; - inline DATA_TYPE &set(const LLUUID &uuid, const DATA_TYPE &type); - inline BOOL remove(const LLUUID &uuid); - void removeAll(); - - inline S32 getLength() const; // Warning, NOT O(1!) -public: - BOOL (*mEquals)(const LLUUID &uuid, const DATA_TYPE &data); - LLUUIDHashNode mNodes[256]; - - S32 mIterCount; -protected: - DATA_TYPE mNull; -}; - - -// -// LLUUIDHashMap implementation -// - -template -LLUUIDHashMap::LLUUIDHashMap(BOOL (*equals)(const LLUUID &uuid, const DATA_TYPE &data), - const DATA_TYPE &null_data) -: mEquals(equals), - mIterCount(0), - mNull(null_data) -{ } - -template -LLUUIDHashMap::~LLUUIDHashMap() -{ - removeAll(); -} - -template -void LLUUIDHashMap::removeAll() -{ - S32 bin; - for (bin = 0; bin < 256; bin++) - { - LLUUIDHashNode* nodep = &mNodes[bin]; - - BOOL first = TRUE; - while (nodep) - { - 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. - - LLUUIDHashNode* 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; - } - } - } -} - -template -inline S32 LLUUIDHashMap::getLength() const -{ - S32 count = 0; - S32 bin; - for (bin = 0; bin < 256; bin++) - { - LLUUIDHashNode* nodep = (LLUUIDHashNode*) &mNodes[bin]; - while (nodep) - { - count += nodep->mCount; - nodep = nodep->mNextNodep; - } - } - return count; -} - -template -inline DATA_TYPE &LLUUIDHashMap::get(const LLUUID &uuid) -{ - LLUUIDHashNode* nodep = &mNodes[uuid.mData[0]]; - - // Grab the second byte of the UUID, which is the key for the node data - const S32 second_byte = uuid.mData[1]; - while (nodep) - { - S32 i; - const S32 count = nodep->mCount; - - // Iterate through all members of this node - for (i = 0; i < count; i++) - { - if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) - { - // The second byte matched, and our equality test passed. - // We found it. - return nodep->mData[i]; - } - } - - // Done with all objects in this node, go to the next. - nodep = nodep->mNextNodep; - } - return mNull; -} - - -template -inline BOOL LLUUIDHashMap::check(const LLUUID &uuid) const -{ - const LLUUIDHashNode* nodep = &mNodes[uuid.mData[0]]; - - // Grab the second byte of the UUID, which is the key for the node data - const S32 second_byte = uuid.mData[1]; - while (nodep) - { - S32 i; - const S32 count = nodep->mCount; - - // Iterate through all members of this node - for (i = 0; i < count; i++) - { - if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) - { - // The second byte matched, and our equality test passed. - // We found it. - return TRUE; - } - } - - // Done with all objects in this node, go to the next. - nodep = nodep->mNextNodep; - } - - // Didn't find anything - return FALSE; -} - - -template -inline DATA_TYPE &LLUUIDHashMap::set(const LLUUID &uuid, 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. - - LLUUIDHashNode* nodep = &mNodes[uuid.mData[0]]; - - const S32 second_byte = uuid.mData[1]; - while (1) - { - const S32 count = nodep->mCount; - - S32 i; - for (i = 0; i < count; i++) - { - if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) - { - // 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] = second_byte; - 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 LLUUIDHashNode; - nodep->mNextNodep->mKey[0] = second_byte; - 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 -inline BOOL LLUUIDHashMap::remove(const LLUUID &uuid) -{ - if (mIterCount) - { - // We don't allow remove when we're iterating, it's bad karma! - llerrs << "Attempted remove while an outstanding iterator in LLUUIDHashMap!" << llendl; - } - // 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. - - LLUUIDHashNode *nodep = &mNodes[uuid.mData[0]]; - - // Not empty, we need to search through the nodes - const S32 second_byte = uuid.mData[1]; - - // A modification of the standard search algorithm. - while (nodep) - { - const S32 count = nodep->mCount; - - S32 i; - for (i = 0; i < count; i++) - { - if ((nodep->mKey[i] == second_byte) && mEquals(uuid, nodep->mData[i])) - { - // 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. - - LLUUIDHashNode *prevp = &mNodes[uuid.mData[0]]; - LLUUIDHashNode *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[uuid.mData[0]]) - { - // 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; - } - return FALSE; -} - - -// -// LLUUIDHashMapIter -// - -template -class LLUUIDHashMapIter -{ -public: - LLUUIDHashMapIter(LLUUIDHashMap *hash_mapp); - ~LLUUIDHashMapIter(); - - - inline void reset(); - inline void first(); - inline void next(); - inline BOOL done() const; - - DATA_TYPE& operator*() const - { - return mCurHashNodep->mData[mCurHashNodeKey]; - } - DATA_TYPE* operator->() const - { - return &(operator*()); - } - -protected: - LLUUIDHashMap *mHashMapp; - LLUUIDHashNode *mCurHashNodep; - - S32 mCurHashMapNodeNum; - S32 mCurHashNodeKey; - - DATA_TYPE mNull; -}; - - -// -// LLUUIDHashMapIter Implementation -// -template -LLUUIDHashMapIter::LLUUIDHashMapIter(LLUUIDHashMap *hash_mapp) -{ - mHashMapp = hash_mapp; - mCurHashNodep = NULL; - mCurHashMapNodeNum = 0; - mCurHashNodeKey = 0; -} - -template -LLUUIDHashMapIter::~LLUUIDHashMapIter() -{ - reset(); -} - -template -inline void LLUUIDHashMapIter::reset() -{ - if (mCurHashNodep) - { - // We're partway through an iteration, we can clean up now - mHashMapp->mIterCount--; - mCurHashNodep = NULL; - } -} - -template -inline void LLUUIDHashMapIter::first() -{ - // Iterate through until we find the first non-empty node; - S32 i; - for (i = 0; i < 256; i++) - { - if (mHashMapp->mNodes[i].mCount) - { - if (!mCurHashNodep) - { - // Increment, since it's no longer safe for us to do a remove - mHashMapp->mIterCount++; - } - - mCurHashNodep = &mHashMapp->mNodes[i]; - mCurHashMapNodeNum = i; - mCurHashNodeKey = 0; - //return mCurHashNodep->mData[0]; - return; - } - } - - // Completely empty! - mCurHashNodep = NULL; - //return mNull; - return; -} - -template -inline BOOL LLUUIDHashMapIter::done() const -{ - return mCurHashNodep ? FALSE : TRUE; -} - -template -inline void LLUUIDHashMapIter::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; -} - -#endif // LL_LLUUIDHASHMAP_H diff --git a/indra/newview/llviewerprecompiledheaders.h b/indra/newview/llviewerprecompiledheaders.h index 0316f79973..cafe28356d 100644 --- a/indra/newview/llviewerprecompiledheaders.h +++ b/indra/newview/llviewerprecompiledheaders.h @@ -83,7 +83,6 @@ #include "llsys.h" #include "llthread.h" #include "lltimer.h" -#include "lluuidhashmap.h" #include "stdenums.h" #include "stdtypes.h" #include "timing.h" diff --git a/indra/test/CMakeLists.txt b/indra/test/CMakeLists.txt index 816f1d7175..271b7fe647 100644 --- a/indra/test/CMakeLists.txt +++ b/indra/test/CMakeLists.txt @@ -52,7 +52,6 @@ set(test_SOURCE_FILES llstreamtools_tut.cpp lltemplatemessagebuilder_tut.cpp lltut.cpp - lluuidhashmap_tut.cpp message_tut.cpp test.cpp ) diff --git a/indra/test/lluuidhashmap_tut.cpp b/indra/test/lluuidhashmap_tut.cpp deleted file mode 100644 index 9712a613f4..0000000000 --- a/indra/test/lluuidhashmap_tut.cpp +++ /dev/null @@ -1,455 +0,0 @@ -/** - * @file lluuidhashmap_tut.cpp - * @author Adroit - * @date 2007-02 - * @brief Test cases for LLUUIDHashMap - * - * $LicenseInfo:firstyear=2007&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$ - */ - -#include -#include "linden_common.h" -#include "lluuidhashmap.h" -#include "llsdserialize.h" -#include "lldir.h" -#include "stringize.h" -#include -#include - -namespace tut -{ - class UUIDTableEntry - { - public: - UUIDTableEntry() - { - mID.setNull(); - mValue = 0; - } - - UUIDTableEntry(const LLUUID& id, U32 value) - { - mID = id; - mValue = value; - } - - ~UUIDTableEntry(){}; - - static BOOL uuidEq(const LLUUID &uuid, const UUIDTableEntry &id_pair) - { - if (uuid == id_pair.mID) - { - return TRUE; - } - return FALSE; - } - - const LLUUID& getID() { return mID; } - const U32& getValue() { return mValue; } - - protected: - LLUUID mID; - U32 mValue; - }; - - struct hashmap_test - { - }; - - typedef test_group hash_index_t; - typedef hash_index_t::object hash_index_object_t; - tut::hash_index_t tut_hash_index("hashmap_test"); - - // stress test - template<> template<> - void hash_index_object_t::test<1>() - { - set_test_name("stress test"); - // As of 2012-10-10, I (nat) have observed sporadic failures of this - // test: "set/get did not work." The trouble is that since test data - // are randomly generated with every run, it is impossible to debug a - // test failure. One is left with the uneasy suspicion that - // LLUUID::generate() can sometimes produce duplicates even within the - // moderately small number requested here. Since rerunning the test - // generally allows it to pass, it's too easy to shrug and forget it. - // The following code is intended to support reproducing such test - // failures. The idea is that, on test failure, we save the generated - // data to a canonical filename in a temp directory. Then on every - // subsequent run, we check for that filename. If it exists, we reload - // that specific data rather than generating fresh data -- which - // should presumably reproduce the same test failure. But we inform - // the user that to resume normal (random) test runs, s/he need only - // delete that file. And since it's in a temp directory, sooner or - // later the system will clean it up anyway. - const char* tempvar = "TEMP"; - const char* tempdir = getenv(tempvar); // Windows convention - if (! tempdir) - { - tempvar = "TMPDIR"; - tempdir = getenv(tempvar); // Mac convention - } - if (! tempdir) - { - // reset tempvar to the first var we check; it's just a - // recommendation - tempvar = "TEMP"; - tempdir = "/tmp"; // Posix in general - } - std::string savefile(gDirUtilp->add(tempdir, "lluuidhashmap_tut.save.txt")); - const int numElementsToCheck = 32*256*32; - std::vector idList; - if ((! getenv("TEAMCITY_PROJECT_NAME")) && gDirUtilp->fileExists(savefile)) - { - // This is not a TeamCity build, and we have saved data from a - // previous failed run. Reload that data. - std::ifstream inf(savefile.c_str()); - if (! inf.is_open()) - { - fail(STRINGIZE("Although save file '" << savefile << "' exists, it cannot be opened")); - } - std::string item; - while (std::getline(inf, item)) - { - idList.push_back(LLUUID(item)); - } - std::cout << "Reloaded " << idList.size() << " items from '" << savefile << "'"; - if (idList.size() != numElementsToCheck) - { - std::cout << " (expected " << numElementsToCheck << ")"; - } - std::cout << " -- delete this file to generate new data" << std::endl; - } - else - { - // This is a TeamCity build, or (normal case) savefile does not - // exist: regenerate idList from scratch. - for (int i = 0; i < numElementsToCheck; ++i) - { - LLUUID id; - id.generate(); - idList.push_back(id); - } - } - - LLUUIDHashMap hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - int i; - - for (i = 0; i < idList.size(); ++i) - { - UUIDTableEntry entry(idList[i], i); - hashTable.set(idList[i], entry); - } - - try - { - for (i = 0; i < idList.size(); i++) - { - LLUUID idToCheck = idList[i]; - UUIDTableEntry entryToCheck = hashTable.get(idToCheck); - ensure_equals(STRINGIZE("set/get ID (entry " << i << ")").c_str(), - entryToCheck.getID(), idToCheck); - ensure_equals(STRINGIZE("set/get value (ID " << idToCheck << ")").c_str(), - entryToCheck.getValue(), (size_t)i); - } - - for (i = 0; i < idList.size(); i++) - { - LLUUID idToCheck = idList[i]; - if (i % 2 != 0) - { - hashTable.remove(idToCheck); - } - } - - for (i = 0; i < idList.size(); i++) - { - LLUUID idToCheck = idList[i]; - ensure("remove or check did not work", (i % 2 == 0 && hashTable.check(idToCheck)) || (i % 2 != 0 && !hashTable.check(idToCheck))); - } - } - catch (const failure&) - { - // One of the above tests failed. Try to save idList to repro with - // a later run. - std::ofstream outf(savefile.c_str()); - if (! outf.is_open()) - { - // Sigh, don't use fail() here because we want to preserve - // the original test failure. - std::cout << "Cannot open file '" << savefile - << "' to save data -- check and fix " << tempvar << std::endl; - } - else - { - // outf.is_open() - for (int i = 0; i < idList.size(); ++i) - { - outf << idList[i] << std::endl; - } - std::cout << "Saved " << idList.size() << " entries to '" << savefile - << "' -- rerun test to debug with these" << std::endl; - } - // re-raise the same exception -- we WANT this test failure to - // be reported! We just needed to save the data on the way out. - throw; - } - } - - // test removing all but one element. - template<> template<> - void hash_index_object_t::test<2>() - { - LLUUIDHashMap hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 5; - std::vector idList(numElementsToCheck*10); - int i; - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - } - - ensure("getLength failed", hashTable.getLength() == numElementsToCheck); - - // remove all but the last element - for (i = 0; i < numElementsToCheck-1; i++) - { - LLUUID idToCheck = idList[i]; - hashTable.remove(idToCheck); - } - - // there should only be one element left now. - ensure("getLength failed", hashTable.getLength() == 1); - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID idToCheck = idList[i]; - if (i != numElementsToCheck - 1) - { - ensure("remove did not work", hashTable.check(idToCheck) == FALSE); - } - else - { - UUIDTableEntry entryToCheck = hashTable.get(idToCheck); - ensure("remove did not work", entryToCheck.getID() == idToCheck && entryToCheck.getValue() == (size_t)i); - } - } - } - - // test overriding of value already set. - template<> template<> - void hash_index_object_t::test<3>() - { - LLUUIDHashMap hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 10; - std::vector idList(numElementsToCheck); - int i; - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - } - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id = idList[i]; - // set new entry with value = i+numElementsToCheck - UUIDTableEntry entry(id, i+numElementsToCheck); - hashTable.set(id, entry); - } - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID idToCheck = idList[i]; - UUIDTableEntry entryToCheck = hashTable.get(idToCheck); - ensure("set/get did not work", entryToCheck.getID() == idToCheck && entryToCheck.getValue() == (size_t)(i+numElementsToCheck)); - } - } - - // test removeAll() - template<> template<> - void hash_index_object_t::test<4>() - { - LLUUIDHashMap hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 10; - std::vector idList(numElementsToCheck); - int i; - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - } - - hashTable.removeAll(); - ensure("removeAll failed", hashTable.getLength() == 0); - } - - - // test sparse map - force it by creating 256 entries that fall into 256 different nodes - template<> template<> - void hash_index_object_t::test<5>() - { - LLUUIDHashMap hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - const int numElementsToCheck = 256; - std::vector idList(numElementsToCheck); - int i; - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - // LLUUIDHashMap uses mData[0] to pick the bucket - // overwrite mData[0] so that it ranges from 0 to 255 - id.mData[0] = i; - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - } - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID idToCheck = idList[i]; - UUIDTableEntry entryToCheck = hashTable.get(idToCheck); - ensure("set/get did not work for sparse map", entryToCheck.getID() == idToCheck && entryToCheck.getValue() == (size_t)i); - } - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID idToCheck = idList[i]; - if (i % 2 != 0) - { - hashTable.remove(idToCheck); - } - } - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID idToCheck = idList[i]; - ensure("remove or check did not work for sparse map", (i % 2 == 0 && hashTable.check(idToCheck)) || (i % 2 != 0 && !hashTable.check(idToCheck))); - } - } - - // iterator - template<> template<> - void hash_index_object_t::test<6>() - { - LLUUIDHashMap hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - LLUUIDHashMapIter hashIter(&hashTable); - const int numElementsToCheck = 256; - std::vector idList(numElementsToCheck); - int i; - - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - // LLUUIDHashMap uses mData[0] to pick the bucket - // overwrite mData[0] so that it ranges from 0 to 255 - // to create a sparse map - id.mData[0] = i; - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - } - - hashIter.first(); - int numElementsIterated = 0; - while(!hashIter.done()) - { - numElementsIterated++; - UUIDTableEntry tableEntry = *hashIter; - LLUUID id = tableEntry.getID(); - hashIter.next(); - ensure("Iteration failed for sparse map", tableEntry.getValue() < (size_t)numElementsToCheck && idList[tableEntry.getValue()] == tableEntry.getID()); - } - - ensure("iteration count failed", numElementsIterated == numElementsToCheck); - } - - // remove after middle of iteration - template<> template<> - void hash_index_object_t::test<7>() - { - LLUUIDHashMap hashTable(UUIDTableEntry::uuidEq, UUIDTableEntry()); - LLUUIDHashMapIter hashIter(&hashTable); - const int numElementsToCheck = 256; - std::vector idList(numElementsToCheck); - int i; - - LLUUID uuidtoSearch; - for (i = 0; i < numElementsToCheck; i++) - { - LLUUID id; - id.generate(); - // LLUUIDHashMap uses mData[0] to pick the bucket - // overwrite mData[0] so that it ranges from 0 to 255 - // to create a sparse map - id.mData[0] = i; - UUIDTableEntry entry(id, i); - hashTable.set(id, entry); - idList[i] = id; - - // pick uuid somewhere in the middle - if (i == 5) - { - uuidtoSearch = id; - } - } - - hashIter.first(); - int numElementsIterated = 0; - while(!hashIter.done()) - { - numElementsIterated++; - UUIDTableEntry tableEntry = *hashIter; - LLUUID id = tableEntry.getID(); - if (uuidtoSearch == id) - { - break; - } - hashIter.next(); - } - - // current iterator implementation will not allow any remove operations - // until ALL elements have been iterated over. this seems to be - // an unnecessary restriction. Iterator should have a method to - // reset() its state so that further operations (inckuding remove) - // can be performed on the HashMap without having to iterate thru - // all the remaining nodes. - -// hashIter.reset(); -// hashTable.remove(uuidtoSearch); -// ensure("remove after iteration reset failed", hashTable.check(uuidtoSearch) == FALSE); - } -} -- cgit v1.3