aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Data/SQLite
diff options
context:
space:
mode:
authorCharles Krinke2008-08-10 16:44:25 +0000
committerCharles Krinke2008-08-10 16:44:25 +0000
commit54af3b4f4dd8a2885dcc57904f04d603bb444f24 (patch)
treec66693db07a1452595c08c509b818f94003fe3c2 /OpenSim/Data/SQLite
parentMantis#1910. Thank you kindly, HomerHorwitz for a patch that: (diff)
downloadopensim-SC-54af3b4f4dd8a2885dcc57904f04d603bb444f24.zip
opensim-SC-54af3b4f4dd8a2885dcc57904f04d603bb444f24.tar.gz
opensim-SC-54af3b4f4dd8a2885dcc57904f04d603bb444f24.tar.bz2
opensim-SC-54af3b4f4dd8a2885dcc57904f04d603bb444f24.tar.xz
Mantis#1903. Thank you kindly, CMickeyb for a patch that:
patch attached replaces the tree walk algorithm used to build the folder hierarchy with a single database query. That is, we replace 1 database query per folder with 1 query for the root folder's properties and 1 query to retrieve the entire collection of folders for a user.
Diffstat (limited to 'OpenSim/Data/SQLite')
-rw-r--r--OpenSim/Data/SQLite/SQLiteInventoryStore.cs97
1 files changed, 93 insertions, 4 deletions
diff --git a/OpenSim/Data/SQLite/SQLiteInventoryStore.cs b/OpenSim/Data/SQLite/SQLiteInventoryStore.cs
index ef4ef99..e29b99c 100644
--- a/OpenSim/Data/SQLite/SQLiteInventoryStore.cs
+++ b/OpenSim/Data/SQLite/SQLiteInventoryStore.cs
@@ -392,6 +392,7 @@ namespace OpenSim.Data.SQLite
392 { 392 {
393 folders.Add(buildFolder(row)); 393 folders.Add(buildFolder(row));
394 } 394 }
395
395 } 396 }
396 } 397 }
397 398
@@ -414,12 +415,100 @@ namespace OpenSim.Data.SQLite
414 /// <returns></returns> 415 /// <returns></returns>
415 public List<InventoryFolderBase> getFolderHierarchy(LLUUID parentID) 416 public List<InventoryFolderBase> getFolderHierarchy(LLUUID parentID)
416 { 417 {
417 List<InventoryFolderBase> folders = new List<InventoryFolderBase>(); 418 /* Note: There are subtle changes between this implementation of getFolderHierarchy and the previous one
418 getInventoryFolders(ref folders, Util.ToRawUuidString(parentID)); 419 * - We will only need to hit the database twice instead of n times.
420 * - We assume the database is well-formed - no stranded/dangling folders, all folders in heirarchy owned
421 * by the same person, each user only has 1 inventory heirarchy
422 * - The returned list is not ordered, instead of breadth-first ordered
423 There are basically 2 usage cases for getFolderHeirarchy:
424 1) Getting the user's entire inventory heirarchy when they log in
425 2) Finding a subfolder heirarchy to delete when emptying the trash.
426 This implementation will pull all inventory folders from the database, and then prune away any folder that
427 is not part of the requested sub-heirarchy. The theory is that it is cheaper to make 1 request from the
428 database than to make n requests. This pays off only if requested heirarchy is large.
429 By making this choice, we are making the worst case better at the cost of making the best case worse
430 - Francis
431 */
419 432
420 for (int i = 0; i < folders.Count; i++) 433 List<InventoryFolderBase> folders = new List<InventoryFolderBase>();
421 getInventoryFolders(ref folders, Util.ToRawUuidString(folders[i].ID)); 434 DataRow[] folderRows = null, parentRow;
435 InventoryFolderBase parentFolder = null;
436 lock (ds)
437 {
438 /* Fetch the parent folder from the database to determine the agent ID.
439 * Then fetch all inventory folders for that agent from the agent ID.
440 */
441 DataTable inventoryFolderTable = ds.Tables["inventoryfolders"];
442 string selectExp = "UUID = '" + Util.ToRawUuidString(parentID) + "'";
443 parentRow = inventoryFolderTable.Select(selectExp); // Assume at most 1 result
444 if (parentRow.GetLength(0) >= 1) // No result means parent folder does not exist
445 {
446 parentFolder = buildFolder(parentRow[0]);
447 LLUUID agentID = parentFolder.Owner;
448 selectExp = "agentID = '" + Util.ToRawUuidString(agentID) + "'";
449 folderRows = inventoryFolderTable.Select(selectExp);
450 }
422 451
452 if ( folderRows!=null && folderRows.GetLength(0)>=1 ) // No result means parent folder does not exist
453 { // or has no children
454 /* if we're querying the root folder, just return an unordered list of all folders in the user's
455 * inventory
456 */
457 if (parentFolder.ParentID == LLUUID.Zero)
458 {
459 foreach (DataRow row in folderRows)
460 {
461 InventoryFolderBase curFolder = buildFolder(row);
462 if (curFolder.ID != parentID) // Return all folders except the parent folder of heirarchy
463 folders.Add(buildFolder(row));
464 }
465 } // If requesting root folder
466 /* else we are querying a non-root folder. We currently have a list of all of the user's folders,
467 * we must construct a list of all folders in the heirarchy below parentID.
468 * Our first step will be to construct a hash table of all folders, indexed by parent ID.
469 * Once we have constructed the hash table, we will do a breadth-first traversal on the tree using the
470 * hash table to find child folders.
471 */
472 else
473 { // Querying a non-root folder
474
475 // Build a hash table of all user's inventory folders, indexed by each folder's parent ID
476 Dictionary<LLUUID, List<InventoryFolderBase>> hashtable =
477 new Dictionary<LLUUID, List<InventoryFolderBase>>(folderRows.GetLength(0));
478
479 foreach (DataRow row in folderRows)
480 {
481 InventoryFolderBase curFolder = buildFolder(row);
482 if (curFolder.ParentID != LLUUID.Zero) // Discard root of tree - not needed
483 {
484 if ( hashtable.ContainsKey(curFolder.ParentID ) )
485 {
486 // Current folder already has a sibling - append to sibling list
487 hashtable[curFolder.ParentID].Add( curFolder );
488 }
489 else {
490 List<InventoryFolderBase> siblingList = new List<InventoryFolderBase>();
491 siblingList.Add( curFolder );
492 // Current folder has no known (yet) siblings
493 hashtable.Add( curFolder.ParentID, siblingList );
494 }
495 }
496 } // For all inventory folders
497
498 // Note: Could release the ds lock here - we don't access folderRows or the database anymore.
499 // This is somewhat of a moot point as the callers of this function usually lock db anyways.
500
501 if ( hashtable.ContainsKey( parentID ) ) // if requested folder does have children
502 folders.AddRange( hashtable[parentID] );
503
504 // BreadthFirstSearch build inventory tree **Note: folders.Count is *not* static
505 for ( int i = 0; i < folders.Count; i++ )
506 if (hashtable.ContainsKey(folders[i].ID))
507 folders.AddRange(hashtable[folders[i].ID]);
508
509 } // if requesting a subfolder heirarchy
510 } // if folder parentID exists and has children
511 } // lock ds
423 return folders; 512 return folders;
424 } 513 }
425 514