[fireball] 36053: - Implement a linear search in CmpFindSubKeyInRoot (until cells are stored in a lexically sorted way). - Implement Leaf->Root index conversion (leaf selecting algorithm, splitting the leaf if necessary). See issue #3418 for more details.
Author: fireball Date: Mon Sep 8 07:56:08 2008 New Revision: 36053
URL: http://svn.reactos.org/svn/reactos?rev=36053&view=rev Log: - Implement a linear search in CmpFindSubKeyInRoot (until cells are stored in a lexically sorted way). - Implement Leaf->Root index conversion (leaf selecting algorithm, splitting the leaf if necessary). See issue #3418 for more details.
Modified: trunk/reactos/ntoskrnl/config/cmindex.c
Modified: trunk/reactos/ntoskrnl/config/cmindex.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/config/cmindex.c?r... ============================================================================== --- trunk/reactos/ntoskrnl/config/cmindex.c [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/config/cmindex.c [iso-8859-1] Mon Sep 8 07:56:08 2008 @@ -145,13 +145,12 @@ IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey) { - ULONG High, Low = 0, i, ReturnIndex; + ULONG High, Low = 0, i = 0, ReturnIndex; HCELL_INDEX LeafCell; PCM_KEY_INDEX Leaf; LONG Result;
/* Verify Index for validity */ - ASSERTMSG("We don't do a linear search yet!\n", FALSE); ASSERT(Index->Count != 0); ASSERT(Index->Signature == CM_KEY_INDEX_ROOT);
@@ -160,7 +159,9 @@ while (TRUE) { /* Choose next entry */ +#ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED i = ((High - Low) / 2) + Low; +#endif
/* Get the leaf cell and then the leaf itself */ LeafCell = Index->List[i]; @@ -190,6 +191,7 @@ goto Return; }
+#ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED /* Check for negative result */ if (Result < 0) { @@ -228,6 +230,7 @@ /* Update the base to this index, since we know it's not lower. */ Low = i; } +#endif } else { @@ -242,6 +245,16 @@
/* Release the leaf cell */ HvReleaseCell(Hive, LeafCell); + +#ifndef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED + /* Go to the next index, and return failure if we reach the end */ + if (++i > High) + { + /* Return failure */ + *SubKey = HCELL_NIL; + return 0; + } +#endif }
/* Make sure we got here for the right reasons */ @@ -1114,6 +1127,366 @@ /* Update the leaf count and return the new cell */ Leaf->Count += 1; return NewCell; +} + +HCELL_INDEX +NTAPI +CmpSplitLeaf(IN PHHIVE Hive, + IN HCELL_INDEX RootCell, + IN ULONG RootSelect, + IN HSTORAGE_TYPE Type) +{ + PCM_KEY_INDEX IndexKey, LeafKey, NewKey; + PCM_KEY_FAST_INDEX FastLeaf; + HCELL_INDEX LeafCell, NewCell; + ULONG FirstHalf, LastHalf; + ULONG EntrySize, TotalSize; + + /* Get the cell */ + IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, RootCell); + + /* Check if we've got valid IndexKey */ + if (!IndexKey) return HCELL_NIL; + + /* Get the leaf cell and key */ + LeafCell = IndexKey->List[RootSelect]; + LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell); + + /* Check if we've got valid LeafKey */ + if (!LeafKey) return HCELL_NIL; + + /* We are going to divide this leaf into two halves */ + FirstHalf = (LeafKey->Count / 2); + LastHalf = LeafKey->Count - FirstHalf; + + /* Now check what kind of hive we're dealing with, + * and compute entry size + */ + if (Hive->Version >= 5) + { + /* XP Hive: Use hash leaf */ + ASSERT(LeafKey->Signature == CM_KEY_HASH_LEAF); + EntrySize = sizeof(CM_INDEX); + } + else + { + /* Use index leaf */ + ASSERT(LeafKey->Signature == CM_KEY_INDEX_LEAF); + EntrySize = sizeof(HCELL_INDEX); + } + + /* Compute the total size */ + TotalSize = (EntrySize * LastHalf) + FIELD_OFFSET(CM_KEY_INDEX, List) + 1; + + /* Mark the leaf cell dirty */ + HvMarkCellDirty(Hive, LeafCell, FALSE); + + /* Make sure its type is the same */ + ASSERT(HvGetCellType(LeafCell) == Type); + + /* Allocate the cell, fail in case of error */ + NewCell = HvAllocateCell(Hive, TotalSize, Type, LeafCell); + if (NewCell == HCELL_NIL) return NewCell; + + /* Get the key */ + NewKey = (PCM_KEY_INDEX)HvGetCell(Hive, NewCell); + if (!NewKey) + { + /* Free the cell and exit - should not happen! */ + ASSERT(FALSE); + HvFreeCell(Hive, NewCell); + return HCELL_NIL; + } + + /* Release the newly created cell */ + HvReleaseCell(Hive, NewCell); + + /* Set its signature according to the version of the hive */ + if (Hive->Version >= 5) + { + /* XP Hive: Use hash leaf signature */ + NewKey->Signature = CM_KEY_HASH_LEAF; + } + else + { + /* Use index leaf signature */ + NewKey->Signature = CM_KEY_INDEX_LEAF; + } + + /* Calculate the size of the free entries in the root key */ + TotalSize = HvGetCellSize(Hive, IndexKey) - + (IndexKey->Count * sizeof(HCELL_INDEX)) - + FIELD_OFFSET(CM_KEY_INDEX, List); + + /* Check if we're out of space */ + if (TotalSize / sizeof(HCELL_INDEX) < 1) + { + /* Grow the leaf by one more entry */ + TotalSize = HvGetCellSize(Hive, IndexKey) + sizeof(HCELL_INDEX); + + /* Re-allocate the root */ + RootCell = HvReallocateCell(Hive, RootCell, TotalSize); + if (RootCell == HCELL_NIL) + { + /* Free the cell and exit */ + HvFreeCell(Hive, NewCell); + return HCELL_NIL; + } + + /* Get the leaf cell */ + IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, RootCell); + if (!IndexKey) + { + /* This shouldn't happen */ + ASSERT(FALSE); + return HCELL_NIL; + } + } + + /* Splitting is done, now we need to copy the contents, + * according to the hive version + */ + if (Hive->Version >= 5) + { + /* Copy the fast indexes */ + FastLeaf = (PCM_KEY_FAST_INDEX)LeafKey; + RtlMoveMemory(&NewKey->List[0], + &FastLeaf->List[FirstHalf], + LastHalf * EntrySize); + } + else + { + /* Copy the indexes themselves */ + RtlMoveMemory(&NewKey->List[0], + &LeafKey->List[FirstHalf], + LastHalf * EntrySize); + } + + /* Shift the data inside the root key */ + if (RootSelect < (IndexKey->Count - 1)) + { + RtlMoveMemory(&IndexKey->List[RootSelect + 2], + &IndexKey->List[RootSelect + 1], + IndexKey->Count - + (RootSelect + 1) * sizeof(HCELL_INDEX)); + } + + /* Make sure both old and new computed counts are valid */ + ASSERT(FirstHalf != 0); + ASSERT(LastHalf != 0); + + /* Update the count value of old and new keys */ + LeafKey->Count = FirstHalf; + NewKey->Count = LastHalf; + + /* Increase the count value of the root key */ + IndexKey->Count++; + + /* Set the new cell in root's list */ + IndexKey->List[RootSelect + 1] = NewCell; + + /* Return the root cell */ + return RootCell; +} + +HCELL_INDEX +NTAPI +CmpSelectLeaf(IN PHHIVE Hive, + IN PCM_KEY_NODE KeyNode, + IN PUNICODE_STRING Name, + IN HSTORAGE_TYPE Type, + IN PHCELL_INDEX *RootCell) +{ + PCM_KEY_INDEX IndexKey, LeafKey; + PCM_KEY_FAST_INDEX FastLeaf; + HCELL_INDEX LeafCell, CurrentCell; + ULONG SubKeyIndex; + LONG Result; + + /* Mark it as dirty */ + HvMarkCellDirty(Hive, KeyNode->SubKeyLists[Type], FALSE); + + /* Get the cell */ + IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]); + + /* Check if we've got a valid key */ + if (!IndexKey) + { + /* Should not happen! */ + ASSERTMSG("IndexKey = NULL!, it should not happen!\n", FALSE); + return HCELL_NIL; + } + + /* Sanity check */ + ASSERT(IndexKey->Signature == CM_KEY_INDEX_ROOT); + + while (TRUE) + { + /* Find subkey */ + SubKeyIndex = CmpFindSubKeyInRoot(Hive, IndexKey, Name, &LeafCell); + + /* Make sure we found something valid */ + if (SubKeyIndex & 0x80000000) return HCELL_NIL; + + /* Try to fit it into the LeafCell, if it was found */ + if (LeafCell != HCELL_NIL) + { + /* Get the leaf key */ + LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell); + + /* Check for failure */ + if (!LeafKey) return HCELL_NIL; + + /* Check if it fits into this leaf and break */ + if (LeafKey->Count < CmpMaxIndexPerHblock) + { + /* Fill in the result and return it */ + *RootCell = &IndexKey->List[SubKeyIndex]; + return LeafCell; + } + } + else + { + /* Get the leaf cell at the very end */ + LeafCell = IndexKey->List[SubKeyIndex]; + LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell); + + /* Return an error in case of problems */ + if (!LeafKey) return HCELL_NIL; + + /* Choose the cell to search from depending on the key type */ + if ((LeafKey->Signature == CM_KEY_FAST_LEAF) || + (LeafKey->Signature == CM_KEY_HASH_LEAF)) + { + FastLeaf = (PCM_KEY_FAST_INDEX)LeafKey; + CurrentCell = FastLeaf->List[0].Cell; + } + else + { + /* Make sure it's an index leaf */ + ASSERT(LeafKey->Signature == CM_KEY_INDEX_LEAF); + CurrentCell = LeafKey->List[0]; + } + + /* Do a name compare */ + Result = CmpDoCompareKeyName(Hive, Name, CurrentCell); + + /* Check for failure */ + if (Result == 2) return HCELL_NIL; + + /* Names can't be equal, ensure that */ + ASSERT(Result != 0); + + /* Check if it's above */ + if (Result >= 0) + { + /* Get the first cell in the index */ + LeafCell = IndexKey->List[0]; + LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell); + + /* Return an error in case of problems */ + if (!LeafKey) return HCELL_NIL; + + /* Check if it fits into this leaf and break */ + if (LeafKey->Count < CmpMaxIndexPerHblock) + { + /* Fill in the result and return the cell */ + *RootCell = &IndexKey->List[SubKeyIndex + 1]; + return LeafCell; + } + + /* No, it doesn't fit, check the other leaf */ + if (SubKeyIndex < (IndexKey->Count - 1)) + { + /* Yes, there is space */ + LeafCell = IndexKey->List[SubKeyIndex + 1]; + LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell); + + /* Return an error in case of problems */ + if (!LeafKey) return HCELL_NIL; + + /* Check if it fits and break */ + if (LeafKey->Count < CmpMaxIndexPerHblock) + { + /* Fill in the result and return the cell */ + *RootCell = &IndexKey->List[SubKeyIndex + 1]; + return LeafCell; + } + } + } + else + { + /* No, it's below, check the subkey index */ + if (SubKeyIndex > 0) + { + /* There should be space at the leaf one before that */ + LeafCell = IndexKey->List[SubKeyIndex - 1]; + LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell); + + /* Return an error in case of problems */ + if (!LeafKey) return HCELL_NIL; + + /* Check if it fits and break */ + if (LeafKey->Count < CmpMaxIndexPerHblock) + { + /* Decrement the subkey index */ + SubKeyIndex--; + + /* Fill in the result and return the cell */ + *RootCell = &IndexKey->List[SubKeyIndex]; + return LeafCell; + } + } + else + { + /* Use the first leaf, if possible */ + LeafCell = IndexKey->List[0]; + LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell); + + /* Return an error in case of problems */ + if (!LeafKey) return HCELL_NIL; + + /* Check if it fits and break */ + if (LeafKey->Count < CmpMaxIndexPerHblock) + { + /* Fill in the result and return the cell */ + *RootCell = &IndexKey->List[0]; + return LeafCell; + } + } + + /* It didn't fit into either, so proceed to splitting */ + } + } + + /* We need to split */ + CurrentCell = CmpSplitLeaf(Hive, + KeyNode->SubKeyLists[Type], + SubKeyIndex, + Type); + + /* Return failure in case splitting failed */ + if (CurrentCell == HCELL_NIL) return CurrentCell; + + /* Set the SubKeyLists value with the new key */ + KeyNode->SubKeyLists[Type] = CurrentCell; + + /* Get the new cell */ + IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]); + + /* Return in case of failure */ + if (!IndexKey) return HCELL_NIL; + + /* Make sure the new key became index root */ + ASSERT(IndexKey->Signature == CM_KEY_INDEX_ROOT); + + /* Now loop over with the new IndexKey value, which definately + * has the space now + */ + } + + /* Shouldn't come here */ + return HCELL_NIL; }
BOOLEAN @@ -1253,7 +1626,7 @@ /* Convert */ OldIndex = (PCM_KEY_FAST_INDEX)Index;
- for (i=0; i < OldIndex->Count; i++) + for (i = 0; i < OldIndex->Count; i++) { Index->List[i] = OldIndex->List[i].Cell; } @@ -1299,9 +1672,17 @@ /* Check if we turned the index into a root */ if (Index->Signature == CM_KEY_INDEX_ROOT) { - /* Not handled yet */ - DPRINT1("Leaf->Root Index Conversion not yet implemented!\n"); - ASSERT(FALSE); + DPRINT("Leaf->Root Index Conversion\n"); + + /* Get the leaf where to add the new entry (the routine will do + * the splitting if necessary) + */ + LeafCell = CmpSelectLeaf(Hive, KeyNode, &Name, Type, &RootPointer); + if (LeafCell == HCELL_NIL) + { + /* Not handled */ + ASSERT(FALSE); + } }
/* Add our leaf cell */
-
fireball＠svn.reactos.org