Question

The object manager's interface is given by the file ObjectManager.h and the implementation will be in the file ObjectManager.c. Your task is to implement the functions required for the object manager. This includes all the functions listed in ObjectManager.h.

#ifndef _OBJECT_MANAGER_H
#define _OBJECT_MANAGER_H

#ifndef MEMORY_SIZE
#define MEMORY_SIZE 1024*512
#endif

#define NULL_REF 0

typedef unsigned long Ref;


// This function trys to allocate a block of given size from our buffer.
// It will fire the garbage collector as required.
// We always assume that an insert always creates a new object...
// On success it returns the reference number for the block of memory allocated for the object.
// On failure it returns NULL_REF (0)
Ref insertObject( const int size );

// returns a pointer to the object being requested given by the reference id
void *retrieveObject( const Ref ref );

// update our index to indicate that we have another reference to the given object
void addReference( const Ref ref );

// update our index to indicate that a reference is gone
void dropReference( const Ref ref );

// initialize the object manager
void initPool();

// clean up the object manager (before exiting)
void destroyPool();

// This function traverses the index and prints the info in each entry corresponding to a block of allocated memory.
// You should print the block's reference id, it's starting address, and it's size (in bytes).
void dumpPool();

#endif

Answer 1

main.c

#include <stdio.h>
#include "ObjectManager.h"

int main(int argc, char *argv[])
{
    char *ptr;
    int i;
    Ref id1, id2, id3;
    initPool();
  
    id1 = insertObject(1020);
    ptr = (char*)retrieveObject(id1);
    for (i = 0; i < 1020; i++)
        ptr[i] = (char)(i%26 + 'A');
  
    id2 = insertObject(4);
    ptr = (char*)retrieveObject(id2);
    for (i = 0; i < 4; i++)
        ptr[i] = (char)(i%26 + 'H');
  
    dropReference(id2);
  
    id3 = insertObject(3);
    dropReference(id3);
    id3 = insertObject(12);
    ptr = (char*)retrieveObject(id3);
    for (i = 0; i < 12; i++)
        ptr[i] = (char)(i%26 + 'O');
  
    ptr = (char*)retrieveObject(id1);
    for (i = 0; i < 30; i++)
        fprintf(stderr,"%c",ptr[i]);
    fprintf(stderr,"\n");
  
    dumpPool();
    dumpPool();
    destroyPool();
    fprintf(stderr,"---\n");
    return 0;
}

ObjectManager.h

#ifndef _OBJECT_MANAGER_H
#define _OBJECT_MANAGER_H

// The number of bytes of memory we have access to -- put here so everyone's consistent.
#ifndef MEMORY_SIZE
#define MEMORY_SIZE 1024*512
#endif

#define NULL_REF 0

typedef unsigned long Ref;

Ref insertObject( const int size );

// returns a pointer to the object being requested given by the reference id
void *retrieveObject( const Ref ref );

// update our index to indicate that we have another reference to the given object
void addReference( const Ref ref );

// update our index to indicate that a reference is gone
void dropReference( const Ref ref );

// initialize the object manager
void initPool();

// clean up the object manager (before exiting)
void destroyPool();

// This function traverses the index and prints the info in each entry corresponding to a block of allocated memory.
// You should print the block's reference id, it's starting address, and it's size (in bytes).
void dumpPool();

// Mark and Sweep Defragmenting garbage collector
static unsigned long compact();
#endif

ObjectManager.c

#include "ObjectManager.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

typedef struct Index index_item;

struct Index
{
    Ref ID;       // number of the object in pool
    void *start; // pointer to the object
    int size;     // size of object in bytes
    unsigned int refCount;   // number of references currently in use
    index_item *next; // pointer to the next index_item, NULL if the last
};

#define poolSize 1024

//-------------------------------------------------------------------------------------
// FILE-SCOPE VARIABLES
//-------------------------------------------------------------------------------------

// pools of objects in the heap
void *pool[2] = {NULL, NULL};
int active_pool = 0;

// pointer to the first index_item
index_item *top = NULL;
index_item *last = NULL;

// number of currently created objects
int objectCount = 0;

// pointer to the beginning of the next unused address
void *freePtr = NULL;

//-----------------------------------------------------------------------------
// IMPLEMENTATION
//-----------------------------------------------------------------------------

index_item *createIndexItem (const int size)
{
    index_item *newindex_item = malloc (sizeof (index_item));
  
    assert (newindex_item != NULL);

    if (newindex_item)
    {
        newindex_item->ID = ++objectCount;
        newindex_item->refCount = 1;
        newindex_item->size = size;
        newindex_item->next = NULL;
    }
    return newindex_item;
}

// search for given number, return pointer to index_item if found or NULL otherwise
index_item *searchIndex (const Ref ref)
{
    index_item *ind = top;
    while ( (ind) && (ind->ID != ref) )
        ind = ind->next;
    return ind;
}

void removeIndexItem (const Ref ref)
{
    index_item *ind = top;
    index_item *prev = top;
    while ( (ind) && (ind->ID != ref) )
    {
        prev = ind;
        ind = ind->next;
    }
    prev->next = ind->next;
    free(ind);
}

Ref insertObject (const int size)
{
    Ref result = NULL_REF;
    index_item *newindex_item = createIndexItem (size);
  
    unsigned long memAvailable = pool[active_pool] + poolSize - freePtr;
  
    // if not enough memory, try to GC the pool and check again
    if ( (memAvailable < size) && (memAvailable + compact() < size) )
        return NULL_REF;
    else if (newindex_item)
    {
        if (!top)
            top = newindex_item;
        else
            last->next = newindex_item;
        last = newindex_item;
        newindex_item->start = freePtr;
        freePtr += size*sizeof(char);
        result = newindex_item->ID;
    }
  
//    assert ( ((result == true) && (newindex_item != NULL)) || (result == false && newindex_item == NULL) );
//    assert (search(item));
  
    return result;
}

void *retrieveObject (const Ref ref)
{
    void *result = NULL;
    index_item *ind = searchIndex (ref);
  
    if (ind)
        result = ind->start;
    return result;
}

void addReference (const Ref ref)
{
    index_item *ind = searchIndex (ref);
    if (ind)
        ind->refCount++;
}

void dropReference (const Ref ref)
{
    index_item *ind = searchIndex (ref);
    if (ind && (ind->refCount > 0))
        ind->refCount--;
}

void initPool()
{
    pool[0] = malloc(sizeof(char)*poolSize);
    pool[1] = malloc(sizeof(char)*poolSize);
    freePtr = pool[0];
}

void destroyPool()
{
    if (top)
    {
        index_item *temp = NULL;
      
        while (top != NULL)
        {
            temp = top;
            top = top->next;
            free (temp);
            objectCount--;
        }
        top = NULL;
    }
    free (pool[0]);
    free (pool[1]);
    assert (objectCount == 0);
}

void dumpPool()
{
    index_item *ind = top;
    unsigned long offset = 0;
  
    printf ("\n==================================");
    printf ("\n|         Pool information:       |");
    printf ("\n==================================\n");
    while (ind)
    {
        assert ( pool[active_pool] + offset == ind->start );
        offset += ind->size;
        printf ("\nID:    %lu\nStart: %#011x\nSize: %d\n", ind->ID, (unsigned)ind->start, ind->size);
        ind = ind->next;
    }
}

static unsigned long compact()
{
    unsigned long memFreed = 0;
    index_item *ind = top;
    freePtr = pool[!active_pool];
    while (ind)
    {
        if (ind->refCount)
        {
            memcpy(freePtr, ind->start, ind->size);
            ind->start = freePtr;
            freePtr += ind->size;
        }
        else
        {
            memFreed += ind->size;
            removeIndexItem(ind->ID);
            objectCount--;
        }
        ind = ind->next;
    }
    active_pool = !active_pool;   //toggle
    return memFreed;
}