title: Defragment Memory Blocks in C Memory Pool
body: <p>I've built a simple memory pool in C and I've also implemented the ability to implement memory blocks in this pool.</p>
  
  <p>The memory blocks themselves are quite simple, just a doubly linked list with a free flag and size property.</p>
  
  <p>What I'm trying to do now is create a function that takes a pointer to my memory pool and defragments the memory blocks inside so that allocated (free == 0) blocks are towards the beginning of the pool and deallocated blocks are towards the end of the pool.</p>
  
  <p>For example, if I had the blocks of memory structured like this before I called my defragment function:</p>
  
  <pre><code>Block Size: 25 (41 w/ header), Free: 1
  Block Size: 100 (116 w/ header), Free: 0
  Block Size: 25 (41 w/ header), Free: 1
  Block Size: 100 (116 w/ header), Free: 0
  Block Size: 100 (116 w/ header), Free: 0
  Block Size: 54 (70 w/ header), Free: 1
  </code></pre>
  
  <p>Then after calling my function the blocks would be arranged like so:</p>
  
  <pre><code>Block Size: 100 (116 w/ header), Free: 0
  Block Size: 100 (116 w/ header), Free: 0
  Block Size: 100 (116 w/ header), Free: 0
  Block Size: 25 (41 w/ header), Free: 1
  Block Size: 25 (41 w/ header), Free: 1
  Block Size: 54 (70 w/ header), Free: 1
  </code></pre>
  
  <p>I've attempted to build the function already however I've ran into a problem with moving the correct blocks around it seems as this is my output after the function is called:</p>
  
  <pre><code>Block Size: 100 (116 w/ header), Free: 0
  Block Size: 25 (41 w/ header), Free: 1
  Block Size: 100 (116 w/ header), Free: 0
  Block Size: 1744830464 (1744830480 w/ header), Free: 21
  </code></pre>
  
  <p>I'm not certain at all where the function is performing the incorrect operations so hopefully someone can shed some light on this for me.</p>
  
  <p>My defragment function:</p>
  
  <pre><code>void defragment(Pool* pool)
  {
      if(pool &amp;&amp; pool-&gt;root)
      {
          Block* current = pool-&gt;root;
  
          while(current)
          {
              if(!current-&gt;free)
              {
                  Block* current_prev = current-&gt;prev;
  
                  if(current_prev &amp;&amp; current_prev-&gt;free)
                  {
                      Block* prev_prev = current_prev-&gt;prev;
                      int new_block_size = current_prev-&gt;size;
  
                      Block* moved_current = memmove(current_prev, current, sizeof(Block) + current-&gt;size);
  
                      if(!moved_current)
                      {
                          printf("couldn't move memory\n");
                      }
                      else
                      {
                          Block* new_block = initBlock((((char*)moved_current) + sizeof(Block) + moved_current-&gt;size), new_block_size);
                          new_block-&gt;prev = moved_current;
                          new_block-&gt;next = moved_current-&gt;next;
  
                          moved_current-&gt;prev = prev_prev;
                          moved_current-&gt;next = new_block;
  
                          if(prev_prev)
                          {
                              prev_prev-&gt;next = moved_current;
                          }
  
                          current = moved_current;
                          continue;
                      }
                  }
              }
  
              current = current-&gt;next;
          }
  
          //Join Contiguous Blocks
      }
  }
  </code></pre>
  
  <p>The call to the initBlock function just takes a memory address, treats it as a Block structure, then sets the free property to true and the size property to the given size.</p>
  
  <p>I'm using the GCC compiler with the -std=C99 flag.</p>