Changeset 01e48c1 in mainline

Timestamp:

2005-09-15T21:02:27Z (19 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

0a50f59

Parents:

d6dcdd2e

Message:

Optimize sorting functions so that malloc() and free() is called only for e_size > EBUFSIZE.
Smaller buffers are allocated directly on the stack.

Some copyright holder fixes on some files written by Ondrej Palkovsky.

Files:

• arch/amd64/include/mm/frame.h (modified) (1 diff)
• arch/amd64/include/mm/page.h (modified) (1 diff)
• arch/amd64/include/mm/vm.h (modified) (1 diff)
• arch/ia32/src/acpi/madt.c (modified) (1 diff)
• src/lib/sort.c (modified) (3 diffs)

arch/amd64/include/mm/frame.h

@@ -1 +1 @@
 /*
- * Copyright (C) 2005 Martin Decky
+ * Copyright (C) 2005 Ondrej Palkovsky
  * All rights reserved.
  *

arch/amd64/include/mm/page.h

@@ -1 +1 @@
 /*
- * Copyright (C) 2005 Martin Decky
+ * Copyright (C) 2005 Ondrej Palkovsky
  * All rights reserved.
  *

arch/amd64/include/mm/vm.h

@@ -1 +1 @@
 /*
- * Copyright (C) 2005 Martin Decky
+ * Copyright (C) 2005 Ondrej Palkovsky
  * All rights reserved.
  *

arch/ia32/src/acpi/madt.c

@@ -113 +113 @@
 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);
+        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;

src/lib/sort.c

@@ -32 +32 @@
 #include <panic.h>
 
+#define EBUFSIZE        32
+
 static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp);
 
@@ -38 +40 @@
  */
 void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
-        void * tmp = (void *) malloc(e_size);
-        void * pivot = (void *) malloc(e_size);
+        __u8 buf_tmp[EBUFSIZE];
+        __u8 buf_pivot[EBUFSIZE];
+        void * tmp = buf_tmp;
+        void * pivot = buf_pivot;
+
+        if (e_size > EBUFSIZE) {
+                pivot = (void *) malloc(e_size);
+                tmp = (void *) malloc(e_size);
         
-        if (!tmp || !pivot) {
-                panic("Cannot allocate memory\n");
+                if (!tmp || !pivot) {
+                        panic("Cannot allocate memory\n");
+                }
         }
 
         _qsort(data, n, e_size, cmp, pivot, tmp);
         
-        free(tmp);
-        free(pivot);
+        if (e_size > EBUFSIZE) {
+                free(tmp);
+                free(pivot);
+        }
 }
 
 
 void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
+        __u8 buf_slot[EBUFSIZE];
         bool done = false;
         void * p;
-        void * slot = (void *) malloc(e_size);
+        void * slot = buf_slot;
+        
+        if (e_size > EBUFSIZE) {
+                slot = (void *) malloc(e_size);
+                
+                if (!slot) {
+                        panic("Cannot allocate memory\n");
+                }
+        }
 
         while (!done) {
@@ -69 +89 @@
         }
         
-        free(slot);
+        if (e_size > EBUFSIZE) {        
+                free(slot);
+        }
 }