Complete the following GC functions mmInit, mmAllocate, mmCollect, mmMark, mmAss
ID: 3869890 • Letter: C
Question
Complete the following GC functions mmInit, mmAllocate, mmCollect, mmMark, mmAssoc.
header file:
-----------
Driver File
infinite loop. This code has to understand metadata to know where the pointers are located void mmCollect(StorageManager .pMgr. MMResult +pm nResult) This is the third subphase of Garbage Collection. In this phase, you will sequentially traverse the heap, collecting the 'C' nodes, combining adjacent 'C' nodes, and placing the nodes onto a new free list. Each insertion will be to the front of the free list. As you collect free space, print one of the two following messages: printf(eCollecting %O8IXm". ULAddr(Candidate)) printf("cCombining %08IX with %O81Xm" ULAddripPrecedes), ULAddr(pCandidate)) void mmASsoC(Storage Manager pMgr, void pUserData From,char szAttrName sets a user pointer in the specified user data node to a new referenced user data node. Search for the specified attribute name in the meta data for the from node. If not found, set the pmmResult->rc to RC_ASSOC_ATTR NOT_FOUND, provide an error message that contains the attribute name, and return. (Ignore the remaining bullets.) If the specified attribute is not apointer, set the pmmResult->rc to RC_ASSOC_ATTR NOT_PTR provide an error message that contains the attribute name, and return. (Ignore the remaining bullets.) Change the user pointer in the specified user data node to point to the new referenced user data node or NULL (if that was specified Hint: once you know the offset in the user data: void *.ppNode = (void * *)&(plnUseFromxbDatalpAttr.>shOffset!); ppNode-pUserDataTo;Explanation / Answer
Driver.c
-----------------------------------------------------------------------------
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdarg.h>
#include "cs3723p1.h"
#define MAX_TOKEN_SIZE 50 // largest token size for tokenizer
#define MAX_BUFFER_SZ 100 // size of input buffer
// prototypes only used by the driver
void processCommands(StorageManager *pMgr, FILE *pfileCommand);
int getSimpleToken(char szInput[], const char szDelims[]
, int *piBufferPosition, char szToken[]);
void setData(StorageManager *pMgr, short shNodeType, char szInput[], char sbData[]);
void initMetadata(StorageManager *pMgr);
void printMeta(StorageManager *pMgr);
// If on Windows, don't use extern "C" in calling file.
// g++ compiler requires the extern "C".
#if defined(_WIN32) || defined(_WIN64)
extern void *getHash(const char *szKey);
extern void putHash(const char *szKey, void *value);
extern void eraseAll();
extern void getAll(HashMO *pHashMO);
#else
extern "C" void *getHash(const char *szKey);
extern "C" void putHash(const char *szKey, void *value);
extern "C" void eraseAll();
extern "C" void getAll(HashMO *pHashMO);
#endif
int main(int argc, char *argv[])
{
StorageManager storageManager;
// Set up the storage manager and our metadata
smInit(&storageManager);
initMetadata(&storageManager);
// Print the metadata
printMeta(&storageManager);
// Process commands for manipulating user data nodes
processCommands(&storageManager, stdin);
free(storageManager.pBeginStorage);
printf(" ");
return 0;
}
#define HEAP_SIZE 900
void smInit(StorageManager *pMgr)
{
pMgr->pBeginStorage = (char *)malloc(HEAP_SIZE);
if (pMgr->pBeginStorage == NULL)
errExit("%s", "malloc failed to allocate heap ");
pMgr->iHeapSize = HEAP_SIZE;
pMgr->pEndStorage = pMgr->pBeginStorage + HEAP_SIZE;
pMgr->pFreeHead = NULL;
// The minimum node size is the size of a minimum free node.
// This is 12 bytes on 32-bit or 16 bytes on 64 bit
// 2 byte - shNodeSize
// 2 byte - shNodeType
// 1 byte - cGC
// 3 slack bytes
// 4 or 8 byte pointer to the next free node.
pMgr->iMinimumNodeSize = sizeof(FreeNode);
// Invoke student's mmInit to initialize the free list and a huge free node
mmInit(pMgr);
}
void initMetadata(StorageManager *pMgr)
{
#define SHCUST 0 // node type for Customer
#define SHLINE 1 // node type for LineItem
// The following macro gives values to the size and offset attributes
#define SIZE_OFFSET(ptr,attr)
((short)sizeof(attr)), (short)(((char *)&attr) - ((char *) ptr))
struct LineItem
{
char szProductId[10];
int iQtyRequest;
double dCost;
struct LineItem *pNextItem;
} lineItem;
struct Customer
{
char szCustomerId[8];
char szName[16];
struct LineItem *pFirstItem;
struct Customer *pNextCustomer;
double dBalance;
} customer;
char *pCustomer = (char *)&customer;
char *pLineItem = (char *)&lineItem;
int iN = 0;
// nodeTypeM contains metadata about each node type which will be copied to storage manager
NodeType nodeTypeM[MAX_NODE_TYPE] =
{
{ "Customer", 0, sizeof(struct Customer) }
, { "LineItem", 5, sizeof(struct LineItem) }
, { "", 0 } // sentinel
};
// metaAttrM contains metadata about each user data attribute which will be copied
// to storage manager. This is using the excellent initialization capability of C.
MetaAttr metaAttrM[MAX_NODE_ATTR] =
{
{ SHCUST, "customerId", 'S', SIZE_OFFSET(pCustomer, customer.szCustomerId) }
, { SHCUST, "name", 'S', SIZE_OFFSET(pCustomer, customer.szName) }
, { SHCUST, "pFirstItem", 'P', SIZE_OFFSET(pCustomer, customer.pFirstItem) }
, { SHCUST, "pNextCust", 'P', SIZE_OFFSET(pCustomer, customer.pNextCustomer) }
, { SHCUST, "balance", 'D', SIZE_OFFSET(pCustomer, customer.dBalance) }
, { SHLINE, "productId", 'S', SIZE_OFFSET(pLineItem, lineItem.szProductId) }
, { SHLINE, "iQtyReq", 'I', SIZE_OFFSET(pLineItem, lineItem.iQtyRequest) }
, { SHLINE, "dCost", 'D', SIZE_OFFSET(pLineItem, lineItem.dCost) }
, { SHLINE, "pNextItem", 'P', SIZE_OFFSET(pLineItem, lineItem.pNextItem) }
, { -1, "END_OF_ATTR" } // sentinel
};
memcpy(pMgr->nodeTypeM, nodeTypeM, sizeof(nodeTypeM));
memcpy(pMgr->metaAttrM, metaAttrM, sizeof(metaAttrM));
}
void printMeta(StorageManager *pMgr)
{
int iN; // subscript in nodeTypeM array
int iAt; // subscript in metaAttrM array
printf("Metadata ");
printf("%-10s %-12s %8s ", "Node Type", "Beg Attr Sub", "Total Sz");
// Loop for each node type. The end is marked by a name which is an empty string.
for (iN = 0; pMgr->nodeTypeM[iN].szNodeTypeNm[0] != ''; iN++)
{
printf("%-10s %4d%8s %4d "
, pMgr->nodeTypeM[iN].szNodeTypeNm
, pMgr->nodeTypeM[iN].shBeginMetaAttr
, " "
, pMgr->nodeTypeM[iN].shNodeTotalSize);
printf(" %-14s %-4s %-6s %-4s "
, "Attribute Name"
, "Type"
, "Offset"
, "Size");
// The attributes for the node type begin at its shBeginMetaAttr subscript and continue while
// the shNodeType is this node's node type (which is the node type's subscript in
// the nodeTypeM array).
for (iAt = pMgr->nodeTypeM[iN].shBeginMetaAttr; pMgr->metaAttrM[iAt].shNodeType == iN; iAt++)
{
printf(" %-14s %c %6i %4i "
, pMgr->metaAttrM[iAt].szAttrName
, pMgr->metaAttrM[iAt].cDataType
, pMgr->metaAttrM[iAt].shOffset
, pMgr->metaAttrM[iAt].shSizeBytes);
}
}
}
void processCommands(StorageManager *pMgr, FILE *pfileCommand)
{
// variables for command processing
char szInputBuffer[MAX_BUFFER_SZ+1]; // input buffer for a single text line
char szCommand[MAX_TOKEN_SIZE + 1]; // command
int bGotToken; // TRUE if getSimpleToken got a token
int iBufferPosition; // This is used by getSimpleToken to
// track parsing position within input buffer
// variables used for the buffer passed to hexdump
int iBytesPerLine = 40; // number of bytes to be displayed per line
// by hexDump
int iScanfCnt; // number of values returned by sscanf
int iBytesToSend = 0; // number of bytes sent to hexDump
int iLines = 0; // number of lines returned from hexDump
MMResult mmResult = { 0, "" };
// get command data until EOF
while (fgets(szInputBuffer, MAX_BUFFER_SZ, pfileCommand) != NULL)
{
// if the line is just a line feed, ignore it
if (szInputBuffer[0] == ' ')
continue;
// get the command
iBufferPosition = 0; // reset buffer position
bGotToken = getSimpleToken(szInputBuffer, " ", &iBufferPosition, szCommand);
if (! bGotToken)
errExit("Invalid command: %s", szInputBuffer);
// see if the command is a comment
if (szCommand[0]== '*')
{
printf("%s", szInputBuffer);
continue; // it was just a comment
}
memset(&mmResult, '', sizeof(mmResult)); // in case the mm functions didn't
printf(">>> %s", szInputBuffer);
if (strcmp(szCommand, "ALLOC") == 0)
{ // ALLOC key nodeTypeNm val1, val2, ...
char szKey[MAX_KEY_SIZE + 1];
char szNodeTypeNm[MAX_STRING + 1];
char szRemainingInput[MAX_DATA_SZ + 1]; // Used for a node's data values
char sbData[MAX_DATA_SZ];
void *pUserData = NULL;
iScanfCnt = sscanf(&szInputBuffer[iBufferPosition]
, "%10s %10s %100[^ ]"
, szKey
, szNodeTypeNm
, szRemainingInput);
if (iScanfCnt < 3)
errExit("Invalid ALLOC argument; only %d valid values Input is %s"
, iScanfCnt, szInputBuffer);
// get the node type (i.e., subscript in the nodeTypeM array
short shNodeType = findNodeType(pMgr, szNodeTypeNm);
if (shNodeType == NOT_FOUND)
errExit("ALLOC command has invalid node type = '%s'", szNodeTypeNm);
short shSize = pMgr->nodeTypeM[shNodeType].shNodeTotalSize;
// Set up the data attributes in the user data
setData(pMgr, shNodeType, szRemainingInput, sbData);
// Invoke the memory manager allocate function
pUserData = mmAllocate(pMgr, shSize, shNodeType, sbData, &mmResult);
// If it allocated memory, record the key and pointer in the hash table
if (pUserData != NULL)
{ // they gave it memory, confirm that the pointer is a user pointer
InUseNode *pInUse;
if ((char *)pUserData < pMgr->pBeginStorage || (char *)pUserData >= pMgr->pEndStorage)
errExit("mmAllocate returned a pointer outside of heap range");
pInUse = (InUseNode *)((char *)pUserData - NODE_OVERHEAD_SZ);
if (pInUse->cGC != 'U')
errExit("mmAllocate returned a pointer which has a cGC not equal to 'U'");
// Must be ok
putHash(szKey, pUserData); // record where it was placed
}
else
{ // Did not allocate memory
printf(" !!! Memory not allocated ");
printf(" smAllocate rc=%d, %s "
, mmResult.rc
, mmResult.szErrorMessage);
}
}
else if (strcmp(szCommand, "DEREF") == 0)
{ // FREE key
char szKey[MAX_KEY_SIZE + 1];
char szNULL[MAX_STRING + 1] = "";
// get the key from the input
iScanfCnt = sscanf(&szInputBuffer[iBufferPosition]
, "%10s"
, szKey);
// was the key in it?
if (iScanfCnt < 1)
errExit("Invalid DEREF argument; only %d valid values Input is %s"
, iScanfCnt, szInputBuffer);
// Set the reference in the hash table to NULL.
putHash(szKey, NULL);
}
else if (strcmp(szCommand, "ASSOC") == 0)
{ // ASSOC keyFrom attrName keyTo
char szKeyFrom[MAX_KEY_SIZE + 1];
char szKeyTo[MAX_KEY_SIZE + 1];
char szAttrNm[MAX_STRING + 1];
void *pUserFromData = NULL;
void *pUserToData = NULL;
iScanfCnt = sscanf(&szInputBuffer[iBufferPosition]
, "%10s %10s %10s"
, szKeyFrom
, szAttrNm
, szKeyTo);
if (iScanfCnt < 3)
errExit("Invalid ASSOC argument; only %d valid values Input is %s"
, iScanfCnt, szInputBuffer);
// get the user address of the from
pUserFromData = (char *)getHash(szKeyFrom);
if (pUserFromData == NULL)
{
printf("*** getHash for 'from' returned NULL ");
continue;
}
// get the user address of the to
pUserToData = (char *)getHash(szKeyTo);
if (pUserToData == NULL)
{
printf("*** getHash for 'to' returned NULL ");
continue;
}
mmAssoc(pMgr, pUserFromData, szAttrNm, pUserToData, &mmResult);
if (mmResult.rc != 0)
{
printf(" mmAssoc rc=%d, %s "
, mmResult.rc
, mmResult.szErrorMessage);
}
}
else if (strcmp(szCommand, "GCOLL") == 0)
{ // Garbage Collection Process
garbageCollection(pMgr, &mmResult);
}
else if (strcmp(szCommand, "DUMP") == 0)
smDump(pMgr);
else if (strcmp(szCommand, "PRTNODE") == 0)
{ // PRTNODE key
char szKey[MAX_KEY_SIZE + 1];
char *pUserData;
// get the key from the input
iScanfCnt = sscanf(&szInputBuffer[iBufferPosition]
, "%10s"
, szKey);
// was the key in it?
if (iScanfCnt < 1)
errExit("Invalid PRTNODE argument; only %d valid values Input is %s"
, iScanfCnt, szInputBuffer);
// get the address to user data
pUserData = (char *)getHash(szKey);
if (pUserData == NULL)
{
printf("*** getHash returned NULL ");
continue;
}
else
printNode(pMgr, pUserData);
}
else if (strcmp(szCommand, "PRTALL") == 0)
{ // Print all the nodes having a reference in the hash table
printAll(pMgr);
printf(" ");
}
else
errExit("Invalid command: '%s'", szCommand);
}
printf(" "); // good place for a breakpoint
}
short findNodeType(StorageManager *pMgr, char szNodeTypeNm[])
{
int iN;
// Loop for each node type. The end is marked by a name which is an empty string.
for (iN = 0; pMgr->nodeTypeM[iN].szNodeTypeNm[0] != ''; iN++)
{
if (strcmp(pMgr->nodeTypeM[iN].szNodeTypeNm, szNodeTypeNm) == 0)
return iN;
}
return NOT_FOUND;
}
void setData(StorageManager *pMgr, short shNodeType, char szInput[], char sbData[])
{
int iAt; // control variable representing subscript in metaAttrM
char szToken[MAX_STRING]; // token returned by getSimpleToken
int iBufferPos = 0; // current buffer position used by getSimpleToken
MetaAttr *pAttr; // slightly simplifies referencing item in metaAttrM
int iScanfCnt; // returned by sscanf
int iValue; // integer value when attribute is an int
double dValue; // double value when attribute is a double
char *pszMemAtOffset; // pointer into user data if this attribute is a string
int *piMemAtOffset; // pointer into user data if this attribute is an int
void **ppNode; // pointer into user data if this attribute is a pointer
double *pdMemAtOffset; // pointer into user data if this attribute is a double
int iLen; // helps with checking too long of a string value
// zero out the user data
memset(sbData, '', pMgr->nodeTypeM[shNodeType].shNodeTotalSize);
// Loop through each of the user data's attributes. The subscripts start with
// shBeginMetaAttr from nodeTypeM and end when the corresponding metaAttr's node type is
// different.
for (iAt = pMgr->nodeTypeM[shNodeType].shBeginMetaAttr; pMgr->metaAttrM[iAt].shNodeType == shNodeType; iAt++)
{
pAttr = &(pMgr->metaAttrM[iAt]); // slightly simplify the reference in the metaAttrM array
// get the next token from the input
if (!getSimpleToken(szInput, ", ",&iBufferPos, szToken))
return;
// set the data based on the attribute data type
switch (pAttr->cDataType)
{
case 'P': // pointer
// The value in the data must state NULL
if (strcmp(szToken, "NULL")!= 0)
errExit("Invalid ALLOC command argument: '%s'", szToken);
// get the attribute's address based on its offset
ppNode = (void **) &(sbData[pAttr->shOffset]);
*ppNode = NULL; // assign it NULL
break;
case 'S': // char string
// check for too long of a value
iLen = strlen(szToken);
if (iLen > pAttr->shSizeBytes - 1)
errExit("Invalid ALLOC command argument, value too long: '%s'", szToken);
// get the attribute's address based on its offset
pszMemAtOffset = (char *) &(sbData[pAttr->shOffset]);
strcpy(pszMemAtOffset, szToken);
break;
case 'I': // int
// Convert the token to an int
iScanfCnt = sscanf(szToken, "%d", &iValue);
if (iScanfCnt < 1)
errExit("Invalid ALLOC command argument, not an int: '%s'", szToken);
// get the attribute's address based on its offset
piMemAtOffset = (int *) &(sbData[pAttr->shOffset]);
*piMemAtOffset = iValue;
break;
case 'D': // double
// Convert the token to a double
iScanfCnt = sscanf(szToken, "%lf", &dValue);
if (iScanfCnt < 1)
errExit("Invalid ALLOC command argument, not an double: '%s'", szToken);
// get the attribute's address based on its offset
pdMemAtOffset = (double *)&(sbData[pAttr->shOffset]);
*pdMemAtOffset = dValue;
break;
default:
errExit("Invalid data type '%c' for attribute named '%s'"
, pAttr->cDataType
, pAttr->szAttrName);
}
}
}
void smDump(StorageManager *pMgr)
{
int iBytesToSend;
int iBytesPerLine = 20;
char *pCh;
short shTempSize;
InUseNode *pAlloc;
FreeNode *pFree;
// Print each item from the beginning of the heap to the end
printf(" %-8s %-5s %4s %8s ", "Address", "Mem", "Size", "NodeType");
for (pCh = pMgr->pBeginStorage; pCh < pMgr->pEndStorage; pCh += shTempSize)
{
pAlloc = (InUseNode *)pCh;
shTempSize = pAlloc->shNodeSize;
// Change the output based on the cGC type
switch (pAlloc->cGC)
{
case 'F':
// It is a free item
printf(" %08lX %-5s %4d "
, ULAddr(pAlloc), "Free", shTempSize);
pFree = (FreeNode *)pAlloc;
printf(" Next:%08lX", ULAddr(pFree->pFreeNext));
// check for bad pFreeNext pointer
if ( pFree->pFreeNext != NULL &&
((char *)pFree->pFreeNext) < pMgr->pBeginStorage
|| ((char *) pFree->pFreeNext) > pMgr->pEndStorage )
printf(" *** next pointer is outside of heap ");
else
printf(" ");
break;
case 'U':
// It is in use
printf(" %08lX %-5s %4d %d "
, ULAddr(pAlloc), "InUse", shTempSize, pAlloc->shNodeType);
iBytesToSend = shTempSize - NODE_OVERHEAD_SZ;
if (iBytesToSend > HEAP_SIZE)
iBytesToSend = HEAP_SIZE; // checking bad node size
hexDump(pCh + NODE_OVERHEAD_SZ, iBytesToSend, iBytesPerLine);
break;
case 'C':
// It is a candidate
printf(" %08lX %-5s %4d "
, ULAddr(pAlloc), "Cand", shTempSize);
iBytesToSend = shTempSize - NODE_OVERHEAD_SZ;
if (iBytesToSend > HEAP_SIZE)
iBytesToSend = HEAP_SIZE; // checking bad node size
hexDump(pCh + NODE_OVERHEAD_SZ, iBytesToSend, iBytesPerLine);
break;
default:
// It is unknown
printf(" %08lX %-5s %4d *** unknown cGC "
, ULAddr(pAlloc), "Unk", shTempSize);
iBytesToSend = shTempSize - NODE_OVERHEAD_SZ;
if (iBytesToSend > HEAP_SIZE)
iBytesToSend = HEAP_SIZE; // checking bad node size
hexDump(pCh + NODE_OVERHEAD_SZ, iBytesToSend, iBytesPerLine);
}
if (shTempSize <= 0)
errExit("shNodeSize is zero or negative");
}
}
void printAll(StorageManager *pMgr)
{
int i;
void *pUserData;
HashMO hashMO;
// get the hash table entries as an array
getAll(&hashMO);
// Iterate through the entire hash table
for (i = 0; i < hashMO.iNumEntries; i += 1)
{
pUserData = hashMO.entryM[i].pUserData;
// Print the node if the hash value is not NULL
if (pUserData != NULL)
printNode(pMgr, pUserData);
}
}
void garbageCollection(StorageManager *pMgr, MMResult *pmmResult)
{
int i;
void *pUserData;
HashMO hashMO;
// mark all nodes as candidates ('C') for collection
mmMark(pMgr, pmmResult);
if (pmmResult->rc != 0)
{
printf(" mmMark rc=%d, %s "
, pmmResult->rc
, pmmResult->szErrorMessage);
return;
}
// To get the references, we need the contents of the hash table.
// In most GC solutions, we would get the entries from either the
// runtime memory stack or (in the case of Python) a hash table.
getAll(&hashMO);
// go through the array of hash entries, calling mmFollow
for (i = 0; i < hashMO.iNumEntries; i += 1)
{
pUserData = hashMO.entryM[i].pUserData;
if (pUserData != NULL)
{ // mark any reachable nodes as in use ('U')
mmFollow(pMgr, pUserData, pmmResult);
if (pmmResult->rc != 0)
{
printf(" mmFollow rc=%d, %s "
, pmmResult->rc
, pmmResult->szErrorMessage);
return;
}
}
}
// Collect all the candidate entries as free.
mmCollect(pMgr, pmmResult);
if (pmmResult->rc != 0)
{
printf(" mmCollect rc=%d, %s "
, pmmResult->rc
, pmmResult->szErrorMessage);
return;
}
}
/*
** This Hex Dump can be used instead of calling the real
** hexDump from smDump when using Visual Studio. Rename this to hexDump.
** Please remember to remove it when you run your code on a fox server.
*/
int dumbHexDump(char *sbBuffer, int iBufferLength, int iBytesPerLine)
{
printf(" , %s", sbBuffer); // print the data
return 1; // arbitrary value and meaningless in this case
}
/*
** This is the dumb version of print node which can be used instead
** of calling the real printnode. Rename this to printNode.
** Please remember to remove it when you run your code on a fox server.
*/
void dumbPrintNode(StorageManager *pMgr, void *pUserData)
{
InUseNode *pAlloc = (InUseNode *)(((char *)pUserData) - 2 * sizeof(short) - 1);
printf(" %-14s %-4s %-9s %-14s ", "Alloc Address", "Size", "Node Type", "Data Address");
printf(" %p %4i %6i %08lX ", pAlloc
, pAlloc->shNodeSize, pAlloc->shNodeType, ULAddr(pUserData));
printf("dumb print");
}
int getSimpleToken(char szInput[], const char szDelims[]
, int *piBufferPosition, char szToken[])
{
int iDelimPos; // found position of delim
int iCopy; // number of characters to copy
// check for past the end of the string
if (*piBufferPosition >= (int) strlen(szInput))
{
szToken[0] = ''; // mark it empty
return FALSE; // no more tokens
}
// get the position of the first delim, relative to the iBufferPosition
iDelimPos = strcspn(&szInput[*piBufferPosition], szDelims);
// see if we have more characters than target token, if so, trunc
if (iDelimPos > MAX_TOKEN_SIZE)
iCopy = MAX_TOKEN_SIZE; // truncated size
else
iCopy = iDelimPos;
// copy the token into the target token variable
memcpy(szToken, &szInput[*piBufferPosition], iCopy);
szToken[iCopy] = ''; // null terminate
// advance the position
*piBufferPosition += iDelimPos + 1;
return TRUE;
}
void errExit(const char szFmt[], ... )
{
va_list args; // This is the standard C variable argument list type
va_start(args, szFmt); // This tells the compiler where the variable arguments
// begins. They begin after szFmt.
printf("ERROR: ");
vprintf(szFmt, args); // vprintf receives a printf format string and a
// va_list argument
va_end(args); // let the C environment know we are finished with the
// va_list argument
printf(" ");
exit(99);
}
----------------------------------------------------------------------------------------------------------
cs3723p1.c
------------------------------------------------------------
#include "cs3723p1.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//ADD PMM RESULT TO EVERYTHING
void mmInit(StorageManager *pMgr){
pMgr->pFreeHead = (FreeNode *)pMgr->pBeginStorage;
memset(pMgr->pBeginStorage,'',pMgr->iHeapSize);
pMgr->pFreeHead->cGC = 'F';
pMgr->pFreeHead->shNodeSize = pMgr->iHeapSize;
pMgr->pFreeHead->pFreeNext = (FreeNode *)0;
}
void * mmAllocate(StorageManager *pMgr, short shDataSize, short shNodeType, char sbData[], MMResult *pmmResult)
{
char *errMsg; //temp pointer for error message
FreeNode *pPrev = (FreeNode *)0; //previous free node in free list
FreeNode *pCurr = pMgr->pFreeHead; //the current free node in the list
InUseNode *pNewNode = (InUseNode *)0; //enhance readability
short shDiff; //stores leftover space after allocation
int totalSize; //stores pNewNodes size
while(pCurr && (char *)pCurr < pMgr->pEndStorage) //traces through free node list
{
if(pCurr->shNodeSize >= (shDataSize + NODE_OVERHEAD_SZ)) //find a node large enough to fit another one
{
shDiff = pCurr->shNodeSize - (shDataSize + NODE_OVERHEAD_SZ); //check if there's enough space for an in use node + free node
if(shDiff >= pMgr->iMinimumNodeSize)
{
if(!pPrev)
pMgr->pFreeHead = pCurr->pFreeNext; //free node is in beginning of list
else
pPrev->pFreeNext = pCurr->pFreeNext; //free node is somewhere else in the list
totalSize = shDataSize + NODE_OVERHEAD_SZ;
//totalSize = shDataSize + iMinumumNodeSize;
pNewNode = (InUseNode *)pCurr;
pNewNode->cGC = 'U'; //user input mark node as in use
pNewNode->shNodeType = shNodeType;
pNewNode->shNodeSize = totalSize;
memcpy((void *)pNewNode->sbData, (void *)sbData, shDataSize);//allocate user node
//if enough space is left over for a free node make a new free node
pCurr = (FreeNode *)((char *)pCurr + totalSize);
pCurr->cGC = 'F'; //set current to Free
pCurr->shNodeSize = shDiff;
pCurr->pFreeNext = pMgr->pFreeHead;
pMgr->pFreeHead = pCurr; //insert free node at beginning of free list
} //end if
else{
if(!pPrev) //beginning of free list
pMgr->pFreeHead = pCurr->pFreeNext;
else
pPrev->pFreeNext = pCurr->pFreeNext;
pNewNode = (InUseNode *)pCurr;
pNewNode->cGC = 'U';
pNewNode->shNodeType = shNodeType;
memcpy((void *)pNewNode->sbData, (void *)sbData, shDataSize);
}//end else
return pNewNode->sbData;
}//end if large enough node
else
{
pPrev = pCurr;
pCurr = pCurr->pFreeNext;
}
}//end while
pmmResult->rc = RC_NOT_AVAIL;
errMsg = "Free node not found";
memcpy((void*)pmmResult->szErrorMessage, errMsg, strlen(errMsg)+1);
return (void *)0;
} //end mmAllocate
void mmMark(StorageManager *pMgr, MMResult *pmmResult){
char * cursor = NULL;
short shTempSize = 0;
for(cursor = pMgr->pBeginStorage;cursor < pMgr->pEndStorage;cursor += shTempSize)//increments the cursor by 1 byte
{
shTempSize = ((InUseNode *)cursor)->shNodeSize;
((InUseNode *)cursor)->cGC = 'C';
}
}
void mmFollow(StorageManager *pMgr, void *pUserData, MMResult *pmmResult){
if(!pUserData)
{
return;
}
InUseNode * pCurr;
int iAttr;
short shNodeType;
MetaAttr *pAttr;
void **pp;
pCurr = (InUseNode *)((char *)pUserData - NODE_OVERHEAD_SZ);
shNodeType = pCurr->shNodeType;
switch(pCurr->cGC)
{
case 'U':
return;
//break;
case 'C':
pCurr->cGC = 'U';
for(iAttr = pMgr->nodeTypeM[shNodeType].shBeginMetaAttr; pMgr->metaAttrM[iAttr].shNodeType == shNodeType; iAttr++)
{
pAttr = &(pMgr->metaAttrM[iAttr]);
if(pAttr->cDataType == 'P')
pp = (void **)&pCurr->sbData[pAttr->shOffset];
mmFollow(pMgr, *pp, pmmResult);
/*{
pp = (void **)&pCurr->sbData[]
}*/
}
break;
}
}
void mmCollect(StorageManager *pMgr, MMResult *pmmResult){
//sets free nodes to F from C
char * pCur;
char * pNext;
char * pPrev = (char *)0;
FreeNode * pNewNode;
short shTempSize;
int iTotalSize;
pMgr->pFreeHead = (FreeNode *)0;
pCur = pMgr->pBeginStorage;
while(pCur < pMgr->pEndStorage)
{
shTempSize = ((FreeNode *)pCur)->shNodeSize;
pNext = pCur + shTempSize;
if(((FreeNode *)pCur)->cGC == 'C')
{
if(pNext < pMgr->pEndStorage && ((FreeNode *)pNext)->cGC == 'C')
{
printf(" Combining %08lX with %08lX ", ULAddr(pCur), ULAddr(pNext));
pNewNode = (FreeNode *)pCur;
iTotalSize = ((FreeNode *)pCur)->shNodeSize + ((FreeNode *)pNext)->shNodeSize;
pNewNode->shNodeSize = iTotalSize;
}
else
{
printf(" Collecting %08lX ", ULAddr(pCur));
pNewNode = (FreeNode *)pCur;
pNewNode->cGC = 'F';
pNewNode->pFreeNext = (FreeNode *)pPrev;
pPrev = pCur;
pCur += shTempSize;
}
}
else
{
pCur += shTempSize;
}
}
pMgr->pFreeHead = (FreeNode *)pPrev;
}
/*void mmCollect(StorageManager *pMgr, MMResult *pmmResult)
{
char *pCurr;
char *pTrace;
char *pPrev = (char *)0;
FreeNode *pNewNode;
short shTempSize;
int totalSize;
pMgr->pFreeHead = (FreeNode *)0;
pCurr = pMgr->pBeginStorage;
while(pCurr < pMgr->pEndStorage)
{
shTempSize = ((FreeNode *)pCurr)->shNodeSize;
pTrace = pCurr + shTempSize;
if(((FreeNode *)pCurr)->cGC == 'C')
{
if(pTrace < pMgr->pEndStorage && ((FreeNode *)pTrace)->cGC == 'C')
{
printf(" Combining %08lX with %08lX ", ULAddr(pCurr), ULAddr(pTrace));
pNewNode = (FreeNode *)pCurr;
totalSize = ((FreeNode *)pCurr)->shNodeSize + ((FreeNode *)pTrace)->shNodeSize;
pNewNode->shNodeSize = totalSize;
}
else
{
printf(" Collecting %08lX ", ULAddr(pCurr));
pNewNode = (FreeNode *)pCurr;
pNewNode->cGC = 'F';
pNewNode->pFreeNext = (FreeNode *)pPrev;
pPrev = pCurr;
pCurr += shTempSize;
}
}
else
{
pCurr += shTempSize;
}
}
pMgr->pFreeHead = (FreeNode *)pPrev;
}*/
void mmAssoc(StorageManager *pMgr, void *pUserDataFrom, char szAttrName[], void *pUserDataTo, MMResult *pmmResult){
char *pUserNode;
MetaAttr *pAttr;
char *errMsg;
short shNodeType;
int iAt;
void **ppNode;
pUserNode = (char *)pUserDataFrom - NODE_OVERHEAD_SZ;
shNodeType = ((InUseNode *)pUserNode)->shNodeType;
for(iAt = pMgr->nodeTypeM[shNodeType].shBeginMetaAttr; iAt < MAX_NODE_ATTR && pMgr->metaAttrM[iAt].shNodeType == shNodeType; iAt++)
{
pAttr = &(pMgr->metaAttrM[iAt]);
if(strcmp(pAttr->szAttrName, szAttrName) == 0)
{
if(pAttr->cDataType == 'P')
{
ppNode = (void **)&(((InUseNode *)pUserNode)->sbData[pAttr->shOffset]);
*ppNode = pUserDataTo;
return;
}
else
{
pmmResult->rc = RC_ASSOC_ATTR_NOT_PTR;
sscanf(errMsg, "Attribute not a pointer: %s", szAttrName);
memcpy((void *)pmmResult->szErrorMessage, errMsg, strlen(errMsg)+1);
return;
}
}
}
pmmResult->rc = RC_ASSOC_ATTR_NOT_FOUND;
sscanf(errMsg, "Attribute not found: %s", szAttrName);
memcpy((void *)pmmResult->szErrorMessage, errMsg, strlen(errMsg)+1);
}
----------------------------------------------------------------------------------------------------------
cs3723p1.h
-------------------------------------------------------------------
#define TRUE 1
#define FALSE 0
#define MAX_KEY_SIZE 10 // Maximum size of a key for Hash Table
#define MAX_MESSAGE_SIZE 100 // Maximum message size for smResult
#define MAX_STRING 30 // Maximum size of strings like
// node type names, attribute names
#define MAX_NODE_TYPE 5 // Maximum number of node types
#define MAX_NODE_ATTR 50 // Maximum number of combined node attr
#define MAX_DATA_SZ 500 // Maximum size of sbData
#define ERROR_PROCESSING 3 // error during processing - exit value
#define MAX_HASH_ENTRIES 100 // Maximum number of hash entries
#define NOT_FOUND -1 // Could not find name in metadata
// Errors returned in the rc of MMResult
#define RC_NOT_AVAIL 901 // There isn't any free memory to handle alloc request
#define RC_INVALID_ADDR 903 // Invalid address which isn't within heap
#define RC_ASSOC_ATTR_NOT_PTR 801 // Attribute name for ASSOC not a pointer attribute
#define RC_ASSOC_ATTR_NOT_FOUND 802 // Attribute name for ASSOC not found for the from node
// MetaAttr describes an attribute within a node type
typedef struct MetaAttr
{
short shNodeType; // Type of node
char szAttrName[MAX_STRING+1]; // Name of the attribute
char cDataType; // Data type: S - char string, P -Ptr, D - double, I - int
short shSizeBytes; // size in bytes including zero byte for strings
short shOffset;
}MetaAttr;
// NodeType describes one type of node
typedef struct NodeType
{
char szNodeTypeNm[MAX_STRING+1];
short shBeginMetaAttr; // Subscript in metaAttrM of first attribute for
// this node type.
short shNodeTotalSize;
}NodeType;
// InUseNode represents an allocated node. The actual size of an allocated item may be much
// larger.
typedef struct InUseNode
{
short shNodeSize; // total size of the allocated item.
short shNodeType; // Node Type subscript.
char cGC; // Garbage Collection status byte has one of these
// values: F - free, C - candidate to free,
// U - in use
char sbData[MAX_DATA_SZ]; // This is the user's data in the node. It might
// be bigger than MAX_STRING.
} InUseNode;
// Define the size of overhead in an InUseNode
#define NODE_OVERHEAD_SZ (sizeof(short)+sizeof(short)+1)
// FreeNode represent a free node. Note that an actual free node
// will occupt more than the size of this structure.
typedef struct FreeNode
{
short shNodeSize; // Total size of this free node.
short shNodeType; // Not used
char cGC; // Garbage Collection status byte has one of these
// values: F - free, C - candidate to free,
// U - in use
struct FreeNode *pFreeNext; // Points to next free node
} FreeNode;
// StorageManager is the primary structure used by this program.
typedef struct
{
int iHeapSize; // Total size of the heap memory being managed
int iMinimumNodeSize; // The minimum size of any node.
char *pBeginStorage; // Beginning of the heap memory being managed
char *pEndStorage; // End address immediately after the heap memory
FreeNode *pFreeHead; // Head of the free list
NodeType nodeTypeM[MAX_NODE_TYPE]; // array of node types
MetaAttr metaAttrM[MAX_NODE_ATTR]; // array of attribute meta data
} StorageManager;
// This is returned by many of the mm functions via the parameter list.
typedef struct
{
int rc; // Return Code is 0 if it is normal. Otheriwise,
// it is not zero. See the defined constants.
char szErrorMessage[MAX_MESSAGE_SIZE + 1]; // If a problem is encountered, this should
// explain the error.
} MMResult;
// This is for returning one Hash Table entry pair
typedef struct
{
char szKey[MAX_KEY_SIZE + 1]; // the hash key
void *pUserData; // the entry contains just a ptr
} HashEntryPair;
// This is used to return the entire contents of the Hash Table
typedef struct
{
int iNumEntries;
HashEntryPair entryM[MAX_HASH_ENTRIES];
} HashMO;
// student functions
void * mmAllocate(StorageManager *pMgr
, short shDataSize, short shNodeType, char sbData[], MMResult *pmmResult);
void mmInit(StorageManager *pMgr);
void mmMark(StorageManager *pMgr, MMResult *pmmResult);
void mmFollow(StorageManager *pMgr, void *pUserData, MMResult *pmmResult);
void mmCollect(StorageManager *pMgr, MMResult *pmmResult);
void mmAssoc(StorageManager *pMgr
, void *pUserDataFrom, char szAttrName[], void *pUserDataTo, MMResult *pmmResult);
// Driver functions
void smPrintMeta(StorageManager *pMgr);
void smPrintFree(StorageManager *pMgr);
short findNodeType(StorageManager *pMgr, char szNodeTypeNm[]);
void smInit(StorageManager *pMgr);
void smDump(StorageManager *pMgr);
void garbageCollection(StorageManager *pMgr, MMResult *pmmResult);
void printAll(StorageManager *pMgr);
void errExit(const char szFmt[], ...);
// Larry provided .o versions of these functions.
// If you are running your code on Microsoft, you must use
// the dummy versions
void printNode(StorageManager *pMgr, void *pUserData);
int hexDump(char *psbBuffer, int iBufferLength, int iBytesPerLine);
// Simple macro for converting addresses to unsigned long
#if defined(_WIN32)
#define ULAddr(addr) ((unsigned long) addr)
#else
#define ULAddr(addr) (((unsigned long) addr)&0x00000000FFFFFFFF)
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.