blachlylab / intervaltree Goto Github PK

Currently, AVL tree and Splay tree insert function signatures differ:

AVL:
Node *insert(Node *x, out uint cnt)

Splay:
Node * insert(IntervalType i)

In practice then calling code looks like:

                    foreach(link; c.links)
                    {
                        version(avl)    { uint cnt; (*tree).insert( new IntervalTreeNode!ChainLink(*link), cnt ); }
                        version(splay)  (*tree).insert(*link);

Proposal:
Both should take an IntervalType (current behavior of splay tree)

As a bonus, could also include overload that takes pointer

use static array stack

With the proposed transition to @safe by default, we should correctly annotate functions. The cgranges interface directly manipulates pointers, and the functions should be annotated @trusted

This strategy is a huge win for certain serial workloads and was introduced in commit a112efb

However, it currently uses a hardcoded probability threshold (ubyte). This should be templatized so a probability, p, can be passed at compile time (debtably, parameterize the function to allow runtime selection as well, but I don't like this as much)

Include bool in signature for cr_destroy and write C code to optionally free ->data if container is the only owner.

1. reduce use of updateMax (may not need to bubble up since we update on the way down on insert)

2. templatize zig, ziz-zig, and zig-zag by direction to factor out if/else (although these if/else may be branch predicted well already)

3. findOverlapsWith: static array stack. Will need to instrument this to see how deep an unbalanced tree we have after loading chain file.

4. findOverlapsWith: static array ret. (would also want to change IntervalAVLTree to match)

5. (Benchmark) When # overlapping intervals > 1, splay once or more

Presently, find(interval) returns Node*

Source of really hard to track down bugs.

Currently, all three tree implementations manage their own memory. Being containers, they copy in whatever object is passed to them. If this has, say, a string, with a pointer to the GC heap it may be reaped when its original reference goes out of scope, even though the tree holds on to it. Potential disaster. Of course this can be avoided by passing only value types.

Because I first discovered this when dealing with IITree (indeed at that time I think the splaytree and avltree were using the GC to alloc anyway so it wasn't manifest there) I did implement in the IITree insert options
(a) specify whether the passed in pointer (IITree takes a pointer instead of an object) was a GC managed pointer (GCptr=true), and
(b) indicate whether it may contain other pointers to the GC heap (trackGC=true)

See discussion here:

Need to add trackGC option to the other tree implementations. Since they don't take pointer, probably skip adding GCptr.

Also TODO: document the difference in the APIs, and document that non-value-types shouldn't be added to splaytree and avltree for now.