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 #include #include #include #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] != '\0'; iN++) { printf("%-10s %4d%8s %4d " , pMgr->nodeTypeM[iN].szNodeTypeNm , pMgr->nodeTypeM[iN].shBeginMetaAttr , " " , pMgr->nodeTypeM[iN].shNodeTotalSize); printf("\t\t%-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("\t\t%-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, '\0', 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("\t!!! Memory not allocated "); printf("\t\tsmAllocate 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("\t\tmmAssoc 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] != '\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, '\0', 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("\t%-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("\t%08lX %-5s %4d " , ULAddr(pAlloc), "Free", shTempSize); pFree = (FreeNode *)pAlloc; printf("\t\t\tNext:%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("\t%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("\t%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("\t%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("\t\tmmMark 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("\t\tmmFollow rc=%d, %s " , pmmResult->rc , pmmResult->szErrorMessage); return; } } } // Collect all the candidate entries as free. mmCollect(pMgr, pmmResult); if (pmmResult->rc != 0) { printf("\t\tmmCollect 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("\t\t\t, %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("\t%-14s %-4s %-9s %-14s ", "Alloc Address", "Size", "Node Type", "Data Address"); printf("\t%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] = '\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] = '\0'; // 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 **************************************************************************/ 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); }