aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim
diff options
context:
space:
mode:
authorCharles Krinke2008-09-12 03:33:26 +0000
committerCharles Krinke2008-09-12 03:33:26 +0000
commit8d6096b815cf0425fdf8b5a4abad4d34f163f8e5 (patch)
tree50dec2dd934e366edd9727a9735f4d8bd4ea9486 /OpenSim
parent* minor: CONTRIBUTORS adjustments (diff)
downloadopensim-SC_OLD-8d6096b815cf0425fdf8b5a4abad4d34f163f8e5.zip
opensim-SC_OLD-8d6096b815cf0425fdf8b5a4abad4d34f163f8e5.tar.gz
opensim-SC_OLD-8d6096b815cf0425fdf8b5a4abad4d34f163f8e5.tar.bz2
opensim-SC_OLD-8d6096b815cf0425fdf8b5a4abad4d34f163f8e5.tar.xz
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.
Diffstat (limited to 'OpenSim')
-rw-r--r--OpenSim/Framework/Communications/Cache/CachedUserInfo.cs58
1 files changed, 40 insertions, 18 deletions
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
146 /// Recursively, in depth-first order, add all the folders we've received (stored 146 /// Recursively, in depth-first order, add all the folders we've received (stored
147 /// in a dictionary indexed by parent ID) into the tree that describes user folder 147 /// in a dictionary indexed by parent ID) into the tree that describes user folder
148 /// heirarchy 148 /// heirarchy
149 /// Any folder that is resolved into the tree is also added to resolvedFolderDictionary,
150 /// indexed by folder ID.
149 /// </summary> 151 /// </summary>
150 /// <param name="parentId"> 152 /// <param name="parentId">
151 /// A <see cref="UUID"/> 153 /// A <see cref="UUID"/>
152 /// </param> 154 /// </param>
153 private void ResolveReceivedFolders(InventoryFolderImpl parentFolder, IDictionary<UUID, IList<InventoryFolderImpl>> folderDictionary) 155 private void ResolveReceivedFolders(InventoryFolderImpl parentFolder,
156 IDictionary<UUID, IList<InventoryFolderImpl>> receivedFolderDictionary,
157 IDictionary<UUID, InventoryFolderImpl> resolvedFolderDictionary)
154 { 158 {
155 if (folderDictionary.ContainsKey(parentFolder.ID)) 159 if (receivedFolderDictionary.ContainsKey(parentFolder.ID))
156 { 160 {
157 List<InventoryFolderImpl> resolvedFolders = new List<InventoryFolderImpl>(); // Folders we've resolved with this invocation 161 List<InventoryFolderImpl> resolvedFolders = new List<InventoryFolderImpl>(); // Folders we've resolved with this invocation
158 foreach (InventoryFolderImpl folder in folderDictionary[parentFolder.ID]) 162 foreach (InventoryFolderImpl folder in receivedFolderDictionary[parentFolder.ID])
159 { 163 {
160 lock (parentFolder.SubFolders) 164 lock (parentFolder.SubFolders)
161 { 165 {
@@ -167,16 +171,25 @@ namespace OpenSim.Framework.Communications.Cache
167 } 171 }
168 else 172 else
169 { 173 {
170 resolvedFolders.Add(folder); 174 if ( resolvedFolderDictionary.ContainsKey( folder.ID ) ) {
171 parentFolder.SubFolders.Add(folder.ID, folder); 175 m_log.WarnFormat(
176 "[INVENTORY CACHE]: Received folder {0} {1} from inventory service has already been received but with different parent",
177 folder.Name, folder.ID);
178 }
179 else
180 {
181 resolvedFolders.Add(folder);
182 resolvedFolderDictionary[folder.ID] = folder;
183 parentFolder.SubFolders.Add(folder.ID, folder);
184 }
172 } 185 }
173 } 186 } // lock (parentFolder.SubFolders)
174 } // foreach (folder in pendingCategorizationFolders[parentFolder.ID]) 187 } // foreach (folder in pendingCategorizationFolders[parentFolder.ID])
175 188
176 folderDictionary.Remove(parentFolder.ID); 189 receivedFolderDictionary.Remove(parentFolder.ID);
177 foreach (InventoryFolderImpl folder in resolvedFolders) 190 foreach (InventoryFolderImpl folder in resolvedFolders)
178 ResolveReceivedFolders(folder, folderDictionary); 191 ResolveReceivedFolders(folder, receivedFolderDictionary, resolvedFolderDictionary);
179 } 192 } // if (receivedFolderDictionary.ContainsKey(parentFolder.ID))
180 } 193 }
181 194
182 /// <summary> 195 /// <summary>
@@ -211,6 +224,13 @@ namespace OpenSim.Framework.Communications.Cache
211 IDictionary<UUID, IList<InventoryFolderImpl>> receivedFolders = 224 IDictionary<UUID, IList<InventoryFolderImpl>> receivedFolders =
212 new Dictionary<UUID, IList<InventoryFolderImpl>>(); 225 new Dictionary<UUID, IList<InventoryFolderImpl>>();
213 226
227 // collection of all folders that have been placed into the folder heirarchy starting at m_rootFolder
228 // This dictonary exists so we don't have to do an InventoryFolderImpl.FindFolder(), which is O(n) on the
229 // number of folders in our inventory.
230 // Maybe we should make this structure a member so we can skip InventoryFolderImpl.FindFolder() calls later too?
231 IDictionary<UUID, InventoryFolderImpl> resolvedFolders =
232 new Dictionary<UUID, InventoryFolderImpl>();
233
214 // Take all received folders, find the root folder, and put ther rest into 234 // Take all received folders, find the root folder, and put ther rest into
215 // the pendingCategorizationFolders collection 235 // the pendingCategorizationFolders collection
216 foreach (InventoryFolderImpl folder in folders) 236 foreach (InventoryFolderImpl folder in folders)
@@ -222,6 +242,7 @@ namespace OpenSim.Framework.Communications.Cache
222 { 242 {
223 IList<InventoryFolderImpl> rootFolderList = receivedFolders[UUID.Zero]; 243 IList<InventoryFolderImpl> rootFolderList = receivedFolders[UUID.Zero];
224 m_rootFolder = rootFolderList[0]; 244 m_rootFolder = rootFolderList[0];
245 resolvedFolders[m_rootFolder.ID] = m_rootFolder;
225 if (rootFolderList.Count > 1) 246 if (rootFolderList.Count > 1)
226 { 247 {
227 for (int i = 1; i < rootFolderList.Count; i++) 248 for (int i = 1; i < rootFolderList.Count; i++)
@@ -237,7 +258,7 @@ namespace OpenSim.Framework.Communications.Cache
237 // Now take the pendingCategorizationFolders collection, and turn that into a tree, 258 // Now take the pendingCategorizationFolders collection, and turn that into a tree,
238 // with the root being RootFolder 259 // with the root being RootFolder
239 if (RootFolder != null) 260 if (RootFolder != null)
240 ResolveReceivedFolders(RootFolder, receivedFolders); 261 ResolveReceivedFolders(RootFolder, receivedFolders, resolvedFolders);
241 262
242 // Generate a warning for folders that are not part of the heirarchy 263 // Generate a warning for folders that are not part of the heirarchy
243 foreach (KeyValuePair<UUID, IList<InventoryFolderImpl>> folderList in receivedFolders) 264 foreach (KeyValuePair<UUID, IList<InventoryFolderImpl>> folderList in receivedFolders)
@@ -247,10 +268,10 @@ namespace OpenSim.Framework.Communications.Cache
247 } 268 }
248 269
249 // Take all ther received items and put them into the folder tree heirarchy 270 // Take all ther received items and put them into the folder tree heirarchy
250 // TBD: This operation is O(n^2), if we made a dictionary of all folders indexed by their ID, we could make 271 foreach (InventoryItemBase item in items) {
251 // this O(n) 272 InventoryFolderImpl folder = resolvedFolders.ContainsKey(item.Folder) ? resolvedFolders[item.Folder] : null;
252 foreach (InventoryItemBase item in items) 273 ItemReceive(item, folder );
253 ItemReceive(item); 274 }
254 } 275 }
255 catch (Exception e) 276 catch (Exception e)
256 { 277 {
@@ -276,16 +297,17 @@ namespace OpenSim.Framework.Communications.Cache
276 /// 297 ///
277 /// We're assuming here that items are always received after all the folders 298 /// We're assuming here that items are always received after all the folders
278 /// received. 299 /// received.
300 /// If folder is null, we will search for it starting from RootFolder (an O(n) operation),
301 /// otherwise we'll just put it into folder
279 /// </summary> 302 /// </summary>
280 /// <param name="folderInfo"></param> 303 /// <param name="folderInfo"></param>
281 private void ItemReceive(InventoryItemBase itemInfo) 304 private void ItemReceive(InventoryItemBase itemInfo, InventoryFolderImpl folder)
282 { 305 {
283 // m_log.DebugFormat( 306 // m_log.DebugFormat(
284 // "[INVENTORY CACHE]: Received item {0} {1} for user {2}", 307 // "[INVENTORY CACHE]: Received item {0} {1} for user {2}",
285 // itemInfo.Name, itemInfo.ID, userID); 308 // itemInfo.Name, itemInfo.ID, userID);
286 InventoryFolderImpl folder = null;
287 309
288 if ( RootFolder != null ) 310 if (folder == null && RootFolder != null)
289 folder = RootFolder.FindFolder(itemInfo.Folder); 311 folder = RootFolder.FindFolder(itemInfo.Folder);
290 312
291 if (null == folder) 313 if (null == folder)
@@ -550,7 +572,7 @@ namespace OpenSim.Framework.Communications.Cache
550 else 572 else
551 item.Folder = RootFolder.ID; 573 item.Folder = RootFolder.ID;
552 } 574 }
553 ItemReceive(item); 575 ItemReceive(item, null);
554 if (m_commsManager.SecureInventoryService != null) 576 if (m_commsManager.SecureInventoryService != null)
555 { 577 {
556 m_commsManager.SecureInventoryService.AddItem(item, m_session_id); 578 m_commsManager.SecureInventoryService.AddItem(item, m_session_id);