Changeset cb811ac for src/tests


Ignore:
Timestamp:
Aug 23, 2017, 9:02:41 PM (7 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
7ece922
Parents:
d3e4d6c
Message:

change stdlib swap to use references, and update swap tests

Location:
src/tests
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • src/tests/avltree/avl3.c

    rd3e4d6c rcb811ac  
    33#include <stdlib>
    44
    5 // from stdlib
    6 forall(otype T)
    7 void swap(T *, T *);
    8 
    95// swaps the data within two tree nodes
    106forall(otype K | Comparable(K), otype V)
    117void node_swap(tree(K, V) * t, tree(K, V) * t2){
    12   swap(&t->key, &t2->key);
    13   swap(&t->value, &t2->value);
     8        swap( t->key,  t2->key);
     9        swap( t->value, t2->value);
    1410}
    1511
    … …  
    1713forall(otype K | Comparable(K), otype V)
    1814tree(K, V) * find_successor(tree(K, V) * t){
    19   tree(K, V) * find_successor_helper(tree(K, V) * t){
    20     // go left as deep as possible, return the last node
    21     if (empty(t->left)){
    22       return t;
    23     } else {
    24       return find_successor_helper(t->left);
    25     }
    26   }
    27   return find_successor_helper(t->right);
     15        tree(K, V) * find_successor_helper(tree(K, V) * t){
     16                // go left as deep as possible, return the last node
     17                if (empty(t->left)){
     18                        return t;
     19                } else {
     20                        return find_successor_helper(t->left);
     21                }
     22        }
     23        return find_successor_helper(t->right);
    2824}
    2925
    … …  
    3127forall(otype K | Comparable(K), otype V)
    3228void deleteSingleNode(tree(K, V) * t) {
    33   t->left = NULL;
    34   t->right = NULL;
    35   delete(t);
     29        t->left = NULL;
     30        t->right = NULL;
     31        delete(t);
    3632}
    3733
    … …  
    3935forall(otype K | Comparable(K), otype V)
    4036tree(K, V) * remove_node(tree(K, V) * t){
    41   // is the node a leaf?
    42   if (empty(t->left) && empty(t->right)){
    43     // yes, just delete this node
    44     delete(t);
    45     return NULL;
    46   } else if (empty(t->left)){
    47     // if the left is empty, there is only one child -> move right up
    48     node_swap(t, t->right);
    49     tree(K, V) * tmp = t->right;
     37        // is the node a leaf?
     38        if (empty(t->left) && empty(t->right)){
     39                // yes, just delete this node
     40                delete(t);
     41                return NULL;
     42        } else if (empty(t->left)){
     43                // if the left is empty, there is only one child -> move right up
     44                node_swap(t, t->right);
     45                tree(K, V) * tmp = t->right;
    5046
    51     // relink tree
    52     t->left = tmp->left;
    53     t->right = tmp->right;
     47                // relink tree
     48                t->left = tmp->left;
     49                t->right = tmp->right;
    5450
    55     setParent(t->left, t);
    56     setParent(t->right, t);
    57     deleteSingleNode(tmp);
    58     return t;
    59   } else if (empty(t->right)){
    60     // if the right is empty, there is only one child -> move left up
    61     node_swap(t, t->left);
    62     tree(K, V) * tmp = t->left;
     51                setParent(t->left, t);
     52                setParent(t->right, t);
     53                deleteSingleNode(tmp);
     54                return t;
     55        } else if (empty(t->right)){
     56                // if the right is empty, there is only one child -> move left up
     57                node_swap(t, t->left);
     58                tree(K, V) * tmp = t->left;
    6359
    64     // relink tree
    65     t->left = tmp->left;
    66     t->right = tmp->right;
     60                // relink tree
     61                t->left = tmp->left;
     62                t->right = tmp->right;
    6763
    68     setParent(t->left, t);
    69     setParent(t->right, t);
    70     deleteSingleNode(tmp);
    71     return t;
    72   } else {
    73     // swap with the successor
    74     tree(K, V) * s = find_successor(t);
    75     tree(K, V) * parent = s->parent;
     64                setParent(t->left, t);
     65                setParent(t->right, t);
     66                deleteSingleNode(tmp);
     67                return t;
     68        } else {
     69                // swap with the successor
     70                tree(K, V) * s = find_successor(t);
     71                tree(K, V) * parent = s->parent;
    7672
    77     if (parent->left == s){
    78       parent->left = s->right;
    79     } else {
    80       assert(parent->right == s);
    81       parent->right = s->right;
    82     }
    83     setParent(s->right, parent);
    84     node_swap(t, s);
    85     deleteSingleNode(s);
    86     return t;
    87   }
     73                if (parent->left == s){
     74                        parent->left = s->right;
     75                } else {
     76                        assert(parent->right == s);
     77                        parent->right = s->right;
     78                }
     79                setParent(s->right, parent);
     80                node_swap(t, s);
     81                deleteSingleNode(s);
     82                return t;
     83        }
    8884}
    8985
    … …  
    9187forall(otype K | Comparable(K), otype V)
    9288tree(K, V) * remove_helper(tree(K, V) * t, K key, int * worked){
    93   if (empty(t)){
    94     // did not work because key was not found
    95     // set the status variable and return
    96     *worked = 1;
    97   } else if (t->key == key) {
    98     t = remove_node(t);
    99   } else if (t->key < key){
    100     t->right = remove_helper(t->right, key, worked);
    101   } else {
    102     // t->key > key
    103     t->left = remove_helper(t->left, key, worked);
    104   }
    105   // try to fix after deleting
    106   if (! empty(t)) {
    107     t = tryFix(t);
    108   }
    109   return t;
     89        if (empty(t)){
     90                // did not work because key was not found
     91                // set the status variable and return
     92                *worked = 1;
     93        } else if (t->key == key) {
     94                t = remove_node(t);
     95        } else if (t->key < key){
     96                t->right = remove_helper(t->right, key, worked);
     97        } else {
     98                // t->key > key
     99                t->left = remove_helper(t->left, key, worked);
     100        }
     101        // try to fix after deleting
     102        if (! empty(t)) {
     103                t = tryFix(t);
     104        }
     105        return t;
    110106}
    111107
    112108forall(otype K | Comparable(K), otype V)
    113109int remove(tree(K, V) ** t, K key){
    114   int worked = 0;
    115   tree(K, V) * newTree = remove_helper(*t, key, &worked);
    116   *t = newTree;
    117   return worked;
     110        int worked = 0;
     111        tree(K, V) * newTree = remove_helper(*t, key, &worked);
     112        *t = newTree;
     113        return worked;
    118114}
     115
     116// Local Variables: //
     117// tab-width: 4 //
     118// End: //

  • src/tests/swap.c

    rd3e4d6c rcb811ac  
    77// swap.c --
    88//
    9 // Author           : Richard C. Bilson
     9// Author           : Peter A. Buhr
    1010// Created On       : Wed May 27 17:56:53 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Apr 21 08:10:41 2016
    13 // Update Count     : 69
     12// Last Modified On : Wed Aug 23 20:34:45 2017
     13// Update Count     : 70
    1414//
    1515
    … …  
    2020        char c1 = 'a', c2 = 'b';
    2121        sout | "char\t\t\t" | c1 | ' ' | c2 | "\t\t\tswap ";
    22         swap( &c1, &c2 );
     22        swap( c1, c2 );
    2323        sout | '\t' | c1 | ' ' | c2 | endl;
    2424
    2525        signed int i1 = -1, i2 = -2;
    2626        sout | "signed int\t\t" | i1 | i2 | "\t\t\tswap ";
    27         swap( &i1, &i2 );
     27        swap( i1, i2 );
    2828        sout | '\t' | i1 | i2 | endl;
    2929
    3030        unsigned int ui1 = 1, ui2 = 2;
    3131        sout | "unsigned int\t\t" | ui1 | ui2 | "\t\t\tswap ";
    32         swap( &ui1, &ui2 );
     32        swap( ui1, ui2 );
    3333        sout | '\t' | ui1 | ui2 | endl;
    3434
    3535        signed long int li1 = -1, li2 = -2;
    3636        sout | "signed long int\t\t" | li1 | li2 | "\t\t\tswap ";
    37         swap( &li1, &li2 );
     37        swap( li1, li2 );
    3838        sout | '\t' | li1 | li2 | endl;
    3939
    4040        unsigned long int uli1 = 1, uli2 = 2;
    4141        sout | "unsigned long int\t" | uli1 | uli2 | "\t\t\tswap ";
    42         swap( &uli1, &uli2 );
     42        swap( uli1, uli2 );
    4343        sout | '\t' | uli1 | uli2 | endl;
    4444
    4545        signed long long int lli1 = -1, lli2 = -2;
    4646        sout | "signed long long int\t" | lli1 | lli2 | "\t\t\tswap ";
    47         swap( &lli1, &lli2 );
     47        swap( lli1, lli2 );
    4848        sout | '\t' | lli1 | lli2 | endl;
    4949
    5050        unsigned long long int ulli1 = 1, ulli2 = 2;
    5151        sout | "unsigned long long int\t" | ulli1 | ulli2 | "\t\t\tswap ";
    52         swap( &ulli1, &ulli2 );
     52        swap( ulli1, ulli2 );
    5353        sout | '\t' | ulli1 | ulli2 | endl;
    5454
    5555        float f1 = 1.5, f2 = 2.5;
    5656        sout | "float\t\t\t" | f1 | f2 | "\t\t\tswap ";
    57         swap( &f1, &f2 );
     57        swap( f1, f2 );
    5858        sout | '\t' | f1 | f2 | endl;
    5959
    6060        double d1 = 1.5, d2 = 2.5;
    6161        sout | "double\t\t\t" | d1 | d2 | "\t\t\tswap ";
    62         swap( &d1, &d2 );
     62        swap( d1, d2 );
    6363        sout | '\t' | d1 | d2 | endl;
    6464
    6565        long double ld1 = 1.5, ld2 = 2.5;
    6666        sout | "long double\t\t" | ld1 | ld2 | "\t\t\tswap ";
    67         swap( &ld1, &ld2 );
     67        swap( ld1, ld2 );
    6868        sout | '\t' | ld1 | ld2 | endl;
    6969
    7070        float _Complex fc1 = 1.5f+1.5if, fc2 = 2.5f+2.5if;
    7171        sout | "float _Complex\t\t" | fc1 | fc2 | "\tswap ";
    72         swap( &fc1, &fc2 );
     72        swap( fc1, fc2 );
    7373        sout | '\t' | fc1 | fc2 | endl;
    7474
    7575        double _Complex dc1 = 1.5d+1.5id, dc2 = 2.5d+2.5id;
    7676        sout | "double _Complex\t\t" | dc1 | dc2 | "\tswap ";
    77         swap( &dc1, &dc2 );
     77        swap( dc1, dc2 );
    7878        sout | '\t' | dc1 | dc2 | endl;
    7979
    8080        long double _Complex ldc1 = 1.5d+1.5il, ldc2 = 2.5d+2.5il;
    8181        sout | "long double _Complex\t" | ldc1 | ldc2 | "\tswap ";
    82         swap( &ldc1, &ldc2 );
     82        swap( ldc1, ldc2 );
    8383        sout | '\t' | ldc1 | ldc2 | endl;
    8484
    … …  
    8686        ofstream * ?|?( ofstream * os, S s ) { return os | s.i | s.j; }
    8787        sout | "struct S\t\t" | s1 | "," | s2 | "\t\tswap ";
    88         swap( &s1, &s2 );
     88        swap( s1, s2 );
    8989        sout | '\t' | s1 | "," | s2 | endl;
    9090} // main
Note: See TracChangeset for help on using the changeset viewer.