<repo_name>ashvi23/My-Malloc<file_sep>/memgrind90noprint.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "mymalloc.c"
#include "mymalloc.h"
#define malloc(x) mymalloc(x,__FILE__,__LINE__)
#define free(x) myfree(x,__FILE__,__LINE__)

int main (int argc, char**argv){
time_t starttime;
time_t endtime;
double difference=0;
double sumtimeA=0;
double sumtimeB=0;
double sumtimeC=0;
double sumtimeD=0;
double sumtimeE=0;
double sumtimeF=0;
int* ptrarr2[150];
srand(time(NULL));
// case a
time(&starttime);//get time at start
int i=0;
for( i =0 ; i< 150; i++){
  ptrarr2[i] = (int*) malloc(1);
  free(ptrarr2[i]);
ptrarr2[i] = NULL;
}
time(&endtime);//get time at end
difference=difftime(endtime, starttime);//save runtime of iteration
sumtimeA+=difference;
printf("case a done\n");
//case b
int *ptrarr[50];
int malcounter=0;
int *ptr;
time(&starttime);//get time at start
int x ;
for(x =0; x<3; x++){
for(i =0; i< 50; i++){
  ptr = (int*) malloc(1);
  ptrarr[i] =ptr;
  malcounter++;
  if(malcounter == 50){
    int j;
    for (j =0; j<malcounter;j++ ){
      free(ptrarr[j]);
      ptrarr[j]=NULL;
  }
  malcounter =0;
}
}
}
time(&endtime);//get time at end
difference=difftime(endtime, starttime);//save runtime of iteration
sumtimeB+=difference;

// case c
malcounter = 0;
int freedptr = 0;
int ptr2free =-1;
int freeindex =0;
int* pointers[50];
int mallocindex =0;
int random;
time(&starttime);//get time at start
  while(malcounter <=50){
   random = rand()%2;
    if(random == 0){ //malloc if 0
      pointers[mallocindex] = (int*)malloc(1);
      malcounter++;
      mallocindex++;
      ptr2free =malcounter - freedptr;
    }
    else if (random == 1){ // free if 1
      if (ptr2free != 0 && malcounter!=0){
        free(pointers[freeindex]);
        pointers[freeindex] = NULL;
        ++freeindex;
        ++freedptr;
        ptr2free =malcounter - freedptr;
      }
    }
    if(malcounter == 50){
    break;
  }
   
    }
  //  if (malcounter == 50){
      while(ptr2free!= 0){
        free(pointers[freeindex]);
        pointers[freeindex] = NULL;
        ++freedptr;
        ++freeindex;
        ptr2free= malcounter-freedptr;
      }
   //}
time(&endtime);//get time at end
difference=difftime(endtime, starttime);//save runtime of iteration
sumtimeC+=difference;


  //case d
  int memleft=4092;  //the amount of memory left
  int memalloc =0; // the total of memory that is currently allocated
  int* pointers2[50]; // pointer array to all of allocations
  freedptr=0; //amount of pointers that have been freed
  freeindex=0; // index to free at, starts at 0 and frees sequentially. used for pointers2
  malcounter=0; // amount of times malloc has been called
  ptr2free =-1; // amount of pointers left to free
  mallocindex=0; // where to store the next mallocd pointer in pointers2
  int memarr[50];// stores the amount of memory mallocd on each malloc
time(&starttime);//get time at start
while(malcounter<=50){
 if (memleft >0){
    random = rand()%2;
    if(random ==0){// malloc if even
      random = rand();
      while(random < 1 || random > 64){
        random = rand();
        if (random <=64 && random >= 1){
          break;
        }
      }
      if(memleft >=random){
        pointers2[mallocindex]= (int*)malloc(random);
        memarr[mallocindex] = random;
        memalloc +=random;
        mallocindex++;
        malcounter++;
        memleft-=random;
      }
    }
    else if (random ==1){//free if odd
      if(ptr2free!=0&& malcounter!=0){
        free(pointers2[freeindex]);
        memalloc = memalloc - memarr[freeindex];
        freeindex++;
        freedptr++;
        ptr2free = malcounter-freedptr;
        memleft = 4092- memalloc;
        }
    }
  }
  if (malcounter ==50){
    break;
  }
}
//if(malcounter ==50){
  while(freeindex <=50){
    free(pointers2[freeindex]);
    freedptr++;
    ptr2free = malcounter -freedptr;
    memalloc = memalloc - memarr[freeindex];
    freeindex++;
    memleft = 4092- memalloc;
    
    if(ptr2free == 0){
      break;
    }
   }

time(&endtime);//get time at end
difference=difftime(endtime, starttime);//save runtime of iteration
sumtimeD+=difference;

int *fiboptrArr[100];
int prevprev=0;
int prev=1;
int sum=0;
int totalmem=0;
int index=0;
//case E
while(totalmem<(4092/2)){
  sum=prevprev+prev;
  fiboptrArr[index]= (int*)malloc(sum);
  prevprev=prev;
  prev=sum;
  totalmem+=(sum+2);
  index++;
}
  fiboptrArr[index]= (int*)malloc(prevprev);
  totalmem+=(prevprev+2);
  index++;
while(totalmem+(prev-prevprev)<(4092)&& sum>1){
  sum=prev-prevprev;
  fiboptrArr[index]= (int*)malloc(sum);
  prev=prevprev;
  prevprev=sum;
  totalmem+=(sum+2);
  index++;
}

for(i=index-1; i>=0; i--){
  free(fiboptrArr[i]);
}
  int* alternptrArr[250];
  index=0;
  random=0;
  while(sum<=4092 && index<250){
    if((index/4)==0){
      free(alternptrArr[index-1]);//every third element gets freed
      alternptrArr[index-1]=NULL;
      }
    random=abs(rand()%64);
    alternptrArr[index]=(int*)malloc(random);
    index++;
    sum+=random+2;
  }
  for(i=0; i<250; i++){
    if(alternptrArr[i]!=NULL){
    free((alternptrArr[i]));
    }
  }
//print mean times
printf("Mean time of protocol A was %lf\n", (sumtimeA/100));
printf("Mean time of protocol B was %lf\n", (sumtimeB/100));
printf("Mean time of protocol C was %lf\n", (sumtimeC/100));
printf("Mean time of protocol D was %lf\n", (sumtimeD/100));
printf("Mean time of protocol E was %lf\n", (sumtimeE/100));
printf("Mean time of protocol F was %lf\n", (sumtimeF/100));
return 0;
}

<file_sep>/splitBlock.c
unsigned char* splitBlock(unsigned char* curr, int blockSize, int dataSize){
     unsigned char* hi=curr;
     unsigned char* lo=curr+1;
     setBlock(1, *hi);
      if((blockSize-3)>dataSize){//if block can fit at least two bytes of free space, including metadata, make free space
          splitBin(dataSize, hi, lo);//set curr's size to the size of data requested (truncating it)
          hi=curr+dataSize+2;//iterate our new pointers along
          lo=hi+1;
          blockSize=blockSize-dataSize-2;//blocksize of free block created when you allocate less than space in curr block
          *hi=0;//zero out  garbage vals in these bytes
          *lo=0;
          splitBin(blockSize, hi, lo);//set metadata for new metadata block
          setBlock(0, *hi);
      }
      return curr;//curr was never iterated so we can return it as-is
}
<file_sep>/mymalloc.h
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define malloc(x) mymalloc(x,__FILE__,__LINE__)
#define free(x) myfree(x,__FILE__,__LINE__)
#define KEY 11474

    char myMem[4096];
    void* mymalloc(int, char *filename, int linenum);
    void myfree(void*, char *filename, int linenum);
    int bitadd(unsigned char high11, unsigned char low11, unsigned char high22, unsigned char low22);
    int bitsub(unsigned char high11, unsigned char low11, unsigned char high22, unsigned char low22);
    void combineBoth(char* prev, char* curr, char* next);
    void combineNext(char* curr, char* next);
    void combinePrev(char* curr, char* prev);
    int getbit(int num, int position);
    char getsizebits(char bits);
    int bin2int(char highbyte, char lowbyte);
    char* mallocTraverse(char* curr, int dataSize);
    void setInUse(int inUse, char* hiMeta);
    void splitBin(unsigned int currInt, char* hiMeta, char* loMeta);
    char* splitBlock(char* curr, int blockSize, int dataSize);
    char* bootStrap(char* ptr, char* hi, char* lo, int usrBlock);//set key, initialize first metadata
	void printBin(char hi, char lo);
<file_sep>/free.c
#include <stdlib.h>
#include <stdio.h>


char* firstmeta = mem[2];
char* firstMallocPtr = mem[4];
char*lastaddress = mem[4095];
void combineNext(unsigned char* curr, unsigned char* next){
	int nextinusebit = getbit(*next, 1);
	if (nextinusebit == 0){
		unsigned char currlowbits = *(curr+1);
		unsigned char nextlowbits = *(next+1);
		printf("Starting combining process. \n");
		int sum= bitadd(*curr, currlowbits, *next, nextlowbits);
		splitBin(sum, curr, curr+1);
		setInUse(0, curr);
		printf("Curr and Next combined.\n");
	}
	else if (nextinusebit ==1){
		printf("Can't Combine. Next is in use.\n");
	}
}
void combinePrev(unsigned char* curr, unsigned char* prev){
	int previnusebit = getbit(*prev, 1);
	if (previnusebit == 0){
		unsigned char currlowbits = *(curr+1);
		unsigned char prevlowbits = *(prev+1);
		printf("Starting combining process. \n");
		int sum= bitadd( *prev, prevlowbits, *curr, currlowbits);
		splitBin(sum, curr, curr+1);
		setInUse(0, prev);
		printf("Curr and Prev combined.\n");
	}
	else if (previnusebit ==1){
		printf("Can't Combine. Next is in use.\n");
	}
}
void combineBoth(unsigned char* prev, unsigned char* curr, unsigned char* next){
	int nextinuse = getbit(*next, 1);
	int previnuse = getbit(*prev, 1);
	if (nextinuse == 0){
	combineNext(curr, next);
	}
	if (previnuse == 0){
	combinePrev(curr, prev);
	}
}

/*
in main:
//key = 11474
unsigned char lowbits = *(curr-1);
unsigned char highbits = *(curr -2);
int checkKey = bin2int(highbits, lowbits);

if (checkKey == 11474){
	combineRight(curr, curr+1+currsize);
}




*/


/*
  - prev = inuse curr next = inuse
  - prev = !inuse curr next = inuse
  - prev = !inuse curr next = !inuse
  - prev = inuse curr next = !inuse

  check left
  if prev = free
  extract 16-1 rightmost bits (the size bits) on curr
  bin2int size bits on curr
  extract size bits from prev
  bin2int size bits on prev
  bitadd prevsize curr size
  int2bin sum
  change prev ptr size to sum bits
  set char ptr curr in use bit to 0

  check right
  if prev! freeblocks
  check if curr + metadata at(currsize + sizeof(metadata)) is free
  extract 16-1 rightmost bits (the size bits) on curr
  bin2int size bits on curr
  extract size bits from prev
  bin2int size bits on prev
  bitadd prevsize curr size
  int2bin sum
  change prev ptr size to sum bits
  set char ptr curr in use bit to 0

  if left in use and right in Use
    do nothing. there is nothing to combine.

  */


/*
unsigned char* mallocTraverse(unsigned char* curr, int dataSize){
    *curr=myMem[2];
    while(curr>=lowerBound && curr<=upperbound){//lowerBound & upperBound will be global vars
      int currMeta=bin2int(*curr, *(curr+1));
      int inUse=getbit(currMeta, 15);//hopefully this works
      char hiBits=getsizeBits(*curr);//blocking out in use bit
      int currBlockSize=(hiBits, *(curr+1));//getting block size of current block
      if(inUse==0 && currBlockSize>=dataSize){
            //call split fxn
      } else{
          curr=(curr+currBlockSize);
      }
    }
    printf("Memory full\n");
    return NULL;
}

*/
checkptr(){
/*
checks if the pointer given to free is a valid ptr pointing at the start of block
while()
*/


}

void myfree(void *tofree, char*file, int*linenum){
	tofree = (char*) tofree;
	if (tofree == NULL){
	printf("Error in %s line %d: Pointer received is NULL. \n", file, linenum);
	}
	if (ismeminit = 0){
	printf("Error in %s line %d: Nothing malloc'd yet\n", file, linenum);
	}
	if(tofree<=lowerBound || tofree>upperbound){
	printf("Error in %s line %d: Pointer is not in range of memory\n", file, linenum);
	}
	if(tofree>firstmeta && tofree<=lastaddress){

		char *curr = firstmeta;
		char *prev = NULL;
		char *next = NULL;

		while(curr < lastaddress ){
			unsigned char currsizebits = getsize(curr);
			int currsize = bin2int(currsizebits, curr+1);

			if ((curr+2) > tofree){   // pointer is not pointing at the starting address of a block
				printf("Error in %s line %d: Pointer is not the one given by malloc\n", file, linenum);
				break;
			}
			if(curr+2 == tofree){
				int isValid = getbit(curr, 1); //get inuse bit
				if (isValid == 0){  // address already freed
					printf("Error in %s line %d: Pointer is already freed.\n", file, linenum);
					break;
				}
				else if (isValid == 1){ //this pointer can be freed
					//free inuse bit, combine block
					setInUse(0, curr);
					// check if curr is the first and last block (only block)
					if ((curr+1+currsize) == lastaddress && prev == NULL){
						setInUse(0, curr);
						break;
					}
					// check if prev is null / curr is first block
					else{
						if (prev == NULL){
							next = (curr+1+currsize);
							combineNext(curr, next);
							break;
						}
					// check if curr is the last block / there is no next block
						if((curr+1+currsize) == lastaddress){
							combinePrev(curr, prev);
							break;
						}
					// else combine both
						else if((curr+1+currsize) < lastaddress && prev!=NULL){
							next = (curr+1+currsize);
							combineBoth(prev, curr, next);
							break;
						}
					}
					//break;
				}

			}
			//update pointers

			prev = curr;
			curr = curr+1+currsize;
		}
	}

}
<file_sep>/bin2int.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//#include<stdbool.h>
#define KEY 0010110011010010
/*
CONTAINS: getbit, setbit, bin2int, bitadd, bitsub, getsizebits
*/
int bin2int(unsigned char, unsigned char);
int getbit(int , int);
//int adding(unsigned char, unsigned char, unsigned char, unsigned char);
//int bitsub(unsigned char, unsigned char, unsigned char, unsigned char);
unsigned char getsizebits(bits);

//send in the whole byte. returns size bits.
unsigned char getsizebits(unsigned char bits){
	unsigned char sizebits, mask;
	mask = (1 << 7) -1;
	sizebits = bits & mask;
	return sizebits;
}

/*
send in high and low bytes for the meta data you want to add TO   (highleva2, lowleva2)   send in metadata bytes for the meta data you have to add (the one youre gonna free)
bit add will call a method to retreive the size bits from the whole bytes and then send that to bin2int and then add+return the resulting ints' sum
*/
int bitadd(unsigned char high11, unsigned char low11, unsigned char high22, unsigned char low22){
	unsigned char high1, high2;
	high1 = getsize(high11);
	//low1 = getsize(low11);
	high2 = getsize(high22);
	//low2 = getsize(low22);
	int add2 = bin2int(high1, low11);
	int add1 = bin2int(high2, low22);
	int sum = add2+add1;
	return sum;
}
/*
look at notes for bit add, does the same thing. highlevel/lowlevel subfrom should be the bigger number you subtract FROM
bitsub will follow same procedure as bitadd, dont forget to call split in mymalloc()
call method that retrieves the size bits.
 */
int bitsub(unsigned char high11, unsigned char low11, unsigned char high22, unsigned char low22){
	unsigned char high1, high2;
	high1 = getsize(high11);
	//low1 = getsize(low11);
	high2 = getsize(high22);
	//low2 = getsize(low22);
	int subfrom = bin2int(high1, low11);
	int tosub = bin2int(high2, low22);
	int sum = subfrom-tosub;
	return sum;
}

int getbit(int num, int position){   //WORKS
	int bitstate = (num >> position) &1;
	return bitstate;
}

/*
MUST SEND IN SIZE BYTES ONLY
this method will NOT take inuse bit into account when converting.
getbit will give you the bit at any given position
send in the lowlevel and high level bits you want to convert into ints, will return the int
*/
int bin2int(unsigned char highbyte, unsigned char lowbyte){  //WORKS
 	int j =0;
	int i=0;
	char binarr[15];
	  for(i = 7; i>=0; i--){
		binarr[i] = getbit(highbyte, j);
		j++;
	  }
	  j=0;
	  for(i = 15; i>= 8; i--){
		binarr[i] = getbit(lowbyte, j);
		j++;
	  }
	  //bin arr gives you full binary array ex. byte holds 14 -> binarr = [0,0,0,0,0,0,0,0,1,1,1,0]
	  j = 0;
	  int sum = 0;
	  // this loop goes through binarr and calculate 2^binarr[i] power and sums it to give you the final int. starts at 2^0 (binarr[15])
	  for(i =15; i>=0; i-- ){
		int bin = binarr[i];
		if(bin == 0){
		  j++;
		}
		else if (bin == 1){
		  sum += pow(2, j);
		  j++;
		}
	  }
	  return sum;
}

int main (int argc, char**argv){
	unsigned char high= 0b0000001;
	unsigned char low = 0b00001111;
	int f = bin2int(high, low);
	printf("INT : %d", f);
	unsigned char high2= 0b0000000;
	unsigned char low2 = 0b00001111;
	int added = bitadd(high, low, high2, low2);
	printf("sum : %d \n", added);
	int subtracted = bitsub(high, low, high2, low2);
	printf("subtracted : %d\n", subtracted);
	return 0;
}
<file_sep>/mallocfinal.c
#include "mymalloc.h"

void* mymalloc(int size, char *filename, int linenum){
  char* first=&(myMem[0]);
  char* second=&(myMem[1]);
  char* ptr= &(myMem[0]);
  int usrBlock=4092;//size of arr-metadata bits- size of key
  int firstBytes=bin2int(*first, *second);
  if(firstBytes!=KEY){//set key to initialize method
    ptr=bootStrap(ptr, first, second, usrBlock);//set key, initialize first metadata
  
  }
  
  if(size>usrBlock || size<=0){//if user tries to allocate more memory than size of array/metadata/key allows for, or a negative value
      if(size>usrBlock){
      printf("Memory request exceeds size of working memory in file %s at line %d\n", __FILE__, __LINE__);
      return NULL;
    } else{
      printf("Invalid memory request in file %s at line %d\n", __FILE__, __LINE__);
    }
  }else{
    ptr=mallocTraverse(ptr, size);//calling the meat of the program, returns either a pointer to usable memory or a null pointer

}
  return (void*)ptr;
}

void myfree(void *tofree, char *filename, int linenum){
	char* firstmeta = &(myMem[2]);
	tofree = (char*) tofree;
	char* first=&(myMem[0]);//set pointer to first index of arr
	char* second=&(myMem[1]);//set pointer to second byte of arr
	int firstbytes=bin2int(*first, *second);
	if ((char*)tofree == NULL){
	printf("Error in %s line %d: Pointer received is NULL. \n", __FILE__, __LINE__);
	return;
	}
	if(firstbytes!= KEY){
	printf("Error in %s line %d: Nothing malloc'd yet\n", __FILE__, __LINE__);
	return;
	}
	if((char*)tofree<(char*)(&(myMem[2])) || (char*)tofree>(char*)(&(myMem[4095]))){
	printf("Error in %s line %d: Pointer is not in range of memory\n", __FILE__, __LINE__);
	return;
	}
	if((char*)tofree>=(char*)(&(myMem[2])) && (char*)tofree<=(char*)(&(myMem[4095]))){
		char *curr = firstmeta;
		char *prev = NULL;
		char *next = NULL;
		//traversal
		while(curr <= (&(myMem[4095]))){
			char currsizebits = getsizebits(*(curr));
			int currsize = bin2int(currsizebits, *(curr+1));
			
			if ((char*)(curr+2) > (char*)tofree){   // pointer is not pointing at the starting address of a block
				printf("Error in %s line %d: Pointer is not the one given by malloc\n", __FILE__, __LINE__);
				return;
			}
			else if((char*)(curr+2) == tofree){
		
				int isValid = getbit(*(curr), 15); //get inuse bit
			
				if (isValid == 0){  // address already freed
					printf("Error in %s line %d: Pointer is already freed.\n", __FILE__, __LINE__);
					return;
					
				}
				else if (isValid == 1){ //this pointer can be freed
					//free inuse bit, combine block
					setInUse(0, curr);
					// check if curr is the first and last block (only block)
					if ((curr+1+currsize) == (&(myMem[4095])) && prev == NULL){
						setInUse(0, curr);
						return;
					}
					// check if prev is null / curr is first block
					else{
						if (prev == NULL){
							next = (curr+2+currsize);
							combineNext(curr, next);
							return;
						}
						if((curr+1+currsize) == (&(myMem[4095]))){
							combinePrev(curr, prev);
							break;
						}
						else{
							next = (curr+2+currsize);
							combineBoth(prev, curr, next);
							break;
						}
						
					}
				}

			}
			//update pointers
			prev = curr;
			curr = (char*)(curr+2+currsize);
			if ((char*)(curr+2) > (char*)tofree){   // pointer is not pointing at the starting address of a block
				printf("Error in %s line %d: Pointer is not the one given by malloc\n", __FILE__, __LINE__);
				return;
			}

		}
	}
}

char* splitBlock(char* curr, int blockSize, int dataSize){
     char* hi=curr;
     char* lo=curr+1; 
      if((blockSize-3)>dataSize){//if block can fit at least two bytes of free space, including metadata, make free space
         splitBin(dataSize, hi, lo);//set curr's size to the size of data requested (truncating it)
    	 setInUse(1, hi);
          hi=curr+dataSize+2;//iterate our new pointers along
          lo=hi+1;
          blockSize=blockSize-dataSize-2;//blocksize of free block created when you allocate less than space in curr block
          *hi=0;//zero out  garbage vals in these bytes
          *lo=0;
          splitBin(blockSize, hi, lo);//set metadata for new metadata block
          setInUse(0, hi);
      }else{
      	 splitBin(blockSize, hi, lo);
     	 setInUse(1, hi);
      }
      return curr;//curr was never iterated so we can return it as-is
}

void splitBin(unsigned int currInt, char* hiMeta, char* loMeta){
  *hiMeta=0;
  *loMeta=0;
  int i =0;
  unsigned int mask=0;
  unsigned int currBit=0;
  for(i=15; i>=0; i--){
    mask=0;
    currBit=currInt>>i;
    if(i<=7){
        mask=1<<(i);
        *loMeta=(*loMeta & ~mask) | ((currBit << i) & mask);
    } else{
      mask=1<<(i-8);
      *hiMeta=(*hiMeta & ~mask) | ((currBit << (i-8)) & mask);
    }
  }
    return;
}
 char* bootStrap(char* ptr, char* hi, char* lo, int usrBlock){
    hi=ptr;//set key
    lo=ptr+1;
    splitBin(KEY, hi, lo);
    hi=ptr+2;//initialize metadata after key
    lo=hi+1;
    *hi=0;
    *lo=0;
    splitBin(usrBlock, hi, lo);//set metadata for new metadata block
    setInUse(0, hi);
    return hi;
}
/*sets the in use bit , takes in an integer (functioning as a boolean), to tell it whether to assign the val to be either 1 or 0*/
void setInUse(int inUse, char* hiMeta){
    unsigned int mask=1<<7;
    unsigned int currBit=0;
  if(inUse==0){
    *hiMeta=(*hiMeta & ~mask) | ((currBit) & mask);
  } else if(inUse==1){
        currBit=1<<7;
        *hiMeta=(*hiMeta & ~mask) | ((currBit) & mask);
  }
    return;
}

char* mallocTraverse(char* curr, int dataSize){
	curr=&(myMem[2]);
    *curr=myMem[2];
    while(curr>=(&(myMem[2])) && curr<(&(myMem[4095]))){//lowerBound & upperBound will be global vars
      int currMeta=bin2int(*curr, *(curr+1));//converting chars to an int to send to getbit
      int inUse=getbit(currMeta, 15);//getting the in use bit
    
      char hiBits=getsizebits(*curr);//blocking out in use bit to get size of block
      int currBlockSize=bin2int(hiBits, *(curr+1));//getting block size of current block
      if(inUse==0 && currBlockSize>=dataSize){//if there's enough space to return to the user
   
          curr=splitBlock(curr, currBlockSize, dataSize);//prepare it to return
          return curr+2;//return pointer to actual data block, not trying to overwrite metadata
      	  break;
      } 
      else{
          curr=(curr+2+currBlockSize);
      }
    }
    /* got to end of array without finding an empty block */
    printf("Memory request exceeds size of working memory in file %s at line %d\n", __FILE__, __LINE__);
    return NULL;
}

// methods for free: 

int bin2int(char highbyte, char lowbyte){ 
 	int j =0;
	int i=0;
	char binarr[15];
	  for(i = 7; i>=0; i--){
		binarr[i] = getbit(highbyte, j);
		j++;
	  }
	  j=0;
	  for(i = 15; i>= 8; i--){
		binarr[i] = getbit(lowbyte, j);
		j++;
	  }
	  //bin arr gives you full binary array ex. byte holds 14 -> binarr = [0,0,0,0,0,0,0,0,1,1,1,0]
	  j = 0;
	  int sum = 0;
	  // this loop goes through binarr and calculate 2^binarr[i] power and sums it to give you the final int. starts at 2^0 (binarr[15])
	  for(i =15; i>=0; i-- ){
		int bin = binarr[i];
		if(bin == 0){
		  j++;
		}
		else if (bin == 1){
		  sum += pow(2, j);
		  j++;
		}
	  }
	  return sum;
}

char getsizebits(char bits){
	char sizebits, mask;
	mask = (1 << 7) -1;
	sizebits = bits & mask;
	return sizebits;
}

int getbit(int num, int position){   //WORKS
	int bitstate = (num >> position) &1;
	return bitstate;
}

int bitadd(unsigned char high11, unsigned char low11, unsigned char high22, unsigned char low22){
	char high1, high2;
	high1 = getsizebits(high11);
	high2 = getsizebits(high22);
	int add2 = bin2int(high1, low11);
	int add1 = bin2int(high2, low22);
	int sum = add2+add1;
	return sum;
}

void combineNext(char* curr, char* next){
	int nextinusebit = getbit(*next, 7);
	if (nextinusebit == 0){
		char currhibits=getsizebits(*curr);
	    char nexthibits=getsizebits(*next);
		int currNum=bin2int(currhibits, *(curr+1));
		int nextNum=bin2int(nexthibits,*(next+1));
		int sum= bitadd(*curr, currlowbits, *next, nextlowbits);
		sum = sum+2; // add next's meta data 
		splitBin(sum, curr, curr+1);
		setInUse(0, curr);
	}
	
}
void combinePrev(char* curr, char* prev){
	int previnusebit = getbit(*prev, 7);
	if (previnusebit == 0){
		int sum= bitadd( *prev, *(prev+1), *curr,*(curr+1));
		sum = sum+2;
		splitBin(sum, prev, prev+1);
		setInUse(0, prev);
	}

}
void combineBoth(char* prev, char* curr, char* next){
	int nextinuse = getbit(*next, 7);
	int previnuse = getbit(*prev, 7);
	if (nextinuse == 0){
	combineNext(curr, next);
	}
	if (previnuse == 0){
	combinePrev(curr, prev);
	}	
}
<file_sep>/splitBin.c
#include <stdio.h>
#include <stdlib.h>
void splitBin(unsigned int currInt, unsigned char* hiMeta, unsigned char* loMeta);
void printBin(unsigned char hi, unsigned char lo);
void printSingleBin(unsigned char byte);
void printBinInt(unsigned int val);
void setInUse(int inUse, unsigned char* hiMeta);
int main(int argc, char** argv){
  unsigned int input=93;
  unsigned char hi='0';
  unsigned char lo='0';
printf("begin: \n");
printBin(hi, lo);
  unsigned char* ptrhi=&hi;
  unsigned char* ptrlo=&lo;
  splitBin(input, ptrhi, ptrlo);
printf("high: ");
printSingleBin(hi);
printf("low: ");
printSingleBin(lo);
  setInUse(0, ptrhi);
  printf("calling printBin: \n");
  printBin(hi, lo);
  return 0;
}
/*
it effectively works like a function to set size metadata
use after int arithmetic to save new sum to metadata chars
send in an int, this extracts the bits from it and directly inserts them into the meta data chars using the given high and low byte pointers to the metadata -> int holds 615 (equiv.: 0000001001100111): *hiMeta:00000010 	*loMeta: 01100111
(as of right now it deletes the value in the 'in use' bit when assigning the new val to the chars)
*/
void splitBin(unsigned int currInt, unsigned char* hiMeta, unsigned char* loMeta){
  *hiMeta=0;
  *loMeta=0;
printf("currInt: ");
printBinInt(currInt);
  unsigned int mask=0;
  unsigned int currBit=0;
  for(int i=11; i>=0; i--){
    printf("i: %d \n", i);
    mask=0;
    currBit=currInt>>i;
    if(i<=7){
        mask=1<<(i);
        *loMeta=(*loMeta & ~mask) | ((currBit << i) & mask);
    } else{
      mask=1<<(i-8);
      *hiMeta=(*hiMeta & ~mask) | ((currBit << (i-8)) & mask);
    }
    		printf("currBit ");
		printBinInt(currBit);
		printf("mask: ");
		printBinInt(mask);
		printf("at %d: ", i);
		printBin(*hiMeta, *loMeta);

  }
    return;
}
void printBin(unsigned char hi, unsigned char lo){
	int shift=0;
	int currBit=0;
	for(int i=15; i>=0; i--){
		if(i>7){
			shift=(i-8);
			currBit=hi>>shift;
		} else{
			shift=i;
			currBit=lo>>shift;
			}
	if(currBit & 1){
		printf("1");
		}else{
			printf("0");
			}
	}
		printf("\n");
	return;
}
void printBinInt(unsigned int val){
	int shift=0;
	int currBit=0;
	for(int i=31; i>=0; i--){
	shift=i;
	currBit=val>>shift;
	if(currBit & 1){
		printf("1");
		}else{
			printf("0");
			}
	}
		printf("\n");
	return;
}
void printSingleBin(unsigned char byte){
	int shift=0;
	int currBit=0;
	for(int i=7; i>=0; i--){
		shift=i;
		currBit=byte>>shift;
		if(currBit & 1){
			printf("1");
			}else{
				printf("0");
				}
	}
	printf("\n");
	return;
}
<file_sep>/readme.txt
Extra Credit:
- Metadata size: 2 Bytes
The meta data was sorted in chars because the chars are guaranteed to be a single byte. We are using two chars to store all of the metadata (). 
we bit shifted and masked in order to store data. Since the memory array is 4096 bytes, we need a minimum of 12 bits (2^12=4096) to store the size. Since the key takes up 2 bytes and metadata blocks take up 2 bytes, the most we can allocate in one block is 4092, therefore, 2^12 fits our requirements in terms of bits. The 12 rightmost bits store the size bits and the left most bit is the in use bit. If the block has been given to the user by malloc then the in use bit will be 1 else, if the block is free the in use bit is 0. Were using 16 bits however, we really only need 13 bits, however, the extra 3 bits that are wasted do not make much of a difference in terms of space usage. The 3 bits will take some time to add up to a significant amount of bytes. Keeping the extra 3 bits help storing and accessing data easier because it makes up 2 blocks of the array. 

Metadata structure: | 1 000 1111| 11110000|  
					  ^     ^
			in use bits     starting of the size bits

Bit shifting and Masking:
Methods:
setInUse - takes in a byte and the bit you want to set the in use bit to
getbit - takes in the byte and the position of bit to extract and returns the value of the bit at that position. used to check the inuse bit
getsizebits - removes the in use bit and returns the size bits from the given byte. 
bin2int - takes in pointers to high and low bytes and converts it into an integer. used for bit add to find the new sum size after combining blocks
splitbin - takes in an integer and divides the bits into two chars to set the size of the metadata



Malloc
- Algorithm:

	- Traversing: mallocTraverse
		-Traverses through the array, checking size bits and in use bits until it reaches a block the same size as or larger than the amount of space requested that isn't in use. If such a block is found, splitblock is called, otherwise an insufficient memory message is displayed.                  

	- Splitting Blocks: splitBlock 
		- How many bytes to give back to user:
			*If the space found is the exact same size as the amount of memory requested by the user, return just that, without altering the blocks adjacent to it.
			*If the space found is larger than the amount being malloced by the user, and has enough space to store metadata plus 2 bytes of memory, the block is split into a block the same size as the size requested, and the in use bit is flipped. The adjacent block's size is set to that of the original block - user requested size, with an in use bit set to zero.
			*If the space found is larger than the user requested size, but fewer than 4 bytes larger (2 metadata bytes + 2 data bytes), the whole block is returned to the user, without splitting.
			
		- Setting in use bits: In use bits are set using the get bit method, specifically to set a block to 'in use' status, or if a block is being split, to 'not in use'.
	
	- Error Checkings
		- size input validity: Checked for a request larger than 4092 bytes (the size of the array, minus the key bytes and the first metadata block) in the main 'mymalloc' function, and for requests less than or equal to zero (because obviously neither a negative malloc nor a malloc of size zero can occur)
	
Free:
- Algorithm:
	- Traversing: 
	I start at the first metadata (&mem[2]) and move to (metadata size +2) and continue until I find the pointer given in by the user or the current pointer to the meta data is greater than the pointer received. Traverses by comparing pointers and accessing size bits in order to move to the next metadata.


- Fragmentation:
	Upon every free, when the right block to free is found, I try to combine any free blocks surrounding the current block. I check if:
		
		- Current block is the only block in the whole memory (mallocd blocksize is 4092 bytes)
			-> Just change set bit to 0
		
		- Curr is first block -> prev is null but next is not
			- combine with next block if next block is not inuse 
			set currents inuse bit to 0
			- just change set bit of current block to 0 if next block is in use
		
		- Curr is last block -> next is null
			- combine with previous block if previous block's set bit is 0  
			update size of prev to be prev size + curr size+ 2 for metadata block 
			- do nothing if previous block is in use
		
		- Prev block is not null and Next block is not null
			-check if next block's set bit block is 0, if it is then combine current and next by changing the size bits of current to currentsize+nextsize+2 and set current's set bit to 0. 
			- check if previous block's inuse bit is 0 if it is 0 combine by updating prev block size to prevsize+currentsize+2
			change current block inuse bit to 0 


- Error Checks:

If any of the following errors were encountered with the pointer received, the error message was returned. 
	- if pointer given is null
	
	- if key is not initialized --> first two bytes should equal 11474 (a predefined key)
			means that no pointers have been mallocd yet
	
	- if pointer is outside the array length/bounds 
			pointer is not mallocd by mymalloc
	
	- if pointer given does not point to the starting of a block of data --> Checked by seeing if address of pointer given matched address of metadata+2

	| metadata byte 1 | metadata byte 2 | blocks 	of 		data  |
										^     				^
				where pointer should be pointing  		where pointer is pointing
									^
if pointer sent in doesnt = address | of above pointer, then return error 


Findings:
	We are able to confirm that our version of malloc and free works because after the workloads were completed, when the first block's size was printed out, it equaled 4092, which is the amount memory we started out with. 
	
	The workloads helped verify that we are able to deal with extremely small mallocs of 1 byte. We are able to give the user exactly what they ask for. Freeing the one byte pointers showed immediately that free worked. When printing out addresses of the pointers given by malloc showed that each of the 50 pointers were of the same address because they were freed after the malloc call. 
	For B, the workload tested free's fragmentation algorithms. By freeing pointers one by one, we are required to combine the blocks if we want to return to the original free block of 4092. 
	C verified that free wont work on not mallocd array. Shows that program can handle what is asked for regardless of when
	For D, mallocing random bytes tested malloc's ability to take in any given request for bytes and evaluate it. If the request can be fulfilled, malloc sent back a pointer. 
	The workloads helped us find errors in our code. In one space the wrong parametor was sent in. 
<file_sep>/setInUse.c
/*sets the in use bit , takes in an integer (functioning as a boolean), to tell it whether to assign the val to be either 1 or 0*/
void setInUse(int inUse, unsigned char* hiMeta){
    unsigned int mask=1<<7;
    unsigned int currBit=0;
  if(inUse==0){
    *hiMeta=(*hiMeta & ~mask) | ((currBit) & mask);
  } else if(inUse==1){
        currBit=1<<7;
	printf("currBit: ");
	printBinInt(currBit);
	printf("mask: ");
	printBinInt(mask);
	printf("*hiMeta: ");
	printSingleBin(*hiMeta);
	unsigned int combo=(*hiMeta & ~mask);
	printf("*hiMeta & ~mask: ");
	printBinInt(combo);
        *hiMeta=(*hiMeta & ~mask) | ((currBit) & mask);
  }
    return;
}
<file_sep>/decompressor.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h> 
#include <sys/types.h> 
#include <fcntl.h>
#include <math.h>


struct HeapNode* makeHeapNode(struct HeapNode* node, int freq, char* token);
void reverse(char*, int length) ;
char* itoa(int num, char* str, int base) ;
//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 

struct HeapNode* treeFromCBook(struct HeapNode* head, char* codebook);
struct HeapNode* insertEntry(struct HeapNode* head, char* directions, char* token, int index, int count);
void printTree(struct HeapNode* head);
struct HeapNode* makeHeapNode(struct HeapNode* node, int freq, char* token);
void decompress( char* compressed, char* codebook);
//remember to free everything everwhere
char* itoa(int num, char* str, int base) 
{ 
    int i = 0; 
    int isNegative = 0; 
  
    /* Handle 0 explicitely, otherwise empty string is printed for 0 */
    if (num == 0) 
    { 
        str[i++] = '0'; 
        str[i] = '\0'; 
        return str; 
    } 
 
    // Process individual digits 
    while (num != 0) 
    { 
        int rem = num % base; 
        str[i++] = (rem > 9)? (rem-10) + 'a' : rem + '0'; 
        num = num/base; 
    } 
  
    str[i] = '\0'; // Append string terminator 
  
    // Reverse the string 
    //reverse(str, i); 
  printf("STR :%s ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n", str);
    return str; 
} 
/*void reverse(char* str, int length) 
{ 
    int start = 0; 
    int end = length -1; 
    while (start < end) 
    { 
        swap(*(str+start), *(str+end)); 
        
        start++; 
        end--; 
    } 
} */

//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& (duplicate from other file)
struct HeapNode{
	int frequency;
	char* name;//token gathered
	int height;
	struct HeapNode* left;
	struct HeapNode* right;
};
int isFile(char *to_read) ;


int isFile(char *to_read) {

  struct stat s;
  if(stat(to_read, &s) == 0) {

    if(s.st_mode & S_IFDIR) {
      return 0;
    } else if(s.st_mode & S_IFREG) {
      return 1;
    } else {
      printf("Error, not found\n");
      return -7;
    }

  } else {


    return -6;
  }
}
//struct HeapNode* makeHeapNode(struct HeapNode* node, int freq, char* token);
//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 

//struct HeapNode* treeFromCBook(struct HeapNode* head, char* codebook);

struct HeapNode* treeFromCBook(struct HeapNode* head, char* codebook){
printf("CODEBOOK IN TREEFROMC: %s", codebook);
	char* dictEntry[2];
	dictEntry[0]=NULL;
	dictEntry[1]=NULL;
	int fd=open(codebook, O_RDONLY);
	int size=lseek(fd, 0, SEEK_END);//find the size of the file
	printf("filesize: %d\n", size);
	int l= lseek(fd, 0, SEEK_SET);
	char* buffer= NULL;
	buffer = (char*)malloc(size*sizeof(char));
	int bufIndex=0;
	read(fd, buffer,size);
    int count =0; // total number of nodes that 
    int startingindex=0;
    int toklen=0;
	while( bufIndex < size){
		printf("buffer at index %d: %c\n", bufIndex, buffer[bufIndex]);
		 if(buffer[bufIndex]=='\n' || buffer[bufIndex]==' '|| buffer[bufIndex]=='\t' || buffer[bufIndex]=='\r' || buffer[bufIndex]== '\v'){
		    char* delim=(char*) malloc(sizeof(char)*2);
		    if(delim == NULL){
		    printf("malloc failed in decompress\n");
		    return;
		    }
		    delim[0]=buffer[bufIndex];
		printf("_%c_\n", delim[0]);
		    delim[1]='\0';
		    buffer[bufIndex]='\0';//make token complete string
	  
		    toklen = bufIndex-startingindex;
			printf("toklen: %d\n", toklen);
		    char* currNodeName= (char*) malloc(sizeof(char)*toklen+1);
		    strncpy(currNodeName, buffer+startingindex, toklen);
		    currNodeName[toklen] = '\0';
		    startingindex = bufIndex+1; //move up starting index
			if(delim[0]!='\n' && toklen!=0){
				dictEntry[0]=currNodeName;	
			}
			else if(delim[0]=='\n' && toklen!=0){
				printf("EXCUSE ME\n");
				dictEntry[1]=currNodeName;
				int length=strlen(dictEntry[0]);
				
				printf("binary in dict: %s\n", dictEntry[0]);
				printf("length: %d\n", length);
				printf("Dictionaru entries: 0:%s    1:%s\n\n", dictEntry[0],dictEntry[1]);
				head=insertEntry(head, dictEntry[0], dictEntry[1], 0, count);//call fxn
				count = count + length;
				printf("count : %d\n\n", count);
				free(dictEntry[0]);
				free(dictEntry[1]);
				}
		}
		bufIndex++;
	}
	/*create head of tree
	open code book, read from it line by line, tokenizing the first thing after each newline, for each line take binary token and parse it, but also tokenize value, 
	char by char, if char==0, give current node a left node, else give a right node, once binary token has been parsed (having checked each time if any more vals in binary token), fill final node with name of token*/
	
	printTree(head);
	return head;
}

struct HeapNode* insertEntry(struct HeapNode* head, char* directions, char* token, int index, int count){	
printf("Insert Entry DIRECTIONS: %s\n", directions);
	if(head==NULL){
		int count2 = count;
		printf("hello\n");
		int digits = 0; 
		do { 
		count2 /= 10; 
		digits++; 
		} 
		while (count2 != 0);
		printf("NEW COUNT %d AND DIGITS %d", count, digits);
		char* cstr = (char*) malloc(digits+1 * sizeof(char));
		cstr = itoa(count, cstr, 10);
		printf("cstr %s\n", cstr);
		struct HeapNode* node=makeHeapNode(node, 0, cstr);
		printf("PRINT TREE for dir:%s\n", directions);
		printTree(node);
		printf("PRINTED TREE\n\n");
	
		//printf("the name: %s~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n", directions);
		count++;
		
		head=node;
		printf("IE: inserted %d\n", node->height);
		if(index==strlen(directions)){
			printf("IE: index: %d\n", index);
			node->name=token;
			printf("nnnode name :%s \n", node->name);
			return node;
		}
	//return node;
	}
	if(directions[index]=='1'){//if(directions[0]='1')
	printf("going right\n");
	count++;
	index++;
	printf("count in right %d\n", count);
	head->right=insertEntry(head->right,directions, token, index, count);//syntax
	}
	if(directions[index]=='0'){//if(directions[0]='1')
	printf("going left\n");
	count++;
	printf("count in left %d\n", count);
	index++;
	head->left=insertEntry(head->left,directions, token, index, count);
	printf("returned\n");
	}
	printf("index: %d, returning\n", index);
	return head;
}

void printTree(struct HeapNode* head){
	if(head==NULL){
		return;
		}
	if(head->name==NULL){
		printf("NULL\n");
		}
		else{
		printf("Name: %s\n", head->name);
			}
			printf("going left: ");
	printTree(head->left);
	printf("going right: ");
	printTree(head->right);
	}
//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
struct HeapNode* makeHeapNode(struct HeapNode* node, int freq, char* token){
	node=(struct HeapNode*)malloc(sizeof(struct HeapNode)*1);
	node->name=token;
	node->frequency=freq;
	node->left=NULL;
	node->right=NULL;
	return node;
}
//&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
void decompress( char* compressed, char* codebook){
  if (isFile(compressed) == 1){
  printf("Compressed: %s\n",compressed);
  printf("Codebook: %s\n",codebook);
	//WOULD REALISTICALLY HAVE TO SEARCH FOR CODEBOOK IN DIRECTORY, NEED ALGO FOR THAT
	struct HeapNode* head= treeFromCBook( head, codebook); // ????needs head
	struct HeapNode* ptr=NULL;
	ptr=head;
	int td=open(compressed, O_RDONLY);
	if(td == -1){
	printf("Error: Cannot open Compressed file\n");
	}
	
	int clen = strlen(compressed);
	clen = clen - 4; // subtract ".hcz"
	char* decompressed = (char*) malloc(clen*sizeof(char));
	decompressed[0] = '\0';
	
	strncpy(decompressed, compressed, clen);
	int fd=open(codebook, O_RDONLY);
	if(fd == -1){
	printf("Error: Cannot open Codebook\n");
	}
	
	int id=open(decompressed, O_CREAT | O_WRONLY| O_APPEND);
	if(id == -1){
	printf("Error: Cannote open Codebook\n");
	}
	
	char* buffer=NULL;
	buffer = (char*) malloc(2*sizeof(char));
	if(buffer == NULL){
		printf("Malloc failed in decompress\n");
		return;
	}

	while(read(fd, buffer,1)){
		if(ptr==NULL){
			printf("invalid data in compressed file\n");
			ptr=head;//reset
			return; // ??????
		}
		if(ptr->name==NULL){
			if(buffer[0]=='0'){
				ptr=ptr->left;
			}
			else if(buffer[0]=='1'){
				ptr=ptr->right;
			}
			else{
			printf("Error in Decompress:Compressed file contained a non 1 or 0 number \n");
			return;
			}
		}
		else{
			int currSize=strlen(ptr->name);
			char* currToken= NULL;
			currToken=(char*)malloc(currSize*sizeof(char));
			if(currToken == NULL){
				printf("Malloc failed in decompress\n");
				return;
			}
			currToken=ptr->name;
			int written  = write(id, currToken, strlen(currToken));
			if(written <1){
				printf("Error Write to file failed in Decompress\n");
				return;
			}
			ptr=head;//reset ptr to top of stack
		}
	}
	return;
	//call buildtree or whatev its called
	//read from file char by char
	//on a 0, go left in tree, on a 1 go right, at each node check to see if name is null
	//if name isn't null, write that to file
	//if directions steer u to null node, print error message
	}
	else{
	printf("decompress not given file error\n");
	return;
	}
	}

int main(int argc, char** argv){
	if(argc<2){
		printf("error");
		return 0;
	}
	struct HeapNode* head=NULL;
	head=treeFromCBook(head, argv[2]);
	decompress(argv[1], argv[2]);
	return 0;
}


<file_sep>/_myMalloc.c
//main: if first (2? 4?) bytes arent set to key, set key, and set the first piece of metadata.

/*split method: see how much data user is requesting (takes pointer to metadata block, amount of space user requested)
at first instance of a space big enough

                      error checking: did user ask for too much?
                      -->if space is bigger than requested
                      --> reduce
                          -->if too small for metadata+2 bytes, return the whole thing to user as is
                          else: --> make new metadata, set size to the value originally stored for size of currblock MINUS size of space being allocated MINUS
                          size of metadata
                          else if space==size:
                          continue
                          else if no eligible space: print error message
                        traverse array method(returns pointer):
                        while index!=4095
                        if in use bit==flipped
                        bintoInt-> traverse that many spaces onward
                        move to next
                        else    bin2Int ->compare to amount of space user asks for, if too small move on
                        else return pointer to space */
//  make global vars with the address range of the array, size of metadata, key
#include "mymalloc.h"
int getbit(int num, int position);
unsigned char getsizebits(unsigned char bits);
int bin2int(unsigned char highbyte, unsigned char lowbyte);
unsigned char* mallocTraverse(unsigned char* curr, int dataSize);
void setInUse(int inUse, unsigned char* hiMeta);
void splitBin(unsigned int currInt, unsigned char* hiMeta, unsigned char* loMeta);
unsigned char* splitBlock(unsigned char* curr, int blockSize, int dataSize);
void* mymalloc(int size, __FILE__, __LINE__);

void* mymalloc(int size, __FILE__, __LINE__){
  unsigned char* first=myMem[0];
  unsigned char* second=myMem[1];
  unsigned char* ptr= myMem[0];
  int firstBytes=bit2int(*first, *second);
  if(firstBytes!=key){//set key to initialize method
    int usrBlock=4092;//size of arr-metadata bits- size of key
    *ptr=key;
    ptr=ptr+2;
    first=ptr;//initialize metadata after key
    second=ptr+1;
    *first=0;
    *second=0;
    splitBin(usrBlock, first, second);//set metadata for new metadata block
    setBlock(0, *hi);
  }
  if(size>usrBlock || size<0){//if user tries to allocate more memory than size of array/metadata/key allows for, or a negative value
      if(size>usrBlock){
      printf("Memory request exceeds size of working memory in file %d at line %d\n", __FILE__, __LINE__);
      return NULL;
    } else{
      printf("Invalid memory request in file %d at line %d\n", __FILE__, __LINE__);
    }
  }else{
    ptr=mallocTraverse(ptr, size);//calling the meat of the program, returns either a pointer to usable memory or a null pointer
  }
  return (void*)ptr;
}

unsigned char* splitBlock(unsigned char* curr, int blockSize, int dataSize){
     unsigned char* hi=curr;
     unsigned char* lo=curr+1;
     setBlock(1, *hi);
      if((blockSize-3)>dataSize){//if block can fit at least two bytes of free space, including metadata, make free space
          splitBin(dataSize, hi, lo);//set curr's size to the size of data requested (truncating it)
          hi=curr+dataSize+2;//iterate our new pointers along
          lo=hi+1;
          blockSize=blockSize-dataSize-2;//blocksize of free block created when you allocate less than space in curr block
          *hi=0;//zero out  garbage vals in these bytes
          *lo=0;
          splitBin(blockSize, hi, lo);//set metadata for new metadata block
          setBlock(0, *hi);
      }
      return curr;//curr was never iterated so we can return it as-is
}

void splitBin(unsigned int currInt, unsigned char* hiMeta, unsigned char* loMeta){
  *hiMeta=0;
  *loMeta=0;
  unsigned int mask=0;
  unsigned int currBit=0;
  for(int i=11; i>=0; i--){
    mask=0;
    currBit=currInt>>i;
    if(i<=7){
        mask=1<<(i);
        *loMeta=(*loMeta & ~mask) | ((currBit << i) & mask);
    } else{
      mask=1<<(i-8);
      *hiMeta=(*hiMeta & ~mask) | ((currBit << (i-8)) & mask);
    }
  }
    return;
}

/*sets the in use bit , takes in an integer (functioning as a boolean), to tell it whether to assign the val to be either 1 or 0*/
void setInUse(int inUse, unsigned char* hiMeta){
    unsigned int mask=1<<7;
    unsigned int currBit=0;
  if(inUse==0){
    *hiMeta=(*hiMeta & ~mask) | ((currBit) & mask);
  } else if(inUse==1){
        currBit=1<<7;
	unsigned int combo=(*hiMeta & ~mask);
        *hiMeta=(*hiMeta & ~mask) | ((currBit) & mask);
  }
    return;
}

unsigned char* mallocTraverse(unsigned char* curr, int dataSize){
    *curr=myMem[2];
    while(curr>=lowerBound && curr<=upperbound){//lowerBound & upperBound will be global vars
      int currMeta=bin2int(*curr, *(curr+1));//converting chars to an int to send to getbit
      int inUse=getbit(currMeta, 1);//getting the in use bit
      char hiBits=getsizeBits(*curr);//blocking out in use bit to get size of block
      int currBlockSize=bin2int(hiBits, *(curr+1));//getting block size of current block
      if(inUse==0 && currBlockSize>=dataSize){//if there's enough space to return to the user
          curr=splitBlock(curr, currBlockSize, dataSize);//prepare it to return
          return curr+2;//return pointer to actual data block, not trying to overwrite metadata
      } else{
          curr=(curr+currBlockSize);
      }
    }
    /* got to end of array without finding an empty block */
    printf("Memory request exceeds size of working memory in file %d at line %d\n", __FILE__, __LINE__);
    return NULL;
}

int bin2int(unsigned char highbyte, unsigned char lowbyte){  //WORKS
 	int j =0;
	int i=0;
	char binarr[15];
	  for(i = 7; i>=0; i--){
		binarr[i] = getbit(highbyte, j);
		j++;
	  }
	  j=0;
	  for(i = 15; i>= 8; i--){
		binarr[i] = getbit(lowbyte, j);
		j++;
	  }
	  //bin arr gives you full binary array ex. byte holds 14 -> binarr = [0,0,0,0,0,0,0,0,1,1,1,0]
	  j = 0;
	  int sum = 0;
	  // this loop goes through binarr and calculate 2^binarr[i] power and sums it to give you the final int. starts at 2^0 (binarr[15])
	  for(i =15; i>=0; i-- ){
		int bin = binarr[i];
		if(bin == 0){
		  j++;
		}
		else if (bin == 1){
		  sum += pow(2, j);
		  j++;
		}
	  }
	  return sum;
}

unsigned char getsizebits(unsigned char bits){
	unsigned char sizebits, mask;
	mask = (1 << 7) -1;
	sizebits = bits & mask;
	return sizebits;
}

int getbit(int num, int position){   //WORKS
	int bitstate = (num >> position) &1;
	return bitstate;
}
<file_sep>/tempfree.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//#include<stdbool.h>
#define KEY 0010110011010010
/*
CONTAINS: getbit, setbit, bin2int, bitadd, bitsub, getsizebits
*/
char* firstmeta = mem[2];
char* firstMallocPtr = mem[4];
char*lastaddress = mem[4095];

int bin2int(unsigned char, unsigned char);
int getbit(int , int);
//int adding(unsigned char, unsigned char, unsigned char, unsigned char);
//int bitsub(unsigned char, unsigned char, unsigned char, unsigned char);
unsigned char getsizebits(bits);

/*
send in high and low bytes for the meta data you want to add TO   (highleva2, lowleva2)   send in metadata bytes for the meta data you have to add (the one youre gonna free)
bit add will call a method to retreive the size bits from the whole bytes and then send that to bin2int and then add+return the resulting ints' sum
*/
int bitadd(unsigned char high11, unsigned char low11, unsigned char high22, unsigned low22){
	unsigned char, high1, high2;
	high1 = getsize(high11);
	//low1 = getsize(low11);
	high2 = getsize(high22);
	//low2 = getsize(low22);
	int add2 = bin2int(high1, low11);
	int add1 = bin2int(high2, low22);
	int sum = add2+add1;
	return sum;
}
/*
look at notes for bit add, does the same thing. highlevel/lowlevel subfrom should be the bigger number you subtract FROM
bitsub will follow same procedure as bitadd, dont forget to call split in mymalloc()
call method that retrieves the size bits.
 */
int bitsub(unsigned char high11, unsigned char low11, unsigned char high22, unsigned low22){
	unsigned char, high1, high2;
	high1 = getsize(high11);
	//low1 = getsize(low11);
	high2 = getsize(high22);
	//low2 = getsize(low22);
	int subfrom = bin2int(high1, low11);
	int tosub = bin2int(high2, low22);
	int sum = subfrom-tosub;
	return sum;
}

/*
MUST SEND IN SIZE BYTES ONLY
this method will NOT take inuse bit into account when converting.
getbit will give you the bit at any given position
send in the lowlevel and high level bits you want to convert into ints, will return the int
*/
void combineNext(unsigned char* curr, unsigned char* next){
	int nextinusebit = getbit(*next, 1);
	if (nextinusebit == 0){
		unsigned char currlowbits = *(curr+1);
		unsigned char nextlowbits = *(next+1);
		printf("Starting combining process. \n");
		int sum= bitadd(*curr, currlowbits, *next, nextlowbits);
		splitBin(sum, curr, curr+1);
		setInUse(0, curr);
		printf("Curr and Next combined.\n");
	}
	else if (nextinusebit ==1){
		printf("Can't Combine. Next is in use.\n");
	}
}
void combinePrev(unsigned char* curr, unsigned char* prev){
	int previnusebit = getbit(*prev, 1);
	if (previnusebit == 0){
		unsigned char currlowbits = *(curr+1);
		unsigned char prevlowbits = *(prev+1);
		printf("Starting combining process. \n");
		int sum= bitadd( *prev, prevlowbits, *curr, currlowbits);
		splitBin(sum, curr, curr+1);
		setInUse(0, prev);
		printf("Curr and Prev combined.\n");
	}
	else if (previnusebit ==1){
		printf("Can't Combine. Next is in use.\n");
	}
}
void combineBoth(unsigned char* prev, unsigned char* curr, unsigned char* next){
	int nextinuse = getbit(*next, 1);
	int previnuse = getbit(*prev, 1);
	if (nextinuse == 0){
	combineNext(curr, next);
	}
	if (previnuse == 0){
	combinePrev(curr, prev);
	}
}
void myfree(void *tofree, __FILE__, __LINE__){
	tofree = (char*) tofree;
	if (tofree == NULL){
	printf("Error in %s line %d: Pointer received is NULL. \n", __FILE__, __LINE__);
	}
	if (ismeminit = 0){
	printf("Error in %s line %d: Nothing malloc'd yet\n", file, linenum);
	}
	if(tofree<=lowerBound || tofree>upperbound){
	printf("Error in %s line %d: Pointer is not in range of memory\n", __FILE__, __LINE__);
	}
	if(tofree>firstmeta && tofree<=lastaddress){

		char *curr = firstmeta;
		char *prev = NULL;
		char *next = NULL;

		while(curr < lastaddress ){
			unsigned char currsizebits = getsize(curr);
			int currsize = bin2int(currsizebits, curr+1);

			if ((curr+2) > tofree){   // pointer is not pointing at the starting address of a block
				printf("Error in %s line %d: Pointer is not the one given by malloc\n", __FILE__, __LINE__);
				break;
			}
			if(curr+2 == tofree){
				int isValid = getbit(curr, 1); //get inuse bit
				if (isValid == 0){  // address already freed
					printf("Error in %s line %d: Pointer is already freed.\n", __FILE__, __LINE__);
					break;
				}
				else if (isValid == 1){ //this pointer can be freed
					//free inuse bit, combine block
					setInUse(0, curr);
					// check if curr is the first and last block (only block)
					if ((curr+1+currsize) == lastaddress && prev == NULL){
						setInUse(0, curr);
						break;
					}
					// check if prev is null / curr is first block
					else{
						if (prev == NULL){
							next = (curr+1+currsize);
							combineNext(curr, next);
							break;
						}
					// check if curr is the last block / there is no next block
						if((curr+1+currsize) == lastaddress){
							combinePrev(curr, prev);
							break;
						}
					// else combine both
						else if((curr+1+currsize) < lastaddress && prev!=NULL){
							next = (curr+1+currsize);
							combineBoth(prev, curr, next);
							break;
						}
					}
					//break;
				}

			}
			//update pointers

			prev = curr;
			curr = curr+1+currsize;
		}
	}

}

int main (int argc, char**argv){
	unsigned char high= 0b0000001;
	unsigned char low = 0b00001111;
	int f = bin2int(high, low);
	printf("INT : %d", f);
	unsigned char high2= 0b0000000;
	unsigned char low2 = 0b00001111;
	int added = bitadd(high, low, high2, low2);
	printf("sum : %d \n", added);
	int subtracted = bitsub(high, low, high2, low2);
	printf("subtracted : %d\n", subtracted);
	return 0;
}
<file_sep>/ignorebitadd.c
#include <math.h>
#include <stdbool.h>
#define KEY 0010110011010010

int bitadd(unsigned char highleva2, unsigned char lowleva2, unsigned char highlevl2add, unsigned char lowlev2add){
  //call bin2int twice. save those numbers. add ints. call int2binary. call split
    int add2int =  bin2int(unsigned char lowleva2, unsigned char highleva2);
    int toadd =  bin2int(unsigned char lowlev2a, unsigned char highlev2a);
    int newsize = add2int+toadd;
    return newsize;
    //char[] newbinary = int2binary(newsize);
    //return newbinary;
//myfree will receive the full 16 bit char array, then call split on the array from within myfree()
}
int bitsub(unsigned char highlevsubfrom, unsigned char lowlevsubfrom, unsigned char highlevl2sub, unsigned char lowlev2sub){
  //bitsub will follow same procedure as bitadd, dont forget to call split in mymalloc()
  int sub =  bin2int(unsigned char lowlevsubfrom, unsigned char highlevsubfrom);
  int tosub =  bin2int(unsigned char lowlev2sub, unsigned char highlev2sub);
  int newsize = sub - tosub;
  char[] newbinary = int2binary(newsize);
  return newbinary;

}
//converts binary to int
bool getBit(unsigned char byte, int position){ // position in range 0-7
    //copied code MODIFY
    return (byte >> position) & 0x1;
}
//getbit will give you the bit at any given position
int bin2int(unsigned char lowlev, unsigned char highlev){
int j =0;
  for(int i = 0; i< 8; i++){
    binarr[i] = getbit(highlev, j);
    j++;
  }
  j=0;
  for(int i = 8; i< 16; i++){
    binarr[i] = getbit(lowlev, j);
    j++;
  }
  ///bin arr gives you full binary array ex. byte holds 14 -> binarr = [0,0,0,0,0,0,0,0,1,1,1,0]
  int j = 0;
  int sum = 0;
  // this loop goes through binarr and calculate 2^binarr[i] power and sums it to give you the final int. starts at 2^0 (binarr[15])
  for(int i =15; i>=0; i-- ){
    int bin = binarr[i]
    if (bin == 0){
      j++;
    }
    else if (bin == 1){
      sum += pow(2, j);
      j++;
    }
  }
  return sum;
}
//http://www.java2s.com/Code/Java/Language-Basics/Setsaspecificbitofanint.htm
//MUST MODIFY
int setBit(int bit, int target) {
       // Create mask
       int mask = 1 << bit;
       // Set bit
       return target | mask;
  }


int main(){
  unsigned char somebit = 0xF;
  printf("bit: %u", somebit);


}

/*char* int2binary(int toconvert){
  static char binum[16]; //idk if this works figure out types later, conversion code should work tho
  //do i need to null terminate? is this a string or a array of characters?
  int i =0;
  for (i = 0; i < 16; i++){
    binum[i]=0;
  }
  i =0;
  while(num>0){
    binum[i] = num%2;
    num = num/2;
    i++;
  }
  //now binum contains reversed binary numbers
  //this loop makes the numbers forward again
  int start = 0;
  int end = 15;
  while(start < end){
    int temp = binum[start];
    binum[start] = binum[end];
    binum[end]= temp;
    start++;
    end--;
  }
  char finbin[16];
  for(int i =0; i<16; i++){
    finbin[i] = binum[i];
  }
}*/
/*unsgined char splitbinary(char* tosplit, int split){
  //split = 1 means high split aka obtain the high level bits
  // split == 0 means low split aka obtain the low level bits
  //https://stackoverflow.com/questions/2666440/how-to-store-binary-string-in-the-binary-form-in-a-file
  if (split ==1){
    return 0;
  }

  else if (split ==0){
    return;
  }
}*/
//unsgined char lowsplitbinary(char* tosplit){}



//following for setting bit is from geeksforgeeks MUST MODIFY!
//Use the bitwise OR operator (|) to set a bit.
//number |= 1UL << n;
//That will set the nth bit of number. n should be zero, if you want to set the 1st bit and so on upto n-1,
//if you want to set the nth bit.
//Use 1ULL if number is wider than unsigned long;
//promotion of 1UL << n doesn't happen until after evaluating 1UL << n where
//it's undefined behaviour to shift by more than the width of a long. T
//he same applies to all the rest of the examples.


/*
binary2int(unsigned char highlev, unsigned char lowlev){
  //copied code MUST MODIFY
  //https://stackoverflow.com/questions/37487528/how-to-get-the-value-of-every-bit-of-an-unsigned-char
//extracts bits from unsigned char and puts in an int array called bits
int lowbits[8];
for (int i = 0 ; i != 8 ; i++) {
    bits[i] = (lowlev & (1 << i)) != 0;
}

int highbits[8];
for (int i = 0 ; i != 8 ; i++) {
    highbits[i] = (highlev & (1 << i)) != 0;
}

*/
<file_sep>/memgrind.c
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
#include "mymalloc.c"
#include "mymalloc.h"
#define malloc(x) mymalloc(x,__FILE__,__LINE__)
#define free(x) myfree(x,__FILE__,__LINE__)

int main (int argc, char**argv){
double difference=0;
double sumtimeA=0;
double sumtimeB=0;
double sumtimeC=0;
double sumtimeD=0;
double sumtimeE=0;
double sumtimeF=0;
int* ptrarr2[150];
srand(time(NULL));
int a=0;
int b=0;
int c=0;
int d=0;
int e=0;
int f=0;
int i=0;
struct timeval start, end;

// case a
for(a=0; a<100;a++){
//time(&starttime);//get time at start
gettimeofday(&start, NULL);
for(i=0 ; i< 150; i++){
  ptrarr2[i] = (int*) malloc(1);
  free(ptrarr2[i]);
ptrarr2[i] = NULL;
}
//time(&endtime);//get time at end
gettimeofday(&end, NULL);
difference=((end.tv_sec-start.tv_sec)*1000000)+(end.tv_usec-start.tv_usec);//save runtime of iteration
sumtimeA+=difference;
}
//case b
int *ptrarr[50];
int malcounter=0;
int *ptr;
for(b=0; b<100; b++){
gettimeofday(&start, NULL);//get time at start 
int x ;
for(x =0; x<3; x++){
for(i =0; i< 50; i++){
  ptr = (int*) malloc(1);
  ptrarr[i] =ptr;
  malcounter++;
  if(malcounter == 50){
    int j;
    for (j =0; j<malcounter;j++ ){
      free(ptrarr[j]);
      ptrarr[j]=NULL;
  }
  malcounter =0;
}
}
}
gettimeofday(&end, NULL);//get time at end
difference=((end.tv_sec-start.tv_sec)*1000000)+(end.tv_usec-start.tv_usec);//save runtime of iteration
sumtimeB+=difference;
}
// case c
malcounter = 0;
int freedptr = 0;
int ptr2free =-1;
int freeindex =0;
int* pointers[50];
int mallocindex =0;
int random;
for(c=0; c<100; c++){
gettimeofday(&start, NULL);//get time at start
  while(malcounter <=50){
   random = rand()%2;
    if(random == 0){ //malloc if 0
      pointers[mallocindex] = (int*)malloc(1);
      malcounter++;
      mallocindex++;
      ptr2free =malcounter - freedptr;
    }
    else if (random == 1){ // free if 1
      if (ptr2free != 0 && malcounter!=0){
        free(pointers[freeindex]);
        pointers[freeindex] = NULL;
        ++freeindex;
        ++freedptr;
        ptr2free =malcounter - freedptr;
      }
    }
    if(malcounter == 50){
    break;
  }
   
    }
  //  if (malcounter == 50){
      while(ptr2free!= 0){
        free(pointers[freeindex]);
        pointers[freeindex] = NULL;
        ++freedptr;
        ++freeindex;
        ptr2free= malcounter-freedptr;
      }
   //}
gettimeofday(&end, NULL);//get time at end
difference=((end.tv_sec-start.tv_sec)*1000000)+(end.tv_usec-start.tv_usec);//save runtime of iteration
sumtimeC+=difference;
}
  //case d
  int memleft=4092;  //the amount of memory left
  int memalloc =0; // the total of memory that is currently allocated
  int* pointers2[50]; // pointer array to all of allocations
  int memarr[50];// stores the amount of memory mallocd on each malloc

for(d=0; d<100; d++){
	gettimeofday(&start, NULL);//get time at start
	  memleft=4092;
	  freedptr=0; //amount of pointers that have been freed
	  freeindex=0; // index to free at, starts at 0 and frees sequentially. used for pointers2
	  malcounter=0; // amount of times malloc has been called
	  ptr2free =-1; // amount of pointers left to free
	  mallocindex=0; // where to store the next mallocd pointer in pointers2
	while(malcounter<=50){
	 if (memleft >0){
	    random = rand()%2;
	    if(random ==0){// malloc if even
	      random = (rand()%64);
		if(random==0){
			random=64;
		}
	      /*while(random < 1 || random > 64){
		random = rand();
		if (random <=64 && random >= 1){
		  break;
		}
	      }*/
	      if(memleft >=random){
		pointers2[mallocindex]= (int*)malloc(random);
		memarr[mallocindex] = random;
		memalloc +=random;
		mallocindex++;
		malcounter++;
		memleft-=random;
	      }
	    }
	    else if (random ==1){//free if odd
	      if(ptr2free!=0&& malcounter!=0){
		free(pointers2[freeindex]);
		memalloc = memalloc - memarr[freeindex];
		freeindex++;
		freedptr++;
		ptr2free = malcounter-freedptr;
		memleft = 4092- memalloc;
		}
	    }
	  }
	  if (malcounter ==50){
	    break;
	  }
	}
	//if(malcounter ==50){
	  while(freeindex <=50){
	    free(pointers2[freeindex]);
	    freedptr++;
	    ptr2free = malcounter -freedptr;
	    memalloc = memalloc - memarr[freeindex];
	    freeindex++;
	    memleft = 4092- memalloc;
	    
	    if(ptr2free == 0){
	      break;
	    }
	   }

	gettimeofday(&end, NULL);//get time at end
	difference=((end.tv_sec-start.tv_sec)*1000000)+(end.tv_usec-start.tv_usec);//save runtime of iteration
	sumtimeD+=difference;
}
int *fiboptrArr[100];
int index=0;//used in E and F
int sum=0;//used in E and F
for(e=0; e<100; e++){
	gettimeofday(&start, NULL);//get time at start
	int prevprev=0;
	int prev=1;
	int totalmem=0;
	index=0;
	//case E
	while(totalmem<(4092/2)){
	  sum=prevprev+prev;
	  fiboptrArr[index]= (int*)malloc(sum);
	  prevprev=prev;
	  prev=sum;
	  totalmem+=(sum+2);
	  index++;
	}
	  fiboptrArr[index]= (int*)malloc(prevprev);
	  totalmem+=(prevprev+2);
	  index++;
	while(totalmem+(prev-prevprev)<(4092)&& sum>1){
	  sum=prev-prevprev;
	  fiboptrArr[index]= (int*)malloc(sum);
	  prev=prevprev;
	  prevprev=sum;
	  totalmem+=(sum+2);
	  index++;
	}
	for(i=index-1; i>=0; i--){
	  free(fiboptrArr[i]);
	}
	gettimeofday(&end, NULL);//get time at end
	difference=((end.tv_sec-start.tv_sec)*1000000)+(end.tv_usec-start.tv_usec);//save runtime of iteration
	sumtimeD+=difference;
}
//F begins here
int* alternptrArr[250];
int* alternptr;
for(f=0; f<100; f++){
	gettimeofday(&start, NULL);//get time at start
	index=0;
	random=0;
	while(sum<=4092 && index<250){
		random=rand()%67;
		if(random==0){
			random=67;
		}
		alternptr=(int*)malloc(random);
		alternptrArr[index]=alternptr;
		if((index%3)==0){
			free(alternptrArr[index]);//every third element gets freed
			alternptrArr[index]=NULL;
			}
		index++;
		sum+=random+2;
	}
	for(i=0; i<index; i++){
	
		if(alternptrArr[i]!=NULL){
		free((alternptrArr[i]));
		}}
	gettimeofday(&end, NULL);//get time at end
	difference=((end.tv_sec-start.tv_sec)*1000000)+(end.tv_usec-start.tv_usec);//save runtime of iteration
	sumtimeD+=difference;
	//Check for successful freeing
	char* testptr;
	char* testptrArr[4];
	//malloc 1000 4X
	for(i=0; i<4; i++){
		testptr=(char*)malloc(1000);
		testptrArr[i]=testptr;
	}
	//free prev mallocs
	for(i=0; i<4; i++){
		free((testptrArr[i]));
	}
	//test to see how this worked
	testptr=(char*)malloc(4092);
	testptrArr[0]=testptr;
	free((testptrArr[0]));
	//test our free
	testptr=(char*)malloc(1);
	testptrArr[0]=testptr;
	free((testptrArr[0]));
	//test splitblock
	testptr=(char*)malloc(4088);
	testptrArr[0]=testptr;
	testptr=(char*)malloc(1);
	testptrArr[1]=testptr;
	free((testptrArr[1]));
	free((testptrArr[0]));
	testptr=(char*)malloc(4092);
	testptrArr[0]=testptr;
	free((testptrArr[0]));
}
//print mean times
printf("Mean time of protocol A was %lf milliseconds\n", (sumtimeA/100));
printf("Mean time of protocol B was %lf milliseconds\n", (sumtimeB/100));
printf("Mean time of protocol C was %lf milliseconds\n", (sumtimeC/100));
printf("Mean time of protocol D was %lf milliseconds\n", (sumtimeD/100));
printf("Mean time of protocol E was %lf milliseconds\n", (sumtimeE/100));
printf("Mean time of protocol F was %lf milliseconds\n", (sumtimeF/100));
return 0;
}
<file_sep>/mallocTraverse.c
unsigned char* mallocTraverse(unsigned char* curr, int dataSize){
    *curr=myMem[2];
    while(curr>=lowerBound && curr<=upperbound){//lowerBound & upperBound will be global vars
      int currMeta=bin2int(*curr, *(curr+1));//converting chars to an int to send to getbit
      int inUse=getbit(currMeta, 1);//getting the in use bit
      char hiBits=getsizeBits(*curr);//blocking out in use bit to get size of block
      int currBlockSize=bin2int(hiBits, *(curr+1));//getting block size of current block
      if(inUse==0 && currBlockSize>=dataSize){//if there's enough space to return to the user
          curr=splitBlock(curr, currBlockSize, dataSize);//prepare it to return
          return curr+2;//return pointer to actual data block, not trying to overwrite metadata
      } else{
          curr=(curr+currBlockSize);
      }
    }
    /* got to end of array without finding an empty block */
    printf("Memory request exceeds size of working memory in file %d at line %d\n", __FILE__, __LINE__);
    return NULL;
}
