alloc.c

#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <limits.h>
#include "alloc.h"
meta *base;
meta *last;

void *m_find(size_t size)
{
  if(!base) return 0;
  //else if(base==last) return base+1;

  meta *cur=base, *ans=0;
  size_t max=0, min=SIZE_T_MAX;
  int find=FALSE;

  do
  {
    switch(fit_type)
    {
      case FIRST_FIT:
        if(cur->free && cur->size>=size) find=TRUE;
        break;

      case BEST_FIT:
        if(cur->free && cur->size>=size && cur->size<min)
        {
          ans=cur;
          min=ans->size;
        }
        break;

      case WORST_FIT:
        if(cur->free && cur->size>=size && cur->size>max)
        {
          ans=cur;
          max=ans->size;
        }
        break;
    }
    if(!find) cur=cur->next;
  } while(cur && !find);
  
  if(find) ans=cur;
  
  return !ans?ans:ans+1;
}

meta *m_merge(meta *cur1, meta *cur2)
{
  cur1->next=cur2->next;
  cur1->size+=(cur2->size+META_SIZE);
  
  if(cur2==last) last=cur1;
  
  if(cur2->next && cur2->next->free)
    m_merge(cur1, cur2->next);
  else if(cur1->prev && cur1->prev->free)
    cur1=m_merge(cur1->prev, cur1);
  return cur1;
}

meta *m_split(meta *cur, size_t size)
{
  size_t size_sum=size+META_SIZE;
  if(cur->size<=size_sum) return cur;
  
  meta *new_meta=(void *)cur+size_sum;
  new_meta->prev=cur;
  new_meta->next=cur->next;
  new_meta->free=TRUE;
  new_meta->size=cur->size-size_sum;

  cur->size=size;
  cur->next=new_meta;
  return cur;
}

void *m_malloc(size_t size)
{
  size=align(size);
  size_t size_sum=size+META_SIZE;
  void *result;

  if(!base)
  {
    //if(sbrk(0)==-1) return;
    base=sbrk(0);
    sbrk((int)size_sum);
    base->free=TRUE;
    base->size=size;
    last=base;
  }
  
  result=m_find(size);
  
  //if no result
  if(!result)
  {
    if(last->free && (last->size < size))
      size_sum=size-last->size;
    meta *result_meta=last;
    last=sbrk((int)size_sum);
    last->prev=result_meta;
    last->free=TRUE;
    last->size=size;
    result_meta->next=last;
    result=result_meta+1;
    
    //realloc for the merging case
    if(last->free && (last->size < size))
      result=m_realloc(result, size);
    else
      result=last+1;
  }
  result=m_split(result-META_SIZE, size)+1;
  
  return result;
}

void *m_realloc(void *ptr, size_t size)
{
  size=align(size);
  void *cur=ptr;
  meta *cur_meta=cur-META_SIZE;

  if(cur_meta->size==size) return ptr;
  if(cur_meta->size>size)
    cur=m_split(cur_meta, size);
  else if(cur_meta->next && cur_meta->next->free && cur_meta->size+cur_meta->next->size+META_SIZE > size)
  {
    m_free(ptr);
    cur=m_merge(cur_meta, cur_meta->next);
    cur_meta=cur-META_SIZE;
    if(cur_meta->size+META_SIZE > size)
      cur=m_split(cur_meta, size);
  }
  //if nothing to merge or split
  else
  {
    cur=m_malloc(size);
    cur_meta=cur-META_SIZE;
    memcpy(cur, ptr, size);
    cur_meta->free=FALSE;
    m_free(ptr);
  }
  
  return cur;
}

void m_free(void *ptr)
{
  //if(!ptr) return 0;

  meta *cur=ptr-META_SIZE;
  cur->free=TRUE;
  
  if(cur->prev && cur->prev->free)
    cur=m_merge(cur->prev,cur);
  else if(cur->next && cur->next->free)
    cur=m_merge(cur,cur->next);
  
  //release memory on the last block
  if(cur->prev && cur==last)
  {
    last=last->prev;
    last->next=NULL;
  }
  
  //back to origin state if there are no blocks
  else if(!cur->prev && cur==last)
    base=last=NULL;
}

void *m_travel(int idx)
{
  if(!base) return 0;
  meta *cur=base;
  for(int i=0;cur && i<idx;i++)
    cur=cur->next;

  if(!cur) return 0;
  else return cur+1;
}

void print_mem(void)
{
  /*
  if(!base)
  {
    fprintf(stdout, "No memory allocated!\n");
    return;
  }
  */

  meta *cur=base;
  while(cur)
  {
    fprintf(stdout, "%d %zu", cur->free, cur->size);
    if(!cur->free) fprintf(stdout, " %s", (char *)(cur+1));
    fprintf(stdout, "\n");
    cur=cur->next;
  }

  return;
}