diff options
Diffstat (limited to 'gcc/fortran/data.c')
| -rw-r--r-- | gcc/fortran/data.c | 143 |
1 files changed, 101 insertions, 42 deletions
diff --git a/gcc/fortran/data.c b/gcc/fortran/data.c index b17d6b8..5af3bd77 100644 --- a/gcc/fortran/data.c +++ b/gcc/fortran/data.c @@ -80,41 +80,48 @@ get_array_index (gfc_array_ref * ar, mpz_t * offset) /* Find if there is a constructor which offset is equal to OFFSET. */ static gfc_constructor * -find_con_by_offset (mpz_t offset, gfc_constructor *con) +find_con_by_offset (splay_tree spt, mpz_t offset) { mpz_t tmp; gfc_constructor *ret = NULL; + gfc_constructor *con; + splay_tree_node sptn; - mpz_init (tmp); +/* The complexity is due to needing quick access to the linked list of + constructors. Both a linked list and a splay tree are used, and both are + kept up to date if they are array elements (which is the only time that + a specific constructor has to be found). */ - for (; con; con = con->next) - { - int cmp = mpz_cmp (offset, con->n.offset); - - /* We retain a sorted list, so if we're too large, we're done. */ - if (cmp < 0) - break; + gcc_assert (spt != NULL); + mpz_init (tmp); - /* Yaye for exact matches. */ - if (cmp == 0) - { - ret = con; - break; - } + sptn = splay_tree_lookup (spt, (splay_tree_key) mpz_get_si(offset)); - /* If the constructor element is a range, match any element. */ - if (mpz_cmp_ui (con->repeat, 1) > 0) - { - mpz_add (tmp, con->n.offset, con->repeat); - if (mpz_cmp (offset, tmp) < 0) - { - ret = con; - break; - } - } + if (sptn) + ret = (gfc_constructor*) sptn->value; + else + { + /* Need to check and see if we match a range, so we will pull + the next lowest index and see if the range matches. */ + sptn = splay_tree_predecessor (spt, (splay_tree_key) mpz_get_si(offset)); + if (sptn) + { + con = (gfc_constructor*) sptn->value; + if (mpz_cmp_ui (con->repeat, 1) > 0) + { + mpz_init (tmp); + mpz_add (tmp, con->n.offset, con->repeat); + if (mpz_cmp (offset, tmp) < 0) + ret = con; + mpz_clear (tmp); + } + else + ret = NULL; /* The range did not match. */ + } + else + ret = NULL; /* No pred, so no match. */ } - mpz_clear (tmp); return ret; } @@ -230,9 +237,12 @@ gfc_assign_data_value (gfc_expr * lvalue, gfc_expr * rvalue, mpz_t index) gfc_expr *expr; gfc_constructor *con; gfc_constructor *last_con; + gfc_constructor *pred; gfc_symbol *symbol; gfc_typespec *last_ts; mpz_t offset; + splay_tree spt; + splay_tree_node sptn; symbol = lvalue->symtree->n.sym; init = symbol->value; @@ -279,16 +289,38 @@ gfc_assign_data_value (gfc_expr * lvalue, gfc_expr * rvalue, mpz_t index) else mpz_set (offset, index); - /* Find the same element in the existing constructor. */ - con = expr->value.constructor; - con = find_con_by_offset (offset, con); + /* Splay tree containing offset and gfc_constructor. */ + spt = expr->con_by_offset; + + if (spt == NULL) + { + spt = splay_tree_new (splay_tree_compare_ints,NULL,NULL); + expr->con_by_offset = spt; + con = NULL; + } + else + con = find_con_by_offset (spt, offset); if (con == NULL) { /* Create a new constructor. */ con = gfc_get_constructor (); mpz_set (con->n.offset, offset); - gfc_insert_constructor (expr, con); + sptn = splay_tree_insert (spt, (splay_tree_key) mpz_get_si(offset), + (splay_tree_value) con); + /* Fix up the linked list. */ + sptn = splay_tree_predecessor (spt, (splay_tree_key) mpz_get_si(offset)); + if (sptn == NULL) + { /* Insert at the head. */ + con->next = expr->value.constructor; + expr->value.constructor = con; + } + else + { /* Insert in the chain. */ + pred = (gfc_constructor*) sptn->value; + con->next = pred->next; + pred->next = con; + } } break; @@ -379,9 +411,12 @@ gfc_assign_data_value_range (gfc_expr * lvalue, gfc_expr * rvalue, gfc_ref *ref; gfc_expr *init, *expr; gfc_constructor *con, *last_con; + gfc_constructor *pred; gfc_symbol *symbol; gfc_typespec *last_ts; mpz_t offset; + splay_tree spt; + splay_tree_node sptn; symbol = lvalue->symtree->n.sym; init = symbol->value; @@ -435,19 +470,43 @@ gfc_assign_data_value_range (gfc_expr * lvalue, gfc_expr * rvalue, } /* Find the same element in the existing constructor. */ - con = expr->value.constructor; - con = find_con_by_offset (offset, con); - /* Create a new constructor. */ - if (con == NULL) - { - con = gfc_get_constructor (); - mpz_set (con->n.offset, offset); - if (ref->next == NULL) - mpz_set (con->repeat, repeat); - gfc_insert_constructor (expr, con); - } - else + /* Splay tree containing offset and gfc_constructor. */ + spt = expr->con_by_offset; + + if (spt == NULL) + { + spt = splay_tree_new (splay_tree_compare_ints,NULL,NULL); + expr->con_by_offset = spt; + con = NULL; + } + else + con = find_con_by_offset (spt, offset); + + if (con == NULL) + { + /* Create a new constructor. */ + con = gfc_get_constructor (); + mpz_set (con->n.offset, offset); + if (ref->next == NULL) + mpz_set (con->repeat, repeat); + sptn = splay_tree_insert (spt, (splay_tree_key) mpz_get_si(offset), + (splay_tree_value) con); + /* Fix up the linked list. */ + sptn = splay_tree_predecessor (spt, (splay_tree_key) mpz_get_si(offset)); + if (sptn == NULL) + { /* Insert at the head. */ + con->next = expr->value.constructor; + expr->value.constructor = con; + } + else + { /* Insert in the chain. */ + pred = (gfc_constructor*) sptn->value; + con->next = pred->next; + pred->next = con; + } + } + else gcc_assert (ref->next != NULL); break; |