From: Zhiyi Zhang zzhang@codeweavers.com
--- dlls/ntdll/ntdll.spec | 2 +- dlls/ntdll/rtl.c | 75 +++++++++++++++++++++++++++++ dlls/ntoskrnl.exe/ntoskrnl.exe.spec | 2 +- include/ddk/ntddk.h | 1 + 4 files changed, 78 insertions(+), 2 deletions(-)
diff --git a/dlls/ntdll/ntdll.spec b/dlls/ntdll/ntdll.spec index 8614ecf9d47..63fc62c5d38 100644 --- a/dlls/ntdll/ntdll.spec +++ b/dlls/ntdll/ntdll.spec @@ -819,7 +819,7 @@ @ stdcall RtlInitializeSRWLock(ptr) @ stdcall RtlInitializeSid(ptr ptr long) # @ stub RtlInitializeStackTraceDataBase -@ stub RtlInsertElementGenericTable +@ stdcall RtlInsertElementGenericTable(ptr ptr long ptr) @ stdcall RtlInsertElementGenericTableAvl(ptr ptr long ptr) @ cdecl -arch=!i386 RtlInstallFunctionTableCallback(long long long ptr ptr wstr) @ stdcall RtlInt64ToUnicodeString(int64 long ptr) diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c index ee330482162..8138c060795 100644 --- a/dlls/ntdll/rtl.c +++ b/dlls/ntdll/rtl.c @@ -236,6 +236,24 @@ NTSTATUS WINAPI RtlResetNtUserPfn(void) return STATUS_SUCCESS; }
+/* data is a place holder to align stored data on a 8 byte boundary */ +struct rtl_generic_table_entry +{ + RTL_SPLAY_LINKS splay_links; + LIST_ENTRY list_entry; + LONGLONG data; +}; + +static void *get_data_from_splay_links(RTL_SPLAY_LINKS *links) +{ + return (unsigned char *)links + FIELD_OFFSET(struct rtl_generic_table_entry, data); +} + +static LIST_ENTRY *get_list_entry_from_splay_links(RTL_SPLAY_LINKS *links) +{ + return (LIST_ENTRY *)((unsigned char *)links + FIELD_OFFSET(struct rtl_generic_table_entry, list_entry)); +} + static void rtl_splay_replace(RTL_SPLAY_LINKS *x, RTL_SPLAY_LINKS *y, RTL_SPLAY_LINKS **root) { if (RtlIsRoot(x)) @@ -556,6 +574,63 @@ BOOLEAN WINAPI RtlIsGenericTableEmpty(RTL_GENERIC_TABLE *table) return !table->TableRoot; }
+/*********************************************************************** + * RtlInsertElementGenericTable (NTDLL.@) + */ +void * WINAPI RtlInsertElementGenericTable(RTL_GENERIC_TABLE *table, void *value, CLONG size, BOOLEAN *new_element) +{ + RTL_SPLAY_LINKS *child, *parent = NULL; + RTL_GENERIC_COMPARE_RESULTS result; + void *buffer; + + TRACE("(%p, %p, %lu, %p)\n", table, value, size, new_element); + + child = table->TableRoot; + while (child) + { + buffer = get_data_from_splay_links(child); + result = table->CompareRoutine(table, buffer, value); + parent = child; + if (result == GenericLessThan) + { + child = child->RightChild; + } + else if (result == GenericGreaterThan) + { + child = child->LeftChild; + } + else + { + if (new_element) + *new_element = FALSE; + return buffer; + } + } + + /* data should be stored on a 8 byte boundary */ + child = (RTL_SPLAY_LINKS *)table->AllocateRoutine(table, size + FIELD_OFFSET(struct rtl_generic_table_entry, data)); + RtlInitializeSplayLinks(child); + InsertTailList(&table->InsertOrderList, get_list_entry_from_splay_links(child)); + buffer = get_data_from_splay_links(child); + memcpy(buffer, value, size); + + if (parent) + { + buffer = get_data_from_splay_links(parent); + result = table->CompareRoutine(table, buffer, value); + if (result == GenericLessThan) + RtlInsertAsRightChild(parent, child); + else + RtlInsertAsLeftChild(parent, child); + } + + if (new_element) + *new_element = TRUE; + table->TableRoot = RtlSplay(child); + table->NumberGenericTableElements++; + return get_data_from_splay_links(child); +} + /****************************************************************************** * RtlEnumerateGenericTableWithoutSplaying [NTDLL.@] */ diff --git a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec index 57a947ea821..050409f993d 100644 --- a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec +++ b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec @@ -1150,7 +1150,7 @@ @ stub RtlInitializeRangeList @ stdcall RtlInitializeSid(ptr ptr long) @ stub RtlInitializeUnicodePrefix -@ stub RtlInsertElementGenericTable +@ stdcall RtlInsertElementGenericTable(ptr ptr long ptr) @ stdcall RtlInsertElementGenericTableAvl(ptr ptr long ptr) @ stub RtlInsertElementGenericTableFull @ stub RtlInsertElementGenericTableFullAvl diff --git a/include/ddk/ntddk.h b/include/ddk/ntddk.h index 67198da2f3d..f16b3fd628a 100644 --- a/include/ddk/ntddk.h +++ b/include/ddk/ntddk.h @@ -308,6 +308,7 @@ BOOLEAN WINAPI RtlEqualString(const STRING*,const STRING*,BOOLEAN); void * WINAPI RtlGetElementGenericTable(PRTL_GENERIC_TABLE,ULONG); void WINAPI RtlInitializeGenericTable(PRTL_GENERIC_TABLE,PRTL_GENERIC_COMPARE_ROUTINE,PRTL_GENERIC_ALLOCATE_ROUTINE,PRTL_GENERIC_FREE_ROUTINE,void *); void WINAPI RtlInitializeGenericTableAvl(PRTL_AVL_TABLE,PRTL_AVL_COMPARE_ROUTINE,PRTL_AVL_ALLOCATE_ROUTINE, PRTL_AVL_FREE_ROUTINE,void *); +PVOID WINAPI RtlInsertElementGenericTable(PRTL_GENERIC_TABLE,PVOID,CLONG,PBOOLEAN); void WINAPI RtlInsertElementGenericTableAvl(PRTL_AVL_TABLE,void *,ULONG,BOOL*); BOOLEAN WINAPI RtlIsGenericTableEmpty(PRTL_GENERIC_TABLE); void * WINAPI RtlLookupElementGenericTable(PRTL_GENERIC_TABLE,void *);