The data structure, presented in Fig. 3 (a), is a doubly linked list of pointers to trees. Besides this, the leaves of the trees have pointers to doubly linked lists. The pointer variable points to the first element of the doubly linked list (header list). Each item in this list has three pointers: , , and . This selector points to the root of a binary tree in which each element has the and selectors. Finally, the leaves of the trees point to additional doubly linked lists. All the trees pointed to by the header list are independent and do not share any element. In the same way, the lists pointed to by the leaves of the same tree or different trees are also independent.
This data structure is built by a C code which traverses the elements of the header list with two pointers and eventually can permute two trees. Our compiler has analyzed this code obtaining an RSRSG for each sentence in the program. Figure 3 (b) shows a compact2 representation of the RSRSG obtained for the last sentence of the code after the compiler analysis.
As we will see in the next sections, from the RSRSG represented in Fig. 3 (b) we can infer the actual properties of the real data structure: the trees and lists do not share elements and therefore they can be traversed in parallel. These results and other examples of real codes (sparse matrix-vector and matrix-matrix multiplication, sparse LU factorization and Barnes-Hut N-body simulation) with different data structures are presented in Sect. 5. But first, we describe our framework with a formal description of the RSGs in the next section.