/* ** debug.c */ #include #include #include #include "debug.h" /* ** Fatal (FATAL): Display an error message and terminate the program. ** If you are debugging, make sure you compile with WITHOUT ** the constant NDEBUG defined. Doing so will cause and "assert(false)" statement ** to be inserted before the program is terminated by calling "exit(1)". This allows ** the debugger to catch your program before it exits, allowing you to debug the problem. ** If NDEBUG is defined, the program will simply terminate when this function is called ** (i.e., the program will terminate before the debugger has a chance to catch the ** error). ** ** IMPORTANT NOTE: You should not call this function directly. Use the ** macro FATAL instead, because FATAL fills in the 'file' and 'line' parameters for you. */ void Fatal( const char *message, const char *file, const int line ) { fprintf( stderr, "[%s:%d] Error: %s\n", file, line, message ); #ifndef NDEBUG assert( FALSE ); #endif exit( 1 ); } /* ** debugprintf: empty function to allow removal of DEBUGPRINTF statements when debugging ** is turned off by defining the constant NDEBUG. ** ** Do not call this function directly. Use the macro DEBUGPRINTF instead. */ void debugprintf( const char *format, ... ) {} /* ** MEMORY_BLOCK_HEADER: structure used by Malloc (MALLOC) and Free (FREE) to facilitate ** memory tracking and reporting. */ #define ALIGN_PADDING 2 typedef struct _memoryBlockHeader { struct _memoryBlockHeader *next; /* pointer to next memory block */ struct _memoryBlockHeader *last; /* pointer to previous memory block */ const char *file; /* pointer to constant string containing the name of the source file in which the block was allocated */ int line; /* line number in the source file where the block was allcoated */ int size; /* size of the user portion of the block, in bytes */ double align[ALIGN_PADDING]; /* field to force correct alignement of the block and to provide padding between this header and the user portion of the memory block */ } MEMORY_BLOCK_HEADER; /* ** memoryBlockList: list of MEMORY_BLOCK_HEADER structures for all blocks of memory ** currently allocated by Malloc. */ static MEMORY_BLOCK_HEADER memoryBlockList = { NULL, NULL, __FILE__, __LINE__, 0 }; /* ** Total number of memory blocks currently allocated. */ static int memoryBlockCount = 0; /* ** Total number of bytes of memory currently allocated. */ static int memoryTotalUsage = 0; /* ** TRUE if memory tracking and reporting is enabled, FALSE otherwise. */ static int memoryTrackingEnabled = FALSE; /* ** Malloc (MALLOC): Allocate and return a pointer to a block of 'size' bytes of memory. If the ** allocation fails (due to an out of memory condition), the program is terminated. If memory ** tracking and reporting is enabled (by calling EnableMemoryTracking before any calls ** to Malloc), a list of allocated memory blocks will be maintained. If you fail to ** release allocated memory blocks before your program terminates, you will receive ** an error message saying 'Memory leaks detected' when your program exits, followed by a list ** of the allocated blocks, their memory address, their size in bytes, and the location in the ** source code where they were allocated (i.e., the file name and line number). You can also manually ** view this list at any time by calling calling the function MemoryAllocationReport. ** ** IMPORTANT NOTES: ** 1. You should not call this function directly. Use the macro MALLOC instead. ** which fills in the 'file' and 'line' parameters for you. ** 2. All memory allocated by Malloc (i.e., MALLOC) must be freed by calling Free (i.e., FREE). ** 3. DO NOT mix calls to Malloc and Free with calls to the standard C library functions ** malloc and free. */ void *Malloc( const int size, const char *file, const int line ) { MEMORY_BLOCK_HEADER *memoryBlockHeader; void *memoryBlock; int totalSize; assert( size >= 0 ); totalSize = size + ( memoryTrackingEnabled ? sizeof(MEMORY_BLOCK_HEADER) : 0 ); memoryBlock = malloc( totalSize ); if( memoryBlock == NULL ) FATAL( "out of memory" ); if( memoryTrackingEnabled ) { memoryBlockHeader = (MEMORY_BLOCK_HEADER *)memoryBlock; memoryBlock = (void *)( (unsigned char *)memoryBlockHeader + sizeof(MEMORY_BLOCK_HEADER) ); memoryBlockHeader->file = file; memoryBlockHeader->line = line; memoryBlockHeader->size = size; memoryBlockHeader->last = &memoryBlockList; memoryBlockHeader->next = memoryBlockList.next; if( memoryBlockHeader->next != NULL ) memoryBlockHeader->next->last = memoryBlockHeader; memoryBlockList.next = memoryBlockHeader; assert( memoryTotalUsage >= 0 ); memoryTotalUsage += size; assert( memoryBlockCount >= 0 ); memoryBlockCount++; } return memoryBlock; } /* ** Free (FREE): Release a block of memory allocated by Malloc (i.e., MALLOC). ** ** IMPORTANT NOTES: ** 1. You should not call this function directly. Use the macro FREE instead. ** 2. All memory allocated by Malloc (i.e., MALLOC) must be freed by calling Free (i.e., FREE). ** 3. DO NOT mix calls to Malloc and Free with calls to the standard C library functions ** malloc and free. */ void Free( void *memoryBlock ) { MEMORY_BLOCK_HEADER *memoryBlockHeader; if( memoryBlock == NULL ) FATAL( "attempt to free NULL pointer" ); if( memoryTrackingEnabled ) { memoryBlockHeader = (MEMORY_BLOCK_HEADER *)( (void *)( (unsigned char *)memoryBlock - sizeof(MEMORY_BLOCK_HEADER) ) ); memoryBlockHeader->last->next = memoryBlockHeader->next; if( memoryBlockHeader->next != NULL ) memoryBlockHeader->next->last = memoryBlockHeader->last; memoryBlockCount--; assert( memoryBlockCount >= 0 ); memoryTotalUsage -= memoryBlockHeader->size; assert( memoryTotalUsage >= 0 ); free( memoryBlockHeader ); } else free( memoryBlock ); } /* ** MemoryAllocationReport: Displays a list of all memory blocks allocated by Malloc (MALLOC) ** that have not been deallocated by calling Free (FREE). The list displays the following ** information about each memory block: the memory address of the block, the size of the memory block ** in bytes, and the location (i.e., the name of source file and the line number in that file) ** where the blocks was allocated. The function EnableMemoryTracking must be called BEFORE any ** calls to Malloc (MALLOC) for MemoryAllocationReport to function correctly. ** ** IMPORTANT NOTES: ** 1. Only memory blocks allocated with Malloc (MALLOC) and released with Free (FREE) are ** tracked and reported. ** 2. If you call this function without first enabling memory tracking and reporting (i.e., ** by calling EnableMemoryTracking), then the function will not display any output. */ void MemoryAllocationReport( void ) { MEMORY_BLOCK_HEADER *memoryBlockHeader = memoryBlockList.next; /* do nothing if memory tracking and leak detection is not enabled */ if( !memoryTrackingEnabled ) return; if( memoryBlockCount > 0 ) { fprintf( stderr, "Total allcated memory: %d byte%s in %d block%s.\n\n", memoryTotalUsage, ((memoryTotalUsage > 1)?"s":""), memoryBlockCount, ((memoryBlockCount > 1)?"s":"") ); fprintf( stderr, "Address: Bytes: Line: File:\n" ); fprintf( stderr, "-------- ---------- ----- ----------\n" ); while( memoryBlockHeader != NULL ) { fprintf( stderr, "%8p %10.1d %5.1d %s\n", (void *)( (unsigned char *)memoryBlockHeader + sizeof(MEMORY_BLOCK_HEADER) ), memoryBlockHeader->size, memoryBlockHeader->line, memoryBlockHeader->file ); memoryBlockHeader = memoryBlockHeader->next; } } else fprintf( stderr, "No memory is currently allocated.\n" ); } /* ** MemoryLeakDetect: detect memory leaks (if any) when your program terminates. ** If memory leaks are detected, MemoryAllocationReport is called to display a ** list of allocated memory blocks. After displaying the list, the function ** released all memory blocks before the program terminates. ** ** IMPORTANT NOTE: ** Under no circumstances should you call this function directly! It is "registered" ** by EnableMemoryTracking and is called automatically when the program terminates. */ static void MemoryLeakDetect( void ) { MEMORY_BLOCK_HEADER *memoryBlockHeader; if( !memoryTrackingEnabled ) FATAL( "memory reporting and leak detection is not enabled" ); if( memoryBlockCount > 0 || memoryBlockList.next != NULL ) { fprintf( stderr, "Error: memory leaks detected.\n\n" ); MemoryAllocationReport(); while( memoryBlockList.next != NULL ) { memoryBlockHeader = memoryBlockList.next; memoryBlockList.next = memoryBlockHeader->next; free( (void *)memoryBlockHeader ); } } } /* ** EnableMemoryTracking: Turn on memory tracking and reporting for memory blocks allocated ** by Malloc (MALLOC) and released by Free (FREE). To use memory tracking, this function must be ** called once (and only once) at the beginning of your program BEFORE any memory is allocated. ** ** IMPORTANT NOTES: ** 1. Only memory blocks allocated with Malloc (MALLOC) and released with Free (FREE) are ** tracked and reported. ** 2. If you wish to use the memory tracking and reporting features of Malloc (MALLOC), ** Free (FREE), and MemoryAllocationReport, you must call this function ONCE and ** ONLY ONCE at the beginning of your program BEFORE any memory is allocated. */ void EnableMemoryTracking( void ) { memoryTrackingEnabled = TRUE; if( atexit( MemoryLeakDetect ) != 0 ) FATAL( "could not initialize memory tracking and leak detection" ); } /* ** event.h */ #ifndef _EVENT_H_ #define _EVENT_H_ /* ** The simulation time will be stored as double representing the number of seconds ** that have elapsed since the bank opened at 10 AM. */ typedef double Time; /* simulation time type */ extern Time _simulationTime; /* global simulation time (defined in event.c) */ #define Now() _simulationTime /* "function" to access the simulation time */ /* ** Events are actually function pointers, and your event is expected to take ** one argument that is a pointer to the object to which the event occurs. The ** object is represented as a void pointer (i.e., void*). This pointer will always ** be either NULL or a pointer to dynamically allocated data, such as a double or ** a structure of some kind. */ typedef void (*Event)( void *object ); typedef struct _eventStruct { Time time; /* time at which this even occurs */ Event event; /* pointer to event function that accepts object as param */ void *object; /* the "object" passed to the even function when the event occurs */ } EventInfo; /* ** EventListInit: initialize the event list. */ void EventListInit( void ); /* ** EventListFree: free the event list. */ void EventListFree( void ); /* ** EventInsert: Insert an event into the event queue at time Now() + delta, ** and the event expects some data in "object". Returns a pointer to EventInfo ** (which you can ignore) if OK, else NULL. */ EventInfo *EventInsert( Event event, Time delta, void *object ); /* ** EventNext: Execute the next event. After executing the event, it ** returns the EventInfo struct that was used, or NULL if there were no ** events to execute. It is the responsibility of the ** CALLER to free the memory. Usually all you want to do is free the EventInfo ** struct when it is returned, but if you want to know more about what ** the event was, you're free to look and see. (But don't forget to free ** it afterwards anyway!) */ EventInfo *EventNext( void ); #endif /* _EVENT_H_ */ /* ** debug.h */ #ifndef _DEBUG_H_ #define _DEBUG_H_ /* to ensure we don't include it more than once */ /* ** C does not have a boolean type, so use "int" instead. */ #ifndef BOOLEAN_DEFINED #define BOOLEAN_DEFINED /* ensure that we don't define this constant more than once */ typedef int boolean; enum { FALSE = 0, TRUE = 1 }; #endif /* ** Fatal (FATAL): Display an error message and terminate the program. ** If you are debugging, make sure you compile with WITHOUT ** the constant NDEBUG defined. Doing so will cause and "assert(false)" statement ** to be inserted before the program is terminated by calling "exit(1)". This allows ** the debugger to catch your program before it exits, allowing you to debug the problem. ** If NDEBUG is defined, the program will simply terminate when this function is called ** (i.e., the program will terminate before the debugger has a chance to catch the ** error). ** ** IMPORTANT NOTE: You should not call this function directly. Use the ** macro FATAL instead, because FATAL fills in the 'file' and 'line' parameters for you. */ void Fatal( const char *message, const char *file, const int line ); /* Do not call this function directly. Use FATAL instead. */ #define FATAL(message) Fatal( (message), __FILE__ , __LINE__ ) /* ** Malloc (MALLOC): Allocate and return a pointer to a block of 'size' bytes of memory. If the ** allocation fails (due to an out of memory condition), the program is terminated. If memory ** tracking and reporting is enabled (by calling EnableMemoryTracking before any calls ** to Malloc), a list of allocated memory blocks will be maintained. If you fail to ** release allocated memory blocks before your program terminates, you will receive ** an error message saying 'Memory leaks detected' when your program exits, followed by a list ** of the allocated blocks, their memory address, their size in bytes, and the location in the ** source code where they were allocated (i.e., the file name and line number). You can also manually ** view this list at any time by calling calling the function MemoryAllocationReport. ** ** IMPORTANT NOTES: ** 1. You should not call this function directly. Instead use the macro MALLOC ** which fills in the 'file' and 'line' parameters for you. ** 2. All memory allocated by Malloc (i.e., MALLOC) must be freed by calling Free (i.e., FREE). ** 3. DO NOT mix calls to Malloc and Free with calls to the standard C library functions ** malloc and free. */ void *Malloc( const int size, const char *file, const int line ); /* Do not call this function directly. Use MALLOC instead. */ #define MALLOC(size) Malloc( (size), __FILE__, __LINE__ ) /* ** Free (FREE): Release a block of memory allocated by Malloc (i.e., MALLOC). ** ** IMPORTANT NOTES: ** 1. You should not call this function directly. Use the macro FREE instead. ** 2. All memory allocated by Malloc (i.e., MALLOC) must be freed by calling Free (i.e., FREE). ** 3. DO NOT mix calls to Malloc and Free with calls to the standard C library functions ** malloc and free. */ void Free( void *memoryBlock ); /* Do not call this function directly. Use FREE instead. */ #define FREE(pointer) Free( (pointer) ) /* ** MemoryAllocationReport: Displays a list of all memory blocks allocated by Malloc (MALLOC) ** that have not been deallocated by calling Free (FREE). The list displays the following ** information about each memory block: the memory address of the block, the size of the memory block ** in bytes, and the location (i.e., the name of source file and the line number in that file) ** where the blocks was allocated. The function EnableMemoryTracking must be called BEFORE any ** calls to Malloc (MALLOC) for MemoryAllocationReport to function correctly. ** ** IMPORTANT NOTES: ** 1. Only memory blocks allocated with Malloc (MALLOC) and released with Free (FREE) are ** tracked and reported. ** 2. If you call this function without first enabling memory tracking and reporting (i.e., ** by calling EnableMemoryTracking), then the function will not display any output. */ void MemoryAllocationReport( void ); /* ** EnableMemoryTracking: Turn on memory tracking and reporting for memory blocks allocated ** by Malloc (MALLOC) and released by Free (FREE). To use memory tracking, this function must be ** called once (and only once) at the beginning of your program BEFORE any memory is allocated. ** ** IMPORTANT NOTES: ** 1. Only memory blocks allocated with Malloc (MALLOC) and released with Free (FREE) are ** tracked and reported. ** 2. If you wish to use the memory tracking and reporting features of Malloc (MALLOC), ** Free (FREE), and MemoryAllocationReport, you must call this function ONCE and ** ONLY ONCE at the beginning of your program BEFORE any memory is allocated. */ void EnableMemoryTracking( void ); /* ** DEBUGPRINTF: Execute a printf statement if in debugging mode (i.e., if the constant NDEBUG ** is NOT defined). If NDEBUG is defined, the DEBUGPRINTF statement is automatically ** skipped by the compiler (i.e., you do not need to delete it from the source code). ** ** NOTE: ** Do not call 'debugprintf' directly, call DEBUGPRINTF instead. */ #ifdef NDEBUG #define DEBUGPRINTF debugprintf #else #define DEBUGPRINTF printf #endif void debugprintf( const char *format, ... ); /* do not call this function directly, call DEBUGPRINTF instead */ /* ** HERE: a simple macro that prints the current soure file name and line number ** when debugging (i.e., when the constant NDEBUG is NOT defined). If NDEBUG is defined, ** the HERE statement is automatically skipped by the compiler (i.e., you do not have to ** removed it from the code). This macro can be very useful for determining where a program ** fails. */ #ifdef NDEBUG #define HERE ((void *)0) #else #define HERE fprintf( stderr, "[%s:%d]", __FILE__, __LINE__ ) #endif #endif /* _DEBUG_H_ */ /* ** event.c */ #include #include #include "debug.h" #include "linked-list.h" #include "event.h" /* ** This is an example of a macro to control "conditional compilation". ** You should insert expensive sanity checks (other than simple ** assertions) into your code. For example, you should call ** LinkedListSanityCheck on your LINKED_LIST every time you perform an ** operation on the list, to ensure you haven't corrupted the linked ** list. If SANITY is 1, then the sanity code should be compiled in. If ** we set it to 0, then the error checking code should not be compiled ** into the program. Setting it to 0 will make the program run ** significantly faster, but you should only do it if you're certain your ** linked list code is working correctly. */ #define SANITY 0 /* ** The global simulation time, in seconds. */ Time _simulationTime = 0; /* ** CompareEvents: compare events A and B, returning 0 if their times ** are equal, <0 if A occurs before B, and >0 if A occurs after B. */ static int CompareEvents( void *A, void *B ) { /*** INSERT YOUR CODE AFTER THIS COMMENT ***/ Time a = *(Time*)A; Time b = *(Time*)B; if (a < b) return -1; if (a > b) return 1; return 0; /* A must equal to B. */ /*** INSERT YOUR CODE BEFORE THIS COMMENT ***/ } /* ** The global event list. */ static LINKED_LIST *_eventList; /* ** EventListInit: initialize the event list. */ void EventListInit( void ) { _eventList = LinkedListAlloc( CompareEvents, TRUE ); #if SANITY LinkedListSanityCheck( _eventList, TRUE ); #endif _simulationTime = 0.0; } /* ** EventListFree: free the event list. */ void EventListFree( void ) { LinkedListFree( _eventList ); } /* ** EventInsert: Insert an event into the event queue at time Now() + delta, ** and the event expects some data in "object". Returns a pointer to EventInfo ** (which you can ignore) if OK, else NULL. */ EventInfo *EventInsert( Event event, Time delta, void *object ) { EventInfo *p = (EventInfo *)MALLOC( sizeof(EventInfo) ); p->time = _simulationTime + delta; p->event = event; p->object = object; assert( delta >= 0.0 && delta <= 10.0e10 ); #if SANITY LinkedListSanityCheck( _eventList, TRUE ); #endif LinkedListInsert( _eventList, (void *)p ); return p; } /* ** EventNext: Execute the next event. After executing the event, it ** returns the EventInfo struct that was used, or NULL if there were no ** events to execute. It must also update the simulation to the time of ** the even executed. It is the responsibility of the ** CALLER to free the memory. Usually all you want to do is free the EventInfo ** struct when it is returned, but if you want to know more about what ** the event was, you're free to look and see. (But don't forget to free ** it afterwards anyway!) */ EventInfo *EventNext( void ) { EventInfo *next; /*** INSERT YOUR CODE AFTER THIS COMMENT ***/ if( _eventList->n == 0 ) return NULL; else{ next = LinkedListNext( _eventList ); _simulationTime = next->time; next->event(next->object); /*** INSERT YOUR CODE BEFORE THIS COMMENT ***/ return next;} } /* ** linked-list.c */ #include #include #include #include "debug.h" #include "linked-list.h" /* ** LinkedListAlloc: allocate a linked list and make it empty. If the ** list is to be ordered, a then 'ComparisonFunction' must be specified, ** otherwise it may be set to NULL. If the linked list is to contain ** dynamically allocated data (i.e., if the list nodes 'data' field points ** to allocated memory), then 'DynamicData' must be set to TRUE. A pointer ** to the list is returned. */ LINKED_LIST *LinkedListAlloc( pComparisonFunction comparisonFunction, boolean dynamicData ) { LINKED_LIST *ll = MALLOC( sizeof(LINKED_LIST) ); ll->first = ll->last = NULL; ll->n = 0; ll->comparisonFunction = comparisonFunction; ll->dynamicData = dynamicData; return ll; } /* ** LinkedListReset: set number of items to zero for re-use. */ static void LinkedListReset( LINKED_LIST *ll ) { LINKED_LIST_NODE *node = ll->first; while( node != NULL ) { LINKED_LIST_NODE *prev = node; node = node->next; if( ll->dynamicData && prev->data != NULL ) FREE( prev->data ); FREE( prev ); } ll->first = ll->last = NULL; ll->n = 0; } /* ** LinkedListSize: return the number of items in a linked list. */ int LinkedListSize( LINKED_LIST *ll ) { return ll->n; } /* ** LinkedListFree: Free a list and all it's storage. It does not have to be ** empty. */ void LinkedListFree( LINKED_LIST *ll ) { LinkedListReset( ll ); FREE( ll ); } /* ** LinkedListPrepend: insert a new element at the front of the list, ignoring ** the comparison function. The new value is returned after inserting. */ void *LinkedListPrepend( LINKED_LIST *ll, void *newEntry ) { LINKED_LIST_NODE *newNode = MALLOC( sizeof(LINKED_LIST_NODE) ); newNode->data = newEntry; newNode->next = ll->first; ll->first = newNode; if( ll->last == NULL ) ll->last = newNode; ll->n++; return newEntry; } /* ** LinkedListAppend: insert something at the end of the list, igroning the ** comparison function. The new value is returned after inserting. */ void *LinkedListAppend( LINKED_LIST *ll, void *newEntry ) { /*** INSERT YOUR CODE AFTER THIS COMMENT ***/ LINKED_LIST_NODE *newNode = MALLOC( sizeof(LINKED_LIST_NODE) ); newNode->data = newEntry; newNode->next = NULL; if ( ll->first == NULL){ ll->first = ll->last = newNode; } else { ll->last->next = newNode; ll->last = newNode; } ll->n++; /*** INSERT YOUR CODE BEFORE THIS COMMENT ***/ return newEntry; } /* ** LinkedListInsert: insert something in the list, using the comparison function. ** The element should be inserted *after* any elements that compare equally; that way, ** even if two events have the same time, they get executed in the order ** in which they were inserted. This is sometimes important. The new value is returned ** after inserting. */ void *LinkedListInsert( LINKED_LIST *ll, void *newEntry ) { /*** INSERT YOUR CODE AFTER THIS COMMENT ***/ LINKED_LIST_NODE *newNode = MALLOC( sizeof(LINKED_LIST_NODE) ); newNode->data = newEntry; newNode->next = NULL; if (ll->first == NULL ) { ll->first = ll->last = newNode; } else { LINKED_LIST_NODE *prev; LINKED_LIST_NODE *current; prev = NULL; current = ll->first; while ( current != NULL && ll->comparisonFunction(newEntry, current->data) >= 0) { prev = current; current = current->next; } if ( current == ll->first ) { /* newEntry is the smallest.*/ newNode->next = ll->first; ll->first = newNode; } else if ( current == NULL ) { /*newEntry is the greatest.*/ ll->last->next = newNode; ll->last = newNode; } else { /* It is in the middle of ll. */ prev->next = newNode; newNode->next = current; } } ll->n++; /*** INSERT YOUR CODE BEFORE THIS COMMENT ***/ return newEntry; } /* ** LinkedListPeek: peek at the top of the list without removing it from ** the list. */ void *LinkedListPeek( LINKED_LIST *ll ) { if( ll->n == 0 ) { assert( ll->first == NULL && ll->last == NULL ); FATAL( "LinkedListPeek: the list is empty" ); return (void *)0; /* too keep gcc quiet */ } return ll->first->data; } /* ** LinkedListNext: delete the top entry and returns its value. If the list is ** empty it will fail with an assertion. */ void *LinkedListNext( LINKED_LIST *ll ) { void *data; LINKED_LIST_NODE *newFirst; if( ll->n == 0 ) { assert( ll->first == NULL && ll->last == NULL ); FATAL( "LinkedListNext: nothing to return!" ); } data = ll->first->data; newFirst = ll->first->next; FREE( ll->first ); ll->first = newFirst; if( ll->first == NULL ) ll->last = NULL; ll->n--; return data; } /* ** LinkedListSanityCheck: checks a linked list for "sanity". "ordered" should be ** TRUE or FALSE, and tells us whether we should check that elements are ** in order using the comparison function. This function is provided ** for you. */ void LinkedListSanityCheck( LINKED_LIST *ll, boolean ordered ) { LINKED_LIST_NODE *prev, *curr; assert( ll ); assert( ll->n >= 0 ); if( ordered ) assert( ll->comparisonFunction != NULL ); if( ll->n == 0 ) assert( ll->first == NULL && ll->last == NULL ); else if( ll->n == 1 ) assert( ll->first == ll->last && ll->first->next == NULL ); else { /* n >= 2 */ int i; prev = NULL; curr = ll->first; for( i = 0; i < ll->n - 1; i++ ) { assert( curr != NULL ); assert( curr->next != NULL ); if( ordered ) assert( ll->comparisonFunction(curr->data, curr->next->data) <= 0 ); prev = curr; curr = curr->next; } assert( curr == ll->last ); assert( ll->last->next == NULL ); } } /* ** linked-list.h */ #ifndef _LINKED_LIST_H_ #define _LINKED_LIST_H_ /* to ensure we don't include it more than once */ /* ** C does not have a boolean type, so use "int" intead. */ #ifndef BOOLEAN_DEFINED #define BOOLEAN_DEFINED /* to ensure we don't define this more than once */ typedef int boolean; enum { FALSE = 0, TRUE = 1 }; #endif /* ** The comparison function type. Look up "qsort" in a C book or the online ** manual for details. */ typedef int (*pComparisonFunction)( void *a, void *b ); /* ** LinkedList routines: a smallest-at-top list. You also supply a ** comparison function. You allocate a LL using LinkedListAlloc, and ** LinkedListCmp is a pointer to a function to compare your entries. ** Entries are of type (void *), which is as close to a general "object" ** that you can get in C without doing major surgery. */ typedef struct _linkedListNode { struct _linkedListNode *next; /* pointer to the next node in the list */ void *data; /* data (of unknown type) stored in this node */ } LINKED_LIST_NODE; typedef struct _linkedListType { int n; /* number of elments in the list */ boolean dynamicData; /* TRUE if the node 'data' field points to dynamically allocated memory, FALSE otherwise */ pComparisonFunction comparisonFunction; /* pointer to the comparison function, or NULL for unordered lists. */ LINKED_LIST_NODE *first; /* pointer to the first node in the list */ LINKED_LIST_NODE *last; /* pointer to the last node in the list */ } LINKED_LIST; /* ** LinkedListAlloc: allocate a linked list and make it empty. If the ** list is to be ordered, a then 'ComparisonFunction' must be specified, ** otherwise it may be set to NULL. If the linked list is to contain ** dynamically allocated data (i.e., if the 'data' fields of the list nodes point ** to allocated memory), then 'DynamicData' must be set to TRUE. A pointer ** to the list is returned. */ LINKED_LIST *LinkedListAlloc( pComparisonFunction ComparisonFunction, boolean DynamicData ); /* ** LinkedListSize: return the number of items in a linked list. */ int LinkedListSize( LINKED_LIST *ll ); /* ** LinkedListFree: Free a list and all it's storage. It does not have to be ** empty. */ void LinkedListFree( LINKED_LIST *ll ); /* ** LinkedListPeek: peek at the top of the list without removing it from ** the list. */ void *LinkedListPeek( LINKED_LIST *ll ); /* ** LinkedListNext: delete the top entry and returns its value. If the list is ** empty it will fail with an assertion. */ void *LinkedListNext( LINKED_LIST *ll ); /* ** LinkedListPrepend: insert a new element at the front of the list, ignoring ** the comparison function. The new value is returned after inserting. */ void *LinkedListPrepend( LINKED_LIST *ll, void *newEntry ); /* ** LinkedListAppend: insert something at the end of the list, igroning the ** comparison function. The new value is returned after inserting. */ void *LinkedListAppend( LINKED_LIST *ll, void *newEntry ); /* ** LinkedListInsert: insert something in the list, using the comparison function. ** The element should be inserted *after* any elements that compare equally; that way, ** even if two events have the same time, they get executed in the order ** in which they were inserted. This is sometimes important. The new value is returned ** after inserting. */ void *LinkedListInsert( LINKED_LIST *ll, void *newEntry ); /* ** LinkedListSanityCheck: checks a linked list for "sanity". "ordered" should be ** TRUE or FALSE, and tells us whether we should check that elements are ** in order using the comparison function. This function is provided ** for you. */ void LinkedListSanityCheck( LINKED_LIST *ll, boolean ordered ); #endif /* _LINKED_LIST_H_ */ /* ** main.c */ #include #include #include #include #include #include "debug.h" #include "event.h" #include "queue.h" #include "random.h" /****************************************************************** ** CONSTANTS. ** ******************************************************************/ /* ** NTELLERS: number of teller windows in the bank. */ #define NTELLERS 5 /* ** INTER_ARRIVAL_TIME: average time, in seconds, between arrivals of customers at the bank. */ #define INTER_ARRIVAL_TIME 30 /* ** NO_ARRIVALS: value used to indicate that no more arrivals should occur (i.e., no more customers ** should be admitted to the bank). */ #define NO_ARRIVALS (-1) /* ** MAX_CUST_IN_BANK: maximum number of customers allowed in the bank. */ #define MAX_CUST_IN_BANK 30 /****************************************************************** ** TYPE DEFINITIONS. ** ******************************************************************/ /* ** A customer has an id and a teller number they are served by, which ** happens to be the same as the queue they're in when there is one ** queue per teller. They also have an arrival time, so we can compute their queueing ** delay at the instant their Service starts. */ typedef struct _customer { int id; int teller; double arrivalTime; } CUSTOMER; /****************************************************************** ** GLOBAL VARIABLES. ** ******************************************************************/ /* ** intArrTime: average inter-arrival time. It should be set to either INTER_ARRIVAL_TIME ** or NO_ARRIVALS, depending on whether or not customers are being admitted to the bank. */ static double intArrTime = 0.0; /* ** nextArrivalId: unique integer identifying the next customer to arrive at the bank. */ static int nextArrivalId = 0; /* ** totalCustomersInBank: the total number of customers currently in the bank. */ static int totalCustomersInBank = 0; /* ** tellerBusy: array indicating whether tellers are busy (TRUE) or waiting for customers (FALSE). */ static boolean tellerBusy[NTELLERS]; /* ** queuePerTeller: boolean indicating whether there is one queue per teller (TRUE) or ** a single global queue (FALSE). */ static boolean queuePerTeller = TRUE; /* ** customerQ: array of customer queues. If queuePerTeller is FALSE, we will use customerQ[0] ** as the global queue and ignore the rest. */ static QUEUE *customerQ[NTELLERS]; /* ** Global variables to store the intermediate values that we must collect ** in order to compute the average queuing delay and the standard deviation ** of the queuing delay. */ /*** INSERT YOUR CODE AFTER THIS COMMENT ***/ #define SERVICE_TIME_BASE 240 static int customerServed = 0; static Time totalQueuingDelay = 0.0; static double totalQueuingDelaySquare = 0.0; /*** INSERT YOUR CODE BEFORE THIS COMMENT ***/ /****************************************************************** ** EVENTS ** ******************************************************************/ void Arrival( void *object ); void StartService( void *object ); void Departure( void *object ); /* ** Arrival: the arrival event. The parameter 'object' is a pointer to a dynamically ** allocated integer specifying the ID of the customer that arrives (it is the responsability ** of the Arrival function to free this integer). The function creates a customer, and then ** either sends the customer directly to a teller, places the customer in a queue, or deletes ** the customer (if the bank is full). The function also schedules the next Arrival event. */ void Arrival( void *object ) { int customerId = *((int *)object); /* get the id of the arriving customer */ CUSTOMER *customer = (CUSTOMER *)MALLOC( sizeof(CUSTOMER) ); int i; FREE( object ); /* make sure we free the object parameter! */ if( intArrTime != NO_ARRIVALS ) { int *nextCustomerId = (int *)MALLOC( sizeof(int) ); *nextCustomerId = nextArrivalId++; EventInsert( Arrival, ExponentialRandom(intArrTime), (void *)nextCustomerId ); } DEBUGPRINTF( "Arrival [time = %g, customer = %d]\n", Now(), customerId ); if( totalCustomersInBank >= MAX_CUST_IN_BANK ) { /* this customer looks at the crowd of 30 angry people and ** decides now is not a good time to go to the bank. */ DEBUGPRINTF( "\tCustomer %d departs immediately\n", customerId ); FREE( customer ); return; } ++totalCustomersInBank; customer->id = customerId; customer->arrivalTime = Now(); customer->teller = 0; /* this may change */ if( queuePerTeller ) { /* there is one queue per teller, so we use first teller that's not busy, or the shortest queue. */ int shortest, j; for( i = 0; i < NTELLERS; i++ ) if( !tellerBusy[i] ) { DEBUGPRINTF( "\tStartService immediately at teller %d\n", i ); customer->teller = i; EventInsert( StartService, 0, (void *)customer ); return; } shortest = QueueSize(customerQ[0]); /* The shortest queue size so far. */ j = 0; for ( i = 1; i < NTELLERS; i++) { if ( QueueSize(customerQ[i]) < shortest ) { shortest = QueueSize(customerQ[i]); j = i; } } customer->teller = j; /*** INSERT YOUR CODE BEFORE THIS COMMENT ***/ } else { /* there is only one queue */ if( QueueSize(customerQ[0]) == 0 ) { /* ** See if there's a teller available immediately. */ for( i = 0; i < NTELLERS; i++ ) if( !tellerBusy[i] ) { DEBUGPRINTF( "\tStartService immediately at teller %d\n", i ); customer->teller = i; EventInsert( StartService, 0, (void *)customer ); return; } } } /* ** If we get here, we have to queue up. */ DEBUGPRINTF( "\tCustomer %d joins queue %d ", customer->id, customer->teller ); QueueAppend( customerQ[customer->teller], (void *)customer ); DEBUGPRINTF( "(queue length is now %d)\n", QueueSize(customerQ[customer->teller]) ); } /* ** StartService: event repersenting the beginning of the service of a customer ** at a teller. The 'object' parameter is a pointer to a customer structure dynamically ** allocated by the Arrival event (StartService should not free this structure, that ** task is performed when the customer leaves the bank in the Departure event). StartService ** is where the queuing delay for the current customer is calculated (and where statistics ** should be collected for computing the mean and standard deviation of the queuing delay). ** StartService also determines the service time and and schedules the customer's ** Departure event. */ void StartService( void *object ) { /*** INSERT YOUR CODE AFTER THIS COMMENT ***/ Time queuingDelay; Time serviceTime; CUSTOMER *cust; cust = (CUSTOMER *)object; if (! tellerBusy[cust->teller]){ tellerBusy[cust->teller] = TRUE; } queuingDelay = Now() - cust->arrivalTime ; totalQueuingDelay += queuingDelay; totalQueuingDelaySquare += queuingDelay * queuingDelay; serviceTime = ExponentialRandom(SERVICE_TIME_BASE); EventInsert(Departure, serviceTime, object); /*** INSERT YOUR CODE BEFORE THIS COMMENT ***/ } /* ** Departure: event representing the end of a customer's service at a teller and ** the departure of the customer from the bank. The parameter 'object' is a pointer ** to a CUSTOMER structure dynamically allocated by by the Arrival event. It is the ** responsibility of this to free this structure. If there is someone waiting in ** the queue for this teller (or the global queue if there is only one queue) then ** a this event schedules a StartService event for the appropriate customer. */ void Departure( void *object ) { /*** INSERT YOUR CODE AFTER THIS COMMENT ***/ CUSTOMER *cust, *nextCust; cust = (CUSTOMER *)object; customerServed ++; totalCustomersInBank --; if (queuePerTeller){ if (QueueSize(customerQ[cust->teller]) == 0) tellerBusy[cust->teller] = FALSE; else{ nextCust = (CUSTOMER *)QueueNext(customerQ[cust->teller]); EventInsert(StartService, 0, (void*)nextCust); } } else{ if (QueueSize(customerQ[0]) == 0) tellerBusy[cust->teller] = FALSE; else{ nextCust = (CUSTOMER *)QueueNext(customerQ[0]); EventInsert(StartService, 0, (void*)nextCust); } } FREE(object); /*** INSERT YOUR CODE BEFORE THIS COMMENT ***/ } /****************************************************************** ** PSEUDO-EVENTS ** ******************************************************************/ /* ** EndOfSimulation: the end-of-simulation event. Computes and outputs the average ** queuing delay and its standard deviation from the statistics that we have collected ** during the simulatoin. Do not change the format of the output. The parameter ** 'object' must be NULL. */ static void EndOfSimulation( void *object ) { double averageQueueingDelay; /* the average queueing delay (in minutes!) */ double standardDeviation; /* the standard deviation of the queueing delay (in minutes!) */ /*** INSERT YOUR CODE AFTER THIS COMMENT ***/ averageQueueingDelay = totalQueuingDelay/(double)customerServed/60; standardDeviation = totalQueuingDelaySquare - totalQueuingDelay*totalQueuingDelay/customerServed; standardDeviation = sqrt(standardDeviation/(customerServed-1))/60; /*** INSERT YOUR CODE BEFORE THIS COMMENT ***/ /* ouput the results */ printf("%g %g\n", averageQueueingDelay, standardDeviation ); /* make sure 'object' is NULL */ assert( object == NULL ); } /* ** Change the inter-arrival time. The parameter 'object' is a void pointer to ** a dynamically allocated double that stores the new inter-arrival time (it is the ** responsability of this function to free the double). ** ** Note that the new inter-arrival time won't take effect until the ** next arrival at the current rate. */ static void SetInterArrivalTime( void *object ) { intArrTime = *((double *)object); FREE( object ); } /****************************************************************** ** SIMULATION AND PROGRAM STARTUP ** ******************************************************************/ /* ** Simulate the operation of the bank for one day. */ void Simulate( void ) { double *arrivalRate; int *firstCustomerId; EventInfo *e; /* ** Insert pseudo-events to change the arrival rate at the appropriate times. Since ** we know these times in advance, so we can insert these events before the simulation starts. */ /* set the interarrival time to the normal rate */ arrivalRate = (double *)MALLOC( sizeof(double) ); *arrivalRate = (double)INTER_ARRIVAL_TIME; SetInterArrivalTime( (void *)arrivalRate ); /* the bank is closed, 6 hours after 10am, so set the interarrival time to NO_ARRIVALS at that time */ arrivalRate = (double *)MALLOC( sizeof(double) ); *arrivalRate = (double)NO_ARRIVALS; EventInsert( SetInterArrivalTime, 6*60*60, (void *)arrivalRate ); /* Finally, insert the first arrival. */ assert( intArrTime != NO_ARRIVALS && intArrTime > 0 ); firstCustomerId = (int *)MALLOC( sizeof(int) ); *firstCustomerId = nextArrivalId++; EventInsert( Arrival, ExponentialRandom(intArrTime), (void *)firstCustomerId ); /* Start the loop. The loop exits when the simulation is ** finished. We want to wait until all customers are served, and ** we have just inserted an event at 4pm to set the arrival rate to 0, ** so now the simulation will run until all customers are served, sometime ** after 4pm. */ while( (e = EventNext()) ) FREE(e); } /* ** ParseCommandLine: read in command line parameters and adjust the global ** state of the simulation accordingly. The command line should be as follows: ** ** bank QUEUE_PER_TELLER RANDOM_SEED TRACK_MEMORY ** ** where: ** ** bank...is the name of the exectuable program. ** ** QUEUE_PER_TELLER...is an integer (i.e., boolean), such that ** QUEUE_PER_TELLER = 1...each teller has their own queue ** QUEUE_PER_TELLER = 0...there is only one global queue ** ** RANDOM_SEED...is the number used to seed the random number generator. If ** RANDOM_SEED = 0, then a seed value is chosen depending on the system time ** and the id of the current process. Any other value is used directly as ** the seed for the random number generator. ** ** TRACK_MEMORY...is an integer (i.e., boolean) which determines whether or not ** to use the memory tracking features provided by Malloc (MALLOC) and Free (FREE) ** TRACK_MEMORY = 1...enable memory tracking ** TRACK_MEMORY = 0...disable memory tracking ** ** The following example command line will run the simulation with the a separate ** queue for each teller, the seed 999, and memory tracking turned off: ** ** bank 1 999 0 */ static void ParseCommandLine( int argc, char *argv[] ) { if( argc != 4 ) FATAL( "invalid command line.\nThe following parameters are expected: QUEUE_PER_TELLER RANDOM_SEED TRACK_MEMORY\nSee ParseCommandLine in main.c for details.\n" ); if( atoi(argv[1]) == 0 ) queuePerTeller = FALSE; else queuePerTeller = TRUE; RandomSeed( (long)atoi(argv[2]) ); if( atoi(argv[3]) == 1 ) EnableMemoryTracking(); } /* ** main: the program begins execution here... */ int main( int argc, char *argv[] ) { int i; /* ** Read the command line arguments and set global options. */ ParseCommandLine( argc, argv ); /* ** Initialize the customer queues. Note that we will only use customerQ[0] when ** we have only one global queue. */ for( i = 0; i < NTELLERS; i++ ) customerQ[i] = QueueAlloc(); /* ** Initialize the event list. */ EventListInit(); /* ** Start the simulation. */ Simulate(); /* ** Instead of inserting this "event" into the queue, we call it directly. It calculates ** and outputs the statistics we are collecting. */ EndOfSimulation( NULL ); /* ** Clean up the customer queues and event list. */ for( i = 0; i < NTELLERS; i++ ) QueueFree( customerQ[i] ); EventListFree(); return 0; } /* ** queue.h */ #ifndef _QUEUE_H_ #define _QUEUE_H_ /* to ensure we don't include it more than once */ #include "debug.h" #include "linked-list.h" /* ** This is an implementation of a queue (First-In, First-Out, first-come, ** first-served) that just uses the linked-list stuff. In other words, ** it's a simple wrapper around the LinkedList functions that implement ** a queue. ** ** Note there is no queue.c file. Everything you need is right here. */ #define QUEUE LINKED_LIST #define QueueAlloc() LinkedListAlloc( NULL, TRUE ) /* there's no comparison function */ #define QueueAppend LinkedListAppend #define QueueNext LinkedListNext #define QueueSize LinkedListSize #define QueuePeek LinkedListPeek #define QueueFree LinkedListFree #endif /* _QUEUE_H_ */ /* ** random.c */ #include #include #include /* ** The header file, and function name, of system function to used to return ** the process ID is different on UNIX and Windows. The following conditional ** compilation directive isolates this difference */ #ifdef WIN32 /* Microsoft Windows 95/98/NT (Visual C++) */ #include #define GETPID _getpid #else /* UNIX */ #include #define GETPID getpid #endif #include "debug.h" #include "random.h" /* hidden global seed value */ static long _seed = 0; /* ** RandomSeed: seed the random number generator. You MUST call this routine once (and ** only once) in your program BEFORE calling Random to obtain pseudo-random numbers. ** A particular seed value completely determines the sequence of random numbers generated ** by Random. Thus, when debugging your program you may wish to use the same seed value ** each time to force the behaviour of the program to be reproducible. However, you should ** use different seed values for each run of your program when you collect statistics ** for the analysis portion of your report. ** ** If you pass any value other than 0 to RandomSeed, then that number will be used as ** the seed for the random number generator. However, if you call RandomSeed(0), then ** the routine will use the sum of the current time and the process id as the seed value, ** which saves you the trouble of thinking of providing a unique seed each time. ** ** See also: Random */ void RandomSeed( long seed ) { if( seed == 0 ) _seed = -labs( (long)time(NULL) + GETPID() ); else _seed = -labs( seed ); } /************************************************* ** ** The following code is a modified version of the function ran1 on page 280 ** of: ** ** William H. Press, et. al., "Numerical Recipes in C: The Art of Scientific ** Computing", Second Edition, Cambridge University Press, New York, 1992. ** ** It is subject to all copyrights that bind the orignal code. */ #define IA 16807 #define IM 2147483647 #define AM (1.0/IM) #define IQ 127773 #define IR 2836 #define NTAB 32 #define NDIV (1+(IM-1)/NTAB) #define EPS 1.2e-7 #define RNMX ((float)(1.0-EPS)) /* ** Random: "minimal" random number generator of Park and Miller with Bays-Durham ** shuffle and added safeguards. Returns a uniform deviate between 0.0 and 1.0 ** (exclusive of the endpoint values). ** ** See also: RandomSeed */ float Random( void ) { int j; long k; static long iy = 0; static long iv[NTAB]; float temp; /* initialize the random number generator */ if( _seed <= 0 || !iy ) { /* prevent _seed = 0 */ if( -_seed < 1 ) _seed = 1; else _seed = -_seed; /* load the suffle table (after 8 warm-ups) */ for( j = NTAB + 7; j >= 0; j-- ) { k = _seed / IQ; _seed = IA * (_seed - k*IQ) - IR*k; if( _seed < 0 ) _seed += IM; if( j < NTAB ) iv[j] = _seed; } iy = iv[0]; } /* start here when not initializing */ k = _seed / IQ; /* compute _seed = (IA * _seed) % IM without overflow by Schrange's method */ _seed = IA * (_seed - k*IQ) - IR*k; if( _seed < 0 ) _seed += IM; /* find j in the range 0..NTAB-1 */ j = iy / NDIV; /* output previously stored value and refill the shuffle table */ iy = iv[j]; iv[j] = _seed; /* avoid returning an endpoint value */ if( (temp = (float)(AM*iy)) > RNMX ) return RNMX; /* return the pseudo-random number */ return temp; } /* ** The preceeding code is a modified version of the function ran1 on page 280 ** of: ** ** William H. Press, et. al., "Numerical Recipes in C: The Art of Scientific ** Computing", Second Edition, Cambridge University Press, New York, 1992. ** ** It is subject to all copyrights that bind the orignal code. ** *************************************************/ /* ** Generate an exponentially distributed random variable with average ** inter-arrival time t. Note the average inter-arrival time is ** 1/(average rate). */ double ExponentialRandom( double t ) { /*** INSERT YOUR CODE AFTER THIS COMMENT ***/ double x; float u; u = Random(); x = -t*log((double)u); return x; /*** INSERT YOUR CODE BEFORE THIS COMMENT ***/ } /* ** random.h */ #ifndef _RANDOM_H_ #define _RANDOM_H_ /* to ensure we don't include it more than once */ /* ** RandomSeed: seed the random number generator. You MUST call this routine once (and ** only once) in your program BEFORE calling Random to obtain pseudo-random numbers. ** A particular seed value completely determines the sequence of random numbers generated ** by Random. Thus, when debugging your program you may wish to use the same seed value ** each time to force the behaviour of the program to be reproducible. However, you should ** use different seed values for each run of your program when you collect statistics ** for the analysis portion of your report. ** ** If you pass any value other than 0 to RandomSeed, then that number will be used as ** the seed for the random number generator. However, if you call RandomSeed(0), then ** the routine will use the sum of the current time and the process id as the seed value, ** which saves you the trouble of thinking of providing a unique seed each time. ** ** See also: Random */ void RandomSeed( long seed ); /* ** Random: "minimal" random number generator of Park and Miller with Bays-Durham ** shuffle and added safeguards. Returns a uniform deviate between 0.0 and 1.0 ** (exclusive of the endpoint values). ** ** See also: RandomSeed */ float Random( void ); /* ** Generate an exponentially distributed random variable with average ** inter-arrival time t. Note the aerage inter-arrival time is 1/(average rate). */ double ExponentialRandom( double t ); #endif /* _RANDOM_H_ */