diff options
author | Charles Krinke | 2008-08-10 16:44:25 +0000 |
---|---|---|
committer | Charles Krinke | 2008-08-10 16:44:25 +0000 |
commit | 54af3b4f4dd8a2885dcc57904f04d603bb444f24 (patch) | |
tree | c66693db07a1452595c08c509b818f94003fe3c2 /OpenSim/Data/SQLite | |
parent | Mantis#1910. Thank you kindly, HomerHorwitz for a patch that: (diff) | |
download | opensim-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.cs | 97 |
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 | ||