source: tests/avltree/avl.h @ fcd0b9d7

Last change on this file since fcd0b9d7 was fcd0b9d7, checked in by Michael Brooks <mlbrooks@…>, 12 months ago

PolyCost? calculation result becomes 0 or 1 per type, avoiding double-couting. Fixes #235?

PolyCost? calculation is documented as "Count of parameters and return values bound to some poly type." Before this fix, the cost calculation, looking inside one parameter or return, counted each occurrence of a poly type that it found there. This caused an incorrect increase in PolyCost? on cases like #235 where several type variables are used in the declaration of one parameter.

libcfa/src/concurrency/ Changing a decl-use pattern to keep resolution consistent (no behaviour is changed). The management of defaultResumptionHandler in the thread constructor was benefitting from bug #235 to disambiguate assignment to local variable vs assignment to declared function (due to #234). After this change, the code works around that false ambiguity by using a different name for the local variable.

tests/avl*: Adding a missing assertion on the custom destructor definition. Previously, the destructor definition was benefiting from bug #235 to avoid the missing-assertion-on-custom-dtor problem described in #227.

  • Property mode set to 100644
File size: 2.9 KB
1#pragma once
3extern "C" {
4#define NULL 0
5#define assert(cond) if (! (cond)) { printf("Assertion failed: (%s) at %s:%d\n", #cond, __FILE__, __LINE__); abort(); }
8// #include <types.h>
9// #include <lib.h>
11trait Comparable(otype T) {
12  int ?<?(T, T);
15forall(otype T | Comparable(T))
16int ?==?(T t1, T t2);
18forall(otype T | Comparable(T))
19int ?>?(T t1, T t2);
21// xxx - unbound type variable problems when trying to use new instead of create
22// forall( otype T, ttype Params | { void ?{}(T *, Params); } ) T * new( Params p );
24// To-do: properly use height or balance factor
25// Right now I'm recomputing the height for each
26// node multiple times. It's Theta-log(n), but still..
28// Balanced Binary Search Tree of void pointers; almost an AVL tree -
29//   just needs to make use of the balance factor properly
30// Operations:
31// ?{}, ^?{}
32// create   - allocate a new tree. Just a wrapper around malloc which also calls the tree constructor.
33// find     - search through the tree for the given key; return the associated value
34// empty    - return true if the tree is empty
35// insert   - insert node with key and value pair. Returns 0 on success
36// remove   - remove node with the given key, returns 0 on success, 1 on failure
37// copy     - deep copy of a tree
38// for_each - applies the given function to every data element in the tree
39//    assumes that a non-zero return value is an error, will return
40//    the error code from func
42// temporary: need forward decl to get around typedef problem
43forall(otype K | Comparable(K), otype V)
44struct tree;
46forall(otype K | Comparable(K), otype V)
47struct tree {
48  K key;
49  V value;
50  tree(K, V) * parent;
51  tree(K, V) * left;
52  tree(K, V) * right;
53  int balance;
56forall(otype K | Comparable(K), otype V)
57void ?{}(tree(K, V) &t, K key, V value);
59forall(otype K | Comparable(K), otype V)
60void ^?{}(tree(K, V) & t);
62forall(otype K | Comparable(K), otype V)
63tree(K, V) * create(K key, V value);
65forall(otype K | Comparable(K), otype V)
66V * find(tree(K, V) * t, K key);
68forall(otype K | Comparable(K), otype V)
69int empty(tree(K, V) * t);
71// returns the root of the tree
72forall(otype K | Comparable(K), otype V)
73int insert(tree(K, V) ** t, K key, V value);
75forall(otype K | Comparable(K), otype V)
76int remove(tree(K, V) ** t, K key);
78forall(otype K | Comparable(K), otype V)
79void copy(tree(K, V) * src, tree(K, V) ** ret);
81forall(otype K | Comparable(K), otype V)
82void for_each(tree(K, V) * t, void (*func)(V));
84// // Helper function to print trees
85// forall(otype K | Comparable(K), otype V)
86// void printTree(tree * t, int level){
87//   if (empty(t)){
88//     return;
89//   }
91//   printTree(t->left, level+1);
92//   printf("key: %d, value: %s, level: %d\n", t->key, t->value, level);
93//   printTree(t->right, level+1);
94// }
96// // inorder traversal of t
97// // prints each key, followed by the value
98// forall(otype K | Comparable(K), otype V)
99// void printTree(tree(K, V) * t){
100//     printTree(t, 0);
101// }
Note: See TracBrowser for help on using the repository browser.