自学教程：C++ HDRP函数代码示例

static void place(void *bp, size_t size){    size_t totalsize = GET_SIZE(HDRP(bp));                                                   if((totalsize - size) >= OVERHEAD){                                                          PUT(HDRP(bp), PACK(size, 1));                                                            PUT(FTRP(bp), PACK(size, 1));                                                            mm_remove(bp);                                                                           bp = NEXT_BLKP(bp);                                                                       PUT(HDRP(bp), PACK(totalsize - size, 0));                                                 PUT(FTRP(bp), PACK(totalsize - size, 0));                                                 coalesce(bp);                                                                         }    else{                                                                                         PUT(HDRP(bp), PACK(totalsize, 1));                                                        PUT(FTRP(bp), PACK(totalsize, 1));                                                        mm_remove(bp);                                 }}

/*my helper functions*/static void *extend_heap(size_t words){    void *bp;    size_t size;    /* Allocate an even number of words to maintain alignment. */    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;    if ((bp = mem_sbrk(size)) == (void *)-1)    {	return (NULL);    }    /* Initialize free block header/footer and the epilogue header. */    PUT(HDRP(bp), PACK(size, 0));         /* Free block header */    PUT(NEXT(bp), 0);  /*next address is null*/    PUT(PREV(bp), 0);  /*prev address is null*/    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */    /* Coalesce if the previous block was free. */    return (coalesce(bp));}

static void place(void *bp, size_t asize){    size_t csize = GET_SIZE(HDRP(bp));    if((csize - asize) >= (3*DSIZE))    {        PUT(HDRP(bp), PACK(asize, 1));        PUT(FTRP(bp), PACK(asize , 1));        bp = NEXT_BLKP(bp);        PUT(HDRP(bp), PACK(csize-asize, 0));        PUT(FTRP(bp), PACK(csize-asize, 0));        add_to_group(bp);    }    else    {        PUT(HDRP(bp), PACK(csize, 1));        PUT(FTRP(bp), PACK(csize, 1));    }}

/* * find_fit - Find a fit for a block with asize bytes */static void *find_fit(size_t asize){    /* First-fit search */    void *bp;    /* Free list is empty */    if (free_list_header == NULL) {       return NULL;    }    /* Stop at prologue, while prologue is allocted */    for (bp = free_list_header;        GET_ALLOC(HDRP(bp)) == 0; bp = GET_SUCC_FREE_BLKP(bp)) {        if (asize <= GET_SIZE(HDRP(bp))) {            return bp;        }    }    return NULL; /* No fit */}

//将空闲位标志为分配位static void place(void *bp, size_t asize){	size_t csize=GET_SIZE(HDRP(bp));	//如果一个块儿不够	if((csize-asize) >= (2*DSIZE)){		PUT(HDRP(bp), PACK(asize, 1));		PUT(FTRP(bp), PACK(asize, 1));		bp=NEXT_BLKP(bp);		//占用下一个块儿一些空间		PUT( HDRP(bp), PACK(csize-asize, 0) );			PUT( FTRP(bp), PACK(csize-asize, 0) );		}else{		PUT(HDRP(bp), PACK(csize, 1));		PUT(FTRP(bp), PACK(csize, 1));	}}

/* * extend_heap - Extend heap with free block and return its block pointer */static void *extend_heap(size_t words) /* TODO */{    char *bp;    size_t size;    /* Allocate an even number of words to maintain alignment */    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;    if ((long)(bp = mem_sbrk(size)) == -1)      return NULL;    /* Initialize free block header/footer and the epilogue header */    PUT(HDRP(bp), PACK(size, 0));         /* Free block header */    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */    /* Coalesce if the previous block was free */    return coalesce(bp);}

/* Extends the heap by asking for more space, and reassigning pointersaccordingly. */static void *extend_heap(size_t words) {    char *bp;    size_t size;    size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;    if (size < MIN_BLOCK_SIZE) {        size = MIN_BLOCK_SIZE;    }    if ((long)(bp = mem_sbrk(size)) == -1)        return NULL;    /* Initialize free block header/footer and the epilogue header */    PUT(HDRP(bp), PACK(size, 0)); /* Free block header */    PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));    return coalesce(bp);}

/* Decides whether we can split the block, and if so performs the splitby computing leftover block space, deleting shortened allocated block, and then labeling split free block and coalescing. Otherwise, just resets size and allocation tags of block and deletesit from free list. */static void place(void *bp, size_t asize) {    size_t csize = GET_SIZE(HDRP(bp));    if ((csize - asize) >= MIN_BLOCK_SIZE) {        PUT(HDRP(bp), PACK(asize, 1));        PUT(FTRP(bp), PACK(asize, 1));        deleteBlk(bp);        bp = NEXT_BLKP(bp);        PUT(HDRP(bp), PACK(csize-asize, 0));        PUT(FTRP(bp), PACK(csize-asize, 0));        coalesce(bp);    }    /* Not enoough room to split, simple allocation and free list deletion */    else {        PUT(HDRP(bp), PACK(csize, 1));        PUT(FTRP(bp), PACK(csize, 1));        deleteBlk(bp);    }}

static void *extend_heap(size_t words){    char *ptr;    size_t size;    /* Allocate an even number of words to maintain alignment */    size = (words % 2) ? (words+1) * SWORD : words * SWORD;    if ((long)(ptr = mem_sbrk(size)) == -1)        return NULL;    /* Initialize free block header/footer and the epilogue header */    PUT(HDRP(ptr), PACK(size, 0));           /* Free block header */    PUT(FTRP(ptr), PACK(size, 0));           /* Free block footer */    PUT(HDRP(NEXT_BLKP(ptr)), PACK(0, 1));   /* New epilogue header */    /* Coalesce if the previous block was free */    printf("Before coalesce/n");    return coalesce(ptr);}

static void printblock(void *bp) {    size_t hsize, halloc, fsize, falloc;    checkheap(0);    hsize = GET_SIZE(HDRP(bp));    halloc = GET_ALLOC(HDRP(bp));      fsize = GET_SIZE(FTRP(bp));    falloc = GET_ALLOC(FTRP(bp));      if (hsize == 0) {        printf("%p: EOL/n", bp);        return;    }    /*  printf("%p: header: [%p:%c] footer: [%p:%c]/n", bp, 	hsize, (halloc ? 'a' : 'f'), 	fsize, (falloc ? 'a' : 'f')); */}

static void printblock(void *bp) {  size_t hsize, halloc, fsize, falloc;  hsize = GET_SIZE(HDRP(bp));  halloc = GET_ALLOC(HDRP(bp));    fsize = GET_SIZE(FTRP(bp));  falloc = GET_ALLOC(FTRP(bp));        if (hsize == 0) {    printf("%p: EOL/n", bp);    return;  }  printf("%p: header: [%d:%c] footer: [%d:%c]/n",	 bp, 	 (int) hsize, (halloc ? 'a' : 'f'), 	 (int) fsize, (falloc ? 'a' : 'f')); }

static void Exam_list(int asize){    void *bp;    int csize;    if(!asize){        printf("/n-------mem list----------/n");        for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){            printf("block %x:%x of realsize:%d %d /n",bp,bp+GET_SIZE(HDRP(bp)),GET_SIZE(HDRP(bp)),GET_ALLOC(HDRP(bp)));        }    }else{        printf("/n------mem size[%d]----------/n",asize);        for(bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)){            csize = GET_SIZE(HDRP(bp));            if(!GET_ALLOC(HDRP(bp))){                if(csize<asize)printf("%d /t",csize);                else printf("/033[42;30m%d/033[0m /t",csize);            }        }    }}

static void printblock(void *bp){    size_t hsize, halloc, fsize, falloc;    // checkheap(0);    hsize = GET_SIZE(HDRP(bp));    halloc = GET_ALLOC(HDRP(bp));    fsize = GET_SIZE(FTRP(bp));    falloc = GET_ALLOC(FTRP(bp));    if (hsize == 0) {        dbg_printf("%p: EOL/n", bp);        return;    }    dbg_printf("%p: header: [%u:%c] footer: [%u:%c]/n", bp,               (uint32_t)	hsize, (halloc ? 'a' : 'f'),               (uint32_t)fsize, (falloc ? 'a' : 'f'));}

/* * malloc */void *malloc (size_t size) {    size_t asize;      /* Adjusted block size */    size_t extendsize; /* Amount to extend heap if no fit */    char *bp;          if (heap_listp == 0){        mm_init();    }    /* Ignore spurious requests */    if (size == 0)        return NULL;    asize = ALIGN(size + 4); /* the overhead is payload + header(4 byte) + padding(optional) */    asize = MAX(asize, MINSIZE * WSIZE); /* require minimum size */    /* Search the free list for a fit */    if ((bp = find_fit(asize)) != NULL) {  #ifdef DEBUG            printf("malloc: before alloc./n");        mm_checkheap(1);#endif                    place(bp, asize);                  #ifdef DEBUG        printf("malloc: after alloc./n");                mm_checkheap(1);        printf("/n/n");#endif                return bp;    }    /* No fit found. Get more memory and place the block */    int tail_free = 0; // the free space we have in the tail of heap    if (heap_tailp && !GET_ALLOC(HDRP(heap_tailp))) {        tail_free = GET_SIZE(HDRP(heap_tailp));    }    extendsize = MAX(asize - tail_free,CHUNKSIZE);    bp = extend_heap(extendsize/WSIZE);    if (bp == NULL)         return NULL;    place(bp, asize);    return bp;}

/* * printBlock - prentar ut staka blokk */void printBlock(void *bp) {    if(GET_ALLOC(HDRP(bp)))        printf("%p | hdr: %p | ftr: %p | Size %d | Alloc: %d/n" ,               bp, HDRP(bp), FTRP(bp), GET_SIZE(HDRP(bp)), GET_ALLOC(HDRP(bp)));    else        printf("%p | hdrp %p | ftr: %p | prevfre: %p | nextfre: %p | Size: %d | Alloc: %d/n",               bp, HDRP(bp), FTRP(bp), NEXT_FREE_BLKP(bp), PREV_FREE_BLKP(bp),               GET_SIZE(HDRP(bp)), GET_ALLOC(HDRP(bp)));}

void merge(void *bp , size_t size, int state){//	void *prev_block = PREV_BLKP(bp);//	void *next_block = NEXT_BLKP(bp);//	dbg_printf("merge/n");	switch (state)		//X means current blcok	{	case 1:		//AXA		{//			dbg_printf("case : AXA/n");			PUT(HDRP(bp),PACK(size,0));			PUT(FTRP(bp),PACK(size,0));			merge_case(bp,1);			return;		}	case 2:		//AXF		{//			dbg_printf("case2 : AXF/n");			PUT(HDRP(bp),PACK(size,0));			PUT(FTRP(bp),PACK(size,0));			merge_case(bp,2);			return ;		}	case 3:		//FXA		{//			dbg_printf("case3 : FXA/n");			PUT(HDRP(bp),PACK(size,0));			PUT(FTRP(bp),PACK(size,0));			merge_case(bp,3);			return ;		}	case 4:		//FXF		{//			dbg_printf("case4 : FXF/n");			PUT(HDRP(bp),PACK(size,0));			PUT(FTRP(bp),PACK(size,0));			merge_case(bp,4);			return ;		}	}	}

//对空闲块进行合并static void *coalesce(void *bp){	size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));	size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));	size_t size = GET_SIZE(HDRP(bp));	//分四种情况对前后空闲块进行合并	if (prev_alloc && next_alloc)	{		;	}	else if (prev_alloc && !next_alloc)	{		//将要合并的的块从空闲队列中取出		fetchFromList(NEXT_BLKP(bp));		size += GET_SIZE(HDRP(NEXT_BLKP(bp)));		PUT(HDRP(bp), PACK(size, 0));		PUT(FTRP(bp), PACK(size, 0));	}	else if (!prev_alloc && next_alloc)	{		//将要合并的的块从空闲队列中取出		fetchFromList(PREV_BLKP(bp));		size += GET_SIZE(HDRP(PREV_BLKP(bp)));		PUT(FTRP(bp), PACK(size, 0));		PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));		bp = PREV_BLKP(bp);	}	else	{		//将要合并的的块从空闲队列中取出		fetchFromList(NEXT_BLKP(bp));		fetchFromList(PREV_BLKP(bp));		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));		bp = PREV_BLKP(bp);	}	//将新释放的块放在空闲队列头部	PUT(bp, &head);	PUT((char*)bp + (1 * WSIZE), head.next);	if (head.next != NULL)		PUT(head.next, bp);	head.next = bp;	return bp;}

/*  * Requires: *   words: the number of words to increase the heap by *   next: next pointer at the end of the linked list, to be set to the  	   header of the new block * Effects: *   Extend the heap with a free block and return that block's address. */static void *extend_heap(size_t words) {	size_t size;	void *bp;	/* Allocate an even number of words to maintain alignment. */	size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;	if ((bp = mem_sbrk(size)) == (void *)-1)  		return (NULL);	printf("Before extended block is added to the free list/n");	checkheap(1);	/* Initialize the new node pointers, next precedes previous */	/* The previous point points to the header of the previous block*/			/*PUT(bp, NULL);	PUT(bp + WSIZE, HDRP(next));*/	/* Initialize free block header/footer and the epilogue header. */	PUT(HDRP(bp), PACK(size, 0));         /* Free block header */	PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */	PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */		/* If list start is NULL, initialize the start to the pointer to the	 * added block	 */	if (list_start == NULL) {		list_start = (struct node *)bp;		list_start->next = list_start;		list_start->previous = list_start;	}	printf("For isolation/n");	add_to_front(bp);	printf("After extended block is added to the free list/n");	checkheap(1);	printf("Entering coalesce from extend_heap/n");	/* Coalesce if the previous block was free. */	return (coalesce(bp));}

/** * checkblock - check the current block for consistency * @param bp Block to be checked */static void checkblock(void *bp) {    /**     * Checks-     * 1) Check for alignment     * 2) Check for Header and Footer Match     * 3) Check for the block to be in heap     * 4) Check coalescing- no previous/next free blocks if current is free.     */        /*Check Block for alignment*/    if ((size_t)bp % 8) {       printf("ERROR: %p is not doubleword aligned/n", bp);    }    /*Check Block Header matching Footer*/    if (GET(HDRP(bp)) != GET(FTRP(bp))) {        printf("ERROR: header does not match footer/n");        dbg_printf("**Debug Info /n");        dbg_printf("Heap_listp = %p /n", heap_listp );        dbg_printf("Block %p /n", bp );    }     /* Check for if the block is in the heap */           if( !in_heap(bp)) {        printf("ERROR: %p is not in heap /n", bp);            }    /**     * Concept : As all the blocks are iteratively checked, just checking     *           next block for coalescing will suffice next/previous block     *           checks.     */        /* Check Coalescing with Next Block */    if( GET_ALLOC(HDRP(bp)) ==0 && NEXT_BLKP(bp)!=NULL         && GET_ALLOC(HDRP(NEXT_BLKP(bp))) ==0 ) {        printf("ERROR: %p is not coalesced with next block/n", bp);                print_all();        exit(1);    }}

/********************************************************** * extend_heap * Extend the heap by "words" words, maintaining alignment * requirements of course. Free the former epilogue block * and reallocate its new header **********************************************************/void *extend_heap(size_t words) {	intptr_t *bp;	size_t size;	/* Allocate an even number of words to maintain alignments */	size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;	if ((bp = mem_sbrk(size)) == (void *) -1)		return NULL;	/* Initialize free block header/footer and the epilogue header */	PUT(HDRP(bp), PACK(size, 0));                // free block header	PUT(FTRP(bp), PACK(size, 0));                // free block footer	PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));        // new epilogue header	/* Coalesce if the previous block was free */	// Trade-off between util and thru//    bp = coalesce(bp);	return bp;}

/* put header, footer and free_list pointers in a free block */void free_ptr(void *ptr, void *prev, void *next, unsigned size){    unsigned header = PACK(size, 0);    // header    PUT_INT(HDRP(ptr), header);    // footer    PUT_INT(FTRP(ptr), header);    // prev and next    PUT(PREV_PTR(ptr), prev);    PUT(NEXT_PTR(ptr), next);}

/* * Extend_Heap */static void *extend_heap(size_t words){	char *bp;	size_t size;	/* Allocate an even number of words to maintain alignement */	size = (words % 2) ? (words+1) * WSIZE : words * WSIZE;	if ((long)(bp = mem_sbrk(size)) == -1)		return NULL;	size_t previous = GET_PREV_ALLOC(HDRP(bp));	/* Initialize free block header/footer and the epilogue header */	PUT(HDRP(bp), PACK(size,previous, 0));	PUT(FTRP(bp), size);	epilogueaddr = HDRP(NEXT_BLKP(bp));	PUT(HDRP(NEXT_BLKP(bp)), PACK(0,2,1));	/* Coalesce if the previous block was free */	return coalesce(bp);}

/** * 将请求块放置在空闲块的起始位置，当剩余部分大于等于最小块的大小时进行分割操作 * * @param bp 指向free list中一个size大于asize字节的block */static void place(void *bp, size_t asize){    size_t bsize = GET_SIZE(HDRP(bp));    size_t diff_size = bsize - asize;    if (diff_size >= MIN_BLK) {        /* 请求块防止在空闲块的起始位置 */        PUT(HDRP(bp), PACK(asize, 1));        PUT(FTRP(bp), PACK(asize, 1)); /* 此处FTRP的GET_SIZE取到的是上面的asize */        /* 多余的部分进行分割 */        bp = NEXT_BLKP(bp);        PUT(HDRP(bp), PACK(diff_size, 0));        PUT(FTRP(bp), PACK(diff_size, 0));    } else {        PUT(HDRP(bp), PACK(bsize, 1));        PUT(FTRP(bp), PACK(bsize, 1));    }}

/* * Requires: *   "bp" is the address of a block. * * Effects: *   Print the block "bp". */static void printblock(void *bp){	bool halloc, falloc;	size_t hsize, fsize;	checkheap(false);	hsize = GET_SIZE(HDRP(bp));	halloc = GET_ALLOC(HDRP(bp));  	fsize = GET_SIZE(FTRP(bp));	falloc = GET_ALLOC(FTRP(bp));  	if (hsize == 0) {		printf("%p: end of heap/n", bp);		return;	}	printf("%p: header: [%zu:%c] footer: [%zu:%c]/n", bp, 	       hsize, (halloc ? 'a' : 'f'), 	       fsize, (falloc ? 'a' : 'f'));}

/*  * Requires: *   "bp" is the address of a free block that is at least "asize" bytes. * * Effects: *   Place a block of "asize" bytes at the start of the free block "bp" and *   split that block if the remainder would be at least the minimum block *   size.  */static void place(void *bp, size_t asize){	size_t csize = GET_SIZE(HDRP(bp));   	if ((csize - asize) >= (MINBLOCKSIZE)) { 		PUT(HDRP(bp), PACK(asize, 1));		PUT(FTRP(bp), PACK(asize, 1));		removeBlockFromList(bp);		bp = NEXT_BLKP(bp);		PUT(HDRP(bp), PACK(csize - asize, 0));		PUT(FTRP(bp), PACK(csize - asize, 0));		coalesce(bp);	} else {		PUT(HDRP(bp), PACK(csize, 1));		PUT(FTRP(bp), PACK(csize, 1));		removeBlockFromList(bp);	}}

/*  * Requires: *   "bp" is either the address of an allocated block or NULL. * * Effects: *   Free a block. */voidmm_free(void *bp){	size_t size;		/* Ignore spurious requests. */	if (bp == NULL)		return;	/* Free and coalesce the block. */	size = GET_SIZE(HDRP(bp));	/* Reset Header and Footer to be free */	PUT(HDRP(bp), PACK(size, 0));	PUT(FTRP(bp), PACK(size, 0));	coalesce(bp);	checkheap(1);}

/*split the block if the given free block has larger size than the required size*/void* splitBlock(void* bp, size_t asize) {    size_t totalsize = GET_SIZE(HDRP(bp));    size_t delta = totalsize - asize;    //if the remaining free block larger than min block size we can split    //we know that both bp size and required size are aligned with 8     //so delta is also aligned with 8    if (delta >= MIN_BLOCK_SIZE) {        //split        PUT(HDRP(bp), PACK(asize, 0));        PUT(FTRP(bp), PACK(asize, 0)); //footer        //insert the rest free block to free list        PUT(HDRP(NEXT_BLKP(bp)), PACK(delta, 0));        PUT(FTRP(NEXT_BLKP(bp)), PACK(delta, 0));        insertToFreeList(NEXT_BLKP(bp));        return bp;    }    return bp;}

/** Returns the next suitable free block from the free list using the 'first* fit' algorithm, else a NULL is returned*/static void *find_fit(size_t asize){    /* First fit search */    void *bp;    int current = find_list(asize);    /* Go through all the higher sized lists, if there are no available free     blocks */    while (current < NUMBER_OF_LISTS) {        bp = *(FRONT(current));        while (bp && GET_SIZE(HDRP(bp)) > 0) {            if (asize <= GET_SIZE(HDRP(bp)))                return bp;            bp = SUCC_BP(bp);        }        ++current;    }    /* BOOM! found nothing */    return NULL; }

//// Practice problem 9.8//// find_fit - Find a fit for a block with asize bytes//static void *find_fit(size_t asize){  FL_Pointer ptr;  for (ptr = free_list.next; ptr != &free_list; ptr = ptr->next){    if ( (asize <= GET_SIZE(HDRP(ptr)))) {      return ptr;    }  }  return NULL;}