[PATCH 5/6] ntdll: Implement RtlGetElementGenericTable().

[Zhiyi Zhang]

From: Zhiyi Zhang

---
 dlls/ntdll/rtl.c | 132 ++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 130 insertions(+), 2 deletions(-)

diff --git a/dlls/ntdll/rtl.c b/dlls/ntdll/rtl.c
index a0588db6957..bf1bfb793e7 100644
--- a/dlls/ntdll/rtl.c
+++ b/dlls/ntdll/rtl.c
@@ -249,6 +249,12 @@ static void *get_data_from_splay_links(RTL_SPLAY_LINKS *links)
     return (unsigned char *)links + FIELD_OFFSET(struct rtl_generic_table_entry, data);
 }

+static void *get_data_from_list_entry(LIST_ENTRY *list_entry)
+{
+    return (unsigned char *)list_entry + FIELD_OFFSET(struct rtl_generic_table_entry, data)
+        - FIELD_OFFSET(struct rtl_generic_table_entry, list_entry);
+}
+
 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));
@@ -750,8 +756,130 @@ ULONG WINAPI RtlNumberGenericTableElements(RTL_GENERIC_TABLE *table)
  */
 void * WINAPI RtlGetElementGenericTable(RTL_GENERIC_TABLE *table, ULONG index)
 {
-    FIXME("(%p, %lu) stub!\n", table, index);
-    return NULL;
+    ULONG count, ordered_element_index;
+    LIST_ENTRY *list_entry;
+    BOOL forward;
+
+    TRACE("(%p, %lu)\n", table, index);
+
+    if (index >= table->NumberGenericTableElements)
+        return NULL;
+
+    /* No OrderedPointer, use list header InsertOrderList */
+    if (table->WhichOrderedElement == 0)
+    {
+        /*
+         * |  lower half  | upper half |
+         * ^       ^      ^            ^
+         * head, 0 |      |            tail, table->NumberGenericTableElements - 1
+         *         |      (table->NumberGenericTableElements - 1) / 2
+         *         index closer to head
+         */
+        if (index <= (table->NumberGenericTableElements - 1) / 2)
+        {
+            list_entry = table->InsertOrderList.Flink;
+            count = index;
+            forward = TRUE;
+        }
+        /*
+         * |  lower half  | upper half |
+         * ^              ^       ^    ^
+         * head, 0        |       |    tail, table->NumberGenericTableElements - 1
+         *                |       index closer to tail
+         *                (table->NumberGenericTableElements - 1) / 2
+         */
+        else
+        {
+            list_entry = table->InsertOrderList.Blink;
+            count = table->NumberGenericTableElements - index - 1;
+            forward = FALSE;
+        }
+    }
+    /* Has OrderedPointer, decide to use list header or OrderedPointer */
+    else
+    {
+        ordered_element_index = table->WhichOrderedElement - 1;
+
+        /*
+         * | -------------- | ---------- |
+         * ^         ^      ^            ^
+         * head, 0   |      |            table->NumberGenericTableElements - 1
+         *           |      ordered_element_index
+         *           index, 0 <= index <= ordered_element_index
+         */
+        if (index <= ordered_element_index)
+        {
+            /*
+             * | ------------------- |
+             * ^          ^          ^
+             * | <--d1--> | <--d2--> |
+             * head, 0    |          ordered_element_index
+             *            index
+             *
+             */
+            /* d1 <= d2, index is closer to head, forward from head */
+            if (index <= ordered_element_index - index)
+            {
+                list_entry = table->InsertOrderList.Flink;
+                count = index;
+                forward = TRUE;
+            }
+            /* d1 > d2, index is closer to ordered_element_index, backward from ordered_element_index */
+            else
+            {
+                list_entry = table->OrderedPointer;
+                count = ordered_element_index - index;
+                forward = FALSE;
+            }
+        }
+        /*
+         * | ------ | ---------- |
+         * ^        ^  ^         ^
+         * head, 0  |  |         tail, table->NumberGenericTableElements - 1
+         *          |  index, ordered_element_index < index <= table->NumberGenericTableElements - 1
+         *          ordered_element_index
+         */
+        else
+        {
+            /*
+             * | --------------------------------|
+             * ^                      ^          ^
+             * | <--------d1--------> | <--d2--> |
+             * ordered_element_index  |          tail, table->NumberGenericTableElements - 1
+             *                        index
+             *
+             */
+            /* d1 <= d2, index is closer to ordered_element_index, forward from ordered_element_index */
+            if (index - ordered_element_index <= table->NumberGenericTableElements - index - 1)
+            {
+                list_entry = table->OrderedPointer;
+                count = index - ordered_element_index;
+                forward = TRUE;
+            }
+            /* d1 > d2, index is closer to tail, backward from tail */
+            else
+            {
+                list_entry = table->InsertOrderList.Blink;
+                count = table->NumberGenericTableElements - index - 1;
+                forward = FALSE;
+            }
+        }
+    }
+
+    if (forward)
+    {
+        while (count--)
+            list_entry = list_entry->Flink;
+    }
+    else
+    {
+        while (count--)
+            list_entry = list_entry->Blink;
+    }
+
+    table->OrderedPointer = list_entry;
+    table->WhichOrderedElement = index + 1;
+    return get_data_from_list_entry(list_entry);
 }

/******************************************************************************