Complete the following Garbage Collection functions in a different c file: void
ID: 3889093 • Letter: C
Question
Complete the following Garbage Collection functions in a different c file:
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);
header file:
#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)
#endifcs3723p1Driver.c
Driver file :
#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;
}
/******************** smInit **************************************
void smInit(StorageManager *pMgr)
Purpose:
Initializes the heap and corresponding attributes in the
storage manager.
Parameters:
O StorageManager *pMgr Provides metadata about the user data and
information for storage management.
Returns:
n/a
Notes:
- Uses malloc to actually allocate memory for the heap.
- Inovkes student's mmInit to initialize the free list and
its initially huge free node.
**************************************************************************/
#if defined(_WIN32)
#define HEAP_SIZE 810
#else
#define HEAP_SIZE 900
#endif
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);
}
/******************** initMetadata **************************************
void initMetadata(StorageManager *pMgr)
Purpose:
Initializes the nodeTypeM and metaAttrM arrays with metadata.
Parameters:
O StorageManager *pMgr Provides metadata about the user data and
information for storage management.
Notes:
**************************************************************************/
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));
}
/******************** printMeta **************************************
void printMeta(StorageManager *pMgr)
Purpose:
Prints metadata about each node type.
Parameters:
I StorageManager *pMgr Provides metadata about the user data and
information for storage management.
Notes:
**************************************************************************/
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);
}
}
}
/******************** processCommands **************************************
void processCommands(StorageManager *pMgr, FILE *pfileCommand)
Purpose:
Reads the Command file to process commands. There are several types of
records (see the program header for more information).
Parameters:
I StorageManager *pMgr Provides metadata about the user data and
information for storage management.
I FILE *pfileCommand command stream input
Notes:
This calls functions inside:
hashAPi
hexDump64
cs3723p1
**************************************************************************/
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
}
/******************** findNodeType **************************************
short findNodeType(StorageManager *pMgr, char szNodeTypeNm[])
Purpose:
Searches the storage manager's nodeTypeM array to find the
specified node type and returns its subscript. If not found
it returns NOT_FOUND.
Parameters:
I StorageManager *pMgr Provides metadata about the user data and
information for storage management.
I char szNodeTypeNm[] Node type to find.
Returns:
Subscript of the node type in the nodeTypeM array.
NOT_FOUND (-1) is it isn't found.
**************************************************************************/
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;
}
/******************** setData **************************************
void setData(StorageManager *pMgr, short shNodeType
, char szInput[], char sbData[])
Purpose:
Uses metadata to set the attributes of user data based on comma-
separated input text.
Parameters:
I StorageManager *pMgr Provides metadata about the user data and
information for storage management.
I short shNodeType Node type of the user data
I char szInput[] String containing the comma separated input text
O char sbData[] Binary data set by this function
Returns:
n/a
Notes:
Assumes that shNodeType is a valid subscript in the nodeTypeM array.
**************************************************************************/
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);
}
}
}
/******************** smDump **************************************
void smDump(StorageManager *pMgr)
Purpose:
Uses hexDump to dump each node in the heap.
Parameters:
I StorageManager *pMgr Provides metadata about the user data and
information for storage management.
Returns:
n/a
Notes:
- The heap begins at pBeginStorage and ends at pEndStorage.
- Uses hexDump64.c's hexDump function.
**************************************************************************/
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");
}
}
/******************** printAll *****************************************
void printAll(StorageManager *pMgr)
Purpose:
Prints all nodes referenced by the hash table which have a pointer
value which isn't NULL.
Parameters:
I StorageManager *pMgr Provides metadata about the user data and
information for storage management.
Notes:
- This uses the hash table C++ interface hashApi to return a
message object (structure in C) that contains the pairs of keys
and values.
**************************************************************************/
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);
}
}
/******************** garbageCollection **************************************
void garbageCollection(StorageManager *pMgr, MMResult *pmmResult)
Purpose:
Executes all subphases of the garbage collection process. This includes
Mark Subphase Walk through all memory from the beginning and mark
all nodes to a cGC of 'C' (candidate). It is easier
to combine adjacent free areas if all nodes are
marked as 'C'.
Follow Subphase From any valid starting point (which we are simulating
with a hash table), follow the nodes based on metadata
and mark each referenceable node as 'U' (in use).
Collection Subphase We will build the free list from the entire memory.
(We are affectively ignoring the old free linked list.)
Walk through all the memory looking for 'C' nodes, combining
adjacent ones into a single free area. Each free area
will be placed on the front of the new free list.
Parameters:
I StorageManager *pMgr Provides metadata about the user data and
information for storage management.
O MMResult *pmmResult Result strcuture for returning errors
Returns:
n/a
Notes:
- This uses the hash table C++ interface hashApi to return a
message object (structure in C) that contains the pairs of keys
and values.
**************************************************************************/
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");
}
/******************** getSimpleToken **************************************
int getSimpleToken(char szInput[], char szDelims[]
, int *piBufferPosition, char szToken[])
Purpose:
Returns the next token in a string. The delimiter(s) for the token is
passed as a parameter. To help positioning for a subsequent call, it
also returns the next position in the buffer.
Parameters:
I char szInput[] input buffer to be parsed
I char szDelims[] delimiters for tokens
I/O int *piBufferPosition Position to begin looking for the next token.
This is also used to return the next
position to look for a token (which will
follow the delimiter).
O char szToken[] Returned token.
Returns:
Functionally:
TRUE - a token is returned
FALSE - no more tokens
iBufferPosition parm - the next position for parsing
szToken parm - the returned token. If not found, it will be an empty string.
Notes:
- If the token is larger than MAX_TOKEN_SIZE, we return a truncated value.
**************************************************************************/
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;
}
/******************** errExit **************************************
void errExit(const char szFmt[], ... )
Purpose:
Prints an error message defined by the printf-like szFmt and the
corresponding arguments to that function. The number of
arguments after szFmt varies dependent on the format codes in
szFmt.
It also exits the program.
Parameters:
I const char szFmt[] This contains the message to be printed
and format codes (just like printf) for
values that we want to print.
I ... A variable-number of additional arguments
which correspond to what is needed
by the format codes in szFmt.
Returns:
Exits the program with a return code of 99.
Notes:
- Prints "ERROR: " followed by the formatted error message specified
in szFmt.
- Requires including <stdarg.h>
**************************************************************************/
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);
}
Explanation / Answer
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
};
int getSimpleToken(char szInput[], char szDelims[]
, int *piBufferPosition, char szToken[])
Purpose:
Returns the next token in a string. The delimiter(s) for the token is
passed as a parameter. To help positioning for a subsequent call, it
also returns the next position in the buffer.
Parameters:
I char szInput[] input buffer to be parsed
I char szDelims[] delimiters for tokens
I/O int *piBufferPosition Position to begin looking for the next token.
This is also used to return the next
position to look for a token (which will
follow the delimiter).
O char szToken[] Returned token.
Returns:
Functionally:
TRUE - a token is returned
FALSE - no more tokens
iBufferPosition parm - the next position for parsing
szToken parm - the returned token. If not found, it will be an empty string.
Notes:
- If the token is larger than MAX_TOKEN_SIZE, we return a truncated value.
**************************************************************************/
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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.