Yet another implementation of malloc() in C
Design.

The trouble with your design is that you have to search a list. Where none of the sizes may match. Even if there is a block in the list of the correct size you have to search through all the blocks that don't match your size.

Step 1

Use a list of lists. The top level list is an ordered list of sizes. So you can loop across this list quickly looking for the size you want. And stop if it does not exist.

The second level list is a list of all blocks of a specific size. So if you find the list of 24 bytes. That list contains all the 24 byte blocks that have been freed (so you just take the first one).

When an object is used you remove it from a list and when it is free'd you add it back to the list of free blocks.

global-&gt;********* --&gt;********* --&gt;********* --&gt;*********
        *   8   * |  *   16  * |  *  24   * |  *  32   *
        * next  *-|  * next  *-|  * next  *    * next  *
        *********    *********    *********    *********
            |            |            |            |
            \/           \/           \/           \/
        *********    *********    *********    *********    
        * block *    * block *    * block *    * block *    
        * next  *    * next  *    * next  *    * next  *    
        *********    *********    *********    *********    
            |            |            |            |
            \/           \/           \/           \/
        *********       null      *********    *********    
        * block *                 * block *    * block *    
        * next  *                 * next  *    * next  *    
        *********                 *********    *********    
            |                         |            |
            \/                        \/           \/
        *********                    null      *********    
        * block *                              * block *    
        * next  *                              * next  *    
        *********                              *********    
            |                                      |
            \/                                     \/
        *********                                  null         
        * block *                                          
        * next  *                                          
        *********   
            |
            \/
            null     


Step 2 Simple Optimizations

If you don't find a block of the exact size you can re-use a block that is too large. There are two version of this. a) slightly too large and just waste a small amount of space b) twice as big as you need and split the block into two pieces.

Searching the size list can still be expensive but that can be simplified by using a skip list. This should significantly reduce the time you need to search the list.

Alternatively rather than a top level list you could use a balanced tree to hold the top level structure. That way finding a value is always O(ln(x)) where x is the number of different sizes.                                  

Code Review

Your code is fine for handling string data. But you don't take into account the alignment of the object you are allocating for. If you allocate a block of 5 you don't guarantee that the object is aligned for a structure of 5 bytes (only aligned for an array of 5 characters).

Search across blocks that have already been allocated seems like a waste of time. Either simply remove allocated blocks from the global chain or if you absolutely must track them then keep two lists (one for allocated objects and one for freed objects).

There is no need to add blocks onto the end. It is far simpler to add new blocks to the front of a list.

Your code does not use the prev pointer!!!!