#ifndef ECE250
#define ECE250
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#include "Exception.h"
#ifndef nullptr
#define nullptr 0
#endif
/****************************************************************************
* **************************************************************************
* * You don't have to use the Tester classes to use this to manage your
* * memory. All you must do is include this file and then, if you ever
* * want to test if you have memory which is currently unallocated,
* * you may use ece250::allocation_table.summary();
* *
* * You must simply indicate that you want to start recording by
* * using ece250::alocation_table.summary();
* *
* **************************************************************************
****************************************************************************/
/****************************************************************************
* ece250
* Author: Douglas Wilhelm Harder
* Copyright (c) 2006-13 by Douglas Wilhelm Harder and Vajih Montaghami. All rights reserved.
*
* DO NOT EDIT THIS FILE
*
* This file is broken into two parts:
*
* 1. The first namespace ece250 is associated with tools used by the
* second part.
* 2. The second has globally overloaded new, delete, new[], and delete[].
*
* This tracks everything that deals with memory allocation (new and new[])
* and memory deallocation (delete and delete[]).
*
* Each time 'new' or 'new[]' is called, an appropriate entry is
* set in a hash table 'allocation_table'. The hash function of any address
* is the last log[2](array_size) bits.
*
* Each time that 'delete' or 'delete[]' is called, it is checked whether:
* 1. the memory was actually allocated,
* 2. the appropriate form of delete versus delete[] is being called, and
* 3. delete/delete[] has been called multiple times.
*
* The class also stores how much memory was allocated and how much was
* deallocated. The summary() function prints a summary indicating the
* difference. When this is called at the end of a test, the result must
* be zero (0).
*
* If there is a problem with either allocation or deallocation, two events
* occur: a warning is printed and an exception is thrown.
*
* Each throw is associated with a warning sent to the student through cout.
****************************************************************************/
namespace ece250 {
int memory_alloc_store;
const size_t PAD = 16;
class overflow {};
class invalid_deletion {};
class invalid_input {};
// Each time a student calls either new or new[], the
// information about the memory allocation is stored in
// an instance of this class
class Stopwatch {
private:
clock_t start_time;
float duration;
public:
Stopwatch() {
duration = 0;
}
void start() {
start_time = std::clock();
}
void stop() {
clock_t end_time = std::clock();
//this supposed to be milisecond
duration = ((float)end_time - start_time)/CLOCKS_PER_SEC;
}
float get_last_duration() const {
return duration;
}
};
class Allocation {
public:
void *address;
size_t size;
bool is_array;
bool deleted;
Allocation():
address( 0 ),
size( 0 ),
is_array( false ),
deleted( false ) {
// Empty constructor
}
Allocation( void *a, size_t s, bool i ):
address( a ),
size( s ),
is_array( i ),
deleted( false ) {
// Empty constructor
}
};
int to_int( int *ptr ) {
int result = *ptr;
if ( result < 0 ) {
result = result + (1 << (sizeof( int ) - 1));
}
return result >> 3;
}
// All instances of an allocation are stored in this chained hash table
class HashTable {
private:
int array_size;
Allocation *allocated;
int total_memory_alloc;
int total_memory_deleted;
bool record;
public:
// Initialize all of the addresses to 0
HashTable( int as ):
array_size( as ),
total_memory_alloc( 0 ),
total_memory_deleted( 0 ),
record( false ) {
allocated = new Allocation[array_size];
}
void reserve( int N ) {
// N must be a power of 2
if ( (N & ((~N) + 1)) != N ) {
throw illegal_argument();
}
delete [] allocated;
array_size = N;
allocated = new Allocation[array_size];
}
int memory_alloc() const {
return total_memory_alloc - total_memory_deleted;
}
void memory_store() const {
memory_alloc_store = total_memory_alloc - total_memory_deleted;
}
void memory_change( int n ) const {
int memory_alloc_diff = total_memory_alloc - total_memory_deleted - memory_alloc_store;
if ( memory_alloc_diff != n ) {
std::cout << "WARNING: expecting a change in memory allocation of "
<< n << " bytes, but the change was " << memory_alloc_diff
<< std::endl;
}
}
// Insert uses the last log[2]( array_size ) bits of the address as the hash function
// It finds an unallocated entry in the array and stores the information
// about the memory allocation in that entry, including:
// The amount of memory allocated,
// Whether new or new[] was used for the allocation, and
// The address of the allocated memory.
void insert( void *ptr, size_t size, bool is_array ) {
if ( !record ) {
return;
}
// the hash function is the last log[2]( array_size ) bits
int hash = to_int( reinterpret_cast<int *>( &ptr ) ) & (array_size - 1);
for ( int i = 0; i < array_size; ++i ) {
// It may be possible that we are allocated the same memory
// location twice (if there are numerous allocations and
// deallocations of memory. Thus, the second check is necessary,
// otherwise it may introduce session dependant errors.
if ( allocated[hash].address == 0 || allocated[hash].address == ptr ) {
// Store the address, the amount of memory allocated,
// whether or not new[] was used, and set 'deleted' to false.
allocated[hash] = Allocation( ptr, size, is_array );
// Add the memory allocated to the total memory allocated.
total_memory_alloc += size;
return;
}
hash = (hash + 1) & (array_size - 1);
}
std::cout << "WARNING: allocating more memory than is allowed for this project" << std::endl;
throw overflow();
}
// Remove checks:
// If the given memory location was allocated in the first place, and
// If the appropriate form of delete was used, i.e., delete versus delete[], and
// If delete has already been called on this object
size_t remove( void *ptr, bool is_array ) {
if ( !record || ptr == 0 ) {
return 0;
}
// the hash function is the last log[2]( array_size ) bits
int hash = to_int( reinterpret_cast<int *>( &ptr ) ) & ( array_size - 1 );
// Continue searching until we've checked all bins
// or we find an empty bin.
for ( int i = 0; i < array_size && allocated[hash].address != 0; ++i ) {
if ( allocated[hash].address == ptr ) {
// First check if:
// 1. If the wrong delete was called (e.g., delete[] when new was
// used or delete when new[] was used).
// 2. If the memory has already been deallocated previously.
//
// If the deletion is successful, then:
// 1. Set the 'deleted' flag to 'true', and
// 2. Add the memory deallocated ot the total memory deallocated.
if ( allocated[hash].is_array != is_array ) {
if ( allocated[hash].is_array ) {
std::cout << "WARNING: use 'delete [] ptr;' to free memory allocated with 'ptr = new Class[array_size];'" << std::endl;
} else {
std::cout << "WARNING: use 'delete ptr;' to free memory allocated with 'ptr = new Class(...);'" << std::endl;
}
throw invalid_deletion();
} else if ( allocated[hash].deleted ) {
std::cout << "WARNING: calling delete twice on the same memory location: " << ptr << std::endl;
throw invalid_deletion();
}
allocated[hash].deleted = true;
total_memory_deleted += allocated[hash].size;
// zero the memory before it is deallocated
char *cptr = static_cast<char *>( ptr );
for ( size_t j = 0; j < allocated[hash].size; ++j ) {
cptr[j] = 0;
}
return allocated[hash].size;
}
hash = (hash + 1) & (array_size - 1);
}
// If we've gotten this far, this means that the address was
// never allocated, and therefore we are calling delete on
// something which should be deleted.
std::cout << "WARNING: deleting a pointer to which memory was never allocated: " << ptr << std::endl;
throw invalid_deletion();
}
// Print a difference between the memory allocated and the memory deallocated
void summary() {
std::cout << "Memory allocated minus memory deallocated: "
<< total_memory_alloc - total_memory_deleted << std::endl;
}
// Print the difference between total memory allocated and total memory deallocated.
void details() {
std::cout << "SUMMARY OF MEMORY ALLOCATION:" << std::endl;
std::cout << " Memory allocated: " << total_memory_alloc << std::endl;
std::cout << " Memory deallocated: " << total_memory_deleted << std::endl << std::endl;
std::cout << "INDIVIDUAL REPORT OF MEMORY ALLOCATION:" << std::endl;
std::cout << " Address Using Deleted Bytes " << std::endl;
for ( int i = 0; i < array_size; ++i ) {
if ( allocated[i].address != 0 ) {
std::cout << " " << allocated[i].address
<< ( allocated[i].is_array ? " new[] " : " new " )
<< ( allocated[i].deleted ? "Y " : "N " )
<< std::setw( 6 )
<< allocated[i].size << std::endl;
}
}
}
// Start recording memory allocations
void start_recording() {
record = true;
}
// Stop recording memory allocations
void stop_recording() {
record = false;
}
bool is_recording() {
return record;
}
};
bool asymptotic_tester( double *array, int N, int k, bool ln ) {
double *ratios = new double[N];
double *differences = new double[N- 1];
int M = 2;
for ( int i = 0; i < N; ++i ) {
ratios[i] = array[i] / (M*(ln ? std::log( static_cast<double>( M ) ) : 1.0));
M = M*(1 << k);
}
for ( int i = 0; i < N - 1; ++i ) {
differences[i] = ratios[i + 1] - ratios[i];
// std::cout << differences[i] << std::endl;
}
for ( int i = 1; i < N - 1; ++i ) {
if ( !( differences[i] < 0 ) ) {
if ( differences[i] > differences[i - 1] ) {
delete [] ratios;
delete [] differences;
return false;
}
}
}
delete [] ratios;
delete [] differences;
return true;
}
HashTable allocation_table( 8192 );
std::string history[1000];
int count = 0;
// Set the contents of the allocated memory to alternating 0s and 1s
// 'U' = 0b01010101
// Four bytes are therefore 0x55555555 or 1431655765
//
// Sixteen bytes before and after the requested memory are also allocated and initialized.
// ________________ ________________
// UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
void initialize_array_bounds( char *ptr, size_t size ) {
std::memset( ptr, 'U', size );
}
// When the user returns memory, we must check that the padding is unchaged.
// ________________ ________________
// UUUUUUUUUUUUUUUUxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxUUUUUUUUUUUUUUUU
// We also check that the memory has been used--if allocated memory is left untouched,
// there was an unnecessary allocation of memory.
//
// Finally, we reset all the entries to 'U' to ensure that if the user attempts to
// access this memory again, an error will occur.
// ________________ ________________
// UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
void check_array_bounds( char *ptr, size_t size ) {
for ( size_t i = 0; i < PAD; ++i ) {
if ( ptr[i] != 'U' ) {
std::cout << "Memory before the array located at adderss "
<< static_cast<void *>( ptr + PAD ) << " was overwritten" << std::endl;
throw out_of_range();
}
if ( ptr[size - 1 - i] != 'U' ) {
std::cout << "Memory after the array located at adderss "
<< static_cast<void *>( ptr + PAD ) << " was overwritten" << std::endl;
throw out_of_range();
}
}
bool used = false;
for ( size_t i = 0; i < size - 2*PAD; ++i ) {
if ( ptr[PAD + i] != 'U' ) {
used = true;
break;
}
}
if ( !used ) {
std::cout << "The memory allocated at adderss "
<< static_cast<void *>( ptr + PAD ) << " was not used" << std::endl;
}
std::memset( ptr, 'U', size );
}
// Type input<Type>()
//
// Attempt to parse the input as if it is of the given Type
// - If it fails, it prints an error message and throws an exception
template <typename Type>
Type input() {
std::string s;
std::cin >> s;
std::stringstream ss( s );
Type n;
ss >> n;
if ( ss.fail() ) {
std::cerr << "Not expecting the input \"" << s << "\"" << std::endl;
throw invalid_input();
}
return n;
}
// bool input<bool>()
//
// This is a specialization of the input function for Boolean values
// - It will accept the strings 'true' and 'false' as well as 1 and 0
// - If it fails, it prints an error message and throws an exception
template <>
bool input<bool>() {
std::string s;
std::cin >> s;
std::stringstream ss( s );
if ( s == "true" ) {
return 1;
} else if ( s == "false" ) {
return 0;
} else {
bool n;
ss >> n;
if ( ss.fail() ) {
std::cerr << "Not expecting the input \"" << s << "\"" << std::endl;
throw invalid_input();
}
return n;
}
}
}
/****************************************************************************
* new
* Author: Douglas Wilhelm Harder
* Overloads the global operator new
*
* Use malloc to perform the allocation.
* Insert the pointer returned by malloc into the hash table.
*
* The argument 'false' indicates that this is a call
* to new (versus a call to new[]).
*
* Return the pointer to the user.
****************************************************************************/
void *operator new( size_t size ) throw( std::bad_alloc ) {
void *ptr = malloc( size );
ece250::allocation_table.insert( ptr, size, false );
return static_cast<void *>( ptr );
}
/****************************************************************************
* delete
* Author: Douglas Wilhelm Harder
* Overloads the global operator delete
*
* Remove the pointer from the hash table (the entry is not truly removed,
* simply marked as removed).
*
* The argument 'false' indicates that this is a call
* to delete (versus a call to delete[]).
*
* Use free to perform the deallocation.
****************************************************************************/
void operator delete( void *ptr ) throw () {
ece250::allocation_table.remove( ptr, false );
free( ptr );
}
/****************************************************************************
* new[]
* Author: Douglas Wilhelm Harder
* Overloads the global operator new[]
*
* Use malloc to perform the allocation.
* Insert the pointer returned by malloc into the hash table.
*
* The argument 'true' indicates that this is a call
* to new[] (versus a call to new).
*
* Return the pointer to the user.
****************************************************************************/
void *operator new[]( size_t size ) throw( std::bad_alloc ) {
char *ptr = static_cast<char *>( malloc( size + 2*ece250::PAD ) );
ece250::allocation_table.insert( static_cast<void *>( ptr + ece250::PAD ), size, true );
ece250::initialize_array_bounds( ptr, size + 2*ece250::PAD );
return static_cast<void *>( ptr + ece250::PAD );
}
/****************************************************************************
* delete[]
* Author: Douglas Wilhelm Harder
* Overloads the global operator delete[]
*
* Remove the pointer from the hash table (the entry is not truly removed,
* simply marked as removed).
*
* The argument 'true' indicates that this is a call
* to delete[] (versus a call to delete).
*
* Use free to perform the deallocation.
****************************************************************************/
void operator delete[]( void *ptr ) throw () {
size_t size = ece250::allocation_table.remove( ptr, true );
if ( ece250::allocation_table.is_recording() ) {
ece250::check_array_bounds( static_cast<char *>( ptr ) - ece250::PAD, size + 2*ece250::PAD );
}
free( static_cast<char *>( ptr ) - ece250::PAD );
}
#endif