CareerCup

Below is the solution. This code is taken IBM Developer works site

/* Include the sbrk function */
#include <unistd.h>

int has_initialized = 0;
void *managed_memory_start;
void *last_valid_address;

void malloc_init()
{
/* grab the last valid address from the OS */
last_valid_address = sbrk(0);

/* we don't have any memory to manage yet, so
*just set the beginning to be last_valid_address
*/
managed_memory_start = last_valid_address;

/* Okay, we're initialized and ready to go */
has_initialized = 1;
}

struct mem_control_block {
int is_available;
int size;
};

void free(void *firstbyte) {
struct mem_control_block *mcb;

/* Backup from the given pointer to find the
* mem_control_block
*/
mcb = firstbyte - sizeof(struct mem_control_block);
/* Mark the block as being available */
mcb->is_available = 1;
/* That's It! We're done. */
return;
}

void *malloc(long numbytes) {
/* Holds where we are looking in memory */
void *current_location;

/* This is the same as current_location, but cast to a
* memory_control_block
*/
struct mem_control_block *current_location_mcb;

/* This is the memory location we will return. It will
* be set to 0 until we find something suitable
*/
void *memory_location;

/* Initialize if we haven't already done so */
if(! has_initialized) {
malloc_init();
}

/* The memory we search for has to include the memory
* control block, but the user of malloc doesn't need
* to know this, so we'll just add it in for them.
*/
numbytes = numbytes + sizeof(struct mem_control_block);

/* Set memory_location to 0 until we find a suitable
* location
*/
memory_location = 0;

/* Begin searching at the start of managed memory */
current_location = managed_memory_start;

/* Keep going until we have searched all allocated space */
while(current_location != last_valid_address)
{
/* current_location and current_location_mcb point
* to the same address. However, current_location_mcb
* is of the correct type so we can use it as a struct.
* current_location is a void pointer so we can use it
* to calculate addresses.
*/
current_location_mcb =
(struct mem_control_block *)current_location;

if(current_location_mcb->is_available)
{
if(current_location_mcb->size >= numbytes)
{
/* Woohoo! We've found an open,
* appropriately-size location.
*/

/* It is no longer available */
current_location_mcb->is_available = 0;

/* We own it */
memory_location = current_location;

/* Leave the loop */
break;
}
}

/* If we made it here, it's because the Current memory
* block not suitable, move to the next one
*/
current_location = current_location +
current_location_mcb->size;
}

/* If we still don't have a valid location, we'll
* have to ask the operating system for more memory
*/
if(! memory_location)
{
/* Move the program break numbytes further */
sbrk(numbytes);

/* The new memory will be where the last valid
* address left off
*/
memory_location = last_valid_address;

/* We'll move the last valid address forward
* numbytes
*/
last_valid_address = last_valid_address + numbytes;

/* We need to initialize the mem_control_block */
current_location_mcb = memory_location;
current_location_mcb->is_available = 0;
current_location_mcb->size = numbytes;
}

/* Now, no matter what (well, except for error conditions),
* memory_location has the address of the memory, including
* the mem_control_block
*/

/* Move the pointer past the mem_control_block */
memory_location = memory_location + sizeof(struct mem_control_block);

/* Return the pointer */
return memory_location;
}

input:- map table 
            memory unit
    output:- 0 if falure 
              else address of the location 
    for(every map entry )
     {
        if(current map entry allocatable memory can fit)
           {
              if(map entery size==requird size)
              delete the entry frm the map table
              else 
               adjust the starting address
}
}
}

input:- map table 
            memory unit
    output:- 0 if falure 
              else address of the location 
    for(every map entry )
     {
        if(current map entry allocatable memory can fit)
           {
              if(map entery size==requird size)
              delete the entry frm the map table
              else 
               adjust the starting address
}
}
return(starting address);
}
return 0;

#include <stdio.h>


#define MEMORY_AVAILABLE 1
#define MEMORY_USED 0
#define HEAP_MEMORY 1000


char raw_memory[HEAP_MEMORY];
typedef struct memory_chunk heap_memory;
struct memory_chunk{
heap_memory *next;
int size;
int is_available;
void * memory;
} ;

int heap_size=HEAP_MEMORY;
heap_memory mlist;

int init_memory_mgr(){
heap_size=HEAP_MEMORY;
mlist.next=NULL;
mlist.size=heap_size;
mlist.is_available=MEMORY_AVAILABLE;
mlist.memory=raw_memory;
return 1;
}


void * my_malloc(int size){

if ( size <= 0 ) {
printf("ERROR\n");
return NULL;
}

heap_memory *temp=&mlist;
int alloc_size=size+sizeof(heap_memory);

while(temp) {
if (temp->is_available == MEMORY_AVAILABLE) {
if (temp->size >= alloc_size) {
void * allocated_memory = (heap_memory*)(temp);
printf("\ntemp=0x%x\n",temp);
temp->size=size;
temp->is_available=MEMORY_USED;
temp->memory=(temp)+sizeof(temp->size)+sizeof(temp->is_available);
temp->next = temp->memory+size;
heap_size -= size;

heap_memory * new_memory_ptr = temp->next;
new_memory_ptr->is_available=MEMORY_AVAILABLE;
new_memory_ptr->size=heap_size;
return temp->memory;
}
}
temp=temp->next;
}//while
printf("\nNo Memory Available\n");
return NULL;
}

void print_heap_allocations(){
heap_memory *temp=&mlist;

printf("\n\tSize\tMemory-Ptr");
while(temp){
printf("\n\t%d\t%x ",temp->size,temp->memory);
temp=temp->next;
}
printf("\n");
}


int main() {
init_memory_mgr();
print_heap_allocations();
void * m;
m=my_malloc(10);
printf("\nallocated 10 bytes:0x%x\n",m);
print_heap_allocations();

m=my_malloc(20);
printf("\nallocated 10 bytes:0x%x\n",m);
print_heap_allocations();

m=my_malloc(10);
printf("\nallocated 10 bytes:0x%x\n",m);
print_heap_allocations();
return 1;
}

/**************************************************************
**
**  Auto-generated to help solve interview questions.
**
**  Question : 
    implement your own malloc and free for application x, which should
control the heap memory usage of the application x. 
**  Carreercup Link:
    careercup.com/question?id=3492344

***************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <unistd.h>
#include <sys/mman.h>
#define BSIZE ((10000 * 1024))

struct packet {
    struct packet *next;
    long  psize;
    char pp[0];
};

typedef struct packet* PKT;
PKT FH = NULL;
PKT AH = NULL; 
long rc=0;

int minit()
{
    FH = (PKT) mmap( 0, BSIZE , PROT_READ| PROT_WRITE , MAP_PRIVATE | MAP_ANONYMOUS , -1 , 0);
    if( FH)
    {
        printf(" Starting address %p \n", FH);
        FH->next =  NULL;
        FH->psize = BSIZE - sizeof(struct packet);
    }
    else
    {
        printf(" mmap failed \n");
        exit(1);
    }
}

void *mmalloc(int count)
{
    // find a free node whose size is grater than count + sizeof(struct packet)
    PKT q, p = FH, newfreepacket, nextfreepacket;
    int req =  count + sizeof(struct packet);
    if(count <= 0)
    {
        return NULL;
    }

    rc ++;
    q = p;
    while((p->psize < req) && p->next)
    {
        q = p;
        p = p->next;
    }
    if( p->psize >=  req )
    {
        nextfreepacket = p->next;
        if(p->psize > req)
        {
             // calculate next in chain
            newfreepacket = (PKT) &(p->pp[count]);
            newfreepacket->psize = p->psize - req;
            newfreepacket->next = nextfreepacket;
            // link with previous in chain
            if( p == q )
            {
                FH =  newfreepacket;
            }
        else
        {
            q->next =  newfreepacket;
        }
    }
    else
    {
        // Free list is loosing one node.
        if( p ==  q )
        {
            FH = nextfreepacket;
        }
        else
        {
            q->next = nextfreepacket;
        }
    }
    // Adjust p's size
    p->psize = count;
    // Add p to Allocated list.
    if( AH )
    {
        p->next = AH;
        AH = p;
    }
    else
    {
        AH = p;
    }
    return p->pp;
    }
    else
    {
        printf(" Requested size %d can not be allocated %ld \n", count, rc);
        return NULL;
    }
}
void mdefrag(void)
{
    PKT p, q, next;
    p = FH;
    while(p)
    {
        q = p;
        p = p->next;
        if(p)
        {
            next = (PKT) &(q->pp[q->psize]);
            // can we remove p ?
            if( next == p )
            {
                q->psize +=  p->psize + sizeof(struct packet);
                q->next = p->next;
                // delete the node
                p = q;
            }
        }
    }
}
void mfree(void *r)
{
    PKT p, q;
    // traverse the A list 
    if( r == NULL)
        return;

    if((rc % 1000) == 0)
    mdefrag();

    q = p = AH;
    while(p && (p->pp != r))
    {
        q = p;
        p = p->next;
    }
    if(p)
    {
        // first node
        if( q == p)
        {
            AH =  p->next;
        }
        // rest
        else
        {
            q->next = p->next;
        }
        // Add the node to the F list.
        p->next = FH;
        FH = p;
    }
    else
    {
        printf("Unallocated memory freed  at %p \n", r);
    }
}

int main()
{
  int i, j , c ;
  char* p[100];

  minit();

  // algo goes here.
  for( j = 0 ; j < 5000; j ++ )
  {
    for(i = 0; i < 100; i++)
    {
      c = random();
      c = c % 100;
      p[i] = mmalloc(c);
    }
    for(i = 99; i >= 0; i--)
    {
      mfree(p[i]); 
    }
  }
    printf(" AH : %p \n", AH);
    printf(" FH : %p \n", FH);
    printf(" C  : %ld\n", rc);
  return 0;
}

Google asking questions on malloc???

Someone explain the question

I dont think Google uses malloc/free. They must be using new/delete