Changes in / [a1f7064:f1bcd004]


Ignore:
Location:
src
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • src/libcfa/stdlib

    ra1f7064 rf1bcd004  
    1010// Created On       : Thu Jan 28 17:12:35 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Aug 23 20:29:47 2017
    13 // Update Count     : 224
     12// Last Modified On : Mon Aug  7 11:19:07 2017
     13// Update Count     : 223
    1414//
    1515
    … …  
    230230
    231231forall( otype T )
    232 void swap( T & t1, T & t2 );
     232void swap( T * t1, T * t2 );
    233233
    234234// Local Variables: //

  • src/libcfa/stdlib.c

    ra1f7064 rf1bcd004  
    1010// Created On       : Thu Jan 28 17:10:29 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Aug 23 20:30:44 2017
    13 // Update Count     : 292
     12// Last Modified On : Tue Aug  8 17:31:13 2017
     13// Update Count     : 291
    1414//
    1515
    … …  
    305305
    306306forall( otype T )
    307 void swap( T & t1, T & t2 ) {
    308         T temp = t1;
    309         t1 = t2;
    310         t2 = temp;
     307void swap( T * t1, T * t2 ) {
     308        T temp = *t1;
     309        *t1 = *t2;
     310        *t2 = temp;
    311311} // swap
    312312

  • src/tests/avltree/avl3.c

    ra1f7064 rf1bcd004  
    33#include <stdlib>
    44
     5// from stdlib
     6forall(otype T)
     7void swap(T *, T *);
     8
    59// swaps the data within two tree nodes
    610forall(otype K | Comparable(K), otype V)
    711void node_swap(tree(K, V) * t, tree(K, V) * t2){
    8         swap( t->key,  t2->key);
    9         swap( t->value, t2->value);
     12  swap(&t->key, &t2->key);
     13  swap(&t->value, &t2->value);
    1014}
    1115
    … …  
    1317forall(otype K | Comparable(K), otype V)
    1418tree(K, V) * find_successor(tree(K, V) * t){
    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);
     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);
    2428}
    2529
    … …  
    2731forall(otype K | Comparable(K), otype V)
    2832void deleteSingleNode(tree(K, V) * t) {
    29         t->left = NULL;
    30         t->right = NULL;
    31         delete(t);
     33  t->left = NULL;
     34  t->right = NULL;
     35  delete(t);
    3236}
    3337
    … …  
    3539forall(otype K | Comparable(K), otype V)
    3640tree(K, V) * remove_node(tree(K, V) * t){
    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;
     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;
    4650
    47                 // relink tree
    48                 t->left = tmp->left;
    49                 t->right = tmp->right;
     51    // relink tree
     52    t->left = tmp->left;
     53    t->right = tmp->right;
    5054
    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;
     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;
    5963
    60                 // relink tree
    61                 t->left = tmp->left;
    62                 t->right = tmp->right;
     64    // relink tree
     65    t->left = tmp->left;
     66    t->right = tmp->right;
    6367
    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;
     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;
    7276
    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         }
     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  }
    8488}
    8589
    … …  
    8791forall(otype K | Comparable(K), otype V)
    8892tree(K, V) * remove_helper(tree(K, V) * t, K key, int * worked){
    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;
     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;
    106110}
    107111
    108112forall(otype K | Comparable(K), otype V)
    109113int remove(tree(K, V) ** t, K key){
    110         int worked = 0;
    111         tree(K, V) * newTree = remove_helper(*t, key, &worked);
    112         *t = newTree;
    113         return worked;
     114  int worked = 0;
     115  tree(K, V) * newTree = remove_helper(*t, key, &worked);
     116  *t = newTree;
     117  return worked;
    114118}
    115 
    116 // Local Variables: //
    117 // tab-width: 4 //
    118 // End: //

  • src/tests/swap.c

    ra1f7064 rf1bcd004  
    77// swap.c --
    88//
    9 // Author           : Peter A. Buhr
     9// Author           : Richard C. Bilson
    1010// Created On       : Wed May 27 17:56:53 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Wed Aug 23 20:34:45 2017
    13 // Update Count     : 70
     12// Last Modified On : Thu Apr 21 08:10:41 2016
     13// Update Count     : 69
    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.