[PATCH 2/6] ntdll: Implement RtlDeleteElementGenericTable().

[Zhiyi Zhang]

From: Zhiyi Zhang

---
 dlls/ntdll/ntdll.spec               |  2 +-
 dlls/ntdll/rtl.c                    | 38 +++++++++++++++++++++++++++++
 dlls/ntoskrnl.exe/ntoskrnl.exe.spec |  2 +-
 include/ddk/ntddk.h                 |  1 +
 4 files changed, 41 insertions(+), 2 deletions(-)

diff --git a/dlls/ntdll/ntdll.spec b/dlls/ntdll/ntdll.spec
index 63fc62c5d38..cb6682d7e5c 100644
--- a/dlls/ntdll/ntdll.spec
+++ b/dlls/ntdll/ntdll.spec
@@ -615,7 +615,7 @@
 @ stdcall RtlDeleteAtomFromAtomTable(ptr long)
 @ stdcall RtlDeleteCriticalSection(ptr)
 @ stdcall -arch=!i386 RtlDeleteGrowableFunctionTable(ptr)
-@ stub RtlDeleteElementGenericTable
+@ stdcall RtlDeleteElementGenericTable(ptr ptr)
 @ stub RtlDeleteElementGenericTableAvl
 @ cdecl -arch=!i386 RtlDeleteFunctionTable(ptr)
 @ stdcall RtlDeleteNoSplay(ptr ptr)
diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c
index 8138c060795..7f5282e8b97 100644
--- a/dlls/ntdll/rtl.c
+++ b/dlls/ntdll/rtl.c
@@ -254,6 +254,25 @@ 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 RTL_SPLAY_LINKS *rtl_splay_find(RTL_GENERIC_TABLE *table, void *value)
+{
+    RTL_GENERIC_COMPARE_RESULTS result;
+    RTL_SPLAY_LINKS *child;
+
+    child = table->TableRoot;
+    while (child)
+    {
+        result = table->CompareRoutine(table, get_data_from_splay_links(child), value);
+        if (result == GenericLessThan)
+            child = child->RightChild;
+        else if (result == GenericGreaterThan)
+            child = child->LeftChild;
+        else
+            return child;
+    }
+    return NULL;
+}
+
 static void rtl_splay_replace(RTL_SPLAY_LINKS *x, RTL_SPLAY_LINKS *y, RTL_SPLAY_LINKS **root)
 {
     if (RtlIsRoot(x))
@@ -631,6 +650,25 @@ void * WINAPI RtlInsertElementGenericTable(RTL_GENERIC_TABLE *table, void *value
     return get_data_from_splay_links(child);
 }

+BOOLEAN WINAPI RtlDeleteElementGenericTable(RTL_GENERIC_TABLE *table, void *value)
+{
+    RTL_SPLAY_LINKS *child;
+
+    TRACE("(%p, %p)\n", table, value);
+
+    child = rtl_splay_find(table, value);
+    if (!child)
+        return FALSE;
+
+    table->TableRoot = RtlDelete(child);
+    RemoveEntryList(get_list_entry_from_splay_links(child));
+    table->NumberGenericTableElements--;
+    table->OrderedPointer = &table->InsertOrderList;
+    table->WhichOrderedElement = 0;
+    table->FreeRoutine(table, child);
+    return TRUE;
+}
+
 /******************************************************************************
  *  RtlEnumerateGenericTableWithoutSplaying           [NTDLL.@]
  */
diff --git a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec
index 050409f993d..49a29d06644 100644
--- a/dlls/ntoskrnl.exe/ntoskrnl.exe.spec
+++ b/dlls/ntoskrnl.exe/ntoskrnl.exe.spec
@@ -1054,7 +1054,7 @@
 @ stdcall RtlDelete(ptr)
 @ stdcall RtlDeleteAce(ptr long)
 @ stdcall RtlDeleteAtomFromAtomTable(ptr long)
-@ stub RtlDeleteElementGenericTable
+@ stdcall RtlDeleteElementGenericTable(ptr ptr)
 @ stub RtlDeleteElementGenericTableAvl
 @ stdcall RtlDeleteNoSplay(ptr ptr)
 @ stub RtlDeleteOwnersRanges
diff --git a/include/ddk/ntddk.h b/include/ddk/ntddk.h
index f16b3fd628a..36c52097c16 100644
--- a/include/ddk/ntddk.h
+++ b/include/ddk/ntddk.h
@@ -301,6 +301,7 @@ NTSTATUS  WINAPI PsSetLoadImageNotifyRoutineEx(PLOAD_IMAGE_NOTIFY_ROUTINE,ULONG_
 LONG      WINAPI RtlCompareString(const STRING*,const STRING*,BOOLEAN);
 void      WINAPI RtlCopyString(STRING*,const STRING*);
 PRTL_SPLAY_LINKS WINAPI RtlDelete(PRTL_SPLAY_LINKS);
+BOOLEAN   WINAPI RtlDeleteElementGenericTable(PRTL_GENERIC_TABLE,PVOID);
 void      WINAPI RtlDeleteNoSplay(PRTL_SPLAY_LINKS,PRTL_SPLAY_LINKS *);
 void *    WINAPI RtlEnumerateGenericTableWithoutSplaying(PRTL_GENERIC_TABLE,PVOID*);
 void *    WINAPI RtlEnumerateGenericTableWithoutSplayingAvl(PRTL_AVL_TABLE,PVOID*);