Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    Lecture Slides 06 062-Nestedarrays

    Uploaded by

    yihuangece
    The document discusses arrays and nested arrays, focusing on their allocation, access in memory, and structure. It provides examples of nested arrays, their declaration, row access methods, and the corresponding IA32 code for accessing elements. Additionally, it highlights the importance of row-major ordering and addresses potential referencing issues in nested arrays.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lecture Slides 06 062-Nestedarrays

    Uploaded by

    yihuangece
    9 views12 pages
    The document discusses arrays and nested arrays, focusing on their allocation, access in memory, and structure. It provides examples of nested arrays, their declaration, row access methods, and the corresponding IA32 code for accessing elements. Additionally, it highlights the importance of row-major ordering and addresses potential referencing issues in nested arrays.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses arrays and nested arrays, focusing on their allocation, access in memory, and structure. It provides examples of nested arrays, their declaration, row access methods, and the corresponding IA32 code for accessing elements. Additionally, it highlights the importance of row-major ordering and addresses potential referencing issues in nested arrays.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    9 views12 pages

    Lecture Slides 06 062-Nestedarrays

    Uploaded by

    yihuangece
    The document discusses arrays and nested arrays, focusing on their allocation, access in memory, and structure. It provides examples of nested arrays, their declaration, row access methods, and the corresponding IA32 code for accessing elements. Additionally, it highlights the importance of row-major ordering and addresses potential referencing issues in nested arrays.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 12

    University of Washington

    Section 5: Arrays & Other Data Structures


     Array allocation and access in memory
     Multi-dimensional or nested arrays
     Multi-level arrays
     Other structures in memory
     Data structures and alignment

    Nested Arrays
    University of Washington

    Nested Array Example


    #define PCOUNT 4 Remember, T A[N] is an array
    zip_dig sea[PCOUNT] = with N elements of type T
    {{ 9, 8, 1, 9, 5 },
    { 9, 8, 1, 0, 5 },
    { 9, 8, 1, 0, 3 },
    { 9, 8, 1, 1, 5 }};

    Nested Arrays
    University of Washington

    Nested Array Example


    #define PCOUNT 4 Remember, T A[N] is an array
    zip_dig sea[PCOUNT] = with N elements of type T
    {{ 9, 8, 1, 9, 5 },
    { 9, 8, 1, 0, 5 },
    { 9, 8, 1, 0, 3 }, sea[3][2];
    { 9, 8, 1, 1, 5 }};

    9 8 1 9 5 9 8 1 0 5 9 8 1 0 3 9 8 1 1 5

    76 96 116 136 156

     “Row-major” ordering of all elements


     This is guaranteed

    Nested Arrays
    University of Washington

    Multidimensional (Nested) Arrays


     Declaration A[0][0] • • • A[0][C-1]
     T A[R][C];
    • •
     2D array of data type T
    • •
     R rows, C columns • •
     Type T element requires K bytes
    A[R-1][0] • • • A[R-1][C-1]
     Array size?

    Nested Arrays
    University of Washington

    Multidimensional (Nested) Arrays


     Declaration A[0][0] • • • A[0][C-1]
     T A[R][C];
    • •
     2D array of data type T
    • •
     R rows, C columns • •
     Type T element requires K bytes
    A[R-1][0] • • • A[R-1][C-1]
     Array size
     R * C * K bytes
     Arrangement
     Row-major ordering
    int A[R][C];
    A A A A A A
    [0] • • • [0] [1] • • • [1] • • • [R-1] • • • [R-1]
    [0] [C-1] [0] [C-1] [0] [C-1]

    4*R*C Bytes
    Nested Arrays
    University of Washington

    Nested Array Row Access


     Row vectors
     T A[R][C]: A[i] is array of C elements
     Each element of type T requires K bytes
     Starting address A + i * (C * K)

    int A[R][C];

    A[0] A[i] A[R-1]

    A A A A A A
    [0] ••• [0] • • • [i] ••• [i] • • • [R-1] ••• [R-1]
    [0] [C-1] [0] [C-1] [0] [C-1]

    A A+i*C*4 A+(R-1)*C*4

    Nested Arrays
    University of Washington

    Nested Array Row Access Code


    int *get_sea_zip(int index) #define PCOUNT 4
    { zip_dig sea[PCOUNT] =
    return sea[index]; {{ 9, 8, 1, 9, 5 },
    } { 9, 8, 1, 0, 5 },
    { 9, 8, 1, 0, 3 },
    { 9, 8, 1, 1, 5 }};

    Nested Arrays
    University of Washington

    Nested Array Row Access Code


    int *get_sea_zip(int index) #define PCOUNT 4
    { zip_dig sea[PCOUNT] =
    return sea[index]; {{ 9, 8, 1, 9, 5 },
    } { 9, 8, 1, 0, 5 },
    { 9, 8, 1, 0, 3 },
    { 9, 8, 1, 1, 5 }};

    # %eax = index
    leal (%eax,%eax,4),%eax # 5 * index
    leal sea(,%eax,4),%eax # sea + (20 * index)

     Row Vector
     sea[index] is array of 5 ints (a zip_dig data type)
     Starting address sea+20*index
     IA32 Code
     Computes and returns address
     Compute as sea+4*(index+4*index)=sea+20*index
    Nested Arrays
    University of Washington

    Nested Array Row Access

    int A[R][C];

    A[0] A[i] A[R-1]

    A A A A A
    [0] ••• [0] • • • ••• [i] ••• • • • [R-1] ••• [R-1]
    [0] [C-1] [j] [0] [C-1]

    A A + i*C*4 A + (R-1)*C*4

    Nested Arrays
    University of Washington

    Nested Array Row Access


     Array Elements
     A[i][j] is element of type T, which requires K bytes
     Address A + i * (C * K) + j * K = A + (i * C + j)* K

    int A[R][C];

    A[0] A[i] A[R-1]

    A A A A A
    [0] ••• [0] • • • ••• [i] ••• • • • [R-1] ••• [R-1]
    [0] [C-1] [j] [0] [C-1]

    A A + i*C*4 A + (R-1)*C*4

    A + i*C*4 + j*4
    Nested Arrays
    University of Washington

    Nested Array Element Access Code


    int get_sea_digit zip_dig sea[PCOUNT] =
    (int index, int dig) {{ 9, 8, 1, 9, 5 },
    { { 9, 8, 1, 0, 5 },
    return sea[index][dig]; { 9, 8, 1, 0, 3 },
    } { 9, 8, 1, 1, 5 }};
    # %ecx = dig
    # %eax = index
    leal 0(,%ecx,4),%edx # 4*dig
    leal (%eax,%eax,4),%eax # 5*index
    movl sea(%edx,%eax,4),%eax # *(sea + 4*dig + 20*index)

     Array Elements
     sea[index][dig] is int
     Address: sea + 20*index + 4*dig
     IA32 Code
     Computes address sea + 4*dig + 4*(index+4*index)
     movl performs memory reference
    Nested Arrays
    University of Washington

    Strange Referencing Examples

    zip_dig
    sea[4]; 9 8 1 9 5 9 8 1 0 5 9 8 1 0 3 9 8 1 1 5

    76 96 116 136 156

     Reference Address Value Guaranteed?


    sea[3][3] 76+20*3+4*3 = 148 1 Yes
    sea[2][5] 76+20*2+4*5 = 136 9 Yes
    sea[2][-1] 76+20*2+4*-1 = 112 5 Yes
    sea[4][-1] 76+20*4+4*-1 = 152 5 Yes
    sea[0][19] 76+20*0+4*19 = 152 5 Yes
    sea[0][-1] 76+20*0+4*-1 = 72 ?? No
     Code does not do any bounds checking
     Ordering of elements within array guaranteed

    Nested Arrays

    You might also like