Concept explainers
Explanation of Solution
Modify the allocator to perform constant-time coalescing requires both a header and a footer for each block:
In the “Section 9.9.12 (mm.c)”, remove the red color text and add the highlighted lines which is represented in the below code. The modified “mm.c” file is as follows:
#define MAX(x, y) ((x) > (y)? (x) : (y))
/* Pack a size and allocated bit into a word */
#define PACK(size, alloc) ((size) | (alloc))
// Define a pack with size and allocated bit
#define PACK(size, alloc, prev_alloc) ((size) | (alloc) | (prev_alloc << 1))
/* Read and write a word at address p */
#define GET(p) (*(unsigned int *)(p))
/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
// Define allocated fields
#define GET_PREV_ALLOC(p) ((GET(p) >> 1) & 0x1)
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE)
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0); /* Alignment padding */
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* Prologue header */
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); /* Epilogue header */
// Call PUT() function for Prologue header
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1, 1)); /* Prologue header */
// Call PUT() function for Prologue footer
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1, 1));
// Call PUT() function for Epilogue header
PUT(heap_listp + (3 * WSIZE), PACK(0, 1, 1));
heap_listp += (2 * WSIZE);
/* $end mminit */
return NULL;
/* Adjust block size to include overhead and alignment reqs. */
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + (DSIZE)+(DSIZE - 1)) / DSIZE);
// Check size to adjust block
if (size <= WSIZE)
// Assign size value
asize = DSIZE;
// Otherwise
else
// Compute size to add overhead and alignment requirements
asize = DSIZE * ((size + (WSIZE)+(DSIZE - 1)) / DSIZE);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) {
}
/* $begin mmfree */
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
// Call PUT() function with size and allocated bit
PUT(HDRP(bp), PACK(size, 0, GET_PREV_ALLOC(HDRP(bp))));
PUT(FTRP(bp), PACK(size, 0, GET_PREV_ALLOC(HDRP(bp))));
// Check allocated bit
if (GET_ALLOC(HDRP(NEXT_BLKP(bp))))
// Call PUT() function
PUT(HDRP(NEXT_BLKP(bp)), PACK(GET_SIZE(HDRP(NEXT_BLKP(bp))), 1, 0));
// Otherwise
else {
// Call PUT() function for HDRP
PUT(HDRP(NEXT_BLKP(bp)), PACK(GET_SIZE(HDRP(NEXT_BLKP(bp))), 0, 0));
// Call PUT() function for FTRP
PUT(FTRP(NEXT_BLKP(bp)), PACK(GET_SIZE(HDRP(NEXT_BLKP(bp))), 0, 0));
}
// Call coalesce() function to fill values
coalesce(bp);
}
/* $begin mmfree */
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
// Call GET_PREV_ALLOC() function and the return value is assign to prev_alloc
size_t prev_alloc = GET_PREV_ALLOC(HDRP(bp));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
else if (prev_alloc && !next_alloc) { /* Case 2 */
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
// Call PUT() function for HDRP with PACK size
PUT(HDRP(bp), PACK(size, 0, 1));
// Call PUT() function for FTRP with PACK size
PUT(FTRP(bp), PACK(size, 0, 1));
}
else if (!prev_alloc && next_alloc)
{
/* Case 3 */
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
// Call PUT() function for HDRP with PACK size
PUT(FTRP(bp), PACK(size, 0, 1));
// Call PUT() function for FTRP with PACK size
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0, 1));
bp = PREV_BLKP(bp);
}
else {
/* Case 4 */
size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
// Call PUT() function for HDRP with PACK size
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0, 1));
// Call PUT() function for FTRP with PACK size
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0...
Want to see the full answer?
Check out a sample textbook solution
Chapter 9 Solutions
EBK COMPUTER SYSTEMS
- Given pointers to the head nodes of linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share a common node, return that node's value. Note: After the merge point, both lists will share the same node pointers. Example In the diagram below, the two lists converge at Node x: [List #1] a--->b--->c \ x--->y--->z--->NULL / [List #2] p--->q Function Description Complete the findMergeNode function in the editor below. findMergeNode has the following parameters: SinglyLinkedListNode pointer head1: a reference to the head of the first list SinglyLinkedListNode pointer head2: a reference to the head of the second list Returns int: the value of the node where the lists merge Input Format Do not read any input from…arrow_forwardUsing a Generic class that implements the Comparator interface, write a workingprogram that compares the performance of any two IPL teams in terms of the following:1) Points per match= PTS/PLD2) Form= (# of Ws)/33) Net Run Rare= Net RRYou can use the following data to make comparisons between any two teams of yourchoice: You can hard code the data associated with the two teams you have chosen. Hence, no needto take any inputs from the user. Upon running the program, the program should simplyoutput the three comparison results.Additionally, please mention the names of the two chosen teams in the beginning of theprogram in a comment.arrow_forwardI need help urgently to be able to understand how to do this program it is written in C++ but I am currently lost as to how I should start or do it or what is it even asking I would highly appreciate any good helparrow_forward
- In java please.arrow_forwardCan anyone please solve this question asap ? Thank yoyuIn this question, you are required to implement singly linked list and its concepts to solve the problems of a departmental store described in the scenario given below:A departmental store has a variety of products to sell. Each product type has a unique ID and price associated with it (for example soaps can have an ID of 1 and price of 50 etc.). A customer comes to the store and starts putting items in his/her shopping cart. Once all theitems have been placed in the shopping cart, the customer then proceeds to checkout but before that, he/she will sort (in ascending order of IDs) the shopping cart’s items and proceed to remove all the duplicate items from the shopping cart, that is if two soaps have been added to the cart, only 1 will be kept. At the checkout counter, he/she will then remove items from the cart by removing from the end of the shopping cart (linked list). A bill for that customer is then generated and printed.You…arrow_forwardImplement a stack and solutions to the following problems: balancing parenthesis, evaluating postfix expressions and transforming infix expressions into postfix expressions. We are providing some sample code and input files: public/ balancing.cpp - main method to check whether an expression is balanced infix2postfix.cpp - main method to transform an infix expression into postfix input_balanced.txt - test cases for balancing.cpp input_infix2postfix.txt - test cases for infixtopostfix.cpp input_postfixEval.txt - test cases for postfixEval.cpp postfixEval.cpp - main method to evaluate postfix expressions stack.cpp - stack implementation stack.hpp - stack header file • To compile, run $ g++ stack.cpp balancing.cpp $ g++ stack.cpp postfixEval.cpp $ g++ stack.cpp infixtopostfix.cpp • To run each program, run $ ./a.out • The test cases follow this format: expected_solution input. Given input, your job is to implement code that gets the…arrow_forward
- Implement the code for below assignment Map (the mapper function) EmitIntermediate(the intermediate key,value pairs emitted by the mapper functions) Reduce (the reducer function) Emit (the final output, after summarization from the Reduce functions)We provide you with a single system, single thread version of a basic MapReduce implementation. Task The input is a number of test cases with two matrices each. A single test case will look like: The required output is to print the product of the two matrices in the format shown. The code for the MapReduce class, parts related to IO etc. has already been provided. However, the mapper and reducer functions are incomplete. Your task is to fill up the mapper and reducer functions appropriately, such that the program works, and outputs the product of the two matrices, in row-wise manner. Also, this program outputs certain information to the error stream. This information has been logged to help beginners gain a better understanding of the the…arrow_forwardIntroduction For this assignment, you are to write a program which implements a Sorted List data structure using a circular array-based implementation and a driver program that will test this implementation. The Sorted List ADT is a linear collection of data in which all elements are stored in sorted order. Your implementation has to store a single int value as each element of the list and support the following operations: 1. add(x) – adds the integer x to the list. The resulting list should remain sorted in increasing order. The time complexity of this operation should be 0(N), where N is the size of the list. 2. removefirst() - deletes the first integer from the list and returns its value. The remaining list should remain sorted. Time complexity of this operation should be 0(1). 3. removelast() – deletes the last integer from the list and returns its value. The remaining list should remain sorted. Time complexity of this operation should be 0(1). 4. exists(x) – returns true if the…arrow_forwardWrite a function friend_besties() that calculates the "besties" (i.e. degree-one friends) of a given individual in a social network. The function takes two arguments: individual, an individual in the social network, in the form of a string ID. bestie_dict, a dictionary of sets of friends of each individual in the social network (as per the first question of the Project) The function should return a sorted list, made up of all "degree-one" friends for the individual. In the instance that the individual does not have any friends in the social network, the function should return an empty list. Example function calls are: >>> friend_besties('kim', {'kim': {'sandy', 'alex', 'glenn'}, 'sandy': {'kim', 'alex'}, 'alex': {'kim', 'sandy'}, 'glenn': {'kim'}})['alex', 'glenn', 'sandy']>>> friend_besties('ali', {'kim': {'sandy', 'alex', 'glenn'}, 'sandy': {'kim', 'alex'}, 'alex': {'kim', 'sandy'}, 'glenn': {'kim'}})[] Subject: Python Programmingarrow_forward
- in C++... kth Element Extend the class linkedListType by adding the following operations:a. Write a function that returns the info of the kth element of the linked list. If no such element exists, terminate the program.b. Write a function that deletes the kth element of the linked list. If no such element exists, terminate the program. Provide the definitions of these functions in the class linkedListType. PLEASE DON'T reject this question, this is the whole question that I have... so please do it however u can, Thank you!arrow_forwardImagine we have a linked list as shown below. The ListNodehas two fields: num, an integer, and next, a pointer to the next node. The list is not sorted. Write the definition of a function that calculates and returns the sum of the numbers in the list.arrow_forwardConsider a (literal) plate stack. If the stack becomes too tall, it may collapse.In practise, we would most likely create a new stack when the preceding stack reaches a certain threshold. Create a data structure SetOfStacks that is similar to this. SetOfStacks should be made up of many stacks and should build a new stack when the preceding one reaches its capacity.SetOfStacks. Push() and SetOfStacks are both functions. pop() should operate exactly like a single stack (that is, it should return the same values as if there were just one stack).COMPLETE THE FORMULACreate a popAt(int index) method that executes a pop operation on a given substack.arrow_forward
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning