ReactOS  0.4.13-dev-650-g34bf247
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 PUNICODE_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 PUNICODE_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))
#define HBLOCK_SIZE
Definition: hivedata.h:41
struct _CM_INDEX CM_INDEX
struct _HBIN HBIN
LIST_ENTRY List
Definition: psmgr.c:57

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)
#define HBLOCK_SIZE
Definition: hivedata.h:41
struct _HBIN HBIN
LIST_ENTRY List
Definition: psmgr.c:57
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 1467 of file cmindex.c.

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

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

◆ CmpAddToLeaf()

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

Definition at line 923 of file cmindex.c.

927 {
928  PCM_KEY_INDEX Leaf;
929  PCM_KEY_FAST_INDEX FastLeaf;
930  ULONG Size, OldSize, EntrySize, i, j;
931  HCELL_INDEX NewCell, Child;
932  LONG Result;
933 
934  /* Mark the leaf dirty */
935  HvMarkCellDirty(Hive, LeafCell, FALSE);
936 
937  /* Get the leaf cell */
938  Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
939  if (!Leaf)
940  {
941  /* Shouldn't happen */
942  ASSERT(FALSE);
943  return HCELL_NIL;
944  }
945 
946  /* Release it */
947  HvReleaseCell(Hive, LeafCell);
948 
949  /* Check if this is an index leaf */
950  if (Leaf->Signature == CM_KEY_INDEX_LEAF)
951  {
952  /* This is an old-style leaf */
953  FastLeaf = NULL;
954  EntrySize = sizeof(HCELL_INDEX);
955  }
956  else
957  {
958  /* Sanity check */
959  ASSERT((Leaf->Signature == CM_KEY_FAST_LEAF) ||
960  (Leaf->Signature == CM_KEY_HASH_LEAF));
961 
962  /* This is a new-style optimized fast (or hash) leaf */
963  FastLeaf = (PCM_KEY_FAST_INDEX)Leaf;
964  EntrySize = sizeof(CM_INDEX);
965  }
966 
967  /* Get the current size of the leaf */
968  OldSize = HvGetCellSize(Hive, Leaf);
969 
970  /* Calculate the size of the free entries */
971  Size = OldSize;
973 
974  /* Assume we'll re-use the same leaf */
975  NewCell = LeafCell;
976 
977  /* Check if we're out of space */
978  if ((Size / EntrySize) < 1)
979  {
980  /* Grow the leaf by 1.5x, making sure we can at least fit this entry */
981  Size = OldSize + OldSize / 2;
982  if (Size < (OldSize + EntrySize)) Size = OldSize + EntrySize;
983 
984  /* Re-allocate the leaf */
985  NewCell = HvReallocateCell(Hive, LeafCell, Size);
986  if (NewCell == HCELL_NIL) return HCELL_NIL;
987 
988  /* Get the leaf cell */
989  Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, NewCell);
990  if (!Leaf)
991  {
992  /* This shouldn't happen */
993  ASSERT(FALSE);
994  return HCELL_NIL;
995  }
996 
997  /* Release the cell */
998  HvReleaseCell(Hive, NewCell);
999 
1000  /* Update the fast leaf pointer if we had one */
1001  if (FastLeaf) FastLeaf = (PCM_KEY_FAST_INDEX)Leaf;
1002  }
1003 
1004  /* Find the insertion point for our entry */
1005  i = CmpFindSubKeyInLeaf(Hive, Leaf, Name, &Child);
1006  if (i & INVALID_INDEX) return HCELL_NIL;
1007  ASSERT(Child == HCELL_NIL);
1008 
1009  /* Check if we're not last */
1010  if (i != Leaf->Count)
1011  {
1012  /* Find out where we should go */
1013  Result = CmpCompareInIndex(Hive,
1014  Name,
1015  i,
1016  Leaf,
1017  &Child);
1018  if (Result == 2) return HCELL_NIL;
1019  ASSERT(Result != 0);
1020 
1021  /* Check if we come after */
1022  if (Result > 0)
1023  {
1024  /* We do, insert us after the key */
1025  ASSERT(Result == 1);
1026  i++;
1027  }
1028 
1029  /* Check if we're still not last */
1030  if (i != Leaf->Count)
1031  {
1032  /* Check if we had a fast leaf or not */
1033  if (FastLeaf)
1034  {
1035  /* Copy the fast indexes */
1036  RtlMoveMemory(&FastLeaf->List[i + 1],
1037  &FastLeaf->List[i],
1038  (FastLeaf->Count - i) * sizeof(CM_INDEX));
1039  }
1040  else
1041  {
1042  /* Copy the indexes themselves */
1043  RtlMoveMemory(&Leaf->List[i + 1],
1044  &Leaf->List[i],
1045  (Leaf->Count - i) * sizeof(HCELL_INDEX));
1046  }
1047  }
1048  }
1049 
1050  /* Check if this is a new-style leaf */
1051  if (FastLeaf)
1052  {
1053  /* Set our cell */
1054  FastLeaf->List[i].Cell = NewKey;
1055 
1056  /* Check if this is a hash leaf */
1057  if( FastLeaf->Signature == CM_KEY_HASH_LEAF )
1058  {
1059  /* Set our hash key */
1060  FastLeaf->List[i].HashKey = CmpComputeHashKey(0, Name, FALSE);
1061  }
1062  else
1063  {
1064  /* First, clear the name */
1065  FastLeaf->List[i].NameHint[0] = 0;
1066  FastLeaf->List[i].NameHint[1] = 0;
1067  FastLeaf->List[i].NameHint[2] = 0;
1068  FastLeaf->List[i].NameHint[3] = 0;
1069 
1070  /* Now, figure out if we can fit */
1071  if (Name->Length / sizeof(WCHAR) < 4)
1072  {
1073  /* We can fit, use our length */
1074  j = Name->Length / sizeof(WCHAR);
1075  }
1076  else
1077  {
1078  /* We can't, use a maximum of 4 */
1079  j = 4;
1080  }
1081 
1082  /* Now fill out the name hint */
1083  do
1084  {
1085  /* Look for invalid characters and break out if we found one */
1086  if ((USHORT)Name->Buffer[j - 1] > (UCHAR)-1) break;
1087 
1088  /* Otherwise, copy the a character */
1089  FastLeaf->List[i].NameHint[j - 1] = (UCHAR)Name->Buffer[j - 1];
1090  } while (--j > 0);
1091  }
1092  }
1093  else
1094  {
1095  /* This is an old-style leaf, just set our index directly */
1096  Leaf->List[i] = NewKey;
1097  }
1098 
1099  /* Update the leaf count and return the new cell */
1100  Leaf->Count += 1;
1101  return NewCell;
1102 }
ULONG HashKey
Definition: cmdata.h:169
ULONG NTAPI CmpFindSubKeyInLeaf(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
Definition: cmindex.c:358
struct _CM_KEY_INDEX * PCM_KEY_INDEX
struct _CM_INDEX CM_INDEX
HCELL_INDEX Cell
Definition: cmdata.h:165
HCELL_INDEX CMAPI HvReallocateCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset, ULONG Size)
Definition: hivecell.c:394
#define HvReleaseCell(h, c)
Definition: cmlib.h:390
#define HCELL_NIL
Definition: hivedata.h:85
_In_ UCHAR EntrySize
Definition: iofuncs.h:640
#define RtlMoveMemory(Destination, Source, Length)
Definition: typedefs.h:263
#define INVALID_INDEX
Definition: cmindex.c:17
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
long LONG
Definition: pedump.c:60
USHORT Signature
Definition: cmdata.h:178
ULONG NTAPI CmpComputeHashKey(IN ULONG Hash, IN PCUNICODE_STRING Name, IN BOOLEAN AllowSeparators)
Definition: cmindex.c:460
PVOID CMAPI HvGetCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset)
Definition: hivecell.c:67
#define CM_KEY_HASH_LEAF
Definition: cmdata.h:16
smooth NULL
Definition: ftsmooth.c:416
UCHAR NameHint[4]
Definition: cmdata.h:168
_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
CM_INDEX List[ANYSIZE_ARRAY]
Definition: cmdata.h:190
struct _CM_KEY_FAST_INDEX * PCM_KEY_FAST_INDEX
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
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
USHORT Count
Definition: cmdata.h:179
LIST_ENTRY List
Definition: psmgr.c:57
__wchar_t WCHAR
Definition: xmlstorage.h:180
USHORT Signature
Definition: cmdata.h:188
ULONG HCELL_INDEX
Definition: hivedata.h:80
BOOLEAN CMAPI HvMarkCellDirty(PHHIVE RegistryHive, HCELL_INDEX CellOffset, BOOLEAN HoldingLock)
Definition: hivecell.c:100
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
unsigned char UCHAR
Definition: xmlstorage.h:181
LONG CMAPI HvGetCellSize(PHHIVE RegistryHive, PVOID Cell)
IN PVOID IN PVOID IN USHORT IN USHORT Size
Definition: pci.h:359
HCELL_INDEX List[ANYSIZE_ARRAY]
Definition: cmdata.h:180
unsigned short USHORT
Definition: pedump.c:61
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
#define CM_KEY_FAST_LEAF
Definition: cmdata.h:15
unsigned int ULONG
Definition: retypes.h:1
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn BOOLEAN Physical 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 ACPI_HANDLE Child
Definition: acpixf.h:716
#define CM_KEY_INDEX_LEAF
Definition: cmdata.h:14

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;
75  LONG Result;
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 }
HCELL_INDEX Cell
Definition: cmdata.h:165
#define HCELL_NIL
Definition: hivedata.h:85
_Inout_ __drv_aliasesMem PSLIST_ENTRY _Inout_ PSLIST_ENTRY _In_ ULONG Count
Definition: exfuncs.h:1015
NTSYSAPI WCHAR NTAPI RtlUpcaseUnicodeChar(WCHAR Source)
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
long LONG
Definition: pedump.c:60
#define pp
Definition: hlsl.yy.c:978
#define CM_KEY_HASH_LEAF
Definition: cmdata.h:16
UCHAR NameHint[4]
Definition: cmdata.h:168
_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
CM_INDEX List[ANYSIZE_ARRAY]
Definition: cmdata.h:190
LONG NTAPI CmpDoCompareKeyName(IN PHHIVE Hive, IN PCUNICODE_STRING SearchName, IN HCELL_INDEX Cell)
Definition: cmindex.c:31
struct _CM_KEY_FAST_INDEX * PCM_KEY_FAST_INDEX
__wchar_t WCHAR
Definition: xmlstorage.h:180
static const UCHAR Index[8]
Definition: usbohci.c:18
#define min(a, b)
Definition: monoChain.cc:55
#define CM_KEY_FAST_LEAF
Definition: cmdata.h:15
unsigned int ULONG
Definition: retypes.h:1
GLfloat GLfloat p
Definition: glext.h:8902

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 }
_In_opt_ ULONG _Out_ PULONG Value
Definition: rtlfuncs.h:2343
static int Hash(const char *)
Definition: reader.c:2257
NTSYSAPI WCHAR NTAPI RtlUpcaseUnicodeChar(WCHAR Source)
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
#define OBJ_NAME_PATH_SEPARATOR
Definition: arcname_tests.c:25
__wchar_t WCHAR
Definition: xmlstorage.h:180
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
static const WCHAR L[]
Definition: oid.c:1250
unsigned int ULONG
Definition: retypes.h:1
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 {
37  LONG Result;
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 */
47  Result = CmpCompareCompressedName(SearchName,
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;
57  Result = RtlCompareUnicodeString(SearchName, &KeyName, TRUE);
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 }
#define KEY_COMP_NAME
Definition: cmdata.h:35
_Must_inspect_result_ _Out_ PNDIS_STATUS _In_ NDIS_HANDLE _In_ ULONG _Out_ PNDIS_STRING KeyName
Definition: ndis.h:4711
#define TRUE
Definition: types.h:120
#define HvReleaseCell(h, c)
Definition: cmlib.h:390
long LONG
Definition: pedump.c:60
union node Node
Definition: types.h:1255
PVOID CMAPI HvGetCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset)
Definition: hivecell.c:67
struct _CM_KEY_NODE * PCM_KEY_NODE
_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
Definition: bzip2.c:1694
ULONG RtlCompareUnicodeString(PUNICODE_STRING s1, PUNICODE_STRING s2, BOOLEAN UpCase)
Definition: string_lib.cpp:31
LONG NTAPI CmpCompareCompressedName(IN PCUNICODE_STRING SearchName, IN PWCHAR CompressedName, IN ULONG NameLength)
Definition: cmname.c:109
Definition: dlist.c:348

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 }
struct _CM_KEY_INDEX * PCM_KEY_INDEX
HCELL_INDEX Cell
Definition: cmdata.h:165
#define HvReleaseCell(h, c)
Definition: cmlib.h:390
#define HCELL_NIL
Definition: hivedata.h:85
_Inout_ __drv_aliasesMem PSLIST_ENTRY _Inout_ PSLIST_ENTRY _In_ ULONG Count
Definition: exfuncs.h:1015
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
USHORT Signature
Definition: cmdata.h:178
PVOID CMAPI HvGetCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset)
Definition: hivecell.c:67
#define CM_KEY_HASH_LEAF
Definition: cmdata.h:16
smooth NULL
Definition: ftsmooth.c:416
_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
CM_INDEX List[ANYSIZE_ARRAY]
Definition: cmdata.h:190
#define CM_KEY_INDEX_ROOT
Definition: cmdata.h:13
struct _CM_KEY_FAST_INDEX * PCM_KEY_FAST_INDEX
USHORT Count
Definition: cmdata.h:179
ULONG HCELL_INDEX
Definition: hivedata.h:80
static const UCHAR Index[8]
Definition: usbohci.c:18
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
_In_opt_ PENTER_STATE_SYSTEM_HANDLER _In_opt_ PVOID _In_ LONG _In_opt_ LONG volatile * Number
Definition: ntpoapi.h:204
HCELL_INDEX List[ANYSIZE_ARRAY]
Definition: cmdata.h:180
#define CM_KEY_FAST_LEAF
Definition: cmdata.h:15
unsigned int ULONG
Definition: retypes.h:1

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 }
ULONG HashKey
Definition: cmdata.h:169
HCELL_INDEX Cell
Definition: cmdata.h:165
#define HCELL_NIL
Definition: hivedata.h:85
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 NTAPI CmpComputeHashKey(IN ULONG Hash, IN PCUNICODE_STRING Name, IN BOOLEAN AllowSeparators)
Definition: cmindex.c:460
#define CM_KEY_HASH_LEAF
Definition: cmdata.h:16
LONG NTAPI CmpDoCompareKeyName(IN PHHIVE Hive, IN PCUNICODE_STRING SearchName, IN HCELL_INDEX Cell)
Definition: cmindex.c:31
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
unsigned int ULONG
Definition: retypes.h:1

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 */
709  Found = CmpFindSubKeyInRoot(Hive,
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 */
736  Found = CmpFindSubKeyInLeaf(Hive,
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 }
ULONG NTAPI CmpFindSubKeyInLeaf(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
Definition: cmindex.c:358
struct _CM_KEY_INDEX * PCM_KEY_INDEX
#define HvReleaseCell(h, c)
Definition: cmlib.h:390
#define HCELL_NIL
Definition: hivedata.h:85
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn BOOLEAN Physical 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:716
ULONG NTAPI CmpFindSubKeyInRoot(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
Definition: cmindex.c:143
#define INVALID_INDEX
Definition: cmindex.c:17
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
USHORT Signature
Definition: cmdata.h:178
PVOID CMAPI HvGetCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset)
Definition: hivecell.c:67
#define CM_KEY_HASH_LEAF
Definition: cmdata.h:16
return Found
Definition: dirsup.c:1270
#define CM_KEY_INDEX_ROOT
Definition: cmdata.h:13
ULONG HCELL_INDEX
Definition: hivedata.h:80
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
static HCELL_INDEX NTAPI CmpFindSubKeyByHash(IN PHHIVE Hive, IN PCM_KEY_FAST_INDEX FastIndex, IN PCUNICODE_STRING SearchName)
Definition: cmindex.c:646
#define CM_KEY_FAST_LEAF
Definition: cmdata.h:15
unsigned int ULONG
Definition: retypes.h:1
#define CM_KEY_INDEX_LEAF
Definition: cmdata.h:14

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 }
struct _CM_KEY_INDEX * PCM_KEY_INDEX
#define HvReleaseCell(h, c)
Definition: cmlib.h:390
#define HCELL_NIL
Definition: hivedata.h:85
PVOID CMAPI HvGetCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset)
Definition: hivecell.c:67
_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
HCELL_INDEX NTAPI CmpDoFindSubKeyByNumber(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN ULONG Number)
Definition: cmindex.c:514
ULONG HCELL_INDEX
Definition: hivedata.h:80
static const UCHAR Index[8]
Definition: usbohci.c:18
_In_opt_ PENTER_STATE_SYSTEM_HANDLER _In_opt_ PVOID _In_ LONG _In_opt_ LONG volatile * Number
Definition: ntpoapi.h:204
Definition: dlist.c:348

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

◆ 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 }
#define TRUE
Definition: types.h:120
#define HCELL_NIL
Definition: hivedata.h:85
Definition: strmini.h:380
#define INVALID_INDEX
Definition: cmindex.c:17
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
long LONG
Definition: pedump.c:60
#define CM_KEY_HASH_LEAF
Definition: cmdata.h:16
_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
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
static const UCHAR Index[8]
Definition: usbohci.c:18
Definition: strmini.h:378
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
#define CM_KEY_FAST_LEAF
Definition: cmdata.h:15
unsigned int ULONG
Definition: retypes.h:1
#define CM_KEY_INDEX_LEAF
Definition: cmdata.h:14

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 */
170  ASSERT((Leaf->Signature == CM_KEY_INDEX_LEAF) ||
171  (Leaf->Signature == CM_KEY_FAST_LEAF) ||
172  (Leaf->Signature == CM_KEY_HASH_LEAF));
173  ASSERT(Leaf->Count != 0);
174 
175  /* Do the compare */
176  Result = CmpCompareInIndex(Hive,
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 */
199  Result = CmpCompareInIndex(Hive,
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  {
233 Big:
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 */
255  Result = CmpCompareInIndex(Hive,
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 */
310  Result = CmpCompareInIndex(Hive,
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 */
345 ReturnFailure:
346  *SubKey = HCELL_NIL;
347 
348  /* Return path...check if we have a leaf to free */
349 Return:
350  if (Leaf) HvReleaseCell(Hive, LeafCell);
351 
352  /* Return the index */
353  return ReturnIndex;
354 }
#define TRUE
Definition: types.h:120
struct _CM_KEY_INDEX * PCM_KEY_INDEX
#define HvReleaseCell(h, c)
Definition: cmlib.h:390
#define HCELL_NIL
Definition: hivedata.h:85
Definition: strmini.h:380
#define INVALID_INDEX
Definition: cmindex.c:17
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
long LONG
Definition: pedump.c:60
USHORT Signature
Definition: cmdata.h:178
PVOID CMAPI HvGetCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset)
Definition: hivecell.c:67
#define CM_KEY_HASH_LEAF
Definition: cmdata.h:16
_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
#define CM_KEY_INDEX_ROOT
Definition: cmdata.h:13
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
USHORT Count
Definition: cmdata.h:179
ULONG HCELL_INDEX
Definition: hivedata.h:80
static const UCHAR Index[8]
Definition: usbohci.c:18
Definition: strmini.h:378
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
#define CM_KEY_FAST_LEAF
Definition: cmdata.h:15
unsigned int ULONG
Definition: retypes.h:1
#define CM_KEY_INDEX_LEAF
Definition: cmdata.h:14

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 = CmpAllocate(SearchName.Length,
797  TRUE,
798  TAG_CM);
799  if (!SearchName.Buffer)
800  {
801  /* Fail */
802  HvReleaseCell(Hive, TargetKey);
803  return FALSE;
804  }
805 
806  /* Copy it */
807  CmpCopyCompressedName(SearchName.Buffer,
808  SearchName.MaximumLength,
809  Node->Name,
810  Node->NameLength);
811  }
812  else
813  {
814  /* Name isn't compressed, build it directly from the node */
815  IsCompressed = FALSE;
816  SearchName.Length = Node->NameLength;
817  SearchName.MaximumLength = Node->NameLength;
818  SearchName.Buffer = Node->Name;
819  }
820 
821  /* We can release the target key now */
822  HvReleaseCell(Hive, TargetKey);
823 
824  /* Now get the parent key node */
825  Node = (PCM_KEY_NODE)HvGetCell(Hive, ParentKey);
826  if (!Node) goto Quickie;
827 
828  /* Loop all hive storage */
829  for (i = 0; i < Hive->StorageTypeCount; i++)
830  {
831  /* Check if any subkeys are in this index */
832  if (Node->SubKeyCounts[i])
833  {
834  /* Get the cell index */
835  //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[i]));
836  IndexCell = Node->SubKeyLists[i];
837 
838  /* Check if we had anything to release from before */
839  if (CellToRelease != HCELL_NIL)
840  {
841  /* Release it now */
842  HvReleaseCell(Hive, CellToRelease);
843  CellToRelease = HCELL_NIL;
844  }
845 
846  /* Get the key index for the cell */
847  Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
848  if (!Index) goto Quickie;
849 
850  /* Release it at the next iteration or below */
851  CellToRelease = IndexCell;
852 
853  /* Check if this is a root */
854  if (Index->Signature == CM_KEY_INDEX_ROOT)
855  {
856  /* Get the child inside the root */
857  Result = CmpFindSubKeyInRoot(Hive, Index, &SearchName, &Child);
858  if (Result & INVALID_INDEX) goto Quickie;
859  if (Child == HCELL_NIL) continue;
860 
861  /* We found it, mark the cell dirty */
862  HvMarkCellDirty(Hive, IndexCell, FALSE);
863 
864  /* Check if we had anything to release from before */
865  if (CellToRelease != HCELL_NIL)
866  {
867  /* Release it now */
868  HvReleaseCell(Hive, CellToRelease);
869  CellToRelease = HCELL_NIL;
870  }
871 
872  /* Now this child is the index, get the actual key index */
873  IndexCell = Child;
875  if (!Index) goto Quickie;
876 
877  /* Release it later */
878  CellToRelease = Child;
879  }
880 
881  /* Make sure this is a valid index */
882  ASSERT((Index->Signature == CM_KEY_INDEX_LEAF) ||
883  (Index->Signature == CM_KEY_FAST_LEAF) ||
884  (Index->Signature == CM_KEY_HASH_LEAF));
885 
886  /* Find the child in the leaf */
887  Result = CmpFindSubKeyInLeaf(Hive, Index, &SearchName, &Child);
888  if (Result & INVALID_INDEX) goto Quickie;
889  if (Child != HCELL_NIL)
890  {
891  /* We found it, free the name now */
892  if (IsCompressed) CmpFree(SearchName.Buffer, 0);
893 
894  /* Release the parent key */
895  HvReleaseCell(Hive, ParentKey);
896 
897  /* Check if we had a left over cell to release */
898  if (CellToRelease != HCELL_NIL)
899  {
900  /* Release it */
901  HvReleaseCell(Hive, CellToRelease);
902  }
903 
904  /* And mark the index cell dirty */
905  HvMarkCellDirty(Hive, IndexCell, FALSE);
906  return TRUE;
907  }
908  }
909  }
910 
911 Quickie:
912  /* Release any cells that we still hold */
913  if (Node) HvReleaseCell(Hive, ParentKey);
914  if (CellToRelease != HCELL_NIL) HvReleaseCell(Hive, CellToRelease);
915 
916  /* Free the search name and return failure */
917  if (IsCompressed) CmpFree(SearchName.Buffer, 0);
918  return FALSE;
919 }
#define KEY_COMP_NAME
Definition: cmdata.h:35
#define TRUE
Definition: types.h:120
ULONG NTAPI CmpFindSubKeyInLeaf(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
Definition: cmindex.c:358
struct _CM_KEY_INDEX * PCM_KEY_INDEX
USHORT MaximumLength
Definition: env_spec_w32.h:370
PVOID NTAPI CmpAllocate(_In_ SIZE_T Size, _In_ BOOLEAN Paged, _In_ ULONG Tag)
Definition: bootreg.c:90
#define HvReleaseCell(h, c)
Definition: cmlib.h:390
#define HCELL_NIL
Definition: hivedata.h:85
ULONG NTAPI CmpFindSubKeyInRoot(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
Definition: cmindex.c:143
#define INVALID_INDEX
Definition: cmindex.c:17
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
union node Node
Definition: types.h:1255
VOID NTAPI CmpCopyCompressedName(OUT PWCHAR Destination, IN ULONG DestinationLength, IN PWCHAR Source, IN ULONG SourceLength)
Definition: cmname.c:56
PVOID CMAPI HvGetCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset)
Definition: hivecell.c:67
unsigned char BOOLEAN
#define CM_KEY_HASH_LEAF
Definition: cmdata.h:16
struct _CM_KEY_NODE * PCM_KEY_NODE
_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
#define CM_KEY_INDEX_ROOT
Definition: cmdata.h:13
VOID NTAPI CmpFree(_In_ PVOID Ptr, _In_ ULONG Quota)
Definition: bootreg.c:105
ULONG HCELL_INDEX
Definition: hivedata.h:80
static const UCHAR Index[8]
Definition: usbohci.c:18
BOOLEAN CMAPI HvMarkCellDirty(PHHIVE RegistryHive, HCELL_INDEX CellOffset, BOOLEAN HoldingLock)
Definition: hivecell.c:100
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
#define TAG_CM
Definition: cmlib.h:203
#define CM_KEY_FAST_LEAF
Definition: cmdata.h:15
unsigned int ULONG
Definition: retypes.h:1
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn BOOLEAN Physical 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 ACPI_HANDLE Child
Definition: acpixf.h:716
#define CM_KEY_INDEX_LEAF
Definition: cmdata.h:14
USHORT NTAPI CmpCompressedNameSize(IN PWCHAR Name, IN ULONG Length)
Definition: cmname.c:95
Definition: dlist.c:348

Referenced by CmpMarkKeyDirty().

◆ CmpRemoveSubKey()

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

Definition at line 1696 of file cmindex.c.

1699 {
1701  UNICODE_STRING SearchName;
1702  BOOLEAN IsCompressed;
1703  WCHAR Buffer[50];
1704  HCELL_INDEX RootCell = HCELL_NIL, LeafCell, ChildCell;
1705  PCM_KEY_INDEX Root = NULL, Leaf;
1707  ULONG Storage, RootIndex = INVALID_INDEX, LeafIndex;
1708  BOOLEAN Result = FALSE;
1709  HCELL_INDEX CellToRelease1 = HCELL_NIL, CellToRelease2 = HCELL_NIL;
1710 
1711  /* Get the target key node */
1712  Node = (PCM_KEY_NODE)HvGetCell(Hive, TargetKey);
1713  if (!Node) return FALSE;
1714 
1715  /* Make sure it's dirty, then release it */
1716  ASSERT(HvIsCellDirty(Hive, TargetKey));
1717  HvReleaseCell(Hive, TargetKey);
1718 
1719  /* Check if the name is compressed */
1720  if (Node->Flags & KEY_COMP_NAME)
1721  {
1722  /* Remember for later */
1723  IsCompressed = TRUE;
1724 
1725  /* Build the search name */
1726  SearchName.Length = CmpCompressedNameSize(Node->Name,
1727  Node->NameLength);
1728  SearchName.MaximumLength = SearchName.Length;
1729 
1730  /* Do we need an extra bufer? */
1731  if (SearchName.MaximumLength > sizeof(Buffer))
1732  {
1733  /* Allocate one */
1734  SearchName.Buffer = CmpAllocate(SearchName.Length,
1735  TRUE,
1736  TAG_CM);
1737  if (!SearchName.Buffer) return FALSE;
1738  }
1739  else
1740  {
1741  /* Otherwise, use our local stack buffer */
1742  SearchName.Buffer = Buffer;
1743  }
1744 
1745  /* Copy the compressed name */
1746  CmpCopyCompressedName(SearchName.Buffer,
1747  SearchName.MaximumLength,
1748  Node->Name,
1749  Node->NameLength);
1750  }
1751  else
1752  {
1753  /* It's not compressed, build the name directly from the node */
1754  IsCompressed = FALSE;
1755  SearchName.Length = Node->NameLength;
1756  SearchName.MaximumLength = Node->NameLength;
1757  SearchName.Buffer = Node->Name;
1758  }
1759 
1760  /* Now get the parent node */
1761  Node = (PCM_KEY_NODE)HvGetCell(Hive, ParentKey);
1762  if (!Node) goto Exit;
1763 
1764  /* Make sure it's dirty, then release it */
1765  ASSERT(HvIsCellDirty(Hive, ParentKey));
1766  HvReleaseCell(Hive, ParentKey);
1767 
1768  /* Get the storage type and make sure it's not empty */
1769  Storage = HvGetCellType(TargetKey);
1770  ASSERT(Node->SubKeyCounts[Storage] != 0);
1771  //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[Storage]));
1772 
1773  /* Get the leaf cell now */
1774  LeafCell = Node->SubKeyLists[Storage];
1775  Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1776  if (!Leaf) goto Exit;
1777 
1778  /* Remember to release it later */
1779  CellToRelease1 = LeafCell;
1780 
1781  /* Check if the leaf is a root */
1782  if (Leaf->Signature == CM_KEY_INDEX_ROOT)
1783  {
1784  /* Find the child inside the root */
1785  RootIndex = CmpFindSubKeyInRoot(Hive, Leaf, &SearchName, &ChildCell);
1786  if (RootIndex & INVALID_INDEX) goto Exit;
1787  ASSERT(ChildCell != FALSE);
1788 
1789  /* The root cell is now this leaf */
1790  Root = Leaf;
1791  RootCell = LeafCell;
1792 
1793  /* And the new leaf is now this child */
1794  LeafCell = ChildCell;
1795  Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1796  if (!Leaf) goto Exit;
1797 
1798  /* Remember to release it later */
1799  CellToRelease2 = LeafCell;
1800  }
1801 
1802  /* Make sure the leaf is valid */
1803  ASSERT((Leaf->Signature == CM_KEY_INDEX_LEAF) ||
1804  (Leaf->Signature == CM_KEY_FAST_LEAF) ||
1805  (Leaf->Signature == CM_KEY_HASH_LEAF));
1806 
1807  /* Now get the child in the leaf */
1808  LeafIndex = CmpFindSubKeyInLeaf(Hive, Leaf, &SearchName, &ChildCell);
1809  if (LeafIndex & INVALID_INDEX) goto Exit;
1810  ASSERT(ChildCell != HCELL_NIL);
1811 
1812  /* Decrement key counts and check if this was the last leaf entry */
1813  Node->SubKeyCounts[Storage]--;
1814  if (!(--Leaf->Count))
1815  {
1816  /* Free the leaf */
1817  HvFreeCell(Hive, LeafCell);
1818 
1819  /* Check if we were inside a root */
1820  if (Root)
1821  {
1822  /* Decrease the root count too, since the leaf is going away */
1823  if (!(--Root->Count))
1824  {
1825  /* The root is gone too,n ow */
1826  HvFreeCell(Hive, RootCell);
1827  Node->SubKeyLists[Storage] = HCELL_NIL;
1828  }
1829  else if (RootIndex < Root->Count)
1830  {
1831  /* Bring everything up by one */
1832  RtlMoveMemory(&Root->List[RootIndex],
1833  &Root->List[RootIndex + 1],
1834  (Root->Count - RootIndex) * sizeof(HCELL_INDEX));
1835  }
1836  }
1837  else
1838  {
1839  /* Otherwise, just clear the cell */
1840  Node->SubKeyLists[Storage] = HCELL_NIL;
1841  }
1842  }
1843  else if (LeafIndex < Leaf->Count)
1844  {
1845  /* Was the leaf a normal index? */
1846  if (Leaf->Signature == CM_KEY_INDEX_LEAF)
1847  {
1848  /* Bring everything up by one */
1849  RtlMoveMemory(&Leaf->List[LeafIndex],
1850  &Leaf->List[LeafIndex + 1],
1851  (Leaf->Count - LeafIndex) * sizeof(HCELL_INDEX));
1852  }
1853  else
1854  {
1855  /* This is a fast index, bring everything up by one */
1856  Child = (PCM_KEY_FAST_INDEX)Leaf;
1857  RtlMoveMemory(&Child->List[LeafIndex],
1858  &Child->List[LeafIndex+1],
1859  (Child->Count - LeafIndex) * sizeof(CM_INDEX));
1860  }
1861  }
1862 
1863  /* If we got here, now we're done */
1864  Result = TRUE;
1865 
1866 Exit:
1867  /* Release any cells we may have been holding */
1868  if (CellToRelease1 != HCELL_NIL) HvReleaseCell(Hive, CellToRelease1);
1869  if (CellToRelease2 != HCELL_NIL) HvReleaseCell(Hive, CellToRelease2);
1870 
1871  /* Check if the name was compressed and not inside our local buffer */
1872  if ((IsCompressed) && (SearchName.MaximumLength > sizeof(Buffer)))
1873  {
1874  /* Free the buffer we allocated */
1875  CmpFree(SearchName.Buffer, 0);
1876  }
1877 
1878  /* Return the result */
1879  return Result;
1880 }
#define KEY_COMP_NAME
Definition: cmdata.h:35
BOOLEAN CMAPI HvIsCellDirty(IN PHHIVE Hive, IN HCELL_INDEX Cell)
Definition: hivecell.c:126
#define TRUE
Definition: types.h:120
ULONG NTAPI CmpFindSubKeyInLeaf(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
Definition: cmindex.c:358
struct _CM_KEY_INDEX * PCM_KEY_INDEX
USHORT MaximumLength
Definition: env_spec_w32.h:370
PVOID NTAPI CmpAllocate(_In_ SIZE_T Size, _In_ BOOLEAN Paged, _In_ ULONG Tag)
Definition: bootreg.c:90
#define HvReleaseCell(h, c)
Definition: cmlib.h:390
#define HCELL_NIL
Definition: hivedata.h:85
_Inout_ __drv_aliasesMem PSLIST_ENTRY _Inout_ PSLIST_ENTRY _In_ ULONG Count
Definition: exfuncs.h:1015
#define HvGetCellType(Cell)
Definition: hivedata.h:95
ULONG NTAPI CmpFindSubKeyInRoot(IN PHHIVE Hive, IN PCM_KEY_INDEX Index, IN PCUNICODE_STRING SearchName, IN PHCELL_INDEX SubKey)
Definition: cmindex.c:143
#define RtlMoveMemory(Destination, Source, Length)
Definition: typedefs.h:263
#define INVALID_INDEX
Definition: cmindex.c:17
union node Node
Definition: types.h:1255
VOID NTAPI CmpCopyCompressedName(OUT PWCHAR Destination, IN ULONG DestinationLength, IN PWCHAR Source, IN ULONG SourceLength)
Definition: cmname.c:56
PVOID CMAPI HvGetCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset)
Definition: hivecell.c:67
unsigned char BOOLEAN
#define CM_KEY_HASH_LEAF
Definition: cmdata.h:16
smooth NULL
Definition: ftsmooth.c:416
struct _CM_KEY_NODE * PCM_KEY_NODE
_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
Definition: bufpool.h:45
#define CM_KEY_INDEX_ROOT
Definition: cmdata.h:13
struct _CM_KEY_FAST_INDEX * PCM_KEY_FAST_INDEX
root entry for file system trees
Definition: entries.h:148
__wchar_t WCHAR
Definition: xmlstorage.h:180
VOID NTAPI CmpFree(_In_ PVOID Ptr, _In_ ULONG Quota)
Definition: bootreg.c:105
ULONG HCELL_INDEX
Definition: hivedata.h:80
static void Exit(void)
Definition: sock.c:1331
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
VOID CMAPI HvFreeCell(PHHIVE RegistryHive, HCELL_INDEX CellOffset)
Definition: hivecell.c:441
#define TAG_CM
Definition: cmlib.h:203
#define CM_KEY_FAST_LEAF
Definition: cmdata.h:15
unsigned int ULONG
Definition: retypes.h:1
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn BOOLEAN Physical 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 ACPI_HANDLE Child
Definition: acpixf.h:716
#define CM_KEY_INDEX_LEAF
Definition: cmdata.h:14
IN BOOLEAN OUT PSTR Buffer
Definition: progress.h:34
USHORT NTAPI CmpCompressedNameSize(IN PWCHAR Name, IN ULONG Length)
Definition: cmname.c:95
static IStorage Storage
Definition: ole2.c:3548
Definition: dlist.c:348

Referenced by CmpFreeKeyByCell().

◆ CmpSelectLeaf()

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

Definition at line 1266 of file cmindex.c.

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

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 1106 of file cmindex.c.

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

Referenced by CmpSelectLeaf().