【文章內容簡介】 outines for managing the heap int *a。 a = (int *) malloc(sizeof(int) * k)。 a[5] = 3。 free(a)。 ? Allocate and free arbitrarysized chunks of memory in any order Copyright 169。 2020 Stephen A. Edwards All rights reserved malloc() and free() ? More flexible than automatic variables (stacked) ? More costly in time and space ? malloc() and free() use plicated nonconstanttime algorithms ? Each block generally consumes two additional words of memory ? Pointer to next empty block ? Size of this block ? Common source of errors ? Using uninitialized memory ? Using freed memory ? Not allocating enough ? Neglecting to free disused blocks (memory leaks) Copyright 169。 2020 Stephen A. Edwards All rights reserved malloc() and free() ? Memory usage errors so pervasive, entire successful pany (Pure Software) founded to sell tool to track them down ? Purify tool inserts code that verifies each memory access ? Reports accesses of uninitialized memory, unallocated memory, etc. ? Publiclyavailable Electric Fence tool does something similar Copyright 169。 2020 Stephen A. Edwards All rights reserved Dynamic Storage Allocation ? What are malloc() and free() actually doing? ? Pool of memory segments: Free malloc( ) Copyright 169。 2020 Stephen A. Edwards All rights reserved Dynamic Storage Allocation ? Rules: ? Each segment contiguous in memory (no holes) ? Segments do not move once allocated ? malloc() ? Find memory area large enough for segment ? Mark that memory is allocated ? free() ? Mark the segment as unallocated Copyright 169。 2020 Stephen A. Edwards All rights reserved Dynamic Storage Allocation ? Three issues: ? How to maintain information about free memory ? The algorithm for locating a suitable block ? The algorithm for freeing an allocated block Copyright 169。 2020 Stephen A. Edwards All rights reserved Simple Dynamic Storage Allocation ? Three issues: ? How to maintain information about free memory ? Linked list ? The algorithm for locating a suitable block ? Firstfit ? The algorithm for freeing an allocated block ? Coalesce adjacent free blocks Copyright 169。 2020 Stephen A. Edwards All rights reserved Simple Dynamic Storage Allocation Next Size Next Size Size Free block Allocated block malloc( ) First largeenough free block selected Free block divided into two Previous next pointer updated Newlyallocated region begins with a size value Copyright 169。 2020 Stephen A. Edwards All rights reserved Simple Dynamic Storage Allocation free(a) Appropriate position in free list identified Newlyfreed region added to adjacent free regions Copyright 169。 2020 Stephen A. Edwards All rights reserved Dynamic Storage Allocation ? Many, many variants ? Other “fit” algorithms ? Segregation of objects by sizes ? 8byte objects in one region, 16 in another, etc. ? More intelligent list structures Copyright 169。 2020 Stephen A. Edwards All rights reserved Memory Pools ? An alternative: Memory pools ? Separate management policy for each pool ? Stackbased pool: can only free whole pool at once ? Very cheap operation ? Good for buildonce data structures (., pilers) ? Pool for objects of a single size ? Useful in objectoriented programs ? Not part of the C standard library Copyright 169。 2020 Stephen A. Edwards All rights reserved Arrays ? Array: sequence of identical objects in memory ? int a[10]。 means space for ten integers Filippo Brunelleschi, Ospdale degli Innocenti, Firenze, Italy, 1421 ? By itself, a is the address of the first integer ? *a and a[0] mean the same thing ? The address of a is not stored in memory: the piler inserts code to pute it when it appears ? Ritchie calls this interpretation the biggest conceptual jump from BCPL to C Copyright 169。 2020 Stephen A. Edwards All rights reserved Multidimensional Arrays ? Array declarations read righttoleft ? int a[10][3][2]。 ? “an array of ten arrays of three arrays of two ints” ? In memory 2 2 2 3 2 2 2 3 2 2 2 3 ... 10 Seagram Building, Ludwig Mies van der Rohe,1957 Copyright 169。 2020 Stephen A. Edwards All rights reserved Multidimensional Arrays ? Passing a multidimensional array as an argument requires all but the first dimension int a[10][3][2]。 void examine( a[][3][2] ) { … } ? Address for an access such as a[i][j][k] is a + k + 2*(j + 3*i) Copyright 169。 2020 Stephen A. Edwards All rights reserved Multidimensional Arrays ? Use arrays of pointers for variablesized multidimensional arrays ? You need to allocate space for and initialize the arrays of pointers int ***a。 ? a[3][5][4] expands to *(*(*(a+3)+5)+4) The value int *