Embedded Systems Design - August 2008 - (Page 40)

0808esd.p35to42 7/17/08 11:57 AM Page 40 20 years ago This function searches the free list for a block large enough to meet our needs. If the block is exactly the right size, we remove it from the linked list and allocate the entire block to the caller. If the block is larger than required, malloc() splits it by creating a new header inside the block and decrementing the Listing continued from page 38. /* Otherwise, current free-space head is lower in memory. Walk down free-space list looking for the block being returned. If the next pointer points past the block, make a new entry and link it. If next pointer plus its size points to the block, form one contiguous block. */ nxt = frhd; for (nxt=frhd; nxt && nxt ptr) { if (nxt+nxt->size == f) { nxt->size += f->size; /* They're contiguous. */ f = nxt + nxt->size; /* Form one block. */ if (f==nxt->ptr) { /* The new, larger block is contiguous to the next free block, so form a larger block.There's no need to continue this checking since if the block following this free one were free, the two would already have been combined. */ nxt->size += f->size; nxt->ptr = f->ptr; } return; } } /* The address of the block being returned is greater than one in the free queue (nxt) or the end of the queue was reached. If at end, just link to the end of the queue. Therefore, nxt is null or points to a block higher up in memory than the one being returned. */ prev->ptr = f; prev = f + f->size; if (prev == nxt) { f->size += nxt->size; f->ptr = nxt->ptr; } else f->ptr = nxt; return; } char * malloc(int nbytes) /* bytes to allocate */ { HEADER *nxt, *prev; int nunits; nunits = (nbytes+sizeof(HEADER)-1) / sizeof(HEADER) + 1; /* Change that divide to a shift (for speed) only if the compiler doesn't do it for you, you don't require portability, and you know that sizeof(HEADER) is a power of two. Allocate the space requested plus space for the header of the block. Search the freespace queue for a block that's large enough. If block is larger than needed, break into two pieces and allocate the portion higher up in memory. Otherwise, just allocate the entire block. */ Listing continues on page 42. /* link to queue */ /* right after space to free */ /* 'f' and 'nxt' are contiguous. */ /* Form a larger, contiguous block. */ original block header size by the amount requested. The pointer is incremented by the remaining size, resulting in a pointer to a new header. The requested size is then put into this new header and, as a result, the block splits in two. The upper section (higher in memory) is allocated to the caller, while the lower section re- mains in the free list (see Figure 2). The caller receives a pointer to the block just beyond the header. The application uses free() to return allocated blocks. Because the pointer returned by malloc() points one header unit beyond the actual header for the block, free() decrements it by one 40 AUGUST 2008 | embedded systems design | www.embedded.com http://www.embedded.com

Table of Contents Feed for the Digital Edition of Embedded Systems Design - August 2008

Embedded Systems Design - August 2008 Contents Number Include Parity Bit Programmer's Toolbox Cover Feature: Virtualization for Embedded X86 Multiprocessor Applications Wanted: Industry Standards for Benchmarking Embedded VMM Hypervisors Achieving Cache Coherence in a MIPS32 Multicore Design Memory Allocation in C Advertising Index Break Points Marketplace

Embedded Systems Design - August 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.