diff options
author | Charles Krinke | 2008-09-12 03:33:26 +0000 |
---|---|---|
committer | Charles Krinke | 2008-09-12 03:33:26 +0000 |
commit | 8d6096b815cf0425fdf8b5a4abad4d34f163f8e5 (patch) | |
tree | 50dec2dd934e366edd9727a9735f4d8bd4ea9486 /OpenSim/Framework/Communications/Cache/CachedUserInfo.cs | |
parent | * minor: CONTRIBUTORS adjustments (diff) | |
download | opensim-SC-8d6096b815cf0425fdf8b5a4abad4d34f163f8e5.zip opensim-SC-8d6096b815cf0425fdf8b5a4abad4d34f163f8e5.tar.gz opensim-SC-8d6096b815cf0425fdf8b5a4abad4d34f163f8e5.tar.bz2 opensim-SC-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/Framework/Communications/Cache/CachedUserInfo.cs')
-rw-r--r-- | OpenSim/Framework/Communications/Cache/CachedUserInfo.cs | 58 |
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); |