You are to implement a simple object manager. An object manager is another form

ID: 3576025 • Letter: Y

Question

You are to implement a simple object manager. An object manager is another form of table, but we now store generic objects in a managed buffer (the internal implementation of a table varies based on need). Using a buffer means that we must directly manage the memory and references to objects. This means that our object manager must implement reference counting and a garbage collector, so that we properly handle creation and deletion of objects. 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, along with any (private) static functions that will be useful. You will also need to define appropriate data types and data structures for keeping track of the objects that have been allocated. You are NOT allow to change the prototypes of the functions that are provided to you in ObjectManager.h. To summarize, the functionalities you have to implement are:

initPool() - Initialize the object manager upon starting.

destroyPool() - Clean up the object manager upon quitting.

insertObject(size) - request a block of memory of given size from the object manager.

retrieveObject(id) - retrieve the address of an object, identified by the reference id.

addReference(id) - increment reference count for the object with reference id.

dropReference(id) - decrement reference count for the object with reference id.

compact() - initiate garbage collection (see below).

dumpPool() - print (to stdout) info about each object that is currently allocated including its id, start address, size and reference count.

Explanation / Answer

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," ");

    dumpPool();
    dumpPool();
    destroyPool();
    fprintf(stderr,"--- ");
    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 (" ==================================");
    printf (" |         Pool information:       |");
    printf (" ================================== ");
    while (ind)
    {
        assert ( pool[active_pool] + offset == ind->start );
        offset += ind->size;
        printf (" ID:    %lu Start: %#011x Size: %d ", 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;
}

Navigate

You are to implement a dynamic single Linked List structure. This List will be b

You are to implement a simple object manager. You will also need to define appro

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

You are to implement a simple object manager. An object manager is another form

Question

Explanation / Answer

Related Questions

Navigate