Fix llGetLinkKey() to return the last sat avatar as the last link number.

As per http://wiki.secondlife.com/wiki/LlGetLinkKey
This is done by keeping a scene-object wide list of sitters.
This also fixes bugs in this function where linknums 0 and 1 weren't treated properly if there were sitting avatars on a single prim.
This also fixes a minor race condition for multiple concurrent sitters on a prim with no current sitters by locking on the object-wide list rather than individual sop lists
Addresses http://opensimulator.org/mantis/view.php?id=6477

3 files changed, 99 insertions, 63 deletions

diff --git a/OpenSim/Region/Framework/Scenes/SceneObjectGroup.cs b/OpenSim/Region/Framework/Scenes/SceneObjectGroup.cs
index 35e7c45..15795e5 100644
--- a/OpenSim/Region/Framework/Scenes/SceneObjectGroup.cs
+++ b/OpenSim/Region/Framework/Scenes/SceneObjectGroup.cs
@@ -647,6 +647,18 @@ namespace OpenSim.Region.Framework.Scenes
         /// </remarks>
         public UUID FromFolderID { get; set; }
 
+        /// <summary>
+        /// IDs of all avatars sat on this scene object.
+        /// </summary>
+        /// <remarks>
+        /// We need this so that we can maintain a linkset wide ordering of avatars sat on different parts.
+        /// This must be locked before it is read or written.
+        /// SceneObjectPart sitting avatar add/remove code also locks on this object to avoid race conditions.
+        /// No avatar should appear more than once in this list.
+        /// Do not manipulate this list directly - use the Add/Remove sitting avatar methods on SceneObjectPart.
+        /// </remarks>
+        protected internal List<UUID> m_sittingAvatars = new List<UUID>();
+
         #endregion
 
 //        ~SceneObjectGroup()
@@ -3564,17 +3576,28 @@ namespace OpenSim.Region.Framework.Scenes
         }
 
         /// <summary>
+        /// Get a copy of the list of sitting avatars on all prims of this object.
+        /// </summary>
+        /// <remarks>
+        /// This is sorted by the order in which avatars sat down.  If an avatar stands up then all avatars that sat
+        /// down after it move one place down the list.
+        /// </remarks>
+        /// <returns>A list of the sitting avatars.  Returns an empty list if there are no sitting avatars.</returns>
+        public List<UUID> GetSittingAvatars()
+        {
+            lock (m_sittingAvatars)
+                return new List<UUID>(m_sittingAvatars);
+        }
+
+        /// <summary>
         /// Gets the number of sitting avatars.
         /// </summary>
         /// <remarks>This applies to all sitting avatars whether there is a sit target set or not.</remarks>
         /// <returns></returns>
         public int GetSittingAvatarsCount()
         {
-             int count = 0;
-
-             Array.ForEach<SceneObjectPart>(m_parts.GetArray(), p => count += p.GetSittingAvatarsCount());
-
-             return count;
+            lock (m_sittingAvatars)
+                return m_sittingAvatars.Count;
         }
 
         public override string ToString()
@@ -3583,7 +3606,7 @@ namespace OpenSim.Region.Framework.Scenes
         }
 
         #region ISceneObject
-        
+
         public virtual ISceneObject CloneForNewScene()
         {
             SceneObjectGroup sog = Copy(false);
diff --git a/OpenSim/Region/Framework/Scenes/SceneObjectPart.cs b/OpenSim/Region/Framework/Scenes/SceneObjectPart.cs
index 7a97e5f..232861e 100644
--- a/OpenSim/Region/Framework/Scenes/SceneObjectPart.cs
+++ b/OpenSim/Region/Framework/Scenes/SceneObjectPart.cs
@@ -1256,7 +1256,7 @@ namespace OpenSim.Region.Framework.Scenes
         public UUID SitTargetAvatar { get; set; }
 
         /// <summary>
-        /// IDs of all avatars start on this object part.
+        /// IDs of all avatars sat on this part.
         /// </summary>
         /// <remarks>
         /// We need to track this so that we can stop sat upon prims from being attached.
@@ -4504,18 +4504,22 @@ namespace OpenSim.Region.Framework.Scenes
         /// <param name='avatarId'></param>
         protected internal bool AddSittingAvatar(UUID avatarId)
         {
-            if (IsSitTargetSet && SitTargetAvatar == UUID.Zero)
-                SitTargetAvatar = avatarId;
+            lock (ParentGroup.m_sittingAvatars)
+            {
+                if (IsSitTargetSet && SitTargetAvatar == UUID.Zero)
+                    SitTargetAvatar = avatarId;
 
-            HashSet<UUID> sittingAvatars = m_sittingAvatars;
+                if (m_sittingAvatars == null)
+                    m_sittingAvatars = new HashSet<UUID>();
 
-            if (sittingAvatars == null)
-                sittingAvatars = new HashSet<UUID>();
+                if (m_sittingAvatars.Add(avatarId))
+                {
+                    ParentGroup.m_sittingAvatars.Add(avatarId);
 
-            lock (sittingAvatars)
-            {
-                m_sittingAvatars = sittingAvatars;
-                return m_sittingAvatars.Add(avatarId);
+                    return true;
+                }
+
+                return false;
             }
         }
 
@@ -4529,27 +4533,26 @@ namespace OpenSim.Region.Framework.Scenes
         /// <param name='avatarId'></param>
         protected internal bool RemoveSittingAvatar(UUID avatarId)
         {
-            if (SitTargetAvatar == avatarId)
-                SitTargetAvatar = UUID.Zero;
-
-            HashSet<UUID> sittingAvatars = m_sittingAvatars;
+            lock (ParentGroup.m_sittingAvatars)
+            {
+                if (SitTargetAvatar == avatarId)
+                    SitTargetAvatar = UUID.Zero;
 
-            // This can occur under a race condition where another thread
-            if (sittingAvatars == null)
-                return false;
+                if (m_sittingAvatars == null)
+                    return false;
 
-            lock (sittingAvatars)
-            {
-                if (sittingAvatars.Remove(avatarId))
+                if (m_sittingAvatars.Remove(avatarId))
                 {
-                    if (sittingAvatars.Count == 0)
+                    if (m_sittingAvatars.Count == 0)
                         m_sittingAvatars = null;
 
+                    ParentGroup.m_sittingAvatars.Remove(avatarId);
+
                     return true;
                 }
-            }
 
-            return false;
+                return false;
+            }
         }
 
         /// <summary>
@@ -4559,16 +4562,12 @@ namespace OpenSim.Region.Framework.Scenes
         /// <returns>A hashset of the sitting avatars.  Returns null if there are no sitting avatars.</returns>
         public HashSet<UUID> GetSittingAvatars()
         {
-            HashSet<UUID> sittingAvatars = m_sittingAvatars;
-
-            if (sittingAvatars == null)
-            {
-                return null;
-            }
-            else
+            lock (ParentGroup.m_sittingAvatars)
             {
-                lock (sittingAvatars)
-                    return new HashSet<UUID>(sittingAvatars);
+                if (m_sittingAvatars == null)
+                    return null;
+                else
+                    return new HashSet<UUID>(m_sittingAvatars);
             }
         }
 
@@ -4579,13 +4578,13 @@ namespace OpenSim.Region.Framework.Scenes
         /// <returns></returns>
         public int GetSittingAvatarsCount()
         {
-            HashSet<UUID> sittingAvatars = m_sittingAvatars;
-
-            if (sittingAvatars == null)
-                return 0;
-
-            lock (sittingAvatars)
-                return sittingAvatars.Count;
+            lock (ParentGroup.m_sittingAvatars)
+            {
+                if (m_sittingAvatars == null)
+                    return 0;
+                else
+                    return m_sittingAvatars.Count;
+            }
         }
     }
-}
+}
\ No newline at end of file
diff --git a/OpenSim/Region/ScriptEngine/Shared/Api/Implementation/LSL_Api.cs b/OpenSim/Region/ScriptEngine/Shared/Api/Implementation/LSL_Api.cs
index 75749a9..f31bbff 100644
--- a/OpenSim/Region/ScriptEngine/Shared/Api/Implementation/LSL_Api.cs
+++ b/OpenSim/Region/ScriptEngine/Shared/Api/Implementation/LSL_Api.cs
@@ -3738,33 +3738,47 @@ namespace OpenSim.Region.ScriptEngine.Shared.Api
         public LSL_String llGetLinkKey(int linknum)
         {
             m_host.AddScriptLPS(1);
-            List<UUID> keytable = new List<UUID>();
-            // parse for sitting avatare-uuids
-            World.ForEachRootScenePresence(delegate(ScenePresence presence)
-            {
-                if (presence.ParentID != 0 && m_host.ParentGroup.ContainsPart(presence.ParentID))
-                    keytable.Add(presence.UUID);
-            });
 
-            int totalprims = m_host.ParentGroup.PrimCount + keytable.Count;
-            if (linknum > m_host.ParentGroup.PrimCount && linknum <= totalprims)
+            if (linknum < 0)
             {
-                return keytable[totalprims - linknum].ToString();
+                if (linknum == ScriptBaseClass.LINK_THIS)
+                    return m_host.UUID.ToString();
+                else
+                    return ScriptBaseClass.NULL_KEY;
             }
 
-            if (linknum == 1 && m_host.ParentGroup.PrimCount == 1 && keytable.Count == 1)
+            int actualPrimCount = m_host.ParentGroup.PrimCount;
+            List<UUID> sittingAvatarIds = m_host.ParentGroup.GetSittingAvatars();
+            int adjustedPrimCount = actualPrimCount + sittingAvatarIds.Count;
+
+            // Special case for a single prim.  In this case the linknum is zero.  However, this will not match a single
+            // prim that has any avatars sat upon it (in which case the root prim is link 1).
+            if (linknum == 0)
             {
-                return m_host.UUID.ToString();
-            }
+                if (actualPrimCount == 1 && sittingAvatarIds.Count == 0)
+                    return m_host.UUID.ToString();
 
-            SceneObjectPart part = m_host.ParentGroup.GetLinkNumPart(linknum);
-            if (part != null)
+                return ScriptBaseClass.NULL_KEY;
+            }
+            // Special case to handle a single prim with sitting avatars.  GetLinkPart() would only match zero but
+            // here we must match 1 (ScriptBaseClass.LINK_ROOT).
+            else if (linknum == 1 && actualPrimCount == 1)
             {
-                return part.UUID.ToString();
+                if (sittingAvatarIds.Count > 0)
+                    return m_host.ParentGroup.RootPart.UUID.ToString();
+                else
+                    return ScriptBaseClass.NULL_KEY;
+            }
+            else if (linknum <= adjustedPrimCount)
+            {
+                if (linknum <= actualPrimCount)
+                    return m_host.ParentGroup.GetLinkNumPart(linknum).UUID.ToString();
+                else
+                    return sittingAvatarIds[linknum - actualPrimCount - 1].ToString();
             }
             else
             {
-                return UUID.Zero.ToString();
+                return ScriptBaseClass.NULL_KEY;
             }
         }