ReactOS 0.4.15-dev-5667-ged97270
cmindex.c File Reference
#include "cmlib.h"
#include <debug.h>
Include dependency graph for cmindex.c:

Go to the source code of this file.

Macros

#define NDEBUG
 
#define INVALID_INDEX   0x80000000
 
#define CmpMaxFastIndexPerHblock
 
#define CmpMaxIndexPerHblock
 

Functions

LONG NTAPI CmpDoCompareKeyName (IN PHHIVE Hive, IN PCUNICODE_STRING SearchName, IN HCELL_INDEX Cell)
 
LONG NTAPI CmpCompareInIndex (IN PHHIVE Hive, IN PCUNICODE_STRING SearchName, IN ULONG Count, IN PCM_KEY_INDEX Index, IN PHCELL_INDEX SubKey)
 
ULONG NTAPI CmpFindSubKeyInRoot (IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
 
ULONG NTAPI CmpFindSubKeyInLeaf (IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
 
ULONG NTAPI CmpComputeHashKey (IN ULONG Hash, IN PCUNICODE_STRING Name, IN BOOLEAN AllowSeparators)
 
HCELL_INDEX NTAPI CmpDoFindSubKeyByNumber (IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN ULONG Number)
 
HCELL_INDEX NTAPI CmpFindSubKeyByNumber (IN PHHIVE Hive, IN PCM_KEY_NODE Node, IN ULONG Number)
 
static HCELL_INDEX NTAPI CmpFindSubKeyByHash (IN PHHIVE Hive, IN PCM_KEY_FAST_INDEX FastIndex, IN PCUNICODE_STRING SearchName)
 
HCELL_INDEX NTAPI CmpFindSubKeyByName (IN PHHIVE Hive, IN PCM_KEY_NODE Parent, IN PCUNICODE_STRING SearchName)
 
BOOLEAN NTAPI CmpMarkIndexDirty (IN PHHIVE Hive, IN HCELL_INDEX ParentKey, IN HCELL_INDEX TargetKey)
 
HCELL_INDEX NTAPI CmpAddToLeaf (IN PHHIVE Hive, IN HCELL_INDEX LeafCell, IN HCELL_INDEX NewKey, IN PCUNICODE_STRING Name)
 
HCELL_INDEX NTAPI CmpSplitLeaf (IN PHHIVE Hive, IN HCELL_INDEX RootCell, IN ULONG RootSelect, IN HSTORAGE_TYPE Type)
 
HCELL_INDEX NTAPI CmpSelectLeaf (IN PHHIVE Hive, IN PCM_KEY_NODE KeyNode, IN PCUNICODE_STRING Name, IN HSTORAGE_TYPE Type, IN PHCELL_INDEX *RootCell)
 
BOOLEAN NTAPI CmpAddSubKey (IN PHHIVE Hive, IN HCELL_INDEX Parent, IN HCELL_INDEX Child)
 
BOOLEAN NTAPI CmpRemoveSubKey (IN PHHIVE Hive, IN HCELL_INDEX ParentKey, IN HCELL_INDEX TargetKey)
 

Macro Definition Documentation

◆ CmpMaxFastIndexPerHblock

#define CmpMaxFastIndexPerHblock
Value:
((HBLOCK_SIZE - (sizeof(HBIN) + sizeof(HCELL) + \
FIELD_OFFSET(CM_KEY_FAST_INDEX, List))) / sizeof(CM_INDEX))
struct _CM_INDEX CM_INDEX
#define HBLOCK_SIZE
Definition: hivedata.h:41
struct _HBIN HBIN
_Must_inspect_result_ _In_ WDFCMRESLIST List
Definition: wdfresource.h:550

Definition at line 19 of file cmindex.c.

◆ CmpMaxIndexPerHblock

#define CmpMaxIndexPerHblock
Value:
((HBLOCK_SIZE - (sizeof(HBIN) + sizeof(HCELL) + \
FIELD_OFFSET(CM_KEY_INDEX, List))) / sizeof(HCELL_INDEX) - 1)
ULONG HCELL_INDEX
Definition: hivedata.h:80

Definition at line 23 of file cmindex.c.

◆ INVALID_INDEX

#define INVALID_INDEX   0x80000000

Definition at line 17 of file cmindex.c.

◆ NDEBUG

#define NDEBUG

Definition at line 12 of file cmindex.c.

Function Documentation

◆ CmpAddSubKey()

BOOLEAN NTAPI CmpAddSubKey ( IN PHHIVE  Hive,
IN HCELL_INDEX  Parent,
IN HCELL_INDEX  Child 
)

Definition at line 1465 of file cmindex.c.

1468{
1469 PCM_KEY_NODE KeyNode;
1471 PCM_KEY_FAST_INDEX OldIndex;
1473 HCELL_INDEX IndexCell = HCELL_NIL, CellToRelease = HCELL_NIL, LeafCell;
1474 PHCELL_INDEX RootPointer = NULL;
1475 ULONG Type, i;
1476 BOOLEAN IsCompressed;
1477 PAGED_CODE();
1478
1479 /* Get the key node */
1480 KeyNode = (PCM_KEY_NODE)HvGetCell(Hive, Child);
1481 if (!KeyNode)
1482 {
1483 /* Shouldn't happen */
1484 ASSERT(FALSE);
1485 return FALSE;
1486 }
1487
1488 /* Check if the name is compressed */
1489 if (KeyNode->Flags & KEY_COMP_NAME)
1490 {
1491 /* Remember for later */
1492 IsCompressed = TRUE;
1493
1494 /* Create the compressed name and allocate it */
1495 Name.Length = CmpCompressedNameSize(KeyNode->Name, KeyNode->NameLength);
1496 Name.MaximumLength = Name.Length;
1497 Name.Buffer = Hive->Allocate(Name.Length, TRUE, TAG_CM);
1498 if (!Name.Buffer)
1499 {
1500 /* Release the cell and fail */
1501 HvReleaseCell(Hive, Child);
1502 ASSERT(FALSE);
1503 return FALSE;
1504 }
1505
1506 /* Copy the compressed name */
1508 Name.MaximumLength,
1509 KeyNode->Name,
1510 KeyNode->NameLength);
1511 }
1512 else
1513 {
1514 /* Remember for later */
1515 IsCompressed = FALSE;
1516
1517 /* Build the unicode string */
1518 Name.Length = KeyNode->NameLength;
1519 Name.MaximumLength = KeyNode->NameLength;
1520 Name.Buffer = &KeyNode->Name[0];
1521 }
1522
1523 /* Release the cell */
1524 HvReleaseCell(Hive, Child);
1525
1526 /* Get the parent node */
1527 KeyNode = (PCM_KEY_NODE)HvGetCell(Hive, Parent);
1528 if (!KeyNode)
1529 {
1530 /* Not handled */
1531 ASSERT(FALSE);
1532 }
1533
1534 /* Find out the type of the cell, and check if this is the first subkey */
1536 if (!KeyNode->SubKeyCounts[Type])
1537 {
1538 /* Allocate a fast leaf */
1539 IndexCell = HvAllocateCell(Hive, sizeof(CM_KEY_FAST_INDEX), Type, HCELL_NIL);
1540 if (IndexCell == HCELL_NIL)
1541 {
1542 /* Not handled */
1543 ASSERT(FALSE);
1544 }
1545
1546 /* Get the leaf cell */
1547 Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
1548 if (!Index)
1549 {
1550 /* Shouldn't happen */
1551 ASSERT(FALSE);
1552 }
1553
1554 /* Now check what kind of hive we're dealing with */
1555 if (Hive->Version >= 5)
1556 {
1557 /* XP Hive: Use hash leaf */
1558 Index->Signature = CM_KEY_HASH_LEAF;
1559 }
1560 else if (Hive->Version >= 3)
1561 {
1562 /* Windows 2000 and ReactOS: Use fast leaf */
1563 Index->Signature = CM_KEY_FAST_LEAF;
1564 }
1565 else
1566 {
1567 /* NT 4: Use index leaf */
1568 Index->Signature = CM_KEY_INDEX_LEAF;
1569 }
1570
1571 /* Setup the index list */
1572 Index->Count = 0;
1573 KeyNode->SubKeyLists[Type] = IndexCell;
1574 }
1575 else
1576 {
1577 /* We already have an index, get it */
1578 Index = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
1579 if (!Index)
1580 {
1581 /* Not handled */
1582 ASSERT(FALSE);
1583 }
1584
1585 /* Remember to release the cell later */
1586 CellToRelease = KeyNode->SubKeyLists[Type];
1587
1588 /* Check if this is a fast leaf that's gotten too full */
1589 if ((Index->Signature == CM_KEY_FAST_LEAF) &&
1590 (Index->Count >= CmpMaxFastIndexPerHblock))
1591 {
1592 DPRINT("Doing Fast->Slow Leaf conversion\n");
1593
1594 /* Mark this cell as dirty */
1595 HvMarkCellDirty(Hive, CellToRelease, FALSE);
1596
1597 /* Convert */
1598 OldIndex = (PCM_KEY_FAST_INDEX)Index;
1599
1600 for (i = 0; i < OldIndex->Count; i++)
1601 {
1602 Index->List[i] = OldIndex->List[i].Cell;
1603 }
1604
1605 /* Set the new type value */
1606 Index->Signature = CM_KEY_INDEX_LEAF;
1607 }
1608 else if (((Index->Signature == CM_KEY_INDEX_LEAF) ||
1609 (Index->Signature == CM_KEY_HASH_LEAF)) &&
1610 (Index->Count >= CmpMaxIndexPerHblock))
1611 {
1612 /* This is an old/hashed leaf that's gotten too large, root it */
1613 IndexCell = HvAllocateCell(Hive,
1614 sizeof(CM_KEY_INDEX) +
1615 sizeof(HCELL_INDEX),
1616 Type,
1617 HCELL_NIL);
1618 if (IndexCell == HCELL_NIL)
1619 {
1620 /* Not handled */
1621 ASSERT(FALSE);
1622 }
1623
1624 /* Get the index cell */
1625 Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
1626 if (!Index)
1627 {
1628 /* Shouldn't happen */
1629 ASSERT(FALSE);
1630 }
1631
1632 /* Mark the index as a root, and set the index cell */
1633 Index->Signature = CM_KEY_INDEX_ROOT;
1634 Index->Count = 1;
1635 Index->List[0] = KeyNode->SubKeyLists[Type];
1636 KeyNode->SubKeyLists[Type] = IndexCell;
1637 }
1638 }
1639
1640 /* Now we can choose the leaf cell */
1641 LeafCell = KeyNode->SubKeyLists[Type];
1642
1643 /* Check if we turned the index into a root */
1644 if (Index->Signature == CM_KEY_INDEX_ROOT)
1645 {
1646 DPRINT("Leaf->Root Index Conversion\n");
1647
1648 /* Get the leaf where to add the new entry (the routine will do
1649 * the splitting if necessary)
1650 */
1651 LeafCell = CmpSelectLeaf(Hive, KeyNode, &Name, Type, &RootPointer);
1652 if (LeafCell == HCELL_NIL)
1653 {
1654 /* Not handled */
1655 ASSERT(FALSE);
1656 }
1657 }
1658
1659 /* Add our leaf cell */
1660 LeafCell = CmpAddToLeaf(Hive, LeafCell, Child, &Name);
1661 if (LeafCell == HCELL_NIL)
1662 {
1663 /* Not handled */
1664 ASSERT(FALSE);
1665 }
1666
1667 /* Update the key counts */
1668 KeyNode->SubKeyCounts[Type]++;
1669
1670 /* Check if caller wants us to return the leaf */
1671 if (RootPointer)
1672 {
1673 /* Return it */
1674 *RootPointer = LeafCell;
1675 }
1676 else
1677 {
1678 /* Otherwise, mark it as the list index for the cell */
1679 KeyNode->SubKeyLists[Type] = LeafCell;
1680 }
1681
1682 /* If the name was compressed, free our copy */
1683 if (IsCompressed) Hive->Free(Name.Buffer, 0);
1684
1685 /* Release all our cells */
1686 if (IndexCell != HCELL_NIL) HvReleaseCell(Hive, IndexCell);
1687 if (CellToRelease != HCELL_NIL) HvReleaseCell(Hive, CellToRelease);
1688 HvReleaseCell(Hive, Parent);
1689 return TRUE;
1690}
#define PAGED_CODE()
unsigned char BOOLEAN
Type
Definition: Type.h:7
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn UINT32 *TableIdx UINT32 ACPI_TABLE_HEADER *OutTableHeader ACPI_TABLE_HEADER **OutTable ACPI_HANDLE UINT32 ACPI_WALK_CALLBACK ACPI_WALK_CALLBACK void void **ReturnValue UINT32 ACPI_BUFFER *RetPathPtr ACPI_OBJECT_HANDLER void *Data ACPI_OBJECT_HANDLER void **Data ACPI_STRING ACPI_OBJECT_LIST ACPI_BUFFER *ReturnObjectBuffer ACPI_DEVICE_INFO **ReturnBuffer ACPI_HANDLE Parent
Definition: acpixf.h:732
struct NameRec_ * Name
Definition: cdprocs.h:460
struct _CM_KEY_NODE * PCM_KEY_NODE
#define KEY_COMP_NAME
Definition: cmdata.h:35
#define CM_KEY_INDEX_LEAF
Definition: cmdata.h:14
#define CM_KEY_INDEX_ROOT
Definition: cmdata.h:13
struct _CM_KEY_FAST_INDEX * PCM_KEY_FAST_INDEX
#define CM_KEY_FAST_LEAF
Definition: cmdata.h:15
struct _CM_KEY_INDEX * PCM_KEY_INDEX
#define CM_KEY_HASH_LEAF
Definition: cmdata.h:16
HCELL_INDEX NTAPI CmpSelectLeaf(IN PHHIVE Hive, IN PCM_KEY_NODE KeyNode, IN PCUNICODE_STRING Name, IN HSTORAGE_TYPE Type, IN PHCELL_INDEX *RootCell)
Definition: cmindex.c:1264
#define CmpMaxFastIndexPerHblock
Definition: cmindex.c:19
#define CmpMaxIndexPerHblock
Definition: cmindex.c:23
HCELL_INDEX NTAPI CmpAddToLeaf(IN PHHIVE Hive, IN HCELL_INDEX LeafCell, IN HCELL_INDEX NewKey, IN PCUNICODE_STRING Name)
Definition: cmindex.c:921
#define HvReleaseCell(Hive, Cell)
Definition: cmlib.h:384
VOID NTAPI CmpCopyCompressedName(OUT PWCHAR Destination, IN ULONG DestinationLength, IN PWCHAR Source, IN ULONG SourceLength)
Definition: cmname.c:56
USHORT NTAPI CmpCompressedNameSize(IN PWCHAR Name, IN ULONG Length)
Definition: cmname.c:95
BOOLEAN CMAPI HvMarkCellDirty(PHHIVE RegistryHive, HCELL_INDEX CellOffset, BOOLEAN HoldingLock)
Definition: hivecell.c:109
#define HvGetCell(Hive, Cell)
Definition: cmlib.h:381
HCELL_INDEX CMAPI HvAllocateCell(PHHIVE RegistryHive, ULONG Size, HSTORAGE_TYPE Storage, IN HCELL_INDEX Vicinity)
#define TAG_CM
Definition: cmlib.h:205
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
ULONG * PHCELL_INDEX
Definition: hivedata.h:80
#define HCELL_NIL
Definition: hivedata.h:85
#define HvGetCellType(Cell)
Definition: hivedata.h:95
#define ASSERT(a)
Definition: mode.c:44
#define DPRINT
Definition: sndvol32.h:71
HCELL_INDEX Cell
Definition: cmdata.h:165
CM_INDEX List[ANYSIZE_ARRAY]
Definition: cmdata.h:190
WCHAR Name[ANYSIZE_ARRAY]
Definition: cmdata.h:116
HCELL_INDEX SubKeyLists[HTYPE_COUNT]
Definition: cmdata.h:102
ULONG SubKeyCounts[HTYPE_COUNT]
Definition: cmdata.h:97
USHORT NameLength
Definition: cmdata.h:114
USHORT Flags
Definition: cmdata.h:93
uint32_t ULONG
Definition: typedefs.h:59
_In_ WDFCOLLECTION _In_ ULONG Index
_Must_inspect_result_ _In_ WDFDEVICE _In_ WDFDEVICE Child
Definition: wdffdo.h:536

Referenced by CmiAddSubKey(), CmpCreateLinkNode(), CmpDeepCopyKeyInternal(), and CmpDoCreate().

◆ CmpAddToLeaf()

HCELL_INDEX NTAPI CmpAddToLeaf ( IN PHHIVE  Hive,
IN HCELL_INDEX  LeafCell,
IN HCELL_INDEX  NewKey,
IN PCUNICODE_STRING  Name 
)

Definition at line 921 of file cmindex.c.

925{
926 PCM_KEY_INDEX Leaf;
927 PCM_KEY_FAST_INDEX FastLeaf;
928 ULONG Size, OldSize, EntrySize, i, j;
929 HCELL_INDEX NewCell, Child;
930 LONG Result;
931
932 /* Mark the leaf dirty */
933 HvMarkCellDirty(Hive, LeafCell, FALSE);
934
935 /* Get the leaf cell */
936 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
937 if (!Leaf)
938 {
939 /* Shouldn't happen */
940 ASSERT(FALSE);
941 return HCELL_NIL;
942 }
943
944 /* Release it */
945 HvReleaseCell(Hive, LeafCell);
946
947 /* Check if this is an index leaf */
948 if (Leaf->Signature == CM_KEY_INDEX_LEAF)
949 {
950 /* This is an old-style leaf */
951 FastLeaf = NULL;
952 EntrySize = sizeof(HCELL_INDEX);
953 }
954 else
955 {
956 /* Sanity check */
957 ASSERT((Leaf->Signature == CM_KEY_FAST_LEAF) ||
958 (Leaf->Signature == CM_KEY_HASH_LEAF));
959
960 /* This is a new-style optimized fast (or hash) leaf */
961 FastLeaf = (PCM_KEY_FAST_INDEX)Leaf;
962 EntrySize = sizeof(CM_INDEX);
963 }
964
965 /* Get the current size of the leaf */
966 OldSize = HvGetCellSize(Hive, Leaf);
967
968 /* Calculate the size of the free entries */
969 Size = OldSize;
971
972 /* Assume we'll re-use the same leaf */
973 NewCell = LeafCell;
974
975 /* Check if we're out of space */
976 if ((Size / EntrySize) < 1)
977 {
978 /* Grow the leaf by 1.5x, making sure we can at least fit this entry */
979 Size = OldSize + OldSize / 2;
980 if (Size < (OldSize + EntrySize)) Size = OldSize + EntrySize;
981
982 /* Re-allocate the leaf */
983 NewCell = HvReallocateCell(Hive, LeafCell, Size);
984 if (NewCell == HCELL_NIL) return HCELL_NIL;
985
986 /* Get the leaf cell */
987 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, NewCell);
988 if (!Leaf)
989 {
990 /* This shouldn't happen */
991 ASSERT(FALSE);
992 return HCELL_NIL;
993 }
994
995 /* Release the cell */
996 HvReleaseCell(Hive, NewCell);
997
998 /* Update the fast leaf pointer if we had one */
999 if (FastLeaf) FastLeaf = (PCM_KEY_FAST_INDEX)Leaf;
1000 }
1001
1002 /* Find the insertion point for our entry */
1003 i = CmpFindSubKeyInLeaf(Hive, Leaf, Name, &Child);
1004 if (i & INVALID_INDEX) return HCELL_NIL;
1006
1007 /* Check if we're not last */
1008 if (i != Leaf->Count)
1009 {
1010 /* Find out where we should go */
1012 Name,
1013 i,
1014 Leaf,
1015 &Child);
1016 if (Result == 2) return HCELL_NIL;
1017 ASSERT(Result != 0);
1018
1019 /* Check if we come after */
1020 if (Result > 0)
1021 {
1022 /* We do, insert us after the key */
1023 ASSERT(Result == 1);
1024 i++;
1025 }
1026
1027 /* Check if we're still not last */
1028 if (i != Leaf->Count)
1029 {
1030 /* Check if we had a fast leaf or not */
1031 if (FastLeaf)
1032 {
1033 /* Copy the fast indexes */
1034 RtlMoveMemory(&FastLeaf->List[i + 1],
1035 &FastLeaf->List[i],
1036 (FastLeaf->Count - i) * sizeof(CM_INDEX));
1037 }
1038 else
1039 {
1040 /* Copy the indexes themselves */
1041 RtlMoveMemory(&Leaf->List[i + 1],
1042 &Leaf->List[i],
1043 (Leaf->Count - i) * sizeof(HCELL_INDEX));
1044 }
1045 }
1046 }
1047
1048 /* Check if this is a new-style leaf */
1049 if (FastLeaf)
1050 {
1051 /* Set our cell */
1052 FastLeaf->List[i].Cell = NewKey;
1053
1054 /* Check if this is a hash leaf */
1055 if( FastLeaf->Signature == CM_KEY_HASH_LEAF )
1056 {
1057 /* Set our hash key */
1058 FastLeaf->List[i].HashKey = CmpComputeHashKey(0, Name, FALSE);
1059 }
1060 else
1061 {
1062 /* First, clear the name */
1063 FastLeaf->List[i].NameHint[0] = 0;
1064 FastLeaf->List[i].NameHint[1] = 0;
1065 FastLeaf->List[i].NameHint[2] = 0;
1066 FastLeaf->List[i].NameHint[3] = 0;
1067
1068 /* Now, figure out if we can fit */
1069 if (Name->Length / sizeof(WCHAR) < 4)
1070 {
1071 /* We can fit, use our length */
1072 j = Name->Length / sizeof(WCHAR);
1073 }
1074 else
1075 {
1076 /* We can't, use a maximum of 4 */
1077 j = 4;
1078 }
1079
1080 /* Now fill out the name hint */
1081 do
1082 {
1083 /* Look for invalid characters and break out if we found one */
1084 if ((USHORT)Name->Buffer[j - 1] > (UCHAR)-1) break;
1085
1086 /* Otherwise, copy the a character */
1087 FastLeaf->List[i].NameHint[j - 1] = (UCHAR)Name->Buffer[j - 1];
1088 } while (--j > 0);
1089 }
1090 }
1091 else
1092 {
1093 /* This is an old-style leaf, just set our index directly */
1094 Leaf->List[i] = NewKey;
1095 }
1096
1097 /* Update the leaf count and return the new cell */
1098 Leaf->Count += 1;
1099 return NewCell;
1100}
LONG NTAPI CmpCompareInIndex(IN PHHIVE Hive, IN PCUNICODE_STRING SearchName, IN ULONG Count, IN PCM_KEY_INDEX Index, IN PHCELL_INDEX SubKey)
Definition: cmindex.c:67
ULONG NTAPI CmpFindSubKeyInLeaf(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
Definition: cmindex.c:358
#define INVALID_INDEX
Definition: cmindex.c:17
ULONG NTAPI CmpComputeHashKey(IN ULONG Hash, IN PCUNICODE_STRING Name, IN BOOLEAN AllowSeparators)
Definition: cmindex.c:460
LONG CMAPI HvGetCellSize(PHHIVE RegistryHive, PVOID Cell)
HCELL_INDEX CMAPI HvReallocateCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset, ULONG Size)
Definition: hivecell.c:421
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
long LONG
Definition: pedump.c:60
unsigned short USHORT
Definition: pedump.c:61
UCHAR NameHint[4]
Definition: cmdata.h:168
ULONG HashKey
Definition: cmdata.h:169
USHORT Signature
Definition: cmdata.h:188
USHORT Signature
Definition: cmdata.h:178
USHORT Count
Definition: cmdata.h:179
HCELL_INDEX List[ANYSIZE_ARRAY]
Definition: cmdata.h:180
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:255
#define RtlMoveMemory(Destination, Source, Length)
Definition: typedefs.h:264
_Must_inspect_result_ _In_ WDFDEVICE _In_ PWDF_DEVICE_PROPERTY_DATA _In_ DEVPROPTYPE _In_ ULONG Size
Definition: wdfdevice.h:4533
_At_(*)(_In_ PWSK_CLIENT Client, _In_opt_ PUNICODE_STRING NodeName, _In_opt_ PUNICODE_STRING ServiceName, _In_opt_ ULONG NameSpace, _In_opt_ GUID *Provider, _In_opt_ PADDRINFOEXW Hints, _Outptr_ PADDRINFOEXW *Result, _In_opt_ PEPROCESS OwningProcess, _In_opt_ PETHREAD OwningThread, _Inout_ PIRP Irp Result)(Mem)) NTSTATUS(WSKAPI *PFN_WSK_GET_ADDRESS_INFO
Definition: wsk.h:426
_In_ UCHAR EntrySize
Definition: iofuncs.h:642
unsigned char UCHAR
Definition: xmlstorage.h:181
__wchar_t WCHAR
Definition: xmlstorage.h:180

Referenced by CmpAddSubKey().

◆ CmpCompareInIndex()

LONG NTAPI CmpCompareInIndex ( IN PHHIVE  Hive,
IN PCUNICODE_STRING  SearchName,
IN ULONG  Count,
IN PCM_KEY_INDEX  Index,
IN PHCELL_INDEX  SubKey 
)

Definition at line 67 of file cmindex.c.

72{
73 PCM_KEY_FAST_INDEX FastIndex;
74 PCM_INDEX FastEntry;
76 ULONG i;
77 ULONG ActualNameLength = 4, CompareLength, NameLength;
78 WCHAR p, pp;
79
80 /* Assume failure */
81 *SubKey = HCELL_NIL;
82
83 /* Check if we are a fast or hashed leaf */
84 if ((Index->Signature == CM_KEY_FAST_LEAF) ||
85 (Index->Signature == CM_KEY_HASH_LEAF))
86 {
87 /* Get the Fast/Hash Index */
88 FastIndex = (PCM_KEY_FAST_INDEX)Index;
89 FastEntry = &FastIndex->List[Count];
90
91 /* Check if we are a hash leaf, in which case we skip all this */
92 if (Index->Signature == CM_KEY_FAST_LEAF)
93 {
94 /* Find out just how much of the name is there */
95 for (i = 0; i < 4; i++)
96 {
97 /* Check if this entry is empty */
98 if (!FastEntry->NameHint[i])
99 {
100 /* Only this much! */
101 ActualNameLength = i;
102 break;
103 }
104 }
105
106 /* How large is the name and how many characters to compare */
107 NameLength = SearchName->Length / sizeof(WCHAR);
108 CompareLength = min(NameLength, ActualNameLength);
109
110 /* Loop all the chars we'll test */
111 for (i = 0; i < CompareLength; i++)
112 {
113 /* Get one char from each buffer */
114 p = SearchName->Buffer[i];
115 pp = FastEntry->NameHint[i];
116
117 /* See if they match and return result if they don't */
120 if (Result) return (Result > 0) ? 1 : -1;
121 }
122 }
123
124 /* If we got here then we have to do a full compare */
125 Result = CmpDoCompareKeyName(Hive, SearchName, FastEntry->Cell);
126 if (Result == 2) return Result;
127 if (!Result) *SubKey = FastEntry->Cell;
128 }
129 else
130 {
131 /* We aren't, so do a name compare and return the subkey found */
132 Result = CmpDoCompareKeyName(Hive, SearchName, Index->List[Count]);
133 if (Result == 2) return Result;
134 if (!Result) *SubKey = Index->List[Count];
135 }
136
137 /* Return the comparison result */
138 return Result;
139}
LONG NTAPI CmpDoCompareKeyName(IN PHHIVE Hive, IN PCUNICODE_STRING SearchName, IN HCELL_INDEX Cell)
Definition: cmindex.c:31
GLfloat GLfloat p
Definition: glext.h:8902
#define min(a, b)
Definition: monoChain.cc:55
WCHAR NTAPI RtlUpcaseUnicodeChar(_In_ WCHAR Source)
Definition: nlsboot.c:176
int Count
Definition: noreturn.cpp:7

Referenced by CmpAddToLeaf(), CmpFindSubKeyInLeaf(), and CmpFindSubKeyInRoot().

◆ CmpComputeHashKey()

ULONG NTAPI CmpComputeHashKey ( IN ULONG  Hash,
IN PCUNICODE_STRING  Name,
IN BOOLEAN  AllowSeparators 
)

Definition at line 460 of file cmindex.c.

463{
464 LPWSTR Cp;
465 ULONG Value, i;
466
467 /* Make some sanity checks on our parameters */
468 ASSERT((Name->Length == 0) ||
469 (AllowSeparators) ||
470 (Name->Buffer[0] != OBJ_NAME_PATH_SEPARATOR));
471
472 /* If the name is empty, there is nothing to hash! */
473 if (!Name->Length) return Hash;
474
475 /* Set the buffer and loop every character */
476 Cp = Name->Buffer;
477 for (i = 0; i < Name->Length; i += sizeof(WCHAR), Cp++)
478 {
479 /* Make sure we don't have a separator when we shouldn't */
480 ASSERT(AllowSeparators || (*Cp != OBJ_NAME_PATH_SEPARATOR));
481
482 /* Check what kind of char we have */
483 if (*Cp >= L'a')
484 {
485 /* In the lower case region... is it truly lower case? */
486 if (*Cp < L'z')
487 {
488 /* Yes! Calculate it ourselves! */
489 Value = *Cp - L'a' + L'A';
490 }
491 else
492 {
493 /* No, use the API */
495 }
496 }
497 else
498 {
499 /* Reuse the char, it's already upcased */
500 Value = *Cp;
501 }
502
503 /* Multiply by a prime and add our value */
504 Hash *= 37;
505 Hash += Value;
506 }
507
508 /* Return the hash */
509 return Hash;
510}
#define OBJ_NAME_PATH_SEPARATOR
Definition: arcname_tests.c:25
static int Hash(const char *)
Definition: reader.c:2257
#define L(x)
Definition: ntvdm.h:50
_Must_inspect_result_ _In_ WDFKEY _In_ PCUNICODE_STRING _Out_opt_ PUSHORT _Inout_opt_ PUNICODE_STRING Value
Definition: wdfregistry.h:413
WCHAR * LPWSTR
Definition: xmlstorage.h:184

Referenced by CmpAddToLeaf(), and CmpFindSubKeyByHash().

◆ CmpDoCompareKeyName()

LONG NTAPI CmpDoCompareKeyName ( IN PHHIVE  Hive,
IN PCUNICODE_STRING  SearchName,
IN HCELL_INDEX  Cell 
)

Definition at line 31 of file cmindex.c.

34{
38
39 /* Get the node */
40 Node = (PCM_KEY_NODE)HvGetCell(Hive, Cell);
41 if (!Node) return 2;
42
43 /* Check if it's compressed */
44 if (Node->Flags & KEY_COMP_NAME)
45 {
46 /* Compare compressed names */
48 Node->Name,
49 Node->NameLength);
50 }
51 else
52 {
53 /* Compare the Unicode name directly */
54 KeyName.Buffer = Node->Name;
55 KeyName.Length = Node->NameLength;
56 KeyName.MaximumLength = KeyName.Length;
58 }
59
60 /* Release the cell and return the normalized result */
61 HvReleaseCell(Hive, Cell);
62 return (Result == 0) ? Result : ((Result > 0) ? 1 : -1);
63}
LONG NTAPI CmpCompareCompressedName(IN PCUNICODE_STRING SearchName, IN PWCHAR CompressedName, IN ULONG NameLength)
Definition: cmname.c:109
union node Node
Definition: types.h:1255
ULONG RtlCompareUnicodeString(PUNICODE_STRING s1, PUNICODE_STRING s2, BOOLEAN UpCase)
Definition: string_lib.cpp:31
Definition: dlist.c:348
_Must_inspect_result_ _In_ WDFDEVICE _In_ PCUNICODE_STRING KeyName
Definition: wdfdevice.h:2699

Referenced by CmpCompareInIndex(), CmpFindSubKeyByHash(), and CmpSelectLeaf().

◆ CmpDoFindSubKeyByNumber()

HCELL_INDEX NTAPI CmpDoFindSubKeyByNumber ( IN PHHIVE  Hive,
IN PCM_KEY_INDEX  Index,
IN ULONG  Number 
)

Definition at line 514 of file cmindex.c.

517{
518 ULONG i;
519 HCELL_INDEX LeafCell = 0;
520 PCM_KEY_INDEX Leaf = NULL;
521 PCM_KEY_FAST_INDEX FastIndex;
523
524 /* Check if this is a root */
525 if (Index->Signature == CM_KEY_INDEX_ROOT)
526 {
527 /* Loop the index */
528 for (i = 0; i < Index->Count; i++)
529 {
530 /* Check if this isn't the first iteration */
531 if (i)
532 {
533 /* Make sure we had something valid, and release it */
534 ASSERT(Leaf != NULL );
535 ASSERT(LeafCell == Index->List[i - 1]);
536 HvReleaseCell(Hive, LeafCell);
537 }
538
539 /* Get the leaf cell and the leaf for this index */
540 LeafCell = Index->List[i];
541 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
542 if (!Leaf) return HCELL_NIL;
543
544 /* Check if the index may be inside it */
545 if (Number < Leaf->Count)
546 {
547 /* Check if this is a fast or hash leaf */
548 if ((Leaf->Signature == CM_KEY_FAST_LEAF) ||
549 (Leaf->Signature == CM_KEY_HASH_LEAF))
550 {
551 /* Get the fast index */
552 FastIndex = (PCM_KEY_FAST_INDEX)Leaf;
553
554 /* Look inside the list to get our actual cell */
555 Result = FastIndex->List[Number].Cell;
556 HvReleaseCell(Hive, LeafCell);
557 return Result;
558 }
559 else
560 {
561 /* Regular leaf, so just use the index directly */
562 Result = Leaf->List[Number];
563
564 /* Release and return it */
565 HvReleaseCell(Hive,LeafCell);
566 return Result;
567 }
568 }
569 else
570 {
571 /* Otherwise, skip this leaf */
572 Number = Number - Leaf->Count;
573 }
574 }
575
576 /* Should never get here */
577 ASSERT(FALSE);
578 }
579
580 /* If we got here, then the cell is in this index */
581 ASSERT(Number < Index->Count);
582
583 /* Check if we're a fast or hash leaf */
584 if ((Index->Signature == CM_KEY_FAST_LEAF) ||
585 (Index->Signature == CM_KEY_HASH_LEAF))
586 {
587 /* We are, get the fast index and get the cell from the list */
588 FastIndex = (PCM_KEY_FAST_INDEX)Index;
589 return FastIndex->List[Number].Cell;
590 }
591 else
592 {
593 /* We aren't, so use the index directly to grab the cell */
594 return Index->List[Number];
595 }
596}
_In_opt_ PENTER_STATE_SYSTEM_HANDLER _In_opt_ PVOID _In_ LONG _In_opt_ LONG volatile * Number
Definition: ntpoapi.h:207

Referenced by CmpFindSubKeyByNumber().

◆ CmpFindSubKeyByHash()

static HCELL_INDEX NTAPI CmpFindSubKeyByHash ( IN PHHIVE  Hive,
IN PCM_KEY_FAST_INDEX  FastIndex,
IN PCUNICODE_STRING  SearchName 
)
static

Definition at line 646 of file cmindex.c.

649{
650 ULONG HashKey, i;
651 PCM_INDEX FastEntry;
652
653 /* Make sure it's really a hash */
654 ASSERT(FastIndex->Signature == CM_KEY_HASH_LEAF);
655
656 /* Compute the hash key for the name */
657 HashKey = CmpComputeHashKey(0, SearchName, FALSE);
658
659 /* Loop all the entries */
660 for (i = 0; i < FastIndex->Count; i++)
661 {
662 /* Get the entry */
663 FastEntry = &FastIndex->List[i];
664
665 /* Compare the hash first */
666 if (FastEntry->HashKey == HashKey)
667 {
668 /* Go ahead for a full compare */
669 if (!(CmpDoCompareKeyName(Hive, SearchName, FastEntry->Cell)))
670 {
671 /* It matched, return the cell */
672 return FastEntry->Cell;
673 }
674 }
675 }
676
677 /* If we got here then we failed */
678 return HCELL_NIL;
679}

Referenced by CmpFindSubKeyByName().

◆ CmpFindSubKeyByName()

HCELL_INDEX NTAPI CmpFindSubKeyByName ( IN PHHIVE  Hive,
IN PCM_KEY_NODE  Parent,
IN PCUNICODE_STRING  SearchName 
)

Definition at line 683 of file cmindex.c.

686{
687 ULONG i;
688 PCM_KEY_INDEX IndexRoot;
689 HCELL_INDEX SubKey, CellToRelease;
690 ULONG Found;
691
692 /* Loop each storage type */
693 for (i = 0; i < Hive->StorageTypeCount; i++)
694 {
695 /* Make sure the parent node has subkeys */
696 if (Parent->SubKeyCounts[i])
697 {
698 /* Get the Index */
699 IndexRoot = (PCM_KEY_INDEX)HvGetCell(Hive, Parent->SubKeyLists[i]);
700 if (!IndexRoot) return HCELL_NIL;
701
702 /* Get the cell we'll need to release */
703 CellToRelease = Parent->SubKeyLists[i];
704
705 /* Check if this is another index root */
706 if (IndexRoot->Signature == CM_KEY_INDEX_ROOT)
707 {
708 /* Lookup the name in the root */
710 IndexRoot,
711 SearchName,
712 &SubKey);
713
714 /* Release the previous cell */
715 ASSERT(CellToRelease != HCELL_NIL);
716 HvReleaseCell(Hive, CellToRelease);
717
718 /* Make sure we found something valid */
719 if (Found & INVALID_INDEX) break;
720
721 /* Get the new Index Root and set the new cell to be released */
722 if (SubKey == HCELL_NIL) continue;
723 CellToRelease = SubKey;
724 IndexRoot = (PCM_KEY_INDEX)HvGetCell(Hive, SubKey);
725 }
726
727 /* Make sure the signature is what we expect it to be */
728 ASSERT((IndexRoot->Signature == CM_KEY_INDEX_LEAF) ||
729 (IndexRoot->Signature == CM_KEY_FAST_LEAF) ||
730 (IndexRoot->Signature == CM_KEY_HASH_LEAF));
731
732 /* Check if this isn't a hashed leaf */
733 if (IndexRoot->Signature != CM_KEY_HASH_LEAF)
734 {
735 /* Find the subkey in the leaf */
737 IndexRoot,
738 SearchName,
739 &SubKey);
740
741 /* Release the previous cell */
742 ASSERT(CellToRelease != HCELL_NIL);
743 HvReleaseCell(Hive, CellToRelease);
744
745 /* Make sure we found a valid index */
746 if (Found & INVALID_INDEX) break;
747 }
748 else
749 {
750 /* Find the subkey in the hash */
751 SubKey = CmpFindSubKeyByHash(Hive,
752 (PCM_KEY_FAST_INDEX)IndexRoot,
753 SearchName);
754
755 /* Release the previous cell */
756 ASSERT(CellToRelease != HCELL_NIL);
757 HvReleaseCell(Hive, CellToRelease);
758 }
759
760 /* Make sure we got a valid subkey and return it */
761 if (SubKey != HCELL_NIL) return SubKey;
762 }
763 }
764
765 /* If we got here, then we failed */
766 return HCELL_NIL;
767}
return Found
Definition: dirsup.c:1270
ULONG NTAPI CmpFindSubKeyInRoot(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
Definition: cmindex.c:143
static HCELL_INDEX NTAPI CmpFindSubKeyByHash(IN PHHIVE Hive, IN PCM_KEY_FAST_INDEX FastIndex, IN PCUNICODE_STRING SearchName)
Definition: cmindex.c:646

Referenced by BiLoadHive(), BiOpenKey(), CmGetSystemControlValues(), CmpDoCreate(), CmpFindControlSet(), CmpFindDrivers(), CmpIsSafe(), CmpParseKey(), CmpSortDriverList(), CmpWalkPath(), RegOpenKey(), and RegpCreateOrOpenKey().

◆ CmpFindSubKeyByNumber()

HCELL_INDEX NTAPI CmpFindSubKeyByNumber ( IN PHHIVE  Hive,
IN PCM_KEY_NODE  Node,
IN ULONG  Number 
)

Definition at line 600 of file cmindex.c.

603{
606
607 /* Check if it's in the stable list */
608 if (Number < Node->SubKeyCounts[Stable])
609 {
610 /* Get the actual key index */
611 Index = (PCM_KEY_INDEX)HvGetCell(Hive, Node->SubKeyLists[Stable]);
612 if (!Index) return HCELL_NIL;
613
614 /* Do a search inside it */
616
617 /* Release the cell and return the result */
618 HvReleaseCell(Hive, Node->SubKeyLists[Stable]);
619 return Result;
620 }
621 else if (Hive->StorageTypeCount > Volatile)
622 {
623 /* It's in the volatile list */
624 Number = Number - Node->SubKeyCounts[Stable];
625 if (Number < Node->SubKeyCounts[Volatile])
626 {
627 /* Get the actual key index */
628 Index = (PCM_KEY_INDEX)HvGetCell(Hive, Node->SubKeyLists[Volatile]);
629 if (!Index) return HCELL_NIL;
630
631 /* Do a search inside it */
633
634 /* Release the cell and return the result */
635 HvReleaseCell(Hive, Node->SubKeyLists[Volatile]);
636 return Result;
637 }
638 }
639
640 /* Nothing was found */
641 return HCELL_NIL;
642}
HCELL_INDEX NTAPI CmpDoFindSubKeyByNumber(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN ULONG Number)
Definition: cmindex.c:514
@ Volatile
Definition: hivedata.h:103
@ Stable
Definition: hivedata.h:102

Referenced by BiEnumerateSubKeys(), CmEnumerateKey(), CmpDeepCopyKeyInternal(), and CmpFindDrivers().

◆ CmpFindSubKeyInLeaf()

ULONG NTAPI CmpFindSubKeyInLeaf ( IN PHHIVE  Hive,
IN PCM_KEY_INDEX  Index,
IN PCUNICODE_STRING  SearchName,
IN PHCELL_INDEX  SubKey 
)

Definition at line 358 of file cmindex.c.

362{
363 ULONG High, Low = 0, i;
364 LONG Result;
365
366 /* Verify Index for validity */
367 ASSERT((Index->Signature == CM_KEY_INDEX_LEAF) ||
368 (Index->Signature == CM_KEY_FAST_LEAF) ||
369 (Index->Signature == CM_KEY_HASH_LEAF));
370
371 /* Get the upper bound and middle entry */
372 High = Index->Count - 1;
373 i = High / 2;
374
375 /* Check if we don't actually have any entries */
376 if (!Index->Count)
377 {
378 /* Return failure */
379 *SubKey = HCELL_NIL;
380 return 0;
381 }
382
383 /* Start compare loop */
384 while (TRUE)
385 {
386 /* Do the actual comparison and check the result */
387 Result = CmpCompareInIndex(Hive, SearchName, i, Index, SubKey);
388 if (Result == 2)
389 {
390 /* Fail with special value */
391 *SubKey = HCELL_NIL;
392 return INVALID_INDEX;
393 }
394
395 /* Check if we got lucky and found it */
396 if (!Result) return i;
397
398 /* Check if the result is below us */
399 if (Result < 0)
400 {
401 /* Set the new bound; it can't be higher then where we are now. */
402 ASSERT(Result == -1);
403 High = i;
404 }
405 else
406 {
407 /* Set the new bound... it can't be lower then where we are now. */
408 ASSERT(Result == 1);
409 Low = i;
410 }
411
412 /* Check if this is the last entry, if so, break out and handle it */
413 if ((High - Low) <= 1) break;
414
415 /* Set the new index */
416 i = ((High - Low) / 2) + Low;
417 }
418
419 /*
420 * If we get here, High - Low = 1 or High == Low
421 * Simply look first at Low, then at High
422 */
423 Result = CmpCompareInIndex(Hive, SearchName, Low, Index, SubKey);
424 if (Result == 2)
425 {
426 /* Fail with special value */
427 *SubKey = HCELL_NIL;
428 return INVALID_INDEX;
429 }
430
431 /* Check if we got lucky and found it */
432 if (!Result) return Low;
433
434 /* Check if the result is below us */
435 if (Result < 0)
436 {
437 /* Return the low entry */
438 ASSERT(Result == -1);
439 return Low;
440 }
441
442 /*
443 * If we got here, then just check the high and return it no matter what
444 * the result is (since we're a leaf, it has to be near there anyway).
445 */
446 Result = CmpCompareInIndex(Hive, SearchName, High, Index, SubKey);
447 if (Result == 2)
448 {
449 /* Fail with special value */
450 *SubKey = HCELL_NIL;
451 return INVALID_INDEX;
452 }
453
454 /* Return the high */
455 return High;
456}
@ High
Definition: strmini.h:378
@ Low
Definition: strmini.h:380

Referenced by CmpAddToLeaf(), CmpFindSubKeyByName(), CmpMarkIndexDirty(), and CmpRemoveSubKey().

◆ CmpFindSubKeyInRoot()

ULONG NTAPI CmpFindSubKeyInRoot ( IN PHHIVE  Hive,
IN PCM_KEY_INDEX  Index,
IN PCUNICODE_STRING  SearchName,
IN PHCELL_INDEX  SubKey 
)

Definition at line 143 of file cmindex.c.

147{
148 ULONG High, Low = 0, i = 0, ReturnIndex;
149 HCELL_INDEX LeafCell;
150 PCM_KEY_INDEX Leaf;
151 LONG Result;
152
153 /* Verify Index for validity */
154 ASSERT(Index->Count != 0);
155 ASSERT(Index->Signature == CM_KEY_INDEX_ROOT);
156
157 /* Set high limit and loop */
158 High = Index->Count - 1;
159 while (TRUE)
160 {
161 /* Choose next entry */
162 i = ((High - Low) / 2) + Low;
163
164 /* Get the leaf cell and then the leaf itself */
165 LeafCell = Index->List[i];
166 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
167 if (Leaf)
168 {
169 /* Make sure the leaf is valid */
171 (Leaf->Signature == CM_KEY_FAST_LEAF) ||
172 (Leaf->Signature == CM_KEY_HASH_LEAF));
173 ASSERT(Leaf->Count != 0);
174
175 /* Do the compare */
177 SearchName,
178 Leaf->Count - 1,
179 Leaf,
180 SubKey);
181 if (Result == 2) goto Big;
182
183 /* Check if we found the leaf */
184 if (!Result)
185 {
186 /* We found the leaf */
187 *SubKey = LeafCell;
188 ReturnIndex = i;
189 goto Return;
190 }
191
192 /* Check for negative result */
193 if (Result < 0)
194 {
195 /* If we got here, we should be at -1 */
196 ASSERT(Result == -1);
197
198 /* Do another lookup, since we might still be in the right leaf */
200 SearchName,
201 0,
202 Leaf,
203 SubKey);
204 if (Result == 2) goto Big;
205
206 /* Check if it's not below */
207 if (Result >= 0)
208 {
209 /*
210 * If the name was first below, and now it is above,
211 * then this means that it is somewhere in this leaf.
212 * Make sure we didn't get some weird result
213 */
214 ASSERT((Result == 1) || (Result == 0));
215
216 /* Return it */
217 *SubKey = LeafCell;
218 ReturnIndex = i;
219 goto Return;
220 }
221
222 /* Update the limit to this index, since we know it's not higher. */
223 High = i;
224 }
225 else
226 {
227 /* Update the base to this index, since we know it's not lower. */
228 Low = i;
229 }
230 }
231 else
232 {
233Big:
234 /* This was some sort of special key */
235 ReturnIndex = INVALID_INDEX;
236 goto ReturnFailure;
237 }
238
239 /* Check if there is only one entry left */
240 if ((High - Low) <= 1) break;
241
242 /* Release the leaf cell */
243 HvReleaseCell(Hive, LeafCell);
244 }
245
246 /* Make sure we got here for the right reasons */
247 ASSERT((High - Low == 1) || (High == Low));
248
249 /* Get the leaf cell and the leaf */
250 LeafCell = Index->List[Low];
251 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
252 if (!Leaf) goto Big;
253
254 /* Do the compare */
256 SearchName,
257 Leaf->Count-1,
258 Leaf,
259 SubKey);
260 if (Result == 2) goto Big;
261
262 /* Check if we found it */
263 if (!Result)
264 {
265 /* We got lucky... return it */
266 *SubKey = LeafCell;
267 ReturnIndex = Low;
268 goto Return;
269 }
270
271 /* It's below, so could still be in this leaf */
272 if (Result < 0)
273 {
274 /* Make sure we're -1 */
275 ASSERT(Result == -1);
276
277 /* Do a search from the bottom */
278 Result = CmpCompareInIndex(Hive, SearchName, 0, Leaf, SubKey);
279 if (Result == 2) goto Big;
280
281 /*
282 * Check if it's above, which means that it's within the ranges of our
283 * leaf (since we were below before).
284 */
285 if (Result >= 0)
286 {
287 /* Sanity check */
288 ASSERT((Result == 1) || (Result == 0));
289
290 /* Yep, so we're in the right leaf; return it. */
291 *SubKey = LeafCell;
292 ReturnIndex = Low;
293 goto Return;
294 }
295
296 /* It's still below us, so fail */
297 ReturnIndex = Low;
298 goto ReturnFailure;
299 }
300
301 /* Release the leaf cell */
302 HvReleaseCell(Hive, LeafCell);
303
304 /* Well the low didn't work too well, so try the high. */
305 LeafCell = Index->List[High];
306 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
307 if (!Leaf) goto Big;
308
309 /* Do the compare */
311 SearchName,
312 Leaf->Count - 1,
313 Leaf,
314 SubKey);
315 if (Result == 2) goto Big;
316
317 /* Check if we found it */
318 if (Result == 0)
319 {
320 /* We got lucky... return it */
321 *SubKey = LeafCell;
322 ReturnIndex = High;
323 goto Return;
324 }
325
326 /* Check if we are too high */
327 if (Result < 0)
328 {
329 /* Make sure we're -1 */
330 ASSERT(Result == -1);
331
332 /*
333 * Once again... since we were first too low and now too high, then
334 * this means we are within the range of this leaf... return it.
335 */
336 *SubKey = LeafCell;
337 ReturnIndex = High;
338 goto Return;
339 }
340
341 /* If we got here, then we are too low, again. */
342 ReturnIndex = High;
343
344 /* Failure path */
345ReturnFailure:
346 *SubKey = HCELL_NIL;
347
348 /* Return path...check if we have a leaf to free */
349Return:
350 if (Leaf) HvReleaseCell(Hive, LeafCell);
351
352 /* Return the index */
353 return ReturnIndex;
354}

Referenced by CmpFindSubKeyByName(), CmpMarkIndexDirty(), CmpRemoveSubKey(), and CmpSelectLeaf().

◆ CmpMarkIndexDirty()

BOOLEAN NTAPI CmpMarkIndexDirty ( IN PHHIVE  Hive,
IN HCELL_INDEX  ParentKey,
IN HCELL_INDEX  TargetKey 
)

Definition at line 771 of file cmindex.c.

774{
776 UNICODE_STRING SearchName;
777 BOOLEAN IsCompressed;
778 ULONG i, Result;
780 HCELL_INDEX IndexCell, Child = HCELL_NIL, CellToRelease = HCELL_NIL;
781
782 /* Get the target key node */
783 Node = (PCM_KEY_NODE)HvGetCell(Hive, TargetKey);
784 if (!Node) return FALSE;
785
786 /* Check if it's compressed */
787 if (Node->Flags & KEY_COMP_NAME)
788 {
789 /* Remember this for later */
790 IsCompressed = TRUE;
791
792 /* Build the search name */
793 SearchName.Length = CmpCompressedNameSize(Node->Name,
794 Node->NameLength);
795 SearchName.MaximumLength = SearchName.Length;
796 SearchName.Buffer = Hive->Allocate(SearchName.Length, TRUE, TAG_CM);
797 if (!SearchName.Buffer)
798 {
799 /* Fail */
800 HvReleaseCell(Hive, TargetKey);
801 return FALSE;
802 }
803
804 /* Copy it */
805 CmpCopyCompressedName(SearchName.Buffer,
806 SearchName.MaximumLength,
807 Node->Name,
808 Node->NameLength);
809 }
810 else
811 {
812 /* Name isn't compressed, build it directly from the node */
813 IsCompressed = FALSE;
814 SearchName.Length = Node->NameLength;
815 SearchName.MaximumLength = Node->NameLength;
816 SearchName.Buffer = Node->Name;
817 }
818
819 /* We can release the target key now */
820 HvReleaseCell(Hive, TargetKey);
821
822 /* Now get the parent key node */
824 if (!Node) goto Quickie;
825
826 /* Loop all hive storage */
827 for (i = 0; i < Hive->StorageTypeCount; i++)
828 {
829 /* Check if any subkeys are in this index */
830 if (Node->SubKeyCounts[i])
831 {
832 /* Get the cell index */
833 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[i]));
834 IndexCell = Node->SubKeyLists[i];
835
836 /* Check if we had anything to release from before */
837 if (CellToRelease != HCELL_NIL)
838 {
839 /* Release it now */
840 HvReleaseCell(Hive, CellToRelease);
841 CellToRelease = HCELL_NIL;
842 }
843
844 /* Get the key index for the cell */
845 Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
846 if (!Index) goto Quickie;
847
848 /* Release it at the next iteration or below */
849 CellToRelease = IndexCell;
850
851 /* Check if this is a root */
852 if (Index->Signature == CM_KEY_INDEX_ROOT)
853 {
854 /* Get the child inside the root */
855 Result = CmpFindSubKeyInRoot(Hive, Index, &SearchName, &Child);
856 if (Result & INVALID_INDEX) goto Quickie;
857 if (Child == HCELL_NIL) continue;
858
859 /* We found it, mark the cell dirty */
860 HvMarkCellDirty(Hive, IndexCell, FALSE);
861
862 /* Check if we had anything to release from before */
863 if (CellToRelease != HCELL_NIL)
864 {
865 /* Release it now */
866 HvReleaseCell(Hive, CellToRelease);
867 CellToRelease = HCELL_NIL;
868 }
869
870 /* Now this child is the index, get the actual key index */
871 IndexCell = Child;
873 if (!Index) goto Quickie;
874
875 /* Release it later */
876 CellToRelease = Child;
877 }
878
879 /* Make sure this is a valid index */
880 ASSERT((Index->Signature == CM_KEY_INDEX_LEAF) ||
881 (Index->Signature == CM_KEY_FAST_LEAF) ||
882 (Index->Signature == CM_KEY_HASH_LEAF));
883
884 /* Find the child in the leaf */
885 Result = CmpFindSubKeyInLeaf(Hive, Index, &SearchName, &Child);
886 if (Result & INVALID_INDEX) goto Quickie;
887 if (Child != HCELL_NIL)
888 {
889 /* We found it, free the name now */
890 if (IsCompressed) Hive->Free(SearchName.Buffer, 0);
891
892 /* Release the parent key */
894
895 /* Check if we had a left over cell to release */
896 if (CellToRelease != HCELL_NIL)
897 {
898 /* Release it */
899 HvReleaseCell(Hive, CellToRelease);
900 }
901
902 /* And mark the index cell dirty */
903 HvMarkCellDirty(Hive, IndexCell, FALSE);
904 return TRUE;
905 }
906 }
907 }
908
909Quickie:
910 /* Release any cells that we still hold */
911 if (Node) HvReleaseCell(Hive, ParentKey);
912 if (CellToRelease != HCELL_NIL) HvReleaseCell(Hive, CellToRelease);
913
914 /* Free the search name and return failure */
915 if (IsCompressed) Hive->Free(SearchName.Buffer, 0);
916 return FALSE;
917}
USHORT MaximumLength
Definition: env_spec_w32.h:370
_Must_inspect_result_ _In_opt_ WDFKEY ParentKey
Definition: wdfregistry.h:69

Referenced by CmpMarkKeyDirty().

◆ CmpRemoveSubKey()

BOOLEAN NTAPI CmpRemoveSubKey ( IN PHHIVE  Hive,
IN HCELL_INDEX  ParentKey,
IN HCELL_INDEX  TargetKey 
)

Definition at line 1694 of file cmindex.c.

1697{
1699 UNICODE_STRING SearchName;
1700 BOOLEAN IsCompressed;
1701 WCHAR Buffer[50];
1702 HCELL_INDEX RootCell = HCELL_NIL, LeafCell, ChildCell;
1703 PCM_KEY_INDEX Root = NULL, Leaf;
1705 ULONG Storage, RootIndex = INVALID_INDEX, LeafIndex;
1707 HCELL_INDEX CellToRelease1 = HCELL_NIL, CellToRelease2 = HCELL_NIL;
1708
1709 /* Get the target key node */
1710 Node = (PCM_KEY_NODE)HvGetCell(Hive, TargetKey);
1711 if (!Node) return FALSE;
1712
1713 /* Make sure it's dirty, then release it */
1714 ASSERT(HvIsCellDirty(Hive, TargetKey));
1715 HvReleaseCell(Hive, TargetKey);
1716
1717 /* Check if the name is compressed */
1718 if (Node->Flags & KEY_COMP_NAME)
1719 {
1720 /* Remember for later */
1721 IsCompressed = TRUE;
1722
1723 /* Build the search name */
1724 SearchName.Length = CmpCompressedNameSize(Node->Name,
1725 Node->NameLength);
1726 SearchName.MaximumLength = SearchName.Length;
1727
1728 /* Do we need an extra bufer? */
1729 if (SearchName.MaximumLength > sizeof(Buffer))
1730 {
1731 /* Allocate one */
1732 SearchName.Buffer = Hive->Allocate(SearchName.Length, TRUE, TAG_CM);
1733 if (!SearchName.Buffer) return FALSE;
1734 }
1735 else
1736 {
1737 /* Otherwise, use our local stack buffer */
1738 SearchName.Buffer = Buffer;
1739 }
1740
1741 /* Copy the compressed name */
1742 CmpCopyCompressedName(SearchName.Buffer,
1743 SearchName.MaximumLength,
1744 Node->Name,
1745 Node->NameLength);
1746 }
1747 else
1748 {
1749 /* It's not compressed, build the name directly from the node */
1750 IsCompressed = FALSE;
1751 SearchName.Length = Node->NameLength;
1752 SearchName.MaximumLength = Node->NameLength;
1753 SearchName.Buffer = Node->Name;
1754 }
1755
1756 /* Now get the parent node */
1758 if (!Node) goto Exit;
1759
1760 /* Make sure it's dirty, then release it */
1762 HvReleaseCell(Hive, ParentKey);
1763
1764 /* Get the storage type and make sure it's not empty */
1765 Storage = HvGetCellType(TargetKey);
1766 ASSERT(Node->SubKeyCounts[Storage] != 0);
1767 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[Storage]));
1768
1769 /* Get the leaf cell now */
1770 LeafCell = Node->SubKeyLists[Storage];
1771 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1772 if (!Leaf) goto Exit;
1773
1774 /* Remember to release it later */
1775 CellToRelease1 = LeafCell;
1776
1777 /* Check if the leaf is a root */
1778 if (Leaf->Signature == CM_KEY_INDEX_ROOT)
1779 {
1780 /* Find the child inside the root */
1781 RootIndex = CmpFindSubKeyInRoot(Hive, Leaf, &SearchName, &ChildCell);
1782 if (RootIndex & INVALID_INDEX) goto Exit;
1783 ASSERT(ChildCell != FALSE);
1784
1785 /* The root cell is now this leaf */
1786 Root = Leaf;
1787 RootCell = LeafCell;
1788
1789 /* And the new leaf is now this child */
1790 LeafCell = ChildCell;
1791 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1792 if (!Leaf) goto Exit;
1793
1794 /* Remember to release it later */
1795 CellToRelease2 = LeafCell;
1796 }
1797
1798 /* Make sure the leaf is valid */
1799 ASSERT((Leaf->Signature == CM_KEY_INDEX_LEAF) ||
1800 (Leaf->Signature == CM_KEY_FAST_LEAF) ||
1801 (Leaf->Signature == CM_KEY_HASH_LEAF));
1802
1803 /* Now get the child in the leaf */
1804 LeafIndex = CmpFindSubKeyInLeaf(Hive, Leaf, &SearchName, &ChildCell);
1805 if (LeafIndex & INVALID_INDEX) goto Exit;
1806 ASSERT(ChildCell != HCELL_NIL);
1807
1808 /* Decrement key counts and check if this was the last leaf entry */
1809 Node->SubKeyCounts[Storage]--;
1810 if (!(--Leaf->Count))
1811 {
1812 /* Free the leaf */
1813 HvFreeCell(Hive, LeafCell);
1814
1815 /* Check if we were inside a root */
1816 if (Root)
1817 {
1818 /* Decrease the root count too, since the leaf is going away */
1819 if (!(--Root->Count))
1820 {
1821 /* The root is gone too,n ow */
1822 HvFreeCell(Hive, RootCell);
1823 Node->SubKeyLists[Storage] = HCELL_NIL;
1824 }
1825 else if (RootIndex < Root->Count)
1826 {
1827 /* Bring everything up by one */
1828 RtlMoveMemory(&Root->List[RootIndex],
1829 &Root->List[RootIndex + 1],
1830 (Root->Count - RootIndex) * sizeof(HCELL_INDEX));
1831 }
1832 }
1833 else
1834 {
1835 /* Otherwise, just clear the cell */
1836 Node->SubKeyLists[Storage] = HCELL_NIL;
1837 }
1838 }
1839 else if (LeafIndex < Leaf->Count)
1840 {
1841 /* Was the leaf a normal index? */
1842 if (Leaf->Signature == CM_KEY_INDEX_LEAF)
1843 {
1844 /* Bring everything up by one */
1845 RtlMoveMemory(&Leaf->List[LeafIndex],
1846 &Leaf->List[LeafIndex + 1],
1847 (Leaf->Count - LeafIndex) * sizeof(HCELL_INDEX));
1848 }
1849 else
1850 {
1851 /* This is a fast index, bring everything up by one */
1852 Child = (PCM_KEY_FAST_INDEX)Leaf;
1853 RtlMoveMemory(&Child->List[LeafIndex],
1854 &Child->List[LeafIndex+1],
1855 (Child->Count - LeafIndex) * sizeof(CM_INDEX));
1856 }
1857 }
1858
1859 /* If we got here, now we're done */
1860 Result = TRUE;
1861
1862Exit:
1863 /* Release any cells we may have been holding */
1864 if (CellToRelease1 != HCELL_NIL) HvReleaseCell(Hive, CellToRelease1);
1865 if (CellToRelease2 != HCELL_NIL) HvReleaseCell(Hive, CellToRelease2);
1866
1867 /* Check if the name was compressed and not inside our local buffer */
1868 if ((IsCompressed) && (SearchName.MaximumLength > sizeof(Buffer)))
1869 {
1870 /* Free the buffer we allocated */
1871 Hive->Free(SearchName.Buffer, 0);
1872 }
1873
1874 /* Return the result */
1875 return Result;
1876}
Definition: bufpool.h:45
BOOLEAN CMAPI HvIsCellDirty(IN PHHIVE Hive, IN HCELL_INDEX Cell)
Definition: hivecell.c:153
VOID CMAPI HvFreeCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset)
Definition: hivecell.c:468
static IStorage Storage
Definition: ole2.c:3548
static void Exit(void)
Definition: sock.c:1330
root entry for file system trees
Definition: entries.h:148

Referenced by CmpFreeKeyByCell().

◆ CmpSelectLeaf()

HCELL_INDEX NTAPI CmpSelectLeaf ( IN PHHIVE  Hive,
IN PCM_KEY_NODE  KeyNode,
IN PCUNICODE_STRING  Name,
IN HSTORAGE_TYPE  Type,
IN PHCELL_INDEX RootCell 
)

Definition at line 1264 of file cmindex.c.

1269{
1270 PCM_KEY_INDEX IndexKey, LeafKey;
1271 PCM_KEY_FAST_INDEX FastLeaf;
1272 HCELL_INDEX LeafCell, CurrentCell;
1273 ULONG SubKeyIndex;
1274 LONG Result;
1275
1276 /* Mark it as dirty */
1277 HvMarkCellDirty(Hive, KeyNode->SubKeyLists[Type], FALSE);
1278
1279 /* Get the cell */
1280 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
1281
1282 /* Check if we've got a valid key */
1283 if (!IndexKey)
1284 {
1285 /* Should not happen! */
1286 ASSERT(IndexKey != NULL);
1287 return HCELL_NIL;
1288 }
1289
1290 /* Sanity check */
1291 ASSERT(IndexKey->Signature == CM_KEY_INDEX_ROOT);
1292
1293 while (TRUE)
1294 {
1295 /* Find subkey */
1296 SubKeyIndex = CmpFindSubKeyInRoot(Hive, IndexKey, Name, &LeafCell);
1297
1298 /* Make sure we found something valid */
1299 if (SubKeyIndex & INVALID_INDEX) return HCELL_NIL;
1300
1301 /* Try to fit it into the LeafCell, if it was found */
1302 if (LeafCell != HCELL_NIL)
1303 {
1304 /* Get the leaf key */
1305 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1306
1307 /* Check for failure */
1308 if (!LeafKey) return HCELL_NIL;
1309
1310 /* Check if it fits into this leaf and break */
1311 if (LeafKey->Count < CmpMaxIndexPerHblock)
1312 {
1313 /* Fill in the result and return it */
1314 *RootCell = &IndexKey->List[SubKeyIndex];
1315 return LeafCell;
1316 }
1317
1318 /* It didn't fit, so proceed to splitting */
1319 }
1320 else
1321 {
1322 /* Get the leaf cell at the very end */
1323 LeafCell = IndexKey->List[SubKeyIndex];
1324 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1325
1326 /* Return an error in case of problems */
1327 if (!LeafKey) return HCELL_NIL;
1328
1329 /* Choose the cell to search from depending on the key type */
1330 if ((LeafKey->Signature == CM_KEY_FAST_LEAF) ||
1331 (LeafKey->Signature == CM_KEY_HASH_LEAF))
1332 {
1333 FastLeaf = (PCM_KEY_FAST_INDEX)LeafKey;
1334 CurrentCell = FastLeaf->List[0].Cell;
1335 }
1336 else
1337 {
1338 /* Make sure it's an index leaf */
1339 ASSERT(LeafKey->Signature == CM_KEY_INDEX_LEAF);
1340 CurrentCell = LeafKey->List[0];
1341 }
1342
1343 /* Do a name compare */
1344 Result = CmpDoCompareKeyName(Hive, Name, CurrentCell);
1345
1346 /* Check for failure */
1347 if (Result == 2) return HCELL_NIL;
1348
1349 /* Names can't be equal, ensure that */
1350 ASSERT(Result != 0);
1351
1352 /* Check if it's above */
1353 if (Result >= 0)
1354 {
1355 /* Get the cell in the index */
1356 LeafCell = IndexKey->List[SubKeyIndex];
1357 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1358
1359 /* Return an error in case of problems */
1360 if (!LeafKey) return HCELL_NIL;
1361
1362 /* Check if it fits into this leaf */
1363 if (LeafKey->Count < CmpMaxIndexPerHblock)
1364 {
1365 /* Fill in the result and return the cell */
1366 *RootCell = &IndexKey->List[SubKeyIndex];
1367 return LeafCell;
1368 }
1369
1370 /* No, it doesn't fit, check the next adjacent leaf */
1371 if ((SubKeyIndex + 1) < IndexKey->Count)
1372 {
1373 /* Yes, there is space */
1374 LeafCell = IndexKey->List[SubKeyIndex + 1];
1375 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1376
1377 /* Return an error in case of problems */
1378 if (!LeafKey) return HCELL_NIL;
1379
1380 /* Check if it fits and break */
1381 if (LeafKey->Count < CmpMaxIndexPerHblock)
1382 {
1383 /* Fill in the result and return the cell */
1384 *RootCell = &IndexKey->List[SubKeyIndex + 1];
1385 return LeafCell;
1386 }
1387 }
1388
1389 /* It didn't fit, so proceed to splitting */
1390 }
1391 else
1392 {
1393 /* No, it's below, check the subkey index */
1394 if (SubKeyIndex > 0)
1395 {
1396 /* There should be space at the leaf one before that */
1397 LeafCell = IndexKey->List[SubKeyIndex - 1];
1398 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1399
1400 /* Return an error in case of problems */
1401 if (!LeafKey) return HCELL_NIL;
1402
1403 /* Check if it fits and break */
1404 if (LeafKey->Count < CmpMaxIndexPerHblock)
1405 {
1406 /* Fill in the result and return the cell */
1407 *RootCell = &IndexKey->List[SubKeyIndex - 1];
1408 return LeafCell;
1409 }
1410 }
1411 else
1412 {
1413 /* Use the first leaf, if possible */
1414 LeafCell = IndexKey->List[0];
1415 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1416
1417 /* Return an error in case of problems */
1418 if (!LeafKey) return HCELL_NIL;
1419
1420 /* Check if it fits and break */
1421 if (LeafKey->Count < CmpMaxIndexPerHblock)
1422 {
1423 /* Fill in the result and return the cell */
1424 *RootCell = &IndexKey->List[0];
1425 return LeafCell;
1426 }
1427 }
1428
1429 /* It didn't fit into either, so proceed to splitting */
1430 }
1431 }
1432
1433 /* We need to split */
1434 CurrentCell = CmpSplitLeaf(Hive,
1435 KeyNode->SubKeyLists[Type],
1436 SubKeyIndex,
1437 Type);
1438
1439 /* Return failure in case splitting failed */
1440 if (CurrentCell == HCELL_NIL) return CurrentCell;
1441
1442 /* Set the SubKeyLists value with the new key */
1443 KeyNode->SubKeyLists[Type] = CurrentCell;
1444
1445 /* Get the new cell */
1446 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
1447
1448 /* Return in case of failure */
1449 if (!IndexKey) return HCELL_NIL;
1450
1451 /* Make sure the new key became index root */
1452 ASSERT(IndexKey->Signature == CM_KEY_INDEX_ROOT);
1453
1454 /* Now loop over with the new IndexKey value, which definately
1455 * has the space now
1456 */
1457 }
1458
1459 /* Shouldn't come here */
1460 return HCELL_NIL;
1461}
HCELL_INDEX NTAPI CmpSplitLeaf(IN PHHIVE Hive, IN HCELL_INDEX RootCell, IN ULONG RootSelect, IN HSTORAGE_TYPE Type)
Definition: cmindex.c:1104

Referenced by CmpAddSubKey().

◆ CmpSplitLeaf()

HCELL_INDEX NTAPI CmpSplitLeaf ( IN PHHIVE  Hive,
IN HCELL_INDEX  RootCell,
IN ULONG  RootSelect,
IN HSTORAGE_TYPE  Type 
)

Definition at line 1104 of file cmindex.c.

1108{
1109 PCM_KEY_INDEX IndexKey, LeafKey, NewKey;
1110 PCM_KEY_FAST_INDEX FastLeaf;
1111 HCELL_INDEX LeafCell, NewCell;
1112 USHORT FirstHalf, LastHalf;
1113 ULONG EntrySize, TotalSize;
1114
1115 /* Get the cell */
1116 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, RootCell);
1117
1118 /* Check if we've got valid IndexKey */
1119 if (!IndexKey) return HCELL_NIL;
1120
1121 /* Get the leaf cell and key */
1122 LeafCell = IndexKey->List[RootSelect];
1123 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1124
1125 /* Check if we've got valid LeafKey */
1126 if (!LeafKey) return HCELL_NIL;
1127
1128 /* We are going to divide this leaf into two halves */
1129 FirstHalf = (LeafKey->Count / 2);
1130 LastHalf = LeafKey->Count - FirstHalf;
1131
1132 /* Now check what kind of hive we're dealing with,
1133 * and compute entry size
1134 */
1135 if (Hive->Version >= 5)
1136 {
1137 /* XP Hive: Use hash leaf */
1138 ASSERT(LeafKey->Signature == CM_KEY_HASH_LEAF);
1139 EntrySize = sizeof(CM_INDEX);
1140 }
1141 else
1142 {
1143 /* Use index leaf */
1144 ASSERT(LeafKey->Signature == CM_KEY_INDEX_LEAF);
1145 EntrySize = sizeof(HCELL_INDEX);
1146 }
1147
1148 /* Compute the total size */
1149 TotalSize = (EntrySize * LastHalf) + FIELD_OFFSET(CM_KEY_INDEX, List) + 1;
1150
1151 /* Mark the leaf cell dirty */
1152 HvMarkCellDirty(Hive, LeafCell, FALSE);
1153
1154 /* Make sure its type is the same */
1155 ASSERT(HvGetCellType(LeafCell) == Type);
1156
1157 /* Allocate the cell, fail in case of error */
1158 NewCell = HvAllocateCell(Hive, TotalSize, Type, LeafCell);
1159 if (NewCell == HCELL_NIL) return NewCell;
1160
1161 /* Get the key */
1162 NewKey = (PCM_KEY_INDEX)HvGetCell(Hive, NewCell);
1163 if (!NewKey)
1164 {
1165 /* Free the cell and exit - should not happen! */
1166 ASSERT(FALSE);
1167 HvFreeCell(Hive, NewCell);
1168 return HCELL_NIL;
1169 }
1170
1171 /* Release the newly created cell */
1172 HvReleaseCell(Hive, NewCell);
1173
1174 /* Set its signature according to the version of the hive */
1175 if (Hive->Version >= 5)
1176 {
1177 /* XP Hive: Use hash leaf signature */
1178 NewKey->Signature = CM_KEY_HASH_LEAF;
1179 }
1180 else
1181 {
1182 /* Use index leaf signature */
1183 NewKey->Signature = CM_KEY_INDEX_LEAF;
1184 }
1185
1186 /* Calculate the size of the free entries in the root key */
1187 TotalSize = HvGetCellSize(Hive, IndexKey) -
1188 (IndexKey->Count * sizeof(HCELL_INDEX)) -
1190
1191 /* Check if we're out of space */
1192 if (TotalSize / sizeof(HCELL_INDEX) < 1)
1193 {
1194 /* Grow the leaf by one more entry */
1195 TotalSize = HvGetCellSize(Hive, IndexKey) + sizeof(HCELL_INDEX);
1196
1197 /* Re-allocate the root */
1198 RootCell = HvReallocateCell(Hive, RootCell, TotalSize);
1199 if (RootCell == HCELL_NIL)
1200 {
1201 /* Free the cell and exit */
1202 HvFreeCell(Hive, NewCell);
1203 return HCELL_NIL;
1204 }
1205
1206 /* Get the leaf cell */
1207 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, RootCell);
1208 if (!IndexKey)
1209 {
1210 /* This shouldn't happen */
1211 ASSERT(FALSE);
1212 return HCELL_NIL;
1213 }
1214 }
1215
1216 /* Splitting is done, now we need to copy the contents,
1217 * according to the hive version
1218 */
1219 if (Hive->Version >= 5)
1220 {
1221 /* Copy the fast indexes */
1222 FastLeaf = (PCM_KEY_FAST_INDEX)LeafKey;
1223 RtlMoveMemory(&NewKey->List[0],
1224 &FastLeaf->List[FirstHalf],
1225 LastHalf * EntrySize);
1226 }
1227 else
1228 {
1229 /* Copy the indexes themselves */
1230 RtlMoveMemory(&NewKey->List[0],
1231 &LeafKey->List[FirstHalf],
1232 LastHalf * EntrySize);
1233 }
1234
1235 /* Shift the data inside the root key */
1236 if ((RootSelect + 1) < IndexKey->Count)
1237 {
1238 RtlMoveMemory(&IndexKey->List[RootSelect + 2],
1239 &IndexKey->List[RootSelect + 1],
1240 (IndexKey->Count -
1241 (RootSelect + 1)) * sizeof(HCELL_INDEX));
1242 }
1243
1244 /* Make sure both old and new computed counts are valid */
1245 ASSERT(FirstHalf != 0);
1246 ASSERT(LastHalf != 0);
1247
1248 /* Update the count value of old and new keys */
1249 LeafKey->Count = FirstHalf;
1250 NewKey->Count = LastHalf;
1251
1252 /* Increase the count value of the root key */
1253 IndexKey->Count++;
1254
1255 /* Set the new cell in root's list */
1256 IndexKey->List[RootSelect + 1] = NewCell;
1257
1258 /* Return the root cell */
1259 return RootCell;
1260}

Referenced by CmpSelectLeaf().