From 9d77e030d9a0d23cebce616631677459eec1612c Mon Sep 17 00:00:00 2001 From: Richard Linden Date: Wed, 14 Nov 2012 23:52:27 -0800 Subject: SH-3406 WIP convert fast timers to lltrace system cleaning up build moved most includes of windows.h to llwin32headers.h to disable min/max macros, etc streamlined Time class and consolidated functionality in BlockTimer class llfasttimer is no longer included via llstring.h, so had to add it manually in several places --- indra/llcharacter/llcharacter.cpp | 1 + indra/llcharacter/lljoint.h | 1 + indra/llcharacter/llmotioncontroller.cpp | 3 ++- 3 files changed, 4 insertions(+), 1 deletion(-) (limited to 'indra/llcharacter') diff --git a/indra/llcharacter/llcharacter.cpp b/indra/llcharacter/llcharacter.cpp index 0a6a8f9fa6..5138be0711 100644 --- a/indra/llcharacter/llcharacter.cpp +++ b/indra/llcharacter/llcharacter.cpp @@ -32,6 +32,7 @@ #include "llcharacter.h" #include "llstring.h" +#include "llfasttimer.h" #define SKEL_HEADER "Linden Skeleton 1.0" diff --git a/indra/llcharacter/lljoint.h b/indra/llcharacter/lljoint.h index dc3c58cf64..a9cde545f2 100644 --- a/indra/llcharacter/lljoint.h +++ b/indra/llcharacter/lljoint.h @@ -31,6 +31,7 @@ // Header Files //----------------------------------------------------------------------------- #include +#include #include "linked_lists.h" #include "v3math.h" diff --git a/indra/llcharacter/llmotioncontroller.cpp b/indra/llcharacter/llmotioncontroller.cpp index 829dda9993..5524bba296 100644 --- a/indra/llcharacter/llmotioncontroller.cpp +++ b/indra/llcharacter/llmotioncontroller.cpp @@ -28,8 +28,9 @@ // Header Files //----------------------------------------------------------------------------- #include "linden_common.h" - #include "llmotioncontroller.h" + +#include "llfasttimer.h" #include "llkeyframemotion.h" #include "llmath.h" #include "lltimer.h" -- cgit v1.3 From 8de397b19ec9e2f6206fd5ae57dba96c70e78b74 Mon Sep 17 00:00:00 2001 From: Richard Linden Date: Mon, 18 Mar 2013 08:43:03 -0700 Subject: SH-3931 WIP Interesting: Add graphs to visualize scene load metrics changed LLCriticalDamp to LLSmoothInterpolation and sped up interpolator lookup improvements to stats display of llstatbar added scene load stats floater accessed with ctrl|shift|2 --- indra/llcharacter/lleditingmotion.cpp | 2 +- indra/llcharacter/llheadrotmotion.cpp | 4 +- indra/llcharacter/llkeyframemotion.cpp | 8 +- indra/llcharacter/llkeyframewalkmotion.cpp | 10 +- indra/llcharacter/llmotion.cpp | 4 +- indra/llcharacter/lltargetingmotion.cpp | 2 +- indra/llcommon/llcriticaldamp.cpp | 77 ++- indra/llcommon/llcriticaldamp.h | 32 +- indra/llcommon/lltracerecording.cpp | 17 - indra/llcommon/lltracerecording.h | 8 - indra/llui/llbutton.cpp | 4 +- indra/llui/lllayoutstack.cpp | 6 +- indra/llui/llmenugl.cpp | 2 +- indra/llui/llscrollbar.cpp | 4 +- indra/llui/llstatbar.cpp | 131 +++-- indra/llui/llstatbar.h | 12 +- indra/llui/lltabcontainer.cpp | 2 +- indra/newview/llagentcamera.cpp | 14 +- indra/newview/llappviewer.cpp | 4 +- indra/newview/lldrawable.cpp | 2 +- indra/newview/llfasttimerview.cpp | 6 +- indra/newview/llfloatercolorpicker.cpp | 4 +- indra/newview/llfloatersnapshot.cpp | 4 +- indra/newview/llfolderviewitem.cpp | 6 +- indra/newview/llfollowcam.cpp | 10 +- indra/newview/llhudnametag.cpp | 2 +- indra/newview/llmaniprotate.cpp | 18 +- indra/newview/llmanipscale.cpp | 4 +- indra/newview/llmaniptranslate.cpp | 12 +- indra/newview/llnetmap.cpp | 2 +- indra/newview/lltexturectrl.cpp | 4 +- indra/newview/llviewerdisplay.cpp | 2 +- indra/newview/llviewerfloaterreg.cpp | 1 + indra/newview/llviewerstats.cpp | 4 +- indra/newview/llviewerstats.h | 4 +- indra/newview/llvoavatar.cpp | 8 +- indra/newview/llworldmapview.cpp | 4 +- .../default/xui/en/floater_scene_load_stats.xml | 549 +++++++++++++++++++++ .../newview/skins/default/xui/en/floater_stats.xml | 49 -- indra/newview/skins/default/xui/en/menu_viewer.xml | 8 + 40 files changed, 827 insertions(+), 219 deletions(-) create mode 100644 indra/newview/skins/default/xui/en/floater_scene_load_stats.xml (limited to 'indra/llcharacter') diff --git a/indra/llcharacter/lleditingmotion.cpp b/indra/llcharacter/lleditingmotion.cpp index 0d0b85ba60..ff7ad1c289 100644 --- a/indra/llcharacter/lleditingmotion.cpp +++ b/indra/llcharacter/lleditingmotion.cpp @@ -232,7 +232,7 @@ BOOL LLEditingMotion::onUpdate(F32 time, U8* joint_mask) mIKSolver.solve(); // use blending... - F32 slerp_amt = LLCriticalDamp::getInterpolant(TARGET_LAG_HALF_LIFE); + F32 slerp_amt = LLSmoothInterpolation::getInterpolant(TARGET_LAG_HALF_LIFE); shoulderRot = slerp(slerp_amt, mShoulderJoint.getRotation(), shoulderRot); elbowRot = slerp(slerp_amt, mElbowJoint.getRotation(), elbowRot); diff --git a/indra/llcharacter/llheadrotmotion.cpp b/indra/llcharacter/llheadrotmotion.cpp index 15a58a8389..4a8af2f00c 100644 --- a/indra/llcharacter/llheadrotmotion.cpp +++ b/indra/llcharacter/llheadrotmotion.cpp @@ -182,8 +182,8 @@ BOOL LLHeadRotMotion::onUpdate(F32 time, U8* joint_mask) LLQuaternion currentRootRotWorld = mRootJoint->getWorldRotation(); LLQuaternion currentInvRootRotWorld = ~currentRootRotWorld; - F32 head_slerp_amt = LLCriticalDamp::getInterpolant(HEAD_LOOKAT_LAG_HALF_LIFE); - F32 torso_slerp_amt = LLCriticalDamp::getInterpolant(TORSO_LOOKAT_LAG_HALF_LIFE); + F32 head_slerp_amt = LLSmoothInterpolation::getInterpolant(HEAD_LOOKAT_LAG_HALF_LIFE); + F32 torso_slerp_amt = LLSmoothInterpolation::getInterpolant(TORSO_LOOKAT_LAG_HALF_LIFE); LLVector3* targetPos = (LLVector3*)mCharacter->getAnimationData("LookAtPoint"); diff --git a/indra/llcharacter/llkeyframemotion.cpp b/indra/llcharacter/llkeyframemotion.cpp index c6f45bffa2..831a0a6719 100644 --- a/indra/llcharacter/llkeyframemotion.cpp +++ b/indra/llcharacter/llkeyframemotion.cpp @@ -1031,11 +1031,11 @@ void LLKeyframeMotion::applyConstraint(JointConstraint* constraint, F32 time, U8 if (constraint->mSharedData->mChainLength != 0 && dist_vec_squared(root_pos, target_pos) * 0.95f > constraint->mTotalLength * constraint->mTotalLength) { - constraint->mWeight = lerp(constraint->mWeight, 0.f, LLCriticalDamp::getInterpolant(0.1f)); + constraint->mWeight = LLSmoothInterpolation::lerp(constraint->mWeight, 0.f, 0.1f); } else { - constraint->mWeight = lerp(constraint->mWeight, 1.f, LLCriticalDamp::getInterpolant(0.3f)); + constraint->mWeight = LLSmoothInterpolation::lerp(constraint->mWeight, 1.f, 0.3f); } F32 weight = constraint->mWeight * ((shared_data->mEaseOutStopTime == 0.f) ? 1.f : @@ -1082,9 +1082,9 @@ void LLKeyframeMotion::applyConstraint(JointConstraint* constraint, F32 time, U8 // convert intermediate joint positions to world coordinates positions[joint_num] = ( constraint->mPositions[joint_num] * mPelvisp->getWorldRotation()) + mPelvisp->getWorldPosition(); F32 time_constant = 1.f / clamp_rescale(constraint->mFixupDistanceRMS, 0.f, 0.5f, 0.2f, 8.f); -// llinfos << "Interpolant " << LLCriticalDamp::getInterpolant(time_constant, FALSE) << " and fixup distance " << constraint->mFixupDistanceRMS << " on " << mCharacter->findCollisionVolume(shared_data->mSourceConstraintVolume)->getName() << llendl; +// llinfos << "Interpolant " << LLSmoothInterpolation::getInterpolant(time_constant, FALSE) << " and fixup distance " << constraint->mFixupDistanceRMS << " on " << mCharacter->findCollisionVolume(shared_data->mSourceConstraintVolume)->getName() << llendl; positions[joint_num] = lerp(positions[joint_num], kinematic_position, - LLCriticalDamp::getInterpolant(time_constant, FALSE)); + LLSmoothInterpolation::getInterpolant(time_constant, FALSE)); } S32 iteration_count; diff --git a/indra/llcharacter/llkeyframewalkmotion.cpp b/indra/llcharacter/llkeyframewalkmotion.cpp index d52eb89a5c..e188b06c03 100644 --- a/indra/llcharacter/llkeyframewalkmotion.cpp +++ b/indra/llcharacter/llkeyframewalkmotion.cpp @@ -258,7 +258,7 @@ BOOL LLWalkAdjustMotion::onUpdate(F32 time, U8* joint_mask) // but this will cause the animation playback rate calculation below to // kick in too slowly and sometimes start playing the animation in reverse. - //mPelvisOffset -= PELVIS_COMPENSATION_WIEGHT * (foot_slip_vector * world_to_avatar_rot);//lerp(LLVector3::zero, -1.f * (foot_slip_vector * world_to_avatar_rot), LLCriticalDamp::getInterpolant(0.1f)); + //mPelvisOffset -= PELVIS_COMPENSATION_WIEGHT * (foot_slip_vector * world_to_avatar_rot);//lerp(LLVector3::zero, -1.f * (foot_slip_vector * world_to_avatar_rot), LLSmoothInterpolation::getInterpolant(0.1f)); ////F32 drift_comp_max = DRIFT_COMP_MAX_TOTAL * (llclamp(speed, 0.f, DRIFT_COMP_MAX_SPEED) / DRIFT_COMP_MAX_SPEED); //F32 drift_comp_max = DRIFT_COMP_MAX_TOTAL; @@ -287,7 +287,7 @@ BOOL LLWalkAdjustMotion::onUpdate(F32 time, U8* joint_mask) F32 desired_speed_multiplier = llclamp(speed / foot_speed, min_speed_multiplier, ANIM_SPEED_MAX); // blend towards new speed adjustment value - F32 new_speed_adjust = lerp(mAdjustedSpeed, desired_speed_multiplier, LLCriticalDamp::getInterpolant(SPEED_ADJUST_TIME_CONSTANT)); + F32 new_speed_adjust = LLSmoothInterpolation::lerp(mAdjustedSpeed, desired_speed_multiplier, SPEED_ADJUST_TIME_CONSTANT); // limit that rate at which the speed adjustment changes F32 speedDelta = llclamp(new_speed_adjust - mAdjustedSpeed, -SPEED_ADJUST_MAX_SEC * delta_time, SPEED_ADJUST_MAX_SEC * delta_time); @@ -305,8 +305,8 @@ BOOL LLWalkAdjustMotion::onUpdate(F32 time, U8* joint_mask) { // standing/turning // damp out speed adjustment to 0 - mAnimSpeed = lerp(mAnimSpeed, 1.f, LLCriticalDamp::getInterpolant(0.2f)); - //mPelvisOffset = lerp(mPelvisOffset, LLVector3::zero, LLCriticalDamp::getInterpolant(0.2f)); + mAnimSpeed = LLSmoothInterpolation::lerp(mAnimSpeed, 1.f, 0.2f); + //mPelvisOffset = lerp(mPelvisOffset, LLVector3::zero, LLSmoothInterpolation::getInterpolant(0.2f)); } // broadcast walk speed change @@ -383,7 +383,7 @@ BOOL LLFlyAdjustMotion::onUpdate(F32 time, U8* joint_mask) F32 target_roll = llclamp(ang_vel.mV[VZ], -4.f, 4.f) * roll_factor; // roll is critically damped interpolation between current roll and angular velocity-derived target roll - mRoll = lerp(mRoll, target_roll, LLCriticalDamp::getInterpolant(0.1f)); + mRoll = LLSmoothInterpolation::lerp(mRoll, target_roll, LLUnit(100)); LLQuaternion roll(mRoll, LLVector3(0.f, 0.f, 1.f)); mPelvisState->setRotation(roll); diff --git a/indra/llcharacter/llmotion.cpp b/indra/llcharacter/llmotion.cpp index 2551f125d0..af2e10220a 100644 --- a/indra/llcharacter/llmotion.cpp +++ b/indra/llcharacter/llmotion.cpp @@ -73,7 +73,7 @@ void LLMotion::fadeOut() { if (mFadeWeight > 0.01f) { - mFadeWeight = lerp(mFadeWeight, 0.f, LLCriticalDamp::getInterpolant(0.15f)); + mFadeWeight = lerp(mFadeWeight, 0.f, LLSmoothInterpolation::getInterpolant(0.15f)); } else { @@ -88,7 +88,7 @@ void LLMotion::fadeIn() { if (mFadeWeight < 0.99f) { - mFadeWeight = lerp(mFadeWeight, 1.f, LLCriticalDamp::getInterpolant(0.15f)); + mFadeWeight = lerp(mFadeWeight, 1.f, LLSmoothInterpolation::getInterpolant(0.15f)); } else { diff --git a/indra/llcharacter/lltargetingmotion.cpp b/indra/llcharacter/lltargetingmotion.cpp index 489aef923c..633c1d51eb 100644 --- a/indra/llcharacter/lltargetingmotion.cpp +++ b/indra/llcharacter/lltargetingmotion.cpp @@ -106,7 +106,7 @@ BOOL LLTargetingMotion::onActivate() //----------------------------------------------------------------------------- BOOL LLTargetingMotion::onUpdate(F32 time, U8* joint_mask) { - F32 slerp_amt = LLCriticalDamp::getInterpolant(TORSO_TARGET_HALF_LIFE); + F32 slerp_amt = LLSmoothInterpolation::getInterpolant(TORSO_TARGET_HALF_LIFE); LLVector3 target; LLVector3* lookAtPoint = (LLVector3*)mCharacter->getAnimationData("LookAtPoint"); diff --git a/indra/llcommon/llcriticaldamp.cpp b/indra/llcommon/llcriticaldamp.cpp index 87d79b1ee0..59a31bf9df 100644 --- a/indra/llcommon/llcriticaldamp.cpp +++ b/indra/llcommon/llcriticaldamp.cpp @@ -27,18 +27,38 @@ #include "linden_common.h" #include "llcriticaldamp.h" +#include //----------------------------------------------------------------------------- // static members //----------------------------------------------------------------------------- -LLFrameTimer LLCriticalDamp::sInternalTimer; -std::map LLCriticalDamp::sInterpolants; -F32 LLCriticalDamp::sTimeDelta; +LLFrameTimer LLSmoothInterpolation::sInternalTimer; +std::vector LLSmoothInterpolation::sInterpolants; +F32 LLSmoothInterpolation::sTimeDelta; + +// helper functors +struct LLSmoothInterpolation::CompareTimeConstants +{ + bool operator()(const F32& a, const LLSmoothInterpolation::Interpolant& b) const + { + return a < b.mTimeScale; + } + + bool operator()(const LLSmoothInterpolation::Interpolant& a, const F32& b) const + { + return a.mTimeScale < b; // bottom of a is higher than bottom of b + } + + bool operator()(const LLSmoothInterpolation::Interpolant& a, const LLSmoothInterpolation::Interpolant& b) const + { + return a.mTimeScale < b.mTimeScale; // bottom of a is higher than bottom of b + } +}; //----------------------------------------------------------------------------- -// LLCriticalDamp() +// LLSmoothInterpolation() //----------------------------------------------------------------------------- -LLCriticalDamp::LLCriticalDamp() +LLSmoothInterpolation::LLSmoothInterpolation() { sTimeDelta = 0.f; } @@ -47,43 +67,54 @@ LLCriticalDamp::LLCriticalDamp() //----------------------------------------------------------------------------- // updateInterpolants() //----------------------------------------------------------------------------- -void LLCriticalDamp::updateInterpolants() +void LLSmoothInterpolation::updateInterpolants() { sTimeDelta = sInternalTimer.getElapsedTimeAndResetF32(); - F32 time_constant; - - for (std::map::iterator iter = sInterpolants.begin(); - iter != sInterpolants.end(); iter++) + for (S32 i = 0; i < sInterpolants.size(); i++) { - time_constant = iter->first; - F32 new_interpolant = 1.f - pow(2.f, -sTimeDelta / time_constant); - new_interpolant = llclamp(new_interpolant, 0.f, 1.f); - sInterpolants[time_constant] = new_interpolant; + Interpolant& interp = sInterpolants[i]; + interp.mInterpolant = calcInterpolant(interp.mTimeScale); } } //----------------------------------------------------------------------------- // getInterpolant() //----------------------------------------------------------------------------- -F32 LLCriticalDamp::getInterpolant(const F32 time_constant, BOOL use_cache) +F32 LLSmoothInterpolation::getInterpolant(LLUnit time_constant, bool use_cache) { if (time_constant == 0.f) { return 1.f; } - if (use_cache && sInterpolants.count(time_constant)) + if (use_cache) { - return sInterpolants[time_constant]; + interpolant_vec_t::iterator find_it = std::lower_bound(sInterpolants.begin(), sInterpolants.end(), time_constant.value(), CompareTimeConstants()); + if (find_it != sInterpolants.end() && find_it->mTimeScale == time_constant) + { + return find_it->mInterpolant; + } + else + { + Interpolant interp; + interp.mTimeScale = time_constant.value(); + interp.mInterpolant = calcInterpolant(time_constant.value()); + sInterpolants.insert(find_it, interp); + return interp.mInterpolant; + } } - - F32 interpolant = 1.f - pow(2.f, -sTimeDelta / time_constant); - interpolant = llclamp(interpolant, 0.f, 1.f); - if (use_cache) + else { - sInterpolants[time_constant] = interpolant; + return calcInterpolant(time_constant.value()); + } +} - return interpolant; +//----------------------------------------------------------------------------- +// getInterpolant() +//----------------------------------------------------------------------------- +F32 LLSmoothInterpolation::calcInterpolant(F32 time_constant) +{ + return llclamp(1.f - pow(2.f, -sTimeDelta / time_constant), 0.f, 1.f); } diff --git a/indra/llcommon/llcriticaldamp.h b/indra/llcommon/llcriticaldamp.h index 52f052ae25..ab5d4ba6e2 100644 --- a/indra/llcommon/llcriticaldamp.h +++ b/indra/llcommon/llcriticaldamp.h @@ -28,26 +28,46 @@ #ifndef LL_LLCRITICALDAMP_H #define LL_LLCRITICALDAMP_H -#include +#include #include "llframetimer.h" +#include "llunit.h" -class LL_COMMON_API LLCriticalDamp +class LL_COMMON_API LLSmoothInterpolation { public: - LLCriticalDamp(); + LLSmoothInterpolation(); // MANIPULATORS static void updateInterpolants(); // ACCESSORS - static F32 getInterpolant(const F32 time_constant, BOOL use_cache = TRUE); + static F32 getInterpolant(LLUnit time_constant, bool use_cache = true); -protected: + template + static T lerp(T a, T b, LLUnit time_constant, bool use_cache = true) + { + F32 interpolant = getInterpolant(time_constant, use_cache); + return ((a * (1.f - interpolant)) + + (b * interpolant)); + } + +protected: + static F32 calcInterpolant(F32 time_constant); + + struct CompareTimeConstants; static LLFrameTimer sInternalTimer; // frame timer for calculating deltas - static std::map sInterpolants; + struct Interpolant + { + F32 mTimeScale; + F32 mInterpolant; + }; + typedef std::vector interpolant_vec_t; + static interpolant_vec_t sInterpolants; static F32 sTimeDelta; }; +typedef LLSmoothInterpolation LLCriticalDamp; + #endif // LL_LLCRITICALDAMP_H diff --git a/indra/llcommon/lltracerecording.cpp b/indra/llcommon/lltracerecording.cpp index 6695ebeaca..259f5a7a27 100644 --- a/indra/llcommon/lltracerecording.cpp +++ b/indra/llcommon/lltracerecording.cpp @@ -291,23 +291,6 @@ U32 Recording::getSampleCount( const TraceType >& stat ) c return (*mMeasurementsFloat)[stat.getIndex()].getSampleCount(); } - -F64 Recording::getPerSec( const TraceType >& stat ) const -{ - F64 sum = (*mMeasurementsFloat)[stat.getIndex()].getSum(); - return (sum != 0.0) - ? (sum / mElapsedSeconds) - : 0.0; -} - -F64 Recording::getPerSec( const TraceType >& stat ) const -{ - S64 sum = (*mMeasurements)[stat.getIndex()].getSum(); - return (sum != 0) - ? ((F64)sum / mElapsedSeconds) - : 0.0; -} - F64 Recording::getMin( const TraceType >& stat ) const { return (*mMeasurementsFloat)[stat.getIndex()].getMin(); diff --git a/indra/llcommon/lltracerecording.h b/indra/llcommon/lltracerecording.h index 70afe51d6e..751ff298ce 100644 --- a/indra/llcommon/lltracerecording.h +++ b/indra/llcommon/lltracerecording.h @@ -184,14 +184,6 @@ namespace LLTrace return (T)getSum(static_cast::type_t> >&> (stat)); } - F64 getPerSec(const TraceType >& stat) const; - F64 getPerSec(const TraceType >& stat) const; - template - T getPerSec(const MeasurementStatHandle& stat) const - { - return (T)getPerSec(static_cast::type_t> >&> (stat)); - } - F64 getMin(const TraceType >& stat) const; S64 getMin(const TraceType >& stat) const; template diff --git a/indra/llui/llbutton.cpp b/indra/llui/llbutton.cpp index 705fe16559..93ffa7b70d 100644 --- a/indra/llui/llbutton.cpp +++ b/indra/llui/llbutton.cpp @@ -758,11 +758,11 @@ void LLButton::draw() mCurGlowStrength = lerp(mCurGlowStrength, mFlashing ? (flash? 1.0 : 0.0) : mHoverGlowStrength, - LLCriticalDamp::getInterpolant(0.05f)); + LLSmoothInterpolation::getInterpolant(0.05f)); } else { - mCurGlowStrength = lerp(mCurGlowStrength, 0.f, LLCriticalDamp::getInterpolant(0.05f)); + mCurGlowStrength = lerp(mCurGlowStrength, 0.f, LLSmoothInterpolation::getInterpolant(0.05f)); } // Draw button image, if available. diff --git a/indra/llui/lllayoutstack.cpp b/indra/llui/lllayoutstack.cpp index 194d2b700c..d4a310b8cf 100644 --- a/indra/llui/lllayoutstack.cpp +++ b/indra/llui/lllayoutstack.cpp @@ -586,7 +586,7 @@ bool LLLayoutStack::animatePanels() { if (!mAnimatedThisFrame) { - panelp->mVisibleAmt = lerp(panelp->mVisibleAmt, 1.f, LLCriticalDamp::getInterpolant(mOpenTimeConstant)); + panelp->mVisibleAmt = lerp(panelp->mVisibleAmt, 1.f, LLSmoothInterpolation::getInterpolant(mOpenTimeConstant)); if (panelp->mVisibleAmt > 0.99f) { panelp->mVisibleAmt = 1.f; @@ -611,7 +611,7 @@ bool LLLayoutStack::animatePanels() { if (!mAnimatedThisFrame) { - panelp->mVisibleAmt = lerp(panelp->mVisibleAmt, 0.f, LLCriticalDamp::getInterpolant(mCloseTimeConstant)); + panelp->mVisibleAmt = lerp(panelp->mVisibleAmt, 0.f, LLSmoothInterpolation::getInterpolant(mCloseTimeConstant)); if (panelp->mVisibleAmt < 0.001f) { panelp->mVisibleAmt = 0.f; @@ -638,7 +638,7 @@ bool LLLayoutStack::animatePanels() { if (!mAnimatedThisFrame) { - panelp->mCollapseAmt = lerp(panelp->mCollapseAmt, collapse_state, LLCriticalDamp::getInterpolant(mCloseTimeConstant)); + panelp->mCollapseAmt = lerp(panelp->mCollapseAmt, collapse_state, LLSmoothInterpolation::getInterpolant(mCloseTimeConstant)); } if (llabs(panelp->mCollapseAmt - collapse_state) < 0.001f) diff --git a/indra/llui/llmenugl.cpp b/indra/llui/llmenugl.cpp index cd6cc6a75e..13888920f9 100644 --- a/indra/llui/llmenugl.cpp +++ b/indra/llui/llmenugl.cpp @@ -3673,7 +3673,7 @@ void LLTearOffMenu::draw() if (getRect().getHeight() != mTargetHeight) { // animate towards target height - reshape(getRect().getWidth(), llceil(lerp((F32)getRect().getHeight(), mTargetHeight, LLCriticalDamp::getInterpolant(0.05f)))); + reshape(getRect().getWidth(), llceil(lerp((F32)getRect().getHeight(), mTargetHeight, LLSmoothInterpolation::getInterpolant(0.05f)))); } LLFloater::draw(); } diff --git a/indra/llui/llscrollbar.cpp b/indra/llui/llscrollbar.cpp index 5d3bf7a670..92a80c73fe 100644 --- a/indra/llui/llscrollbar.cpp +++ b/indra/llui/llscrollbar.cpp @@ -493,11 +493,11 @@ void LLScrollbar::draw() BOOL hovered = getEnabled() && !other_captor && (hasMouseCapture() || mThumbRect.pointInRect(local_mouse_x, local_mouse_y)); if (hovered) { - mCurGlowStrength = lerp(mCurGlowStrength, mHoverGlowStrength, LLCriticalDamp::getInterpolant(0.05f)); + mCurGlowStrength = lerp(mCurGlowStrength, mHoverGlowStrength, LLSmoothInterpolation::getInterpolant(0.05f)); } else { - mCurGlowStrength = lerp(mCurGlowStrength, 0.f, LLCriticalDamp::getInterpolant(0.05f)); + mCurGlowStrength = lerp(mCurGlowStrength, 0.f, LLSmoothInterpolation::getInterpolant(0.05f)); } // Draw background and thumb. diff --git a/indra/llui/llstatbar.cpp b/indra/llui/llstatbar.cpp index 2bc385061a..219ddad452 100644 --- a/indra/llui/llstatbar.cpp +++ b/indra/llui/llstatbar.cpp @@ -36,6 +36,7 @@ #include "lluictrlfactory.h" #include "lltracerecording.h" +#include "llcriticaldamp.h" /////////////////////////////////////////////////////////////////////////////////// @@ -45,6 +46,7 @@ LLStatBar::LLStatBar(const Params& p) mUnitLabel(p.unit_label), mMinBar(p.bar_min), mMaxBar(p.bar_max), + mCurMaxBar(p.bar_max), mCountFloatp(LLTrace::CountStatHandle<>::getInstance(p.stat)), mCountIntp(LLTrace::CountStatHandle::getInstance(p.stat)), mMeasurementFloatp(LLTrace::MeasurementStatHandle<>::getInstance(p.stat)), @@ -54,11 +56,14 @@ LLStatBar::LLStatBar(const Params& p) mPrecision(p.precision), mUpdatesPerSec(p.update_rate), mUnitScale(p.unit_scale), + mNumFrames(p.num_frames), + mMaxHeight(p.max_height), mPerSec(p.show_per_sec), mDisplayBar(p.show_bar), mDisplayHistory(p.show_history), mDisplayMean(p.show_mean), - mOrientation(p.orientation) + mOrientation(p.orientation), + mScaleRange(p.scale_range) {} BOOL LLStatBar::handleMouseDown(S32 x, S32 y, MASK mask) @@ -171,24 +176,38 @@ void LLStatBar::draw() S32 bar_top, bar_left, bar_right, bar_bottom; if (mOrientation == HORIZONTAL) { - bar_top = getRect().getHeight() - 15; + bar_top = llmax(5, getRect().getHeight() - 15); bar_left = 0; - bar_right = getRect().getWidth() - 80; - bar_bottom = 0; + bar_right = getRect().getWidth() - 40; + bar_bottom = llmin(bar_top - 5, 0); } else // VERTICAL { - bar_top = getRect().getHeight() - 15; // 16 pixels from top. + bar_top = llmax(5, getRect().getHeight() - 15); bar_left = 0; bar_right = getRect().getWidth(); - bar_bottom = 20; + bar_bottom = llmin(bar_top - 5, 20); } const S32 tick_length = 4; const S32 tick_width = 1; + if (mScaleRange) + { + F32 cur_max = mLabelSpacing; + while(max > cur_max) + { + cur_max += mLabelSpacing; + } + mCurMaxBar = LLSmoothInterpolation::lerp(mCurMaxBar, cur_max, 0.05f); + } + else + { + mCurMaxBar = mMaxBar; + } + F32 value_scale = (mOrientation == HORIZONTAL) - ? (bar_top - bar_bottom)/(mMaxBar - mMinBar) - : (bar_right - bar_left)/(mMaxBar - mMinBar); + ? (bar_top - bar_bottom)/(mCurMaxBar - mMinBar) + : (bar_right - bar_left)/(mCurMaxBar - mMinBar); LLFontGL::getFontMonospace()->renderUTF8(mLabel, 0, 0, getRect().getHeight(), LLColor4(1.f, 1.f, 1.f, 1.f), LLFontGL::LEFT, LLFontGL::TOP); @@ -209,7 +228,9 @@ void LLStatBar::draw() // Draw the value. if (mOrientation == HORIZONTAL) { - + LLFontGL::getFontMonospace()->renderUTF8(value_str, 0, bar_right, getRect().getHeight(), + LLColor4(1.f, 1.f, 1.f, 0.5f), + LLFontGL::RIGHT, LLFontGL::TOP); } else { @@ -227,12 +248,13 @@ void LLStatBar::draw() LLGLSUIDefault gls_ui; gGL.getTexUnit(0)->unbind(LLTexUnit::TT_TEXTURE); - for (F32 tick_value = mMinBar; tick_value <= mMaxBar; tick_value += mTickSpacing) + for (F32 tick_value = mMinBar + mLabelSpacing; tick_value <= mCurMaxBar; tick_value += mTickSpacing) { const S32 begin = llfloor((tick_value - mMinBar)*value_scale); const S32 end = begin + tick_width; if (mOrientation == HORIZONTAL) { + gl_rect_2d(bar_left, end, bar_right - tick_length/2, begin, LLColor4(1.f, 1.f, 1.f, 0.1f)); } else { @@ -241,7 +263,7 @@ void LLStatBar::draw() } // Draw the tick labels (and big ticks). - for (F32 tick_value = mMinBar; tick_value <= mMaxBar; tick_value += mLabelSpacing) + for (F32 tick_value = mMinBar + mLabelSpacing; tick_value <= mCurMaxBar; tick_value += mLabelSpacing) { const S32 begin = llfloor((tick_value - mMinBar)*value_scale); const S32 end = begin + tick_width; @@ -250,13 +272,17 @@ void LLStatBar::draw() // draw labels for the tick marks if (mOrientation == HORIZONTAL) { + gl_rect_2d(bar_left, end, bar_right - tick_length, begin, LLColor4(1.f, 1.f, 1.f, 0.25f)); + LLFontGL::getFontMonospace()->renderUTF8(tick_label, 0, bar_right, begin, + LLColor4(1.f, 1.f, 1.f, 0.5f), + LLFontGL::LEFT, LLFontGL::VCENTER); } else { gl_rect_2d(begin, bar_top, end, bar_bottom - tick_length, LLColor4(1.f, 1.f, 1.f, 0.25f)); LLFontGL::getFontMonospace()->renderUTF8(tick_label, 0, begin - 1, bar_bottom - tick_length, LLColor4(1.f, 1.f, 1.f, 0.5f), - LLFontGL::LEFT, LLFontGL::TOP); + LLFontGL::RIGHT, LLFontGL::TOP); } } @@ -288,69 +314,99 @@ void LLStatBar::draw() gl_rect_2d(begin, bar_top, end, bar_bottom, LLColor4(1.f, 0.f, 0.f, 0.25f)); } + F32 span = (mOrientation == HORIZONTAL) + ? (bar_right - bar_left) + : (bar_top - bar_bottom); + if (mDisplayHistory && (mCountFloatp || mCountIntp || mMeasurementFloatp || mMeasurementIntp)) { const S32 num_values = frame_recording.getNumPeriods() - 1; - S32 begin = 0; - S32 end = 0; + F32 begin = 0; + F32 end = 0; S32 i; - for (i = 1; i <= num_values; i++) + gGL.color4f( 1.f, 0.f, 0.f, 1.f ); + gGL.begin( LLRender::QUADS ); + const S32 max_frame = llmin(mNumFrames, num_values); + U32 num_samples = 0; + for (i = 1; i <= max_frame; i++) { + F32 offset = ((F32)i / (F32)mNumFrames) * span; + LLTrace::Recording& recording = frame_recording.getPrevRecordingPeriod(i); if (mPerSec) { if (mCountFloatp) { - begin = (S32)((frame_recording.getPrevRecordingPeriod(i).getPerSec(*mCountFloatp) - mMinBar) * value_scale); - end = (S32)((frame_recording.getPrevRecordingPeriod(i).getPerSec(*mCountFloatp) - mMinBar) * value_scale) + 1; + begin = ((recording.getPerSec(*mCountFloatp) - mMinBar) * value_scale); + end = ((recording.getPerSec(*mCountFloatp) - mMinBar) * value_scale) + 1; + num_samples = recording.getSampleCount(*mCountFloatp); } else if (mCountIntp) { - begin = (S32)((frame_recording.getPrevRecordingPeriod(i).getPerSec(*mCountIntp) - mMinBar) * value_scale); - end = (S32)((frame_recording.getPrevRecordingPeriod(i).getPerSec(*mCountIntp) - mMinBar) * value_scale) + 1; + begin = ((recording.getPerSec(*mCountIntp) - mMinBar) * value_scale); + end = ((recording.getPerSec(*mCountIntp) - mMinBar) * value_scale) + 1; + num_samples = recording.getSampleCount(*mCountIntp); } else if (mMeasurementFloatp) { - begin = (S32)((frame_recording.getPrevRecordingPeriod(i).getPerSec(*mMeasurementFloatp) - mMinBar) * value_scale); - end = (S32)((frame_recording.getPrevRecordingPeriod(i).getPerSec(*mMeasurementFloatp) - mMinBar) * value_scale) + 1; + //rate isn't defined for measurement stats, so use mean + begin = ((recording.getMean(*mMeasurementFloatp) - mMinBar) * value_scale); + end = ((recording.getMean(*mMeasurementFloatp) - mMinBar) * value_scale) + 1; + num_samples = recording.getSampleCount(*mMeasurementFloatp); } else if (mMeasurementIntp) { - begin = (S32)((frame_recording.getPrevRecordingPeriod(i).getPerSec(*mMeasurementIntp) - mMinBar) * value_scale); - end = (S32)((frame_recording.getPrevRecordingPeriod(i).getPerSec(*mMeasurementIntp) - mMinBar) * value_scale) + 1; + //rate isn't defined for measurement stats, so use mean + begin = ((recording.getMean(*mMeasurementIntp) - mMinBar) * value_scale); + end = ((recording.getMean(*mMeasurementIntp) - mMinBar) * value_scale) + 1; + num_samples = recording.getSampleCount(*mMeasurementIntp); } } else { if (mCountFloatp) { - begin = (S32)((frame_recording.getPrevRecordingPeriod(i).getSum(*mCountFloatp) - mMinBar) * value_scale); - end = (S32)((frame_recording.getPrevRecordingPeriod(i).getSum(*mCountFloatp) - mMinBar) * value_scale) + 1; + begin = ((recording.getSum(*mCountFloatp) - mMinBar) * value_scale); + end = ((recording.getSum(*mCountFloatp) - mMinBar) * value_scale) + 1; + num_samples = recording.getSampleCount(*mCountFloatp); } else if (mCountIntp) { - begin = (S32)((frame_recording.getPrevRecordingPeriod(i).getSum(*mCountIntp) - mMinBar) * value_scale); - end = (S32)((frame_recording.getPrevRecordingPeriod(i).getSum(*mCountIntp) - mMinBar) * value_scale) + 1; + begin = ((recording.getSum(*mCountIntp) - mMinBar) * value_scale); + end = ((recording.getSum(*mCountIntp) - mMinBar) * value_scale) + 1; + num_samples = recording.getSampleCount(*mCountIntp); } else if (mMeasurementFloatp) { - begin = (S32)((frame_recording.getPrevRecordingPeriod(i).getSum(*mMeasurementFloatp) - mMinBar) * value_scale); - end = (S32)((frame_recording.getPrevRecordingPeriod(i).getSum(*mMeasurementFloatp) - mMinBar) * value_scale) + 1; + begin = ((recording.getMean(*mMeasurementFloatp) - mMinBar) * value_scale); + end = ((recording.getMean(*mMeasurementFloatp) - mMinBar) * value_scale) + 1; + num_samples = recording.getSampleCount(*mMeasurementFloatp); } else if (mMeasurementIntp) { - begin = (S32)((frame_recording.getPrevRecordingPeriod(i).getSum(*mMeasurementIntp) - mMinBar) * value_scale); - end = (S32)((frame_recording.getPrevRecordingPeriod(i).getSum(*mMeasurementIntp) - mMinBar) * value_scale) + 1; + begin = ((recording.getMean(*mMeasurementIntp) - mMinBar) * value_scale); + end = ((recording.getMean(*mMeasurementIntp) - mMinBar) * value_scale) + 1; + num_samples = recording.getSampleCount(*mMeasurementIntp); } } + + if (!num_samples) continue; + if (mOrientation == HORIZONTAL) { - gl_rect_2d(bar_right - i, end, bar_right - i - 1, begin, LLColor4(1.f, 0.f, 0.f, 1.f)); + gGL.vertex2f((F32)bar_right - offset, end); + gGL.vertex2f((F32)bar_right - offset, begin); + gGL.vertex2f((F32)bar_right - offset - 1.f, begin); + gGL.vertex2f((F32)bar_right - offset - 1.f, end); } else { - gl_rect_2d(begin, bar_bottom+i+1, end, bar_bottom+i, LLColor4(1.f, 0.f, 0.f, 1.f)); + gGL.vertex2i(begin, (F32)bar_bottom+offset+1.f); + gGL.vertex2i(begin, (F32)bar_bottom+offset); + gGL.vertex2i(end, (F32)bar_bottom+offset); + gGL.vertex2i(end, (F32)bar_bottom+offset+1.f); } } + gGL.end(); } else { @@ -410,7 +466,14 @@ LLRect LLStatBar::getRequiredRect() { if (mDisplayHistory) { - rect.mTop = 35 + LLTrace::get_frame_recording().getNumPeriods(); + if (mOrientation == HORIZONTAL) + { + rect.mTop = mMaxHeight; + } + else + { + rect.mTop = 35 + llmin(mMaxHeight, llmin(mNumFrames, LLTrace::get_frame_recording().getNumPeriods())); + } } else { diff --git a/indra/llui/llstatbar.h b/indra/llui/llstatbar.h index 0ec8aaeaa9..a83ccbe9e5 100644 --- a/indra/llui/llstatbar.h +++ b/indra/llui/llstatbar.h @@ -52,8 +52,11 @@ public: Optional show_per_sec, show_bar, show_history, - show_mean; + show_mean, + scale_range; + Optional num_frames, + max_height; Optional stat; Optional orientation; @@ -71,6 +74,9 @@ public: show_bar("show_bar", TRUE), show_history("show_history", false), show_mean("show_mean", true), + scale_range("scale_range", true), + num_frames("num_frames", 300), + max_height("max_height", 200), stat("stat"), orientation("orientation", VERTICAL) { @@ -92,15 +98,19 @@ public: private: F32 mMinBar; F32 mMaxBar; + F32 mCurMaxBar; F32 mTickSpacing; F32 mLabelSpacing; U32 mPrecision; F32 mUpdatesPerSec; F32 mUnitScale; + S32 mNumFrames; + S32 mMaxHeight; bool mPerSec; // Use the per sec stats. bool mDisplayBar; // Display the bar graph. bool mDisplayHistory; bool mDisplayMean; // If true, display mean, if false, display current value + bool mScaleRange; EOrientation mOrientation; LLTrace::TraceType >* mCountFloatp; diff --git a/indra/llui/lltabcontainer.cpp b/indra/llui/lltabcontainer.cpp index 5fc2cc350d..4df35f77a5 100644 --- a/indra/llui/lltabcontainer.cpp +++ b/indra/llui/lltabcontainer.cpp @@ -406,7 +406,7 @@ void LLTabContainer::draw() } } - setScrollPosPixels((S32)lerp((F32)getScrollPosPixels(), (F32)target_pixel_scroll, LLCriticalDamp::getInterpolant(0.08f))); + setScrollPosPixels((S32)lerp((F32)getScrollPosPixels(), (F32)target_pixel_scroll, LLSmoothInterpolation::getInterpolant(0.08f))); BOOL has_scroll_arrows = !getTabsHidden() && ((mMaxScrollPos > 0) || (mScrollPosPixels > 0)); if (!mIsVertical) diff --git a/indra/newview/llagentcamera.cpp b/indra/newview/llagentcamera.cpp index 4e6079e3f2..6648431459 100644 --- a/indra/newview/llagentcamera.cpp +++ b/indra/newview/llagentcamera.cpp @@ -336,7 +336,7 @@ void LLAgentCamera::resetView(BOOL reset_camera, BOOL change_camera) LLVector3 agent_at_axis = gAgent.getAtAxis(); agent_at_axis -= projected_vec(agent_at_axis, gAgent.getReferenceUpVector()); agent_at_axis.normalize(); - gAgent.resetAxes(lerp(gAgent.getAtAxis(), agent_at_axis, LLCriticalDamp::getInterpolant(0.3f))); + gAgent.resetAxes(lerp(gAgent.getAtAxis(), agent_at_axis, LLSmoothInterpolation::getInterpolant(0.3f))); } setFocusOnAvatar(TRUE, ANIMATE); @@ -1246,7 +1246,7 @@ void LLAgentCamera::updateCamera() gAgentCamera.clearPanKeys(); // lerp camera focus offset - mCameraFocusOffset = lerp(mCameraFocusOffset, mCameraFocusOffsetTarget, LLCriticalDamp::getInterpolant(CAMERA_FOCUS_HALF_LIFE)); + mCameraFocusOffset = lerp(mCameraFocusOffset, mCameraFocusOffsetTarget, LLSmoothInterpolation::getInterpolant(CAMERA_FOCUS_HALF_LIFE)); if ( mCameraMode == CAMERA_MODE_FOLLOW ) { @@ -1364,7 +1364,7 @@ void LLAgentCamera::updateCamera() { const F32 SMOOTHING_HALF_LIFE = 0.02f; - F32 smoothing = LLCriticalDamp::getInterpolant(gSavedSettings.getF32("CameraPositionSmoothing") * SMOOTHING_HALF_LIFE, FALSE); + F32 smoothing = LLSmoothInterpolation::getInterpolant(gSavedSettings.getF32("CameraPositionSmoothing") * SMOOTHING_HALF_LIFE, FALSE); if (!mFocusObject) // we differentiate on avatar mode { @@ -1394,7 +1394,7 @@ void LLAgentCamera::updateCamera() } - mCameraCurrentFOVZoomFactor = lerp(mCameraCurrentFOVZoomFactor, mCameraFOVZoomFactor, LLCriticalDamp::getInterpolant(FOV_ZOOM_HALF_LIFE)); + mCameraCurrentFOVZoomFactor = lerp(mCameraCurrentFOVZoomFactor, mCameraFOVZoomFactor, LLSmoothInterpolation::getInterpolant(FOV_ZOOM_HALF_LIFE)); // llinfos << "Current FOV Zoom: " << mCameraCurrentFOVZoomFactor << " Target FOV Zoom: " << mCameraFOVZoomFactor << " Object penetration: " << mFocusObjectDist << llendl; @@ -1809,7 +1809,7 @@ LLVector3d LLAgentCamera::calcCameraPositionTargetGlobal(BOOL *hit_limit) if (mTargetCameraDistance != mCurrentCameraDistance) { - F32 camera_lerp_amt = LLCriticalDamp::getInterpolant(CAMERA_ZOOM_HALF_LIFE); + F32 camera_lerp_amt = LLSmoothInterpolation::getInterpolant(CAMERA_ZOOM_HALF_LIFE); mCurrentCameraDistance = lerp(mCurrentCameraDistance, mTargetCameraDistance, camera_lerp_amt); } @@ -1827,7 +1827,7 @@ LLVector3d LLAgentCamera::calcCameraPositionTargetGlobal(BOOL *hit_limit) if (isAgentAvatarValid()) { LLVector3d camera_lag_d; - F32 lag_interp = LLCriticalDamp::getInterpolant(CAMERA_LAG_HALF_LIFE); + F32 lag_interp = LLSmoothInterpolation::getInterpolant(CAMERA_LAG_HALF_LIFE); LLVector3 target_lag; LLVector3 vel = gAgent.getVelocity(); @@ -1872,7 +1872,7 @@ LLVector3d LLAgentCamera::calcCameraPositionTargetGlobal(BOOL *hit_limit) } else { - mCameraLag = lerp(mCameraLag, LLVector3::zero, LLCriticalDamp::getInterpolant(0.15f)); + mCameraLag = lerp(mCameraLag, LLVector3::zero, LLSmoothInterpolation::getInterpolant(0.15f)); } camera_lag_d.setVec(mCameraLag); diff --git a/indra/newview/llappviewer.cpp b/indra/newview/llappviewer.cpp index c00fddbb24..0cb7c7b030 100644 --- a/indra/newview/llappviewer.cpp +++ b/indra/newview/llappviewer.cpp @@ -4210,7 +4210,7 @@ void LLAppViewer::idle() LLFrameTimer::updateFrameCount(); LLEventTimer::updateClass(); LLNotificationsUI::LLToast::updateClass(); - LLCriticalDamp::updateInterpolants(); + LLSmoothInterpolation::updateInterpolants(); LLMortician::updateClass(); LLFilePickerThread::clearDead(); //calls LLFilePickerThread::notify() @@ -4865,7 +4865,7 @@ void LLAppViewer::idleNetwork() gPrintMessagesThisFrame = FALSE; } } - sample(LLStatViewer::NUM_NEW_OBJECTS, gObjectList.mNumNewObjects); + add(LLStatViewer::NUM_NEW_OBJECTS, gObjectList.mNumNewObjects); // Retransmit unacknowledged packets. gXferManager->retransmitUnackedPackets(); diff --git a/indra/newview/lldrawable.cpp b/indra/newview/lldrawable.cpp index 9c3d9f4d34..a0c71b0f73 100644 --- a/indra/newview/lldrawable.cpp +++ b/indra/newview/lldrawable.cpp @@ -557,7 +557,7 @@ F32 LLDrawable::updateXform(BOOL undamped) if (damped && isVisible()) { - F32 lerp_amt = llclamp(LLCriticalDamp::getInterpolant(OBJECT_DAMPING_TIME_CONSTANT), 0.f, 1.f); + F32 lerp_amt = llclamp(LLSmoothInterpolation::getInterpolant(OBJECT_DAMPING_TIME_CONSTANT), 0.f, 1.f); LLVector3 new_pos = lerp(old_pos, target_pos, lerp_amt); dist_squared = dist_vec_squared(new_pos, target_pos); diff --git a/indra/newview/llfasttimerview.cpp b/indra/newview/llfasttimerview.cpp index 3893b0e772..f55535b6e3 100644 --- a/indra/newview/llfasttimerview.cpp +++ b/indra/newview/llfasttimerview.cpp @@ -1128,13 +1128,13 @@ void LLFastTimerView::drawLineGraph() } //interpolate towards new maximum - max_time = lerp(max_time.value(), cur_max.value(), LLCriticalDamp::getInterpolant(0.1f)); + max_time = lerp(max_time.value(), cur_max.value(), LLSmoothInterpolation::getInterpolant(0.1f)); if (max_time - cur_max <= 1 || cur_max - max_time <= 1) { max_time = llmax(LLUnit(1), LLUnit(cur_max)); } - max_calls = llround(lerp((F32)max_calls, (F32) cur_max_calls, LLCriticalDamp::getInterpolant(0.1f))); + max_calls = llround(lerp((F32)max_calls, (F32) cur_max_calls, LLSmoothInterpolation::getInterpolant(0.1f))); if (llabs((S32)(max_calls - cur_max_calls)) <= 1) { max_calls = cur_max_calls; @@ -1144,7 +1144,7 @@ void LLFastTimerView::drawLineGraph() F32 alpha_target = (max_time > cur_max) ? llmin(max_time / cur_max - 1.f,1.f) : llmin(cur_max/ max_time - 1.f,1.f); - alpha_interp = lerp(alpha_interp, alpha_target, LLCriticalDamp::getInterpolant(0.1f)); + alpha_interp = lerp(alpha_interp, alpha_target, LLSmoothInterpolation::getInterpolant(0.1f)); if (mHoverID != NULL) { diff --git a/indra/newview/llfloatercolorpicker.cpp b/indra/newview/llfloatercolorpicker.cpp index 05d73c2416..e2beb272e6 100644 --- a/indra/newview/llfloatercolorpicker.cpp +++ b/indra/newview/llfloatercolorpicker.cpp @@ -525,11 +525,11 @@ void LLFloaterColorPicker::draw() if (gFocusMgr.childHasMouseCapture(getDragHandle())) { - mContextConeOpacity = lerp(mContextConeOpacity, gSavedSettings.getF32("PickerContextOpacity"), LLCriticalDamp::getInterpolant(CONTEXT_FADE_TIME)); + mContextConeOpacity = lerp(mContextConeOpacity, gSavedSettings.getF32("PickerContextOpacity"), LLSmoothInterpolation::getInterpolant(CONTEXT_FADE_TIME)); } else { - mContextConeOpacity = lerp(mContextConeOpacity, 0.f, LLCriticalDamp::getInterpolant(CONTEXT_FADE_TIME)); + mContextConeOpacity = lerp(mContextConeOpacity, 0.f, LLSmoothInterpolation::getInterpolant(CONTEXT_FADE_TIME)); } mPipetteBtn->setToggleState(LLToolMgr::getInstance()->getCurrentTool() == LLToolPipette::getInstance()); diff --git a/indra/newview/llfloatersnapshot.cpp b/indra/newview/llfloatersnapshot.cpp index 04fc572220..285f52fcd6 100644 --- a/indra/newview/llfloatersnapshot.cpp +++ b/indra/newview/llfloatersnapshot.cpp @@ -478,7 +478,7 @@ void LLSnapshotLivePreview::draw() { if (mFlashAlpha < 1.f) { - mFlashAlpha = lerp(mFlashAlpha, 1.f, LLCriticalDamp::getInterpolant(0.02f)); + mFlashAlpha = lerp(mFlashAlpha, 1.f, LLSmoothInterpolation::getInterpolant(0.02f)); } else { @@ -487,7 +487,7 @@ void LLSnapshotLivePreview::draw() } else { - mFlashAlpha = lerp(mFlashAlpha, 0.f, LLCriticalDamp::getInterpolant(0.15f)); + mFlashAlpha = lerp(mFlashAlpha, 0.f, LLSmoothInterpolation::getInterpolant(0.15f)); } // Draw shining animation if appropriate. diff --git a/indra/newview/llfolderviewitem.cpp b/indra/newview/llfolderviewitem.cpp index 3aa16b4413..4eb84224bc 100644 --- a/indra/newview/llfolderviewitem.cpp +++ b/indra/newview/llfolderviewitem.cpp @@ -1293,7 +1293,7 @@ S32 LLFolderViewFolder::arrange( S32* width, S32* height, S32 filter_generation) // animate current height towards target height if (llabs(mCurHeight - mTargetHeight) > 1.f) { - mCurHeight = lerp(mCurHeight, mTargetHeight, LLCriticalDamp::getInterpolant(mIsOpen ? FOLDER_OPEN_TIME_CONSTANT : FOLDER_CLOSE_TIME_CONSTANT)); + mCurHeight = lerp(mCurHeight, mTargetHeight, LLSmoothInterpolation::getInterpolant(mIsOpen ? FOLDER_OPEN_TIME_CONSTANT : FOLDER_CLOSE_TIME_CONSTANT)); requestArrange(); @@ -2538,11 +2538,11 @@ void LLFolderViewFolder::draw() } else if (mIsOpen) { - mControlLabelRotation = lerp(mControlLabelRotation, -90.f, LLCriticalDamp::getInterpolant(0.04f)); + mControlLabelRotation = lerp(mControlLabelRotation, -90.f, LLSmoothInterpolation::getInterpolant(0.04f)); } else { - mControlLabelRotation = lerp(mControlLabelRotation, 0.f, LLCriticalDamp::getInterpolant(0.025f)); + mControlLabelRotation = lerp(mControlLabelRotation, 0.f, LLSmoothInterpolation::getInterpolant(0.025f)); } bool possibly_has_children = false; diff --git a/indra/newview/llfollowcam.cpp b/indra/newview/llfollowcam.cpp index b670af1782..d6dc964802 100644 --- a/indra/newview/llfollowcam.cpp +++ b/indra/newview/llfollowcam.cpp @@ -328,11 +328,11 @@ void LLFollowCam::update() F32 force = focusOffsetDistance - focusThresholdNormalizedByDistance; */ - F32 focusLagLerp = LLCriticalDamp::getInterpolant( mFocusLag ); + F32 focusLagLerp = LLSmoothInterpolation::getInterpolant( mFocusLag ); focus_pt_agent = lerp( focus_pt_agent, whereFocusWantsToBe, focusLagLerp ); mSimulatedFocusGlobal = gAgent.getPosGlobalFromAgent(focus_pt_agent); } - mRelativeFocus = lerp(mRelativeFocus, (focus_pt_agent - mSubjectPosition) * ~mSubjectRotation, LLCriticalDamp::getInterpolant(0.05f)); + mRelativeFocus = lerp(mRelativeFocus, (focus_pt_agent - mSubjectPosition) * ~mSubjectRotation, LLSmoothInterpolation::getInterpolant(0.05f)); }// if focus is not locked --------------------------------------------- @@ -415,7 +415,7 @@ void LLFollowCam::update() //------------------------------------------------------------------------------------------------- if ( distanceFromPositionToIdealPosition > mPositionThreshold ) { - F32 positionPullLerp = LLCriticalDamp::getInterpolant( mPositionLag ); + F32 positionPullLerp = LLSmoothInterpolation::getInterpolant( mPositionLag ); simulated_pos_agent = lerp( simulated_pos_agent, whereCameraPositionWantsToBe, positionPullLerp ); } @@ -435,7 +435,7 @@ void LLFollowCam::update() updateBehindnessConstraint(gAgent.getPosAgentFromGlobal(mSimulatedFocusGlobal), simulated_pos_agent); mSimulatedPositionGlobal = gAgent.getPosGlobalFromAgent(simulated_pos_agent); - mRelativePos = lerp(mRelativePos, (simulated_pos_agent - mSubjectPosition) * ~mSubjectRotation, LLCriticalDamp::getInterpolant(0.05f)); + mRelativePos = lerp(mRelativePos, (simulated_pos_agent - mSubjectPosition) * ~mSubjectRotation, LLSmoothInterpolation::getInterpolant(0.05f)); } // if position is not locked ----------------------------------------------------------- @@ -490,7 +490,7 @@ BOOL LLFollowCam::updateBehindnessConstraint(LLVector3 focus, LLVector3& cam_pos if ( cameraOffsetAngle > mBehindnessMaxAngle ) { - F32 fraction = ((cameraOffsetAngle - mBehindnessMaxAngle) / cameraOffsetAngle) * LLCriticalDamp::getInterpolant(mBehindnessLag); + F32 fraction = ((cameraOffsetAngle - mBehindnessMaxAngle) / cameraOffsetAngle) * LLSmoothInterpolation::getInterpolant(mBehindnessLag); cam_position = focus + horizontalSubjectBack * (slerp(fraction, camera_offset_rotation, LLQuaternion::DEFAULT)); cam_position.mV[VZ] = cameraZ; // clamp z value back to what it was before we started messing with it constraint_active = TRUE; diff --git a/indra/newview/llhudnametag.cpp b/indra/newview/llhudnametag.cpp index c12916ec6b..3ac11f906b 100644 --- a/indra/newview/llhudnametag.cpp +++ b/indra/newview/llhudnametag.cpp @@ -981,7 +981,7 @@ void LLHUDNameTag::updateAll() // { // continue; // } - (*this_object_it)->mPositionOffset = lerp((*this_object_it)->mPositionOffset, (*this_object_it)->mTargetPositionOffset, LLCriticalDamp::getInterpolant(POSITION_DAMPING_TC)); + (*this_object_it)->mPositionOffset = lerp((*this_object_it)->mPositionOffset, (*this_object_it)->mTargetPositionOffset, LLSmoothInterpolation::getInterpolant(POSITION_DAMPING_TC)); } } diff --git a/indra/newview/llmaniprotate.cpp b/indra/newview/llmaniprotate.cpp index 826e8d560a..0468560e96 100644 --- a/indra/newview/llmaniprotate.cpp +++ b/indra/newview/llmaniprotate.cpp @@ -240,7 +240,7 @@ void LLManipRotate::render() if (mManipPart == LL_ROT_Z) { - mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, 1.f, SELECTED_MANIPULATOR_SCALE, 1.f), LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, 1.f, SELECTED_MANIPULATOR_SCALE, 1.f), LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); gGL.pushMatrix(); { // selected part @@ -251,7 +251,7 @@ void LLManipRotate::render() } else if (mManipPart == LL_ROT_Y) { - mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, SELECTED_MANIPULATOR_SCALE, 1.f, 1.f), LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, SELECTED_MANIPULATOR_SCALE, 1.f, 1.f), LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); gGL.pushMatrix(); { gGL.rotatef( 90.f, 1.f, 0.f, 0.f ); @@ -262,7 +262,7 @@ void LLManipRotate::render() } else if (mManipPart == LL_ROT_X) { - mManipulatorScales = lerp(mManipulatorScales, LLVector4(SELECTED_MANIPULATOR_SCALE, 1.f, 1.f, 1.f), LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales = lerp(mManipulatorScales, LLVector4(SELECTED_MANIPULATOR_SCALE, 1.f, 1.f, 1.f), LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); gGL.pushMatrix(); { gGL.rotatef( 90.f, 0.f, 1.f, 0.f ); @@ -273,13 +273,13 @@ void LLManipRotate::render() } else if (mManipPart == LL_ROT_ROLL) { - mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, 1.f, 1.f, SELECTED_MANIPULATOR_SCALE), LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, 1.f, 1.f, SELECTED_MANIPULATOR_SCALE), LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); } else if (mManipPart == LL_NO_PART) { if (mHighlightedPart == LL_NO_PART) { - mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, 1.f, 1.f, 1.f), LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, 1.f, 1.f, 1.f), LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); } LLGLEnable cull_face(GL_CULL_FACE); @@ -294,7 +294,7 @@ void LLManipRotate::render() { if (mHighlightedPart == LL_ROT_Z) { - mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, 1.f, SELECTED_MANIPULATOR_SCALE, 1.f), LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, 1.f, SELECTED_MANIPULATOR_SCALE, 1.f), LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); gGL.scalef(mManipulatorScales.mV[VZ], mManipulatorScales.mV[VZ], mManipulatorScales.mV[VZ]); // hovering over part gl_ring( mRadiusMeters, width_meters, LLColor4( 0.f, 0.f, 1.f, 1.f ), LLColor4( 0.f, 0.f, 1.f, 0.5f ), CIRCLE_STEPS, i); @@ -312,7 +312,7 @@ void LLManipRotate::render() gGL.rotatef( 90.f, 1.f, 0.f, 0.f ); if (mHighlightedPart == LL_ROT_Y) { - mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, SELECTED_MANIPULATOR_SCALE, 1.f, 1.f), LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, SELECTED_MANIPULATOR_SCALE, 1.f, 1.f), LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); gGL.scalef(mManipulatorScales.mV[VY], mManipulatorScales.mV[VY], mManipulatorScales.mV[VY]); // hovering over part gl_ring( mRadiusMeters, width_meters, LLColor4( 0.f, 1.f, 0.f, 1.f ), LLColor4( 0.f, 1.f, 0.f, 0.5f ), CIRCLE_STEPS, i); @@ -330,7 +330,7 @@ void LLManipRotate::render() gGL.rotatef( 90.f, 0.f, 1.f, 0.f ); if (mHighlightedPart == LL_ROT_X) { - mManipulatorScales = lerp(mManipulatorScales, LLVector4(SELECTED_MANIPULATOR_SCALE, 1.f, 1.f, 1.f), LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales = lerp(mManipulatorScales, LLVector4(SELECTED_MANIPULATOR_SCALE, 1.f, 1.f, 1.f), LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); gGL.scalef(mManipulatorScales.mV[VX], mManipulatorScales.mV[VX], mManipulatorScales.mV[VX]); // hovering over part @@ -346,7 +346,7 @@ void LLManipRotate::render() if (mHighlightedPart == LL_ROT_ROLL) { - mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, 1.f, 1.f, SELECTED_MANIPULATOR_SCALE), LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales = lerp(mManipulatorScales, LLVector4(1.f, 1.f, 1.f, SELECTED_MANIPULATOR_SCALE), LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); } } diff --git a/indra/newview/llmanipscale.cpp b/indra/newview/llmanipscale.cpp index 00a0bf8894..2d09fb6fe5 100644 --- a/indra/newview/llmanipscale.cpp +++ b/indra/newview/llmanipscale.cpp @@ -535,11 +535,11 @@ void LLManipScale::highlightManipulators(S32 x, S32 y) { if (mHighlightedPart == MANIPULATOR_IDS[i]) { - mManipulatorScales[i] = lerp(mManipulatorScales[i], SELECTED_MANIPULATOR_SCALE, LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales[i] = lerp(mManipulatorScales[i], SELECTED_MANIPULATOR_SCALE, LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); } else { - mManipulatorScales[i] = lerp(mManipulatorScales[i], 1.f, LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); + mManipulatorScales[i] = lerp(mManipulatorScales[i], 1.f, LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE)); } } diff --git a/indra/newview/llmaniptranslate.cpp b/indra/newview/llmaniptranslate.cpp index 362308c176..cf5c646893 100644 --- a/indra/newview/llmaniptranslate.cpp +++ b/indra/newview/llmaniptranslate.cpp @@ -1921,18 +1921,18 @@ void LLManipTranslate::renderTranslationHandles() { if (index == mManipPart - LL_X_ARROW || index == mHighlightedPart - LL_X_ARROW) { - mArrowScales.mV[index] = lerp(mArrowScales.mV[index], SELECTED_ARROW_SCALE, LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); - mPlaneScales.mV[index] = lerp(mPlaneScales.mV[index], 1.f, LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); + mArrowScales.mV[index] = lerp(mArrowScales.mV[index], SELECTED_ARROW_SCALE, LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); + mPlaneScales.mV[index] = lerp(mPlaneScales.mV[index], 1.f, LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); } else if (index == mManipPart - LL_YZ_PLANE || index == mHighlightedPart - LL_YZ_PLANE) { - mArrowScales.mV[index] = lerp(mArrowScales.mV[index], 1.f, LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); - mPlaneScales.mV[index] = lerp(mPlaneScales.mV[index], SELECTED_ARROW_SCALE, LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); + mArrowScales.mV[index] = lerp(mArrowScales.mV[index], 1.f, LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); + mPlaneScales.mV[index] = lerp(mPlaneScales.mV[index], SELECTED_ARROW_SCALE, LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); } else { - mArrowScales.mV[index] = lerp(mArrowScales.mV[index], 1.f, LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); - mPlaneScales.mV[index] = lerp(mPlaneScales.mV[index], 1.f, LLCriticalDamp::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); + mArrowScales.mV[index] = lerp(mArrowScales.mV[index], 1.f, LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); + mPlaneScales.mV[index] = lerp(mPlaneScales.mV[index], 1.f, LLSmoothInterpolation::getInterpolant(MANIPULATOR_SCALE_HALF_LIFE )); } } diff --git a/indra/newview/llnetmap.cpp b/indra/newview/llnetmap.cpp index 1bda7640bd..0abfb59ffd 100644 --- a/indra/newview/llnetmap.cpp +++ b/indra/newview/llnetmap.cpp @@ -162,7 +162,7 @@ void LLNetMap::draw() static LLUICachedControl auto_center("MiniMapAutoCenter", true); if (auto_center) { - mCurPan = lerp(mCurPan, mTargetPan, LLCriticalDamp::getInterpolant(0.1f)); + mCurPan = lerp(mCurPan, mTargetPan, LLSmoothInterpolation::getInterpolant(0.1f)); } // Prepare a scissor region diff --git a/indra/newview/lltexturectrl.cpp b/indra/newview/lltexturectrl.cpp index ec36cf48c2..e227722b29 100644 --- a/indra/newview/lltexturectrl.cpp +++ b/indra/newview/lltexturectrl.cpp @@ -549,11 +549,11 @@ void LLFloaterTexturePicker::draw() if (gFocusMgr.childHasMouseCapture(getDragHandle())) { - mContextConeOpacity = lerp(mContextConeOpacity, gSavedSettings.getF32("PickerContextOpacity"), LLCriticalDamp::getInterpolant(CONTEXT_FADE_TIME)); + mContextConeOpacity = lerp(mContextConeOpacity, gSavedSettings.getF32("PickerContextOpacity"), LLSmoothInterpolation::getInterpolant(CONTEXT_FADE_TIME)); } else { - mContextConeOpacity = lerp(mContextConeOpacity, 0.f, LLCriticalDamp::getInterpolant(CONTEXT_FADE_TIME)); + mContextConeOpacity = lerp(mContextConeOpacity, 0.f, LLSmoothInterpolation::getInterpolant(CONTEXT_FADE_TIME)); } updateImageStats(); diff --git a/indra/newview/llviewerdisplay.cpp b/indra/newview/llviewerdisplay.cpp index 2aec25b7aa..0889c3ec6c 100644 --- a/indra/newview/llviewerdisplay.cpp +++ b/indra/newview/llviewerdisplay.cpp @@ -1041,7 +1041,7 @@ void render_hud_attachments() // clamp target zoom level to reasonable values gAgentCamera.mHUDTargetZoom = llclamp(gAgentCamera.mHUDTargetZoom, 0.1f, 1.f); // smoothly interpolate current zoom level - gAgentCamera.mHUDCurZoom = lerp(gAgentCamera.mHUDCurZoom, gAgentCamera.mHUDTargetZoom, LLCriticalDamp::getInterpolant(0.03f)); + gAgentCamera.mHUDCurZoom = lerp(gAgentCamera.mHUDCurZoom, gAgentCamera.mHUDTargetZoom, LLSmoothInterpolation::getInterpolant(0.03f)); if (LLPipeline::sShowHUDAttachments && !gDisconnected && setup_hud_matrices()) { diff --git a/indra/newview/llviewerfloaterreg.cpp b/indra/newview/llviewerfloaterreg.cpp index 69586e3634..e72ea4b826 100644 --- a/indra/newview/llviewerfloaterreg.cpp +++ b/indra/newview/llviewerfloaterreg.cpp @@ -297,6 +297,7 @@ void LLViewerFloaterReg::registerFloaters() LLFloaterReg::add("settings_debug", "floater_settings_debug.xml", (LLFloaterBuildFunc)&LLFloaterReg::build); LLFloaterReg::add("sound_devices", "floater_sound_devices.xml", (LLFloaterBuildFunc)&LLFloaterReg::build); LLFloaterReg::add("stats", "floater_stats.xml", (LLFloaterBuildFunc)&LLFloaterReg::build); + LLFloaterReg::add("scene_load_stats", "floater_scene_load_stats.xml", (LLFloaterBuildFunc)&LLFloaterReg::build); LLFloaterReg::add("start_queue", "floater_script_queue.xml", (LLFloaterBuildFunc)&LLFloaterReg::build); LLFloaterReg::add("stop_queue", "floater_script_queue.xml", (LLFloaterBuildFunc)&LLFloaterReg::build); LLFloaterReg::add("snapshot", "floater_snapshot.xml", (LLFloaterBuildFunc)&LLFloaterReg::build); diff --git a/indra/newview/llviewerstats.cpp b/indra/newview/llviewerstats.cpp index 921c681e2a..0e2c53ee5b 100755 --- a/indra/newview/llviewerstats.cpp +++ b/indra/newview/llviewerstats.cpp @@ -88,7 +88,8 @@ LLTrace::CountStatHandle<> FPS("fpsstat"), KILLED("killed", "Number of times killed"), FRAMETIME_DOUBLED("frametimedoubled", "Ratio of frames 2x longer than previous"), TEX_BAKES("texbakes"), - TEX_REBAKES("texrebakes"); + TEX_REBAKES("texrebakes"), + NUM_NEW_OBJECTS("numnewobjectsstat"); LLTrace::CountStatHandle KBIT("kbitstat"), LAYERS_KBIT("layerskbitstat"), OBJECT_KBIT("objectkbitstat"), @@ -133,7 +134,6 @@ LLTrace::MeasurementStatHandle<> FPS_SAMPLE("fpssample"), NUM_RAW_IMAGES("numrawimagesstat"), NUM_OBJECTS("numobjectsstat"), NUM_ACTIVE_OBJECTS("numactiveobjectsstat"), - NUM_NEW_OBJECTS("numnewobjectsstat"), NUM_SIZE_CULLED("numsizeculledstat"), NUM_VIS_CULLED("numvisculledstat"), ENABLE_VBO("enablevbo", "Vertex Buffers Enabled"), diff --git a/indra/newview/llviewerstats.h b/indra/newview/llviewerstats.h index 069a726e5e..00e8c66b54 100644 --- a/indra/newview/llviewerstats.h +++ b/indra/newview/llviewerstats.h @@ -90,7 +90,8 @@ extern LLTrace::CountStatHandle<> FPS, KILLED, FRAMETIME_DOUBLED, TEX_BAKES, - TEX_REBAKES; + TEX_REBAKES, + NUM_NEW_OBJECTS; extern LLTrace::CountStatHandle KBIT, @@ -137,7 +138,6 @@ extern LLTrace::MeasurementStatHandle<> FPS_SAMPLE, NUM_RAW_IMAGES, NUM_OBJECTS, NUM_ACTIVE_OBJECTS, - NUM_NEW_OBJECTS, NUM_SIZE_CULLED, NUM_VIS_CULLED, ENABLE_VBO, diff --git a/indra/newview/llvoavatar.cpp b/indra/newview/llvoavatar.cpp index 1d43f96fb7..5a07cdf7c9 100755 --- a/indra/newview/llvoavatar.cpp +++ b/indra/newview/llvoavatar.cpp @@ -2917,7 +2917,7 @@ void LLVOAvatar::idleUpdateWindEffect() LLVector3 velocity = getVelocity(); F32 speed = velocity.length(); //RN: velocity varies too much frame to frame for this to work - mRippleAccel.clearVec();//lerp(mRippleAccel, (velocity - mLastVel) * time_delta, LLCriticalDamp::getInterpolant(0.02f)); + mRippleAccel.clearVec();//lerp(mRippleAccel, (velocity - mLastVel) * time_delta, LLSmoothInterpolation::getInterpolant(0.02f)); mLastVel = velocity; LLVector4 wind; wind.setVec(getRegion()->mWind.getVelocityNoisy(getPositionAgent(), 4.f) - velocity); @@ -2940,11 +2940,11 @@ void LLVOAvatar::idleUpdateWindEffect() F32 interp; if (wind.mV[VW] > mWindVec.mV[VW]) { - interp = LLCriticalDamp::getInterpolant(0.2f); + interp = LLSmoothInterpolation::getInterpolant(0.2f); } else { - interp = LLCriticalDamp::getInterpolant(0.4f); + interp = LLSmoothInterpolation::getInterpolant(0.4f); } mWindVec = lerp(mWindVec, wind, interp); @@ -3794,7 +3794,7 @@ BOOL LLVOAvatar::updateCharacter(LLAgent &agent) // Set the root rotation, but do so incrementally so that it // lags in time by some fixed amount. - //F32 u = LLCriticalDamp::getInterpolant(PELVIS_LAG); + //F32 u = LLSmoothInterpolation::getInterpolant(PELVIS_LAG); F32 pelvis_lag_time = 0.f; if (self_in_mouselook) { diff --git a/indra/newview/llworldmapview.cpp b/indra/newview/llworldmapview.cpp index ccc513b80d..f821cb1ec1 100644 --- a/indra/newview/llworldmapview.cpp +++ b/indra/newview/llworldmapview.cpp @@ -302,8 +302,8 @@ void LLWorldMapView::draw() mVisibleRegions.clear(); // animate pan if necessary - sPanX = lerp(sPanX, sTargetPanX, LLCriticalDamp::getInterpolant(0.1f)); - sPanY = lerp(sPanY, sTargetPanY, LLCriticalDamp::getInterpolant(0.1f)); + sPanX = lerp(sPanX, sTargetPanX, LLSmoothInterpolation::getInterpolant(0.1f)); + sPanY = lerp(sPanY, sTargetPanY, LLSmoothInterpolation::getInterpolant(0.1f)); const S32 width = getRect().getWidth(); const S32 height = getRect().getHeight(); diff --git a/indra/newview/skins/default/xui/en/floater_scene_load_stats.xml b/indra/newview/skins/default/xui/en/floater_scene_load_stats.xml new file mode 100644 index 0000000000..fd3cb37f8f --- /dev/null +++ b/indra/newview/skins/default/xui/en/floater_scene_load_stats.xml @@ -0,0 +1,549 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/indra/newview/skins/default/xui/en/floater_stats.xml b/indra/newview/skins/default/xui/en/floater_stats.xml index 93d9945800..a3f2fb0b9c 100644 --- a/indra/newview/skins/default/xui/en/floater_stats.xml +++ b/indra/newview/skins/default/xui/en/floater_stats.xml @@ -70,7 +70,6 @@ tick_spacing="0.5" label_spacing="1" precision="3" - show_per_sec="false" show_bar="false" show_mean="true"> @@ -85,7 +84,6 @@ label_spacing="1000" precision="0" show_bar="false" - show_per_sec="false" show_mean="false"> @@ -137,7 +135,6 @@ tick_spacing="5000" label_spacing="10000" precision="0" - show_per_sec="false" show_bar="false"> @@ -181,7 +176,6 @@ tick_spacing="20" label_spacing="20" show_history="true" - show_per_sec="false" show_bar="false"> @@ -217,7 +209,6 @@ bar_max="8000.f" tick_spacing="2000.f" label_spacing="4000.f" - show_per_sec="false" show_bar="false"> @@ -232,7 +223,6 @@ tick_spacing="100.f" label_spacing="200.f" precision="1" - show_per_sec="false" show_bar="false"> @@ -247,7 +237,6 @@ tick_spacing="100.f" label_spacing="200.f" precision="3" - show_per_sec="false" show_bar="false"> @@ -262,7 +251,6 @@ tick_spacing="100.f" label_spacing="200.f" precision="3" - show_per_sec="false" show_bar="false"> @@ -277,7 +265,6 @@ tick_spacing="100.f" label_spacing="200.f" precision="3" - show_per_sec="false" show_bar="false"> @@ -398,7 +385,6 @@ label="VFS Pending Operations" stat="vfspendingoperations" unit_label=" Ops." - show_per_sec="false" show_bar="false" > @@ -418,7 +404,6 @@ bar_max="1.f" tick_spacing="0.16666f" label_spacing="0.33333f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -432,7 +417,6 @@ bar_max="45.f" tick_spacing="7.5f" label_spacing="15.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -446,7 +430,6 @@ bar_max="45.f" tick_spacing="7.5.f" label_spacing="15.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -464,7 +447,6 @@ bar_max="500.f" tick_spacing="50.f" label_spacing="100.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -478,7 +460,6 @@ bar_max="500.f" tick_spacing="50.f" label_spacing="100.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -493,7 +474,6 @@ bar_max="1024.f" tick_spacing="128.f" label_spacing="256.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -508,7 +488,6 @@ bar_max="100.f" tick_spacing="25.f" label_spacing="50.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -522,7 +501,6 @@ bar_max="80.f" tick_spacing="10.f" label_spacing="40.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -536,7 +514,6 @@ bar_max="40.f" tick_spacing="5.f" label_spacing="10.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -550,7 +527,6 @@ bar_max="30000.f" tick_spacing="5000.f" label_spacing="10000.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -564,7 +540,6 @@ bar_max="5000.f" tick_spacing="750.f" label_spacing="1250.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -578,7 +553,6 @@ bar_max="15000.f" tick_spacing="1875.f" label_spacing="3750.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -592,7 +566,6 @@ tick_spacing="10" label_spacing="20" precision="3" - show_per_sec="false" show_bar="false" show_mean="true"> @@ -607,7 +580,6 @@ bar_max="5000.f" tick_spacing="750.f" label_spacing="1250.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -626,7 +598,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -640,7 +611,6 @@ bar_max="45" tick_spacing="4" label_spacing="8" - show_per_sec="false" show_bar="false"> @@ -669,7 +638,6 @@ bar_max="2000.f" tick_spacing="250.f" label_spacing="1000.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -684,7 +652,6 @@ bar_max="2000.f" tick_spacing="250.f" label_spacing="1000.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -698,7 +665,6 @@ bar_max="800.f" tick_spacing="100.f" label_spacing="200.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -712,7 +678,6 @@ bar_max="100.f" tick_spacing="25.f" label_spacing="50.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -727,7 +692,6 @@ bar_max="100000.f" tick_spacing="25000.f" label_spacing="50000.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -746,7 +710,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -761,7 +724,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -776,7 +738,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -791,7 +752,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -806,7 +766,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -821,7 +780,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -836,7 +794,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -851,7 +808,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -870,7 +826,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -884,7 +839,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -898,7 +852,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -912,7 +865,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > @@ -926,7 +878,6 @@ bar_max="40.f" tick_spacing="10.f" label_spacing="20.f" - show_per_sec="false" show_bar="false" show_mean="false" > diff --git a/indra/newview/skins/default/xui/en/menu_viewer.xml b/indra/newview/skins/default/xui/en/menu_viewer.xml index 8fe955aed8..5b6a6f908a 100644 --- a/indra/newview/skins/default/xui/en/menu_viewer.xml +++ b/indra/newview/skins/default/xui/en/menu_viewer.xml @@ -1384,6 +1384,14 @@ function="Floater.Toggle" parameter="stats" /> + + + -- 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/llcharacter') 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