From 8d6096b815cf0425fdf8b5a4abad4d34f163f8e5 Mon Sep 17 00:00:00 2001 From: Charles Krinke Date: Fri, 12 Sep 2008 03:33:26 +0000 Subject: Mantis#2165. Thank you kindly, CMickeyB for a patch that: patch is attached that replaces the o(n^2) algorithm currently used to build the inventory cache with an o(n) algorithm using hash tables. the patch also adds some additional error handling. --- .../Communications/Cache/CachedUserInfo.cs | 58 +++++++++++++++------- 1 file changed, 40 insertions(+), 18 deletions(-) (limited to 'OpenSim/Framework/Communications/Cache') diff --git a/OpenSim/Framework/Communications/Cache/CachedUserInfo.cs b/OpenSim/Framework/Communications/Cache/CachedUserInfo.cs index 339bb31..6371105 100644 --- a/OpenSim/Framework/Communications/Cache/CachedUserInfo.cs +++ b/OpenSim/Framework/Communications/Cache/CachedUserInfo.cs @@ -146,16 +146,20 @@ namespace OpenSim.Framework.Communications.Cache /// Recursively, in depth-first order, add all the folders we've received (stored /// in a dictionary indexed by parent ID) into the tree that describes user folder /// heirarchy + /// Any folder that is resolved into the tree is also added to resolvedFolderDictionary, + /// indexed by folder ID. /// /// /// A /// - private void ResolveReceivedFolders(InventoryFolderImpl parentFolder, IDictionary> folderDictionary) + private void ResolveReceivedFolders(InventoryFolderImpl parentFolder, + IDictionary> receivedFolderDictionary, + IDictionary resolvedFolderDictionary) { - if (folderDictionary.ContainsKey(parentFolder.ID)) + if (receivedFolderDictionary.ContainsKey(parentFolder.ID)) { List resolvedFolders = new List(); // Folders we've resolved with this invocation - foreach (InventoryFolderImpl folder in folderDictionary[parentFolder.ID]) + foreach (InventoryFolderImpl folder in receivedFolderDictionary[parentFolder.ID]) { lock (parentFolder.SubFolders) { @@ -167,16 +171,25 @@ namespace OpenSim.Framework.Communications.Cache } else { - resolvedFolders.Add(folder); - parentFolder.SubFolders.Add(folder.ID, folder); + if ( resolvedFolderDictionary.ContainsKey( folder.ID ) ) { + m_log.WarnFormat( + "[INVENTORY CACHE]: Received folder {0} {1} from inventory service has already been received but with different parent", + folder.Name, folder.ID); + } + else + { + resolvedFolders.Add(folder); + resolvedFolderDictionary[folder.ID] = folder; + parentFolder.SubFolders.Add(folder.ID, folder); + } } - } + } // lock (parentFolder.SubFolders) } // foreach (folder in pendingCategorizationFolders[parentFolder.ID]) - folderDictionary.Remove(parentFolder.ID); + receivedFolderDictionary.Remove(parentFolder.ID); foreach (InventoryFolderImpl folder in resolvedFolders) - ResolveReceivedFolders(folder, folderDictionary); - } + ResolveReceivedFolders(folder, receivedFolderDictionary, resolvedFolderDictionary); + } // if (receivedFolderDictionary.ContainsKey(parentFolder.ID)) } /// @@ -211,6 +224,13 @@ namespace OpenSim.Framework.Communications.Cache IDictionary> receivedFolders = new Dictionary>(); + // collection of all folders that have been placed into the folder heirarchy starting at m_rootFolder + // This dictonary exists so we don't have to do an InventoryFolderImpl.FindFolder(), which is O(n) on the + // number of folders in our inventory. + // Maybe we should make this structure a member so we can skip InventoryFolderImpl.FindFolder() calls later too? + IDictionary resolvedFolders = + new Dictionary(); + // Take all received folders, find the root folder, and put ther rest into // the pendingCategorizationFolders collection foreach (InventoryFolderImpl folder in folders) @@ -222,6 +242,7 @@ namespace OpenSim.Framework.Communications.Cache { IList rootFolderList = receivedFolders[UUID.Zero]; m_rootFolder = rootFolderList[0]; + resolvedFolders[m_rootFolder.ID] = m_rootFolder; if (rootFolderList.Count > 1) { for (int i = 1; i < rootFolderList.Count; i++) @@ -237,7 +258,7 @@ namespace OpenSim.Framework.Communications.Cache // Now take the pendingCategorizationFolders collection, and turn that into a tree, // with the root being RootFolder if (RootFolder != null) - ResolveReceivedFolders(RootFolder, receivedFolders); + ResolveReceivedFolders(RootFolder, receivedFolders, resolvedFolders); // Generate a warning for folders that are not part of the heirarchy foreach (KeyValuePair> folderList in receivedFolders) @@ -247,10 +268,10 @@ namespace OpenSim.Framework.Communications.Cache } // Take all ther received items and put them into the folder tree heirarchy - // TBD: This operation is O(n^2), if we made a dictionary of all folders indexed by their ID, we could make - // this O(n) - foreach (InventoryItemBase item in items) - ItemReceive(item); + foreach (InventoryItemBase item in items) { + InventoryFolderImpl folder = resolvedFolders.ContainsKey(item.Folder) ? resolvedFolders[item.Folder] : null; + ItemReceive(item, folder ); + } } catch (Exception e) { @@ -276,16 +297,17 @@ namespace OpenSim.Framework.Communications.Cache /// /// We're assuming here that items are always received after all the folders /// received. + /// If folder is null, we will search for it starting from RootFolder (an O(n) operation), + /// otherwise we'll just put it into folder /// /// - private void ItemReceive(InventoryItemBase itemInfo) + private void ItemReceive(InventoryItemBase itemInfo, InventoryFolderImpl folder) { // m_log.DebugFormat( // "[INVENTORY CACHE]: Received item {0} {1} for user {2}", // itemInfo.Name, itemInfo.ID, userID); - InventoryFolderImpl folder = null; - if ( RootFolder != null ) + if (folder == null && RootFolder != null) folder = RootFolder.FindFolder(itemInfo.Folder); if (null == folder) @@ -550,7 +572,7 @@ namespace OpenSim.Framework.Communications.Cache else item.Folder = RootFolder.ID; } - ItemReceive(item); + ItemReceive(item, null); if (m_commsManager.SecureInventoryService != null) { m_commsManager.SecureInventoryService.AddItem(item, m_session_id); -- cgit v1.1