Changeset 8491c48 in mainline

Timestamp:

2005-09-11T12:19:35Z (19 years ago)

Author:

Sergey Bondari <bondari@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

3156582

Parents:

a1493d9

Message:

Generic quicksort and bubble sort implementation.
ACPI MADT parser now uses qsort() for index sorting

Files:

• arch/ia32/src/acpi/madt.c (modified) (4 diffs)
• include/sort.h (added)
• src/Makefile (modified) (1 diff)
• src/lib/func.c (modified) (1 diff)
• src/lib/sort.c (added)

arch/ia32/src/acpi/madt.c

@@ -39 +39 @@
 #include <mm/heap.h>
 #include <memstr.h>
+#include <sort.h>
 
 struct acpi_madt *acpi_madt = NULL;
@@ -46 +47 @@
 static void madt_l_apic_entry(struct madt_l_apic *la, __u32 index);
 static void madt_io_apic_entry(struct madt_io_apic *ioa, __u32 index);
+static int madt_cmp(void * a, void * b);
 
 struct madt_l_apic *madt_l_apic_entries = NULL;
@@ -109 +111 @@
 }
 
+int madt_cmp(void * a, void * b) 
+{
+    return 
+        (((struct madt_apic_header *) a)->type > ((struct madt_apic_header *) b)->type) ?
+        1 : 
+        ((((struct madt_apic_header *) a)->type < ((struct madt_apic_header *) b)->type) ? -1 : 0);
+}
+        
 void acpi_madt_parse(void)
 {
+
+
         struct madt_apic_header *end = (struct madt_apic_header *) (((__u8 *) acpi_madt) + acpi_madt->header.length);
         struct madt_apic_header *h;
@@ -132 +144 @@
 
 
-        /* Bublesort madt index. Quicksort later. */
-        bool done = false;
-
-        while (!done) {
-                done = true;
-                for (index = 0; index < madt_entries_index_cnt - 1; index++) {
-                        if (madt_entries_index[index]->type > madt_entries_index[index + 1]->type) {
-                                h = madt_entries_index[index];
-                                madt_entries_index[index] = madt_entries_index[index + 1];
-                                madt_entries_index[index + 1] = h;
-                                done = false;
-                        }
-                }
-        
-        }
-                
+        /* Quicksort MADT index structure */
+        qsort(madt_entries_index, madt_entries_index_cnt, sizeof(__address), &madt_cmp);
 
         /* Parse MADT entries */        

src/Makefile

@@ -18 +18 @@
         lib/memstr.c \
         lib/the.c \
+        lib/sort.c \
         debug/print.c \
         debug/symtab.c \

src/lib/func.c

@@ -77 +77 @@
         return 1;
 }
+