[avr-libc-commit] [2137] Submitted by Gerben van den Broeke:

[Joerg Wunsch]

Revision: 2137
          http://svn.sv.gnu.org/viewvc/?view=rev&root=avr-libc&revision=2137
Author:   joerg_wunsch
Date:     2010-06-08 12:18:40 +0000 (Tue, 08 Jun 2010)
Log Message:
-----------
Submitted by Gerben van den Broeke:
patch #6555: malloc improvement
* libc/stdlib/malloc.c (malloc): Speed up reallocations.

Ticket Links:
:-----------
    http://savannah.gnu.org/patch/?6555

Modified Paths:
--------------
    trunk/avr-libc/ChangeLog
    trunk/avr-libc/NEWS
    trunk/avr-libc/libc/stdlib/malloc.c

Modified: trunk/avr-libc/ChangeLog
===================================================================
--- trunk/avr-libc/ChangeLog    2010-06-08 12:03:38 UTC (rev 2136)
+++ trunk/avr-libc/ChangeLog    2010-06-08 12:18:40 UTC (rev 2137)
@@ -1,5 +1,11 @@
 2010-06-08  Joerg Wunsch <address@hidden>
 
+       Submitted by Gerben van den Broeke:
+       patch #6555: malloc improvement
+       * libc/stdlib/malloc.c (malloc): Speed up reallocations.
+
+2010-06-08  Joerg Wunsch <address@hidden>
+
        Submitted by Krzysztof Kosciuszkiewicz:
        patch #6690: Shorten calculation of dallas 1-wire crc
        * include/util/crc16.h (_crc_ibutton_update): no need to

Modified: trunk/avr-libc/NEWS
===================================================================
--- trunk/avr-libc/NEWS 2010-06-08 12:03:38 UTC (rev 2136)
+++ trunk/avr-libc/NEWS 2010-06-08 12:18:40 UTC (rev 2137)
@@ -279,6 +279,7 @@
 
   [#6500] Reentrant code faq
   [#6517] Pgmspace with float support
+  [#6555] malloc improvement
   [#6649] sqrt.S in libm changes
   [#6690] Shorten calculation of dallas 1-wire crc
   [#6718] Optimize the EEPROM functions

Modified: trunk/avr-libc/libc/stdlib/malloc.c
===================================================================
--- trunk/avr-libc/libc/stdlib/malloc.c 2010-06-08 12:03:38 UTC (rev 2136)
+++ trunk/avr-libc/libc/stdlib/malloc.c 2010-06-08 12:18:40 UTC (rev 2137)
@@ -1,4 +1,5 @@
 /* Copyright (c) 2002, 2004, 2010 Joerg Wunsch
+   Copyright (c) 2010  Gerben van den Broeke
    All rights reserved.
 
    Redistribution and use in source and binary forms, with or without
@@ -66,7 +67,7 @@
 void *
 malloc(size_t len)
 {
-       struct __freelist *fp1, *fp2;
+       struct __freelist *fp1, *fp2, *sfp1, *sfp2;
        char *cp;
        size_t s, avail;
 
@@ -82,13 +83,15 @@
        /*
         * First, walk the free list and try finding a chunk that
         * would match exactly.  If we found one, we are done.  While
-        * walking, note down the size of the smallest chunk we found
-        * that would still fit the request -- we need it for step 2.
+        * walking, note down the smallest chunk we found that would
+        * still fit the request -- we need it for step 2.
         *
         */
        for (s = 0, fp1 = __flp, fp2 = 0;
             fp1;
             fp2 = fp1, fp1 = fp1->nx) {
+               if (fp1->sz < len)
+                       continue;
                if (fp1->sz == len) {
                        /*
                         * Found it.  Disconnect the chunk from the
@@ -100,9 +103,13 @@
                                __flp = fp1->nx;
                        return &(fp1->nx);
                }
-               if (fp1->sz > len) {
-                       if (s == 0 || fp1->sz < s)
+               else {
+                       if (s == 0 || fp1->sz < s) {
+                               /* this is the smallest chunk found so far */
                                s = fp1->sz;
+                               sfp1 = fp1;
+                               sfp2 = fp2;
+                       }
                }
        }
        /*
@@ -116,44 +123,30 @@
         * and use the entire chunk.
         */
        if (s) {
-               if (s - len < sizeof(struct __freelist))
-                       len = s;
-               for (fp1 = __flp, fp2 = 0;
-                    fp1;
-                    fp2 = fp1, fp1 = fp1->nx) {
-                       if (fp1->sz == s) {
-                               if (len == s) {
-                                       /*
-                                        * Use entire chunk; same as
-                                        * above.
-                                        */
-                                       if (fp2)
-                                               fp2->nx = fp1->nx;
-                                       else
-                                               __flp = fp1->nx;
-                                       return &(fp1->nx);
-                               }
-                               /*
-                                * Split them up.  Note that we leave
-                                * the first part as the new (smaller)
-                                * freelist entry, and return the
-                                * upper portion to the caller.  This
-                                * saves us the work to fix up the
-                                * freelist chain; we just need to
-                                * fixup the size of the current
-                                * entry, and note down the size of
-                                * the new chunk before returning it
-                                * to the caller.
-                                */
-                               cp = (char *)fp1;
-                               s -= len;
-                               cp += s;
-                               fp2 = (struct __freelist *)cp;
-                               fp2->sz = len;
-                               fp1->sz = s - sizeof(size_t);
-                               return &(fp2->nx);
-                       }
+               if (s - len < sizeof(struct __freelist)) {
+                       /* Disconnect it from freelist and return it. */
+                       if (sfp2)
+                               sfp2->nx = sfp1->nx;
+                       else
+                               __flp = sfp1->nx;
+                       return &(sfp1->nx);
                }
+               /*
+                * Split them up.  Note that we leave the first part
+                * as the new (smaller) freelist entry, and return the
+                * upper portion to the caller.  This saves us the
+                * work to fix up the freelist chain; we just need to
+                * fixup the size of the current entry, and note down
+                * the size of the new chunk before returning it to
+                * the caller.
+                */
+               cp = (char *)sfp1;
+               s -= len;
+               cp += s;
+               sfp2 = (struct __freelist *)cp;
+               sfp2->sz = len;
+               sfp1->sz = s - sizeof(size_t);
+               return &(sfp2->nx);
        }
        /*
         * Step 3: If the request could not be satisfied from a